Way of the exploding head

Whirlygig GPL Hardware RNG

Whirlygig is a USB 1.1 device that contains a fast, high quality hardware random number generator. Via a Linux driver, each whirlygig you connect makes available an additional 7Mbits of high quality randomness a second, or 750-850KBytes/sec sustained using the standard /dev/hw_random API.

Current status

Been using my whirlygig for over a year. A German guy has a production build underway that should be available for sale at a reasonable price in September 2010.

What is the hardware RNG good for?

It gives you a high-bandwidth source of non-repeatable, non-guessable, evenly spread random bits.

The RNG is believed to output numbers very suitable for hard crypto (although note as it is made available under GPL2 I don’t warrant that this or anything else is the case). Unlike many PRNGs, it should not be possible to reverse the RNG state in any usable way from observing the output. Because of the high bandwidth, it is suitable for generating very random numbers for statistical simulation purposes, which should not show any spectral aliasing with your data.

The Linux rng-tools package includes test code and a daemon which transfers entropy from /dev/hw_random into /dev/random, effectively giving you a bottomless pit of standard randomness without having to modify any code using it.

If you need a very high level of assurance that your randomness does not have some known backdoor characteristic, you can use this design with an amended CPLD VHDL to change the number of oscillators and the mixer stage, and run your own statistical tests until you are satisfied. The VHDL sources are provided as are links to the test suites further down the page.

In any event the whole design is Open, all sources, the schematic and PCB layout.

Hardware specification

Whirlygig uses a CPLD with a total of 8 sets of 3, totalling 24, unlocked ring oscillators with inverter chains of length 9. These are mixed into an 8-bit output sampled by a USB-capable microcontroller and fed back to the PC over USB.

Because the oscillators are unlocked to any reference, they wander randomly around their centre frequency. As they go faster the local silicon heats up and becomes less efficient, so they slow down. As they go slower, the local silicon cools and becomes more efficient, so they go faster. In addition, propagation delay at the individual inverters in each chain is affected by the amount of local current being drawn inside the chip due to other local signals transitioning at the same time. The end result is although there is a relatively stable centre frequency for each oscillator, at any moment it is pretty much impossible to model the phase and the actual frequency of each ring oscillator without physical access to the device (and even then the oscillators do not come out on pins of the CPLD).

At the “mixer” block three of the 24 oscillators are combined with XOR for each bit, with a different set of oscillators used for each bit. The mapping of the oscillator sets to the actual output bit is rotated according to a 24MHz clock, so there is on average an equal usage of the oscillator sets on each actual result bit.

The model for an attacker trying to reverse or guess the random stream look like this:

• propogation delay for each of the 216 inverters depends on micro-local silicon temperature and current flow nearby and drifts significantly on a ns scale
• because of this the phase and the frequency of each ring oscillator is changing all the time
• eight sets of six oscillators (a different 6 for each set) are formed by combining with XOR hiding the individual oscillator states
• different phases of oscillators are used in different sets
• which oscillator set maps to which output bit changes all the time
• when the oscillator is sampled is an unknown that grossly varies according to the host PC load, USB stack state and delays in the microcontroller
• Random bits are cached in the driver and pulled from the hardware as they are used, whether any given bits are “old” or “new” is unknown to the usermode code

Build your own whirlygig

A small (27.5mm x 40mm) PCB is provided to allow anyone to make the device.

PDF of PCB and Schematic

• Git repo for full CPLD VHDL design — you will need the Xilinx ISE Webpack if you want to recompile the logic. Otherwise you can use the .jed or .svf file from git to program the CPLD.
• Git repo for full hardware design — you will need Protel CAD system to change these sources. Otherwise use the Gerbers/Drill in the project outputs dir from git, or if you will use PCB Pool or other low cost manufacturers to make boards, use the whirlygig2.gwk file only which is all they need.

You can retrieve a directory full of the git stuff like this

git clone git://git.warmcat.com/whirlygig-hardware

The USB firmware uses a VID/PID combination that is reserved for this specific use.

Components

You can find Farnell here and RS here. Total BOM for one device is around GBP50, but half of that is the CPLD which is only available in the expensive industrial temp range at RS. (You can see that via the Xilinx online store here they are actually only $16 (GBP8) in commerical temp in the US.

The PCBs are so small that 9 of them fit into the 1dm2 minimum of most of the cheap board fabrication places, which was 57EUR (~GBP42) including shipping or ~GBP5/PCB in my case.

Software and firmware sources

• Git repo for full Linux driver module sources: A driver module currently against 2.6.23 is provided. It recognizes inserted Whirlygig USB devices and makes the randomness available at /dev/hw_random using the Linux HW random API. You can insert multiple devices to increase the random bandwidth available. No configuration is needed.
• Git repo for full firmware sources: The whirlygig device needs some firmware compiled with sdcc. The .ihx file provided is the binary that is precompiled and ready to program into the C8051F320 device.

Software validation

800MB of randomness was fetched from the device using dd, and run against Robert G Brown’s dieharder suite, a tougher enhancement to the original diehard suite. Test 2 of 18 is marked up by dieharder as not for use with validating RNGs and was ignored. Tests 3 and 18 were run with -t 30000 and -t 400000 respectively to keep them within the 800MB test file. All 17 relevant tests gave a PASS result. Two additional statistical tests -s1 and -s2, and -r2 and -r3 were performed to PASS too. You can see the histograms and results here.

rng-tools was used to test the RNG against FIPS-140-2 over 750K FIPS packets (15 billion random bits).

rngtest: bits received from input: 14976660032
rngtest: FIPS 140-2 successes: 748233
rngtest: FIPS 140-2 failures: 600
rngtest: FIPS 140-2(2001-10-10) Monobit: 73
rngtest: FIPS 140-2(2001-10-10) Poker: 84
rngtest: FIPS 140-2(2001-10-10) Runs: 219
rngtest: FIPS 140-2(2001-10-10) Long run: 230
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=387.694; avg=7064.868; max=9765625.000)Kibits/s
rngtest: FIPS tests speed: (min=620.118; avg=40016.401; max=77198.617)Kibits/s
rngtest: Program run time: 2440397811 microseconds

The long-term failure probability for a packet was 0.0007, or one packet per 1247 failing. Since the source is genuinely random, some proportion of packets will normally fail the arbitrary tests, after all eventually a really random source might give a whole packet of zeros.

The 400MB random file was also given to ENT:

Entropy = 8.000000 bits per byte.

Optimum compression would reduce the size
of this 819200000 byte file by 0 percent.

Chi square distribution for 819200000 samples is 251.37, and randomly
would exceed this value 50.00 percent of the times.

Arithmetic mean value of data bytes is 127.4996 (127.5 = random).
Monte Carlo value for Pi is 3.141739666 (error 0.00 percent).
Serial correlation coefficient is 0.000045 (totally uncorrelated = 0.0).

The entropy figure of 8.000000 per byte is the maximum possible, and the derivation of PI to 0.00% error also suggests the quality of the randomness produced by Whirlygig is very high.