Generating random numbers

Random numbers are one of the most important aspects of secure cryptography. Without a good source of random numbers it may be possible for an attacker to predict the encryption and authentication keys that are used to protect a session, or to predict the private component of a public/private key pair. This is especially difficult in embedded environments that do not have input sources like keystrokes, mouse movements, disk drive write times, etc to collect entropy from the user.

Features of the random number generator

This library provides the RNG class to manage the global random number pool. It has the following features:

• Provision for plug-in environmental noise sources and entropy estimation.
• Whitening of noise values to scatter the input noise across the entire random number pool.
• Built-in support for the True Random Number Generator (TRNG) in the Arduino Due's CPU.
• Support for mixing in static values like serial numbers and MAC addresses so that otherwise identical devices do not generate the same sequence of random numbers upon first boot.
• Cryptographically secure pseudo random number generator (PRNG) for expanding the noise-based seed into an arbitrary amount of random material for the application.
• Periodic saving of the random seed into EEPROM so that the accumulated entropy is not lost across a power restart.
• Built-in protection so that if an attacker captures the seed, it cannot be used to predict past outputs. And after mixing in a modest amount of new noise, cannot be used to predict future outputs.

The whitening function and the PRNG are based on ChaCha::hashCore() with 20 rounds. The structure of the PRNG is very similar to OpenBSD's ChaCha20-based arc4random() implementation.

Standard noise sources

The library provides two standard noise sources:

• TransistorNoiseSource for collecting avalanche noise from a transistor. This is based on the work of Rob Seward.
• RingOscillatorNoiseSource for collecting entropy from the jitter of a ring oscillator. This is a design of my own.

The transistor design needs an input voltage of 10 to 15 VDC to trigger the avalanche effect, which can sometimes be difficult in a 5V Arduino environment. The ring oscillator design can run at 5V but the quality of the noise is less than for the transistor design. The RingOscillatorNoiseSource class attempts to make up for this by collecting more input bits for the same amount of output entropy. See this page for more information on ring oscillators.

For both of the standard noise sources, the system should have enough entropy to safely generate 256 bits of key material about 3 to 4 seconds after startup. This is sufficient to create a private key for Curve25519 for example.

If you are unsure which noise source to use, then I suggest TransistorNoiseSource as Rob's design has had more review. Another approach is to mix multiple noise sources together to get the best of both worlds.

Built-in entropy sources

Some entropy sources are built in and do not need to be provided via a NoiseSource object.

On the Arduino Due, the built-in True Random Number Generator (TRNG) is used to seed the random number generator in addition to any configured noise sources.

On AVR-based Arduino platforms (Uno, Nano, Mega, etc), jitter between the watchdog timer and the main CPU clock is used to harvest some entropy using a technique similar to that described here. This is not a high quality source of entropy but it is "better than nothing" if an external noise source is not available or practical. Entropy accumulates very slowly and it could take several minutes before the state is sufficiently random for safe use.

On newer AVR chips, Custom Configurable Logic (CCL) is used to generate an unstable clock source which is sampled by the more predictable RTC timer.

For security-critical applications it is very important to combine the built-in entropy sources with an external noise source.

Initializing the random number generator

To use the random number generator, both RNG and a noise source must first be initialized. We start by including the necessary libraries:

#include <Crypto.h>
#include <RNG.h>
#include <TransistorNoiseSource.h>

Next we create a global variable for the noise source and specify the I/O pin that the noise circuit is connected to:

TransistorNoiseSource noise(A1);

Then in the setup() function we call RNG.begin() to start the random number generator running and call RNG.addNoiseSource() to register all of the application's noise sources:

void setup() {
    // Initialize the random number generator with the application tag
    // "MyApp 1.0" and load the previous seed from EEPROM.
    RNG.begin("MyApp 1.0");
 
    // Add the noise source to the list of sources known to RNG.
    RNG.addNoiseSource(noise);
 
    // ...
}

The begin() function is passed a tag string that should be different for every application. The tag string ensures that different applications and versions will generate different random numbers upon first boot before the noise source has collected any entropy. If the device also has a unique serial number or a MAC address, then those can be mixed in during the setup() function after calling begin():

void setup() {
    RNG.begin("MyApp 1.0");
    RNG.stir(serial_number, sizeof(serial_number));
    RNG.stir(mac_address, sizeof(mac_address));
    RNG.addNoiseSource(noise);
    ...
}

The random number generator uses 48 bytes of space at the end of EEPROM memory to store the previous seed. When the system is started next time, the previous saved seed is loaded and then deliberately overwritten with a new seed. This ensures that the device will not accidentally generate the same sequence of random numbers if it is restarted before the first automatic save of the seed.

By default the seed is saved once an hour, although this can be changed with RNG.setAutoSaveTime(). Because the device may be restarted before the first hour expires, there is a special case in the code: the first time that the entropy pool fills up, a save will be automatically forced.

The Arduino Due does not have EEPROM so RNG saves the seed into the last page of system flash memory instead. The RNG class will also mix in data from the CPU's built-in True Random Number Generator (TRNG). Assuming that the CPU's TRNG is trustworthy, this should be sufficient to properly seed the random number generator. It is recommended to also mix in data from other noise sources just in case the CPU's TRNG is not trustworthy.

To use the random number generator properly, there are some regular tasks that must be performed every time around the application's main loop(). Newly accumulated noise must be mixed in and auto-saves must be performed on a regular basis. The RNG.loop() function takes care of these tasks for us:

void loop() {
    // ...
 
    // Perform regular housekeeping on the random number generator.
    RNG.loop();
 
    // ...
}

The random number generator is now ready to generate data.

Generating data with the random number generator

Whenever the application needs random data, it calls RNG.rand() with a buffer to fill. The following example generates a 256-bit encryption key and a 128-bit initialization vector; e.g. for use with AES256 in CTR mode:

byte key[32];
byte iv[16];
 
void generateKeys() {
    RNG.rand(key, sizeof(key));
    RNG.rand(iv, sizeof(iv));
}

The data will be generated immediately, using whatever entropy happens to be in the global random number pool at the time. In Linux terms, the rand() function acts like the /dev/urandom device.

If the system has been running for a while then this should be safe as the noise source would have already permuted the pool with noise-based entropy. However, when the system first starts up there may not be much entropy available other than that from the saved seed (which could have been compromised).

In Linux terms we want the effect of the /dev/random device which blocks until sufficient entropy is available to service the request. Blocking isn't very friendly to other application tasks, so the library instead provides the RNG.available() function to poll how much entropy is in the global random number pool:

byte key[32];
byte iv[16];
bool haveKeys = false;
 
void generateKeys() {
    if (!haveKeys && RNG.available(sizeof(key) + sizeof(iv))) {
        RNG.rand(key, sizeof(key));
        RNG.rand(iv, sizeof(iv));
        haveKeys = true;
    }
}

This feature should allow applications to generate secret material safely at startup. The application may want to implement a timeout: if the application has to wait too long to generate a key then the noise source may be disconnected or faulty.

The global random number pool can hold up to 48 bytes, or 384 bits, of entropy. Requests for more than 384 bits will be allowed if the entropy is at maximum. That is, a request for 64 bytes (512 bits) of data will be allowed when there is only 384 bits of entropy in the pool. This behaviour prevents the application from waiting indefinitely if the request is too large.

If the application truly needs more than 384 bits of real entropy (e.g. to generate a public/private key pair for an algorithm like RSA), then it should break the request up into smaller chunks and poll available() for each chunk.

Destroying secret data

When the application is finished with the secret key material and plaintext, it should destroy the data to remove it from RAM permanently. The memset() function can be used for this purpose:

memset(key, 0, sizeof(key));
memset(iv, 0, sizeof(iv));

However, this may not be safe. Optimizing compilers have been known to optimize away memset() calls if the compiler thinks that the value won't be used again. A safer method is to use the clean() function in the library:

clean(key);
clean(iv);

The clean() function attempts to implement the memory clear in a way that the compiler shouldn't optimize away. By default the clean() function figures out the size of the buffer itself at compile time. In some cases (e.g. buffers that are passed by pointer), it may be necessary to specify the size manually:

clean(key, 32);
clean(iv, 16);