crypto-rng.dox

/*
 * Copyright (C) 2015 Southern Storm Software, Pty Ltd.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included
 * in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
 */

/**
\file crypto-rng.dox
\page crypto_rng 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.

\section crypto_rng_features Features of the random number generator

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

\li Provision for plug-in environmental noise sources and entropy estimation.
\li Whitening of noise values to scatter the input noise across the entire
    random number pool.
\li Built-in support for the True Random Number Generator (TRNG) in the
    Arduino Due's CPU.
\li 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.
\li Cryptographically secure pseudo random number generator (PRNG) for
    expanding the noise-based seed into an arbitrary amount of random material
    for the application.
\li Periodic saving of the random seed into EEPROM so that the accumulated
    entropy is not lost across a power restart.
\li 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.

\section crypto_rng_noise_sources Standard noise sources

The library provides two standard noise sources:

\li TransistorNoiseSource for collecting avalanche noise from a transistor.
    This is based on the work of
    <a href="http://robseward.com/misc/RNG2/">Rob Seward</a>.
\li RingOscillatorNoiseSource for collecting entropy from the jitter of a
    \ref crypto_rng_ring "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 \ref crypto_rng_ring "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.

\section crypto_rng_builtin 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
<a href="https://sites.google.com/site/astudyofentropy/project-definition/timer-jitter-entropy-sources/entropy-library">here</a>.
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.

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

\section crypto_rng_init Initializing the random number generator

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

\code
#include <Crypto.h>
#include <RNG.h>
#include <TransistorNoiseSource.h>
\endcode

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

\code
TransistorNoiseSource noise(A1);
\endcode

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

\code
void setup() {
    // Initialize the random number generator with the application tag
    // "MyApp 1.0" and load the previous seed from EEPROM address 950.
    RNG.begin("MyApp 1.0", 950);

    // Add the noise source to the list of sources known to RNG.
    RNG.addNoiseSource(noise);

    // ...
}
\endcode

The begin() function is passed two arguments: a tag string that should
be different for every application and an EEPROM address to use to
load and save the random number seed.  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():

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

The random number generator needs 49 bytes of EEPROM space at the
specified address 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 \link RNGClass::setAutoSaveTime() RNG.setAutoSaveTime()\endlink.
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 \link RNGClass::loop() RNG.loop()\endlink
function takes care of these tasks for us:

\code
void loop() {
    // ...

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

    // ...
}
\endcode

The random number generator is now ready to generate data.

\section crypto_rng_using Generating data with the random number generator

Whenever the application needs random data, it calls
\link RNGClass::rand() RNG.rand()\endlink 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:

\code
byte key[32];
byte iv[16];

void generateKeys() {
    RNG.rand(key, sizeof(key));
    RNG.rand(iv, sizeof(iv));
}
\endcode

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 <tt>/dev/urandom</tt> 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 <tt>/dev/random</tt> 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 \link RNGClass::available() RNG.available()\endlink
function to poll how much entropy is in the global random number pool:

\code
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;
    }
}
\endcode

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.

\section crypto_rng_secret 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:

\code
memset(key, 0, sizeof(key));
memset(iv, 0, sizeof(iv));
\endcode

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:

\code
clean(key);
clean(iv);
\endcode

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:

\code
clean(key, 32);
clean(iv, 16);
\endcode

*/