TrueRandom is not truly random

A while ago I had to get microcontrollers to generate truly random addresses for themselves, truly random 32-bit addresses to minimize collisions.  I looked around for inspiration and found the TrueRandom library for Arduino.   After testing it, I realized it’s not actually random and shouldn’t be used for anything important.

Here’s a scatterplot of 4800 values from TrueRandom.randomByte():

TrueRandom clustering at powers of 2

and histogram:

TrueRandom histogram

Clearly these are not randomly distributed.  They’re strongly centered around 0 and low powers of 2, probably due to the von Neumann whitening algorithm they threw in there?  “This technique works no matter how the bits have been generated. It cannot assure randomness in its output, however. What it can do (with significant numbers of discarded bits) is transform a biased random bit stream into an unbiased one.”

See Randomness testing of Arduino TrueRandom for details.

It should look like this, uniformly distributed with no clustering:

/dev/urandom no clustering

With the 8051-based micro I was working with, the least significant 2 or 3 bits of the ADC were random thermal noise, even with the input pin grounded, so I used that as my entropy source.  If you XOR a random bit stream with an uncorrelated non-random stream, the output is still random, so I measured the ADC 8 times, bit-rotated each result an increasing amount, and XORed them all together, to spread the randomness around to all 8 bits.  As far as I can tell, this is a good method to produce uniformly distributed, truly random bytes.  (Please correct me if I’m wrong.)

On the Arduino, though, the ADC does not produce any noisy bits, so it can’t be used for this purpose.  The LSBs are just stuck at 0 all the time, and the value can be exactly the same many times in a row:

temperature sensor vs AVCC plot

Ardrand: The Arduino as a Hardware Random-Number Generator “We explore various methods to extract true randomness from the micro-controller and conclude that it should not be used to produce randomness from its analog pins.”

So for Arduino, I used the frequency difference between the watchdog timer and Timer 1 as the entropy source (suggested near the end of True Random Number Generation on an AtmelAVR Microcontroller, but not actually tested).   It uses the watchdog timer to sample (and reset) Timer 1.  Since the watchdog timer runs on its own RC oscillator, and Timer 1 is on the crystal oscillator, there is random variation in the value read. Then the randomness is spread around to all 8 bits by the same method.  The watchdog timer’s minimum length is not short, so this method only produces about 64 bit/s, vs TrueRandom’s 3200 bit/s.  But they’re good bits.

Since TrueRandom doesn’t live up to its name, and I’m not a cryptographic expert, I erred on the side of caution and named it ProbablyRandom:

The output looks uniformly distributed to me (and ent says it’s good, too):

65536 samples watchdog xorshifted plot

65k with TimerOne disabled histogram

I think the main flaw would be if the two oscillators become locked with each other at a certain temperature and supply voltage or something, but I haven’t noticed any drop in randomness, despite running it continuously for days.

Note: This has since been developed into the Entropy library for Arduino.