Random Number Generators

Introduction

Random Number Generators (RNGs) are used in many fields to create randomness. In cryptography, they are often used for generating cryptographically secure keys and padding. For example, take RSA key pair generation and OAEP.

RNG categories

RNGs can be categorized into two:

• Non-deterministic Random Bit Generators (NRBGs) 
• Deterministic Random Bit Generators (DRBGs)

A NRBG generates a sequence of bits non-deterministically using a physical process that is unpredictable. For this reason it is said to produce true random bits, and often called a True Random Number Generator (TRNG).
In contrast, a DRBG uses an algorithm to generate a sequence of random bits from a secret initial value called the seed. Because of this deterministic nature, it is said to produce pseudorandom bits, and often called a Pseudo-Random Number Generator (PRNG). The output will be unpredictable as long as the seed has sufficient entropy and it is kept secret.

NIST recommendations

In their SP 800-90 special publications NIST provides recommendations on the construction and validation of RBGs that can be used for cryptographic applications. Very brief description of each is given below. Please refer to their latest revisions for details.

• SP 800-90A
  Addresses the construction of approved DRBG mechanisms. The latest revision (revision 1 at the time of this writing) provides following DRGB algorithm specifications based on hash functions and block ciphers that use NIST approved hash functions, keyed hash functions and block ciphers in counter mode respectively.

• HASH DRBG
• HMAC DRBG
• CTR DRBG

• SP 800-90B
  Specifies how to design and test entropy sources that can be used by RBGs.

• SP 800-90C
  Addresses the construction of RBGs from the mechanisms in SP 800-90A and the entropy sources in SP 800-90B.

RNGs and Linux

Linux makes its RNGs available to user space as character devices and the kernel APIs provide access to random numbers in the kernel space.

If a hardware RNG is available it will be available from /dev/hwrng. Linux kernel PRNG is available from /dev/urandom for non-blocking pool and from /dev/random for blocking pool.

Kernels APIs get_random_bytes_arch and get_random_bytes provide access to random bytes from hardware RNG and the PRNG non-blocking pool respectively.

Linux kernel PRNG implementation is found in /drivers/char/random.c in the source. It is characterized by entropy pool mixing, entropy estimation and the output generation functions as discussed in the paper The Linux Pseudorandom Number Generator Revisited by Lacharme, Roeck, Strubel, and Videau.

General structure of Linux PRNG

See the source file for the details of mixing and output generation as it contains details for a specific kernel version. Older kernels used LFSRs for mixing and SHA-1 for output generation whereas new ones (4.8 onward) seem to use ChaCha20.

The Linux rngd can be used to feed random data to kernel input pool. It will check the data to ensure that it has sufficient entropy and by default will use hardware RNG, if available, as the source.

OpenSSL RNGs

One can use APIs available in OpenSSL to obtain random data for their applications, specially if cryptographically secure random data is needed. By default OpenSSL uses a MD5 based random number generator.
To use NIST SP800-90 approved generators one should use an FIPS enabled OpenSSL library. In FIPS mode it supports HASH, HMAC and AES-CTR mode DRBGs, 256-bit AES-CTR based DRBG being the default. Refer OpenSSL FIPS Object Module user guide for DRBG API details.

Evaluating the randomness of RNGs

NIST special publication SP 800-22 describes a set of statistical tests for randomness, specifically focusing on randomness required for cryptographic purposes. These tests are made available through a free software called the NIST Statistical Test Suite (NIST STS Tool) that one can download from NIST site, build and use for performing these tests. The suite includes 15 tests. Refer the latest revision of the publication for test details and how to use the software.

References:

• NIST special publications SP 800-90A, SP 800-90B, SP 800-90C, SP 800-22
• The Linux Pseudorandom Number Generator Revisited by Lacharme, Roeck, Strubel, and Videau
• LWN article LCE: Don't play dice with random numbers
• OpenSSL FIPS Object Module v2.0 User Guide