Entropy and Random Numbers

NIST

NIST's Computer Security Resource Center provides a set of cryptographic standards in their Cryptographic Toolkit, of particular interest is the Random Number Generation component.

NIST SP 800-22 Rev. 1a: While focused on the STS, the background information contains a clear and concise introduction to random number generation.
NIST SP 800-90Ar1: NIST has published a set of random number generators that are FIPS 140 approved (FIPS 140-2 Annex C: Approved Random Number Generators). It also has a good discussion of the whole “randomness” thing. There's an implementation below.

These documents and then some can be found with the rest of NIST's Special Publications.

NIST SP 800-90Ar1 CTR_DRBG

nist_rng_20070927.tgz or on GitHub

This code implements a random number generator based on section 10.2 DRBG Mechanisms Based on Block Ciphers in NIST SP 800-90Ar1. More specifically, it implements CTR_DRBG with a derivation function using AES-256 (see FIPS 197) as the block encryption function.

Security strength, prediction resistance, and the like apply to a higher level interface than is currently implemented (the algorithm as implemented can be used to support prediction resistance and a security strength of up to 256).

It gives the same output on i386/OpenBSD, amd64/FreeBSD and Windows, but without test vectors one shouldn't say a whole lot more about that output (DIEHARD seems happy, but that could be true even if things were severely screwed up).

There are known-answer tests included in the kat directory for the Rijndael code, but not for CTR_DRBG (I'm still looking for test vectors). Both the VIA padlock implementation and the default software implementation match the corresponding NIST test vectors.

A new version of c7random is included that adds a full entropy NIST CTR_DRBG random number generator (command line option “-N”). The result should be something along the lines of NIST SP 800-90 Appendix D. It's intended to be consistent with an “RBG” as described in D.1.b and D.2.1—minus runtime tests and such decidedly non-trivial details. For every 16 bytes of output, it consumes at least 18 bytes from the CPU's entropy source. Should the CPU stop generating entropy output the program will stop outputting data, but the entropy output is not validated in any way. Have nist_config.h include nist_aes_padlock.h instead of nist_aes_rijndael.h to use the CPU's AES hardware (c7random always uses the C3/7's hardware entropy). “c7random -N” does not require hardware SHA support, so it works on earlier VIA CPUs that only have the AES and RNG options.

There are number of things to keep in mind:

The API should be based on the “envelope” described in chapter 9 and section F.3.2. So far, only the section 10.2 algorithm is implemented.
The RBG code lacks both test vectors and a way to validate them.
Some basic runtime self-tests need to be implemented (and enforced by the various API functions).
The code should be reviewed to make sure it is consistent with SP 800-90 (there are comments throughout the code referencing the relevant parts of SP 800-90).
The Makefiles will likely need some tweaks for anything other than OpenBSD (there are project files for Microsoft Visual Studio 2005 for building both 32-bit and 64-bit executables).

Linux /dev/random

The Linux /dev/random implementation was written by Theodore Ts'o (now maintained by Matt Mackall). The same design was adopted by a number of other projects.

OpenBSD: The current code's closest relative is probably the 1999 Linux version (see rnd.c).
FreeBSD: Used the Ts'o implementation through release 4 (see kern_random.c) until it was replaced with Yarrow (see An implementation of the Yarrow PRNG for FreeBSD).
NetBSD: Has a home-grown implementation based on Theodore Ts'o's design (in rnd.c and rndpool.c).

B. Barak and S. Halevi. An architecture for robust pseudo-random generation and Applications to /dev/random. In ACM, editor, Proc. Computing and Communication Security (CCS), 2005.

Zvi Gutterman wrote a paper called Holes in the Linux Random Number Generator. Here's Theodore Ts'o's take: LWN: Re: /dev/random on Linux.

Z. Gutterman, B. Pinkas, and T. Reinman. Analysis of the Linux Random Number Generator, IEEE Symposium on Security and Privacy, 2006.

Statistical Testing

NIST Statistical Test Suite

DIEHARD

DieHarder (see also here)

the pLab project

TestU01

VIA PadLock OpenSSL Patch

md_rand.c.diff-20070828.gz

From a software engineering point of view, this is a perfectly evil way of forcing more entropy into OpenSSL's default random implementation (perhaps there should be a nice API for doing this?). Most systems simply do not have such an enormous amount of high-quality entropy as VIA PadLock… Anyhow, even if the hardware goes nuts and starts feeding all zeros, it will be no worse than without the patch. With working hardware, the generator should be pretty close to full entropy.

It should work on any recent gcc. Just make sure that PIC is defined when building a shared library (or change the #if to match whatever is appropriate on the local platform), otherwise gcc will complain about the use of ebx.

The VIA PadLock support for Linux page has more information about OpenSSL and VIA PadLock.