Adding entropy to /dev/random

A hard RNG is good to find

The recent statistical analysis for drumbeat reminded me I could do with a proper source of random numbers, not generated by a pseudorandom feedback action. Back in the early 1990s I was looking at statistical profiling of execution on microcontrollers, I was surprised then to discover that only by making the sampling period random could I get a true picture of execution distribution. If the address bus was sampled at a fixed rate, say 100kHz, instead of a true picture it would be distorted by activity that was happening at some fraction or harmonic of the sampling frequency. So you would alias out pieces of loops completely or get a bloated count for other areas. Only by true randomness in the sampling timing could you see the reality -- a paradox.

Analogue RNG methodologies

A Google or two around showed that most of the techniques are analogue one way or the other. Many of the methods suffer from a problematic need to amplify some very tiny source of noise, a Zener diode or avalanche transistor junction, by really huge amounts, 90dB or more. There are a couple of suppliers of RF "noise diodes" with flat spectra across a wide frequency range, but they are hard to source.

Digital non-pseudorandom technique

However there is one technique which while still relying on analogue noise is basically digital -- to run multiple chains of unlocked inverting oscillators and xor the outputs. The unlocked oscillators have no reference at all, they're basically an inverter fed back on its own input -- in fact a chain of inverters. Such a circuit oscillates according to the period of the total delay through the inverter chain... and that is highly sensitive to temperature. Normally with synchronous digital design we choose a clock rate for a circuit that is just below the maximum possible at the worst temperature it is expected to operate at -- and after that we can forget about temperature. But with this asynchronous unlocked oscillator concept, the micro- and macro- temperature dependence is revealed in all its freaky glory, causing the oscillation to drift unpredictably slightly every cycle and over larger period with gross temperature fluctuations.

RFC4086

RFC4086 mentions a recommendation for a RNG based on unlocked inverter chains that is found in IEEE 802.11i.

             |\     |\                |\
         +-->| >0-->| >0-- 19 total --| >0--+-------+
         |   |/     |/                |/    |       |
         |                                  |       |
         +----------------------------------+       V
                                                 +-----+
             |\     |\                |\         |     | output
         +-->| >0-->| >0-- 23 total --| >0--+--->| XOR |------>
         |   |/     |/                |/    |    |     |
         |                                  |    +-----+
         +----------------------------------+      ^ ^
                                                   | |
             |\     |\                |\           | |
         +-->| >0-->| >0-- 29 total --| >0--+------+ |
         |   |/     |/                |/    |        |
         |                                  |        |
         +----------------------------------+        |
                                                     |
             Other randomness, if available ---------+

This has three unlocked, wandering oscillator chains of different lengths being summed at an XOR gate.

Implementing the RFC4086 RNG

Since it needs 71 inverters, you would need 12 74hc04 or similar, it makes more sense to put it all in one CPLD. I have an old XC95108 lying around, so I wrote up the design in VHDL and added a UART interface to issue the sampled random data. This brings up the issue of how quickly it can be sampled and still get high quality randomness... clearly if we sampled it at 10ps it wouldn't be very random at all, since it didn't have time to change between samples. On the other hand if we sampled it at some high multiple of the fastest free-running oscillator period, then there is a lot of opportunity for each oscillator phase to have been affected over the longer time. By using the UART we can control how often we sample the RNG by the baud rate... I initially set it to 9600 baud or 104us/sample. The oscillators should have periods on the order of 150 - 200ns (5 - 6MHz), so this is allowing 500+ cycles of jitter to accumulate in each oscillator before the summed sample is taken. I'm currently waiting for a programming tool to be delivered so I can program another device to allow programming the XC95108 -- I no longer have any PCs with a printer port I realized yesterday. I am very interested to see what the performance and quality of the randomness is like!