Concept: Ring Oscillator TRNG
I was inspired by the Whirlygig RNG to create a hardware TRNG based on the ring oscillator.The ring oscillator is a small structure composed of an odd number of inverters arranged in a ring. The output is inherently unstable, switching between 1 and 0 at a rate dependant on the physical properties of the gates, including variations due local temperature. When the ring oscillator's output is sampled on the rising edges of a different clock, there is at least some physically-derived entropy in the resulting stream of bits.
By studying the characteristics of specific ring oscillators (specifically the jitter) it is possible to estimate the amount of entropy present in the bitstream from a single ring oscillator, and additionally the correlation between pairs of oscillators. Methodology and results can be found in various papers, such as FPGA Vendor Agnostic True Random Number Generator (pdf).
By combining a large number of samples from a large number of ring oscillators in an appropriate way (for instance using an XOR operation), it is possible to generate a bitstream that is indistinguishable from a random bitstream. Furthermore, armed with the previous estimates of entropy and correlation it is possible to estimate the entropy of the combined bitstream. By tweaking parameters such as the rate of the bitstream it is possible to make the entropy estimate as close to completely random as desired.
Infrastructure: hostmot2 on a mesa 5i20 PCI card
I already owned an appropriate FPGA board, the Mesa 5i20 PCI card. I use this card with emc2 to control a small CNC router. Furthermore, I took advantage of the existing hostmot2 code so that I could skip writing the code to interface the FPGA to the PC. This also served as a learning experience for writing new hostmot2 modules.Initially I used hal for firmware loading and the hostmot2 hal raw interface for reading the random number stream. This was limited to a relatively low rate of a few KB/s. I later wrote a userspace program to load the firmware and perform PCI accesses, achieving a rate of a few MB/s. This rate was satisfactory for me, greatly surpassing the rate of my Arduino Avalanche Noise TRNG.
Details of TRNG Structure
Each ring oscillator is composed of 3 1-input LUTs which perform a NOT function. A group is composed of 15 ring oscillators. At each rising edge of the local bus clock (nominally 50MHz), the oscillators' outputs are latched. Then the group's new output is changed to be the XOR of all the new ring oscillator latch outputs and the group's old output. 32 groups are used to make up the 32 bits in a RNG output word.I had thought that the way I declared the ring oscillator would cause it to be packed into a single slice, but inspecting the layout shows that the oscillators actually end up spread haphazardly across different slices. Thus, I have no estimate of the center frequency of a LUT and the idea that each LUT is subject primarily to local temperature variations is also somewhat suspect.
Due to the property of XOR the amount of entropy in each bit of the RNG output word will tend towards 1.0 over many cycles of the local bus clock. When reading at a rate of 8MB/s there are an average of 25 local bus cycles and thus the XOR of 15*25=375 ring oscillator samples present in one bit of output data. This gives a fill rate of >0.90 for a jitter of 2% or a fill rate of >0.80 for a jitter of 1% (table 1 in the pdf). Reading at a 4MB/s rate there are 15*50=750 ring oscillator samples present in each bit of output data, giving a fill rate of >0.95 even for a jitter of 1%. Of course, these calculations ignore correlation among ring oscillators.
Results: Passes 'dieharder'
Rather than perform the actual work of characterizing my ring oscillators' jitter or entropy, I made the (dubious!) decision of just running its output through the dieharder RNG test suite. It passes, but that's lousy proof of the presence of true random numbers--after all, PRNGs with seeds of only a few dozen bits pass dieharder just fine.Website Copyright © 2004-2024 Jeff Epler