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.

Other Links

Here are some links relevant to cryptographic random number generation.

RFC 4086 Randomness Requirements for Security

RFC 5869 HMAC-based Extract-and-Expand Key Derivation Function (HKDF)

NIST SP 800-108 Recommendation for Key Derivation Using Pseudorandom Functions

NIST SP 800-56C Recommendation for Key Derivation through Extraction-then-Expansion

Why Cryptography Is Harder Than It Looks

Cryptanalytic Attacks on Pseudorandom Number Generators

Fortuna improves on Yarrow by not relying on dubious entropy measurements.

This paper suggests some improvements to Fortuna, including the use of a random permutation instead of a round-robin method to pick the pool: Yevgeniy Dodis and Adi Shamir and Noah Stephens-Davidowitz and Daniel Wichs. How to Eat Your Entropy and Have it Too -- Optimal Recovery Strategies for Compromised RNGs, Cryptology ePrint Archive: Report 2014/167.

Jochen Vosss has a Go implementation of Fortuna and also lists a number of Alternative Implementations.

Yarrow-160: Notes on the Design and Analysis of the Yarrow Cryptographic Pseudorandom Number Generator

Peter Gutmann takes a look at many existing implementations and gives his two cents in Chapter 6: Random Number Generation.

Hard Truths about the Hard Business of finding Hard Random Numbers

L. Dorrendorf, Z. Gutterman, and B. Pinkas. Cryptanalysis of the Random Number Generator of the Windows Operating System, Cryptology ePrint Archive, Report 2007/419, 2007.

Hugo Krawczyk. Cryptographic Extraction and Key Derivation: The HKDF Scheme, 2010

Dana Dachman-Soled and Rosario Gennaro and Hugo Krawczyk and Tal Malkin. Computational Extractors and Pseudorandomness, Cryptology ePrint Archive: Report 2011/708, 2011

Yevgeniy Dodis and Krzysztof Pietrzak and Daniel Wichs. Key Derivation Without Entropy Waste, Cryptology ePrint Archive: Report 2013/708, 2014

Henry Corrigan-Gibbs and Suman Jana. Recommendations for Randomness in the Operating System, or How to Keep Evil Children out of Your Pool and Other Random Facts, HotOS XV, 2015.

Mario Cornejo and Sylvain Ruhault. Characterization of Real-Life PRNGs under Partial State Corruption, Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, 2014. 10.1145/2660267.2660377

Yevgeniy Dodis, David Pointcheval, Sylvain Ruhault, Damien Vergnaud, Daniel Wichs. Security Analysis of Pseudo-Random Number Generators with Input: /dev/random is not Robust

Yvonne Cliff and Colin Boyd and Juan Gonzalez Nieto. How to Extract and Expand Randomness: A Summary and Explanation of Existing Results, Cryptology ePrint Archive: Report 2009/136, 2009

G. Bertoni, J. Daemen, M. Peeters and G. Van Assche. On the security of the keyed sponge construction, Symmetric Key Encryption Workshop, 2011

Denker, John S., High-Entropy Randomness Generator, 2005.

S. Kim, K. Umeno, and A. Hasegawa, Corrections of the NIST statistical test suite for randomness, Cryptology ePrint Archive, Report 2004/018, 2004.

J. S. Coron and D. Naccache, An Accurate Evaluation of Maurer's Universal Test, Proceedings of SAC '98 (Lecture Notes in Computer Science), Springer-Verlag, 1998.

B. Ya. Ryabko, V.A. Monarev, Using Information Theory Approach to Randomness Testing, Journal of Statistical Planning and Inference, 2005.

Peter Gaži and Stefano Tessaro, Provably Robust Sponge-Based PRNGs and KDFs, Cryptology ePrint Archive, Report 2016/169, 2016.

There may also be some links of interest here