Harnessing Entropy

The Pico has a source of entropy in the form of a Ring Oscillator (ROSC). It is basically a clock that runs at a rate that varies according to temperature and operating voltage etc. This means that reading it can provide a moderately random value. The data sheet says:

“If the system clocks are running from the XOSC and/or PLLs the ROSC can be used to generate random numbers. Simply enable the ROSC and read the RANDOMBIT register to get a 1-bit random number and read it n times to get an nbit value. This does not meet the requirements of randomness for security systems because it can be compromised, but it may be useful in less critical applications. If the cores are running from the ROSC then the value will not be random because the timing of the register read will be correlated to the phase of the ROSC. “

In a standard Pico the clock is derived from the XOSC and the ROSC can be used to supply a random bit. This is very easy to do. To access the correct register all you need is:

#include "hardware/structs/rosc.h"

which imports a struct that has the correct address assigned to a pointer. After this you can read a random bit using:

bit = rosc_hw->randombit

The bit is returned as the low order bit of a 32-bit int.

You can create a random byte using:

uint8_t randomByte()
{
    uint32_t random = 0;
    for (int k = 0; k < 8; k++)
    {      
      random = (random << 1) | rosc_hw->randombit;
    }
    return (uint8_t)random;
}

If you try this out you will find that it fails most of the NIST tests of randomness. It doesn’t even pass the test for an equal number of ones and zeros. The probability of generating a zero is 0.55 which is a small, but significant, bias.

A simple transformation, called von Neumann whitening after its inventor, improves the balance of ones and zeros. If you have a bit stream with unequal probabilities of a one or a zero you can transform it to a 0 on a change from 0 to 1 and a 1 on a change from 1 to 0 and discard bits pairs of bits that are equal, i.e. 00 and 11. There are obviously as many up-going edges as there are down-going edges so the number of ones and zeros is the same. The cost of this transformation is needing a few more random bits to throw away:

uint8_t randomByte()
{
    uint32_t random = 0;
    uint32_t bit = 0;
    for (int k = 0; k < 8; k++)
    {
                while (true)
                {
                    bit = rosc_hw->randombit;
                    if (bit != rosc_hw->randombit)
                        break;
                } 
                random = (random << 1) | bit; 
    return (uint8_t)random;
}

If you try this out you will discover that it only reduces the bias to 0.54 and the random sequence still fails the NIST tests. The reason is that the sequential bits are correlated.

The problem is that the ROSC is a source of entropy but we are taking data from it too fast. The oscillator varies over time and to reduce the correlations between subsequent bits we need to allow enough time between readings for the oscillator to have randomly drifted. Putting this another way the entropy accumulates with time.

The solution is to modify the von Neumann whitening to include a delay:

uint8_t randomByte()
{
    uint32_t random = 0;
    uint32_t bit = 0;
    for (int k = 0; k < 8; k++)
    {
                while (true)
                {
                    bit = rosc_hw->randombit;
                    sleep_us(10);
                    if (bit != rosc_hw->randombit)
                        break;
                }  

                random = (random << 1) | bit; 
		   sleep_us(10); 
    }
    return (uint8_t)random;
}

This produces a random sequence that passes all of the NIST tests and has virtually no bias – the probability of a zero bit is 0.499. The delay could possibly be reduced, but if you only want a few tens of random bytes this isn’t worth optimizing. With this delay the ROSC becomes an acceptable source of randomness that you can use to generate keys.