OneRNG - Theory of operation

Change list

Entropy, noise and random numbers

Modern computers need a source of entropy to seed their random number generators - entropy is simply 'randomness' - for example on a Unix/Linux computer random numbers are available from /dev/random, the kernel generates small amounts of entropy into its entropy pool which feeds the random number generator, if applications empty out the pool they will have to slow down and wait until more entropy is available. Programs that use lots of randomness, for example crypto creating lots of SSL certs will perform poorly.

On a Linux machine we can extract our entropy from our device by simply reading from the terminal interface that is created when it's plugged in and writing that data into the kernel entropy pool - the rngd system daemon will do that for us.

Our generator makes random streams of bytes - they're generated by random quantum processes and/or thermal noise - they're don't however present a perfectly randomly distributed bit stream - we get worst case about 7.8 bits of entropy per byte of data presented - it is recommended that you use our generator to feed your kernel random number generator's entropy pool rather than using the data directly. The installation instructions show you how.

Noise Sources

Our entropy generator includes two noise sources, you can choose to use either or both.

The primary noise generator is an avalanche diode (actually a pair of transistors) - it generates a series of random pulses at a frequency faster than we are sampling - we've tweaked the sampling level so that we sample a 1 or 0 roughly 50% of the time - because components are never exactly the same each device will be slightly different, some will sample slightly more 1s than others.

We've measured that our circuit samples slightly more 1s than 0s (about 5% more) - this corresponds to ~7bits/byte of entropy - we could make something with more finely tuned parts, but that would require having someone tweak the circuit on the assembly line, it would likely end up costing twice the price, or more for minimal gain.

The secondary noise generator is an RF receiver built into the CC2531 - it randomly (in time and frequency) skips around channels in and around the 2.4GHz wifi band measuring RF signal levels and sampling just the least significant bit - the CC25xx system document has some analysis of the use of this technique you can look at - we're measuring a very slight bias (0.14% more 1s than 0s). This performance is better than the avalanche diode circuit, but RF is by definition theoretically more susceptible to outside manipulation.

The default setting has the primary (avalanche diode) noise source enabled, and the secondary (RF source) disabled

Whitening

Because our byte streams have the minor built in sampling biases mentioned above it's useful to be able to pass them through a 'whitening' stage - a process that mixes up the bits to even out the number of 1s and 0s without reducing the amount of entropy present in the byte stream. Some applications like rngd check for bitstream sanity and will complain if there are too many more ones or zeros - whitening helps them accept our bitstream and feed it to the kernel random number generator.

In our case we have a CRC16 generator to use for whitening, when it's enabled we push each byte into the generator and extract the upper byte of the running CRC sum - this means that the bits of adjacent bytes are merged and xored together evening out the number of ones and zeros. This operation can be turned on or off, by default it's turned on. If you want the raw data turn it off.

Putting it all Together

Internally most of the device's RAM is used as an entropy pool:

Data is sourced a byte at a time from the two noise sources, if both are enabled alternate bytes are taken from each one, if the whitener is turned on the byte is passed through it.

The entropy pool works as a FIFO until it is full, subsequent data is continually xored into the pool as a ring buffer - this means that the entropy/byte value approaches 8 bits/byte if the pool is sampled at a lower rate than the rate at which it is filled.

.

When data is copied from the entropy pool to the USB controller it is cleared.

Crypto

The CC2531 has AES support, we don't use it in the system firmware - but if want to you're welcome to use it - sample code is available in the base Cheap RF kernel (RF and crypto support has been removed from the version of the OS used here but can be easily added back in).

Command and Control

The basic interface to the device is a simple terminal interface - commands are written to the device, entropy data is returned. All commands are ascii, 4 bytes the first 3 of are always "cmd" (always lower case) followed by a single letter command, any other data is ignored.

There are only a small number of commands:

Measured Performance

'ent' results

We analyzed OneRNG performance in its various modes using the linux 'ent' entropy test program by collecting 100mB worth of data in each mode - our original beta usings (firmware versions 1 or 2) used a simple algorithm for sampling the avalanche data - this resulted in these results:

ModeEntropy bits/byteArithmetic meanChi SquareMonte Carlo value for PiSerial Correlation
07.999998127.508250%3.141540123-0.000107
17.839684148.75020.01%2.5583611940.000466
27.999998127.503625%3.1420112160.000147
37.999352128.86130.01%3.107938012-0.000299
67.999998127.494525%3.141584420-0.000044
77.999998127.496990%3.141813404-0.000096

Version 3 firmware (the version shipping to Kickstarter participants) uses a new algorithm that double samples for each bit with some time separation between samples - this results in improved results:

ModeEntropy bits/byteArithmetic meanChi SquareMonte Carlo value for PiSerial Correlation
07.999998127.48962.5%3.141419209-0.000117
17.967816117.98090.01%3.3500230940.000302

Notes:

  • Entropy: goal is 8 bits/byte
  • Arithmetic mean: 127.5 is the ideal
  • Chi Square: values between 10% and 90% are good

    Analysis: mode 1 is raw avalanche diode data - we know there's a DC sampling bias here which shows in the arithmetic mean, and other numbers (this offset is a design tradeoff, the alternative is hand tweaking devices on the manufacturing line that would raise costs) - mode 7 is raw RF noise, it's higher quality. Mode 3 is combined (interleaved) data from both generators, as a result it's of an intermediate quality. Modes 0, 2, 4 are whitened versions of modes 1, 3, 5 resp.

    The RF noise source makes slightly higher quality noise than the avalanche diode, but it does depend on something external to the device - if you're a bit paranoid we recommend mode 0, otherwise mode 6 or 7 will do well (remember they skip from channel to channel at random intervals which slightly reduces the data rate). We default to mode 0.

    Noise Spectrum

    Another way of looking at the system is to measure the frequency distribution of the sampled values, looking for interfering signals (in our case for example we might be looking for an interfering signal from the boost power supply) - here's a plot obtained from Audacity by capturing a 100mB file from the avalanche diode (mode '1') then reading it in as 8-bit signed raw data then plotting the spectrum using a box ("Rectangular Window") filter.

    'dieharder' results

    dieharder is a well known random number testing program. We plan on running it on a selected group of OneRNG modes - it takes a long time for each run (over a month) so we don't have a large collection yet:

    Circuit Description

    The full schematic is here:

    Briefly:

    The above circuit fragment is a switching voltage boost converter - it converts 3 volts to around 20 volts to drive the avalanche diode

    This circuit fragment consists of two transistors, one biased in an unusual way to form an avalanche junction and the other to help amplify the result, followed by a simple transistor amplifier biased so that it generates a signal that is sampled at roughly 50:50 ones to zeroes by the CC2531's input anti-metastability flops (who's very purpose in life we are sorely testing here - but adding to our entropy in the process).

    Links

    Back to main page