>> SECURE RANDOM NUMBER GENERATOR FOR THE ARDUINO

random, random, random, {identify pattern}, no longer random.

As part of the arduino security investigations the concept of a secure random number generator came up and would be a necessity for implementing cryptographic algorithms on the device. Of course, the use of the standard rand() function wasn't going to cut it - so here is the proposed solution that theoretically should be sufficient for such use cases.

Of course it isn't the first time someone has looked into this - a simple google query will find people hooking up Geiger counters, or complete studies on how reliable an arduino can be as a hardware random number generator such as the report by Benedikt Kristinsson or simply how difficult it is to find a decent algorithm to even implement as written by P. Hellekalek.

The problem with Pseudo Random Number Generators (PRNG) is that they follow a pre-determined algorithm and as a result once a pattern is found they are no longer considered "random". Of course, there are secure PRNG's implemented that monitor entropy, incorporate hashes and do real time analysis of the results to eliminate predictability of the results.

I tinkered with the idea of using the noise of reading an unconnected analog pin on the arduino and blended it together with a standard PRNG - with the goal of randing to generate a minimum of 128 random bytes with some level of unpredictability; the basic code looks as:

• int secureRandomByte()
  {
    static int count = 0;
    static int next  = (randomByte() >> 2) + 1;
    if ((count++ % next) == 0)
    {
      randomSeed(randomWord());
      next = (randomByte() >> 2) + 1; // use the same seed a maximum of 64 times
    }
    return random(256);
  }
  

The idea is to only use a "PRNG" algorithm with a specific starting seed for a maximum of 64 calculations (in fact, it can be anything between 1 and 64) - which is determined based on noise from the analog pin. It would even be possible to skip every second byte and reduce this to down to 32 (worst case scenario) based on the same starting seed.

The underlying randomWord() and randomByte make use of the following function:

• int randomBitRaw()
  {
    for (;;)
    {
      int a = (analogRead(0) & 1) | ((analogRead(0) & 1) << 1);
      if (a == 1) return 0;
      if (a == 2) return 1;
      // otherwise, keep looking
    }
  }

Which in turn uses an algorithm developed by John von Neumann to reduce bias in the stream of bits being identified - basically, only sequences of 01 and 10 would ever produce a value that could be used as part of forming a random number. The random() function provided on the arduino is simply re-used based on these values.

I would argue that this implentation would be sufficient to confidently say that it would be difficult to predict the 128 random bytes that would be used for the symmetric keys - the noise of the analog pin and subsequent random reseeding intervals would make it impossible.