Cryptographic Random Numbers

I've written an article on Secure Random Numbers for the August 2002 issue of Windows Developer Magazine. During the research phase, I found that while a lot of resources were available online (mostly in the form of link farms), it was difficult to decide what to read and what not. I ended up reading most of what I found. To make the job easier for people trying to learn about secure random numbers I've prepared this annotated list of links. More than just another link farm I've tried to categorize and comment each resource. Enjoy!

Index

Overviews

RFC 1750: Randomness Recommendations for Security (here as .pdf).
D. Eastlake, S. Crocker and J. Schiller are the authors of this 30 page document. Very comprehensive. Perhaps not the best if you're just getting started, but if you only read one make sure it is this one.

Cryptographic Random Numbers (see also here).
Carl Ellison wrote this introduction to random numbers as appendix to the P1363 standard. Also very useful. He's also writing a new one. And his main conclusion seems to be that Intel's hardware RNG included in certain Pentium processors makes software RNGs obsolete.

Jon Callas has written Using and Creating Cryptographic-Quality Random Numbers.
Very good paper, but I've found the web server to be quite unreliable. If you have trouble try a Google search and look it up in the cache.

Tim Matthews wrote Suggestions for Random Number Generation in Software as part of the RSA Bulletin Number 1 - January 22, 1996.
Nice and short.

RSA Laboratories' Frequently Asked Questions About Today's Cryptography
Not an in-depth treatment, but section 4.1.2.2 How does one find random numbers for keys? is a nice executive summary of the field.

Playing the numbers, Beating the bias and Software strategies
Under the general title Make your software behave, Gary McGraw and John Viega wrote several columns on software security for IBM's developerWorks. Very easy to read and a good way to get started with PRNGs. As they say "The developerWorks columns by Gary and John have been updated and expanded in the book Building Secure Software, which also includes plenty of new material."

More in-depth

Cryptanalytic Attacks on Pseudorandom Number Generators, J. Kelsey, B. Schneier, D. Wagner, and C. Hall, 1998.
Very important paper, where the authors present a general model for describing PRNGs and then use it to analyze several real-world designs. This paper led to the design of the Yarrow PRNG. The only nitpick I've got is that they don't analyze Peter Gutman's CSPRNG (see below), which is a pity as Peter clearly doesn't agree with their model.

Peter Gutman's Software Generation of Practically Strong Random Numbers
As he says "Although there are a number of papers which give very broad recommendations on random number generation, none seem to give very specific details or real-life analyses of a particular method". He analyzes quite a lot of PRNGs. He also includes a nice overview of common bugs found in PRNG implementations. Only two caveats: he doesn't analyze Yarrow (pact of non-aggression?), which I could understand in his original Usenix98 paper as it came out in 1998 (just as the paper on Yarrow), but his updated version also shies away from it; also, as you'll see from the design he proposes, his opinion on PRNGs is slightly unconventional. Very good stuff though.

John S. Denker's design for a High-Entropy Symbol Generator
I only recently found this paper (through Diceware.com I think) and hesitated a bit before including it in this section. But the design he proposes is different enough from the previous one's to warrant inclusion. He uses SHA on the output, but only to distill entropy as he doesn't maintain any internal state that could be compromised by inverting SHA. Interesting.

(In)famous Bugs

People seem to have a lot of trouble initializing PRNGs. As a matter of fact the following bug reports will probably convince you that bad seeds are the most frequent reason for security failures. That's why a good generator should include some entropy collection code: to avoid relying on user-supplied randomness. As an example see the RSA Bulletin Number 3 - January 25, 1996: Proper Initialization for the BSAFE Random Number Generator. The best overview of bugs found in PRNGs is in Gutman's Software Generation of Practically Strong Random Numbers.

Thomas Roessler: Catastrophic failure of Strip password generation.
A typical example: bad PRNG, bad seeds. Includes C source code that exploits the easy target.

PGP 2.6 (and 2.5) randpool.c bug
Includes a nice description of entropy estimation.

How We Learned to Cheat at Online Poker: A Study in Software Security (in PDF format).
The Software Security group at Reliable Software Technologies (now Cigital) wrote this interesting article on how they broke the (very weak) security build into an online poker game. Shows how you don't need to be a cryptanalyst working for the NSA to break most programs and how implementation bugs result in more spectacular exploits than any weakness in the algorithms used.

Security at Pokerstars
A company that read the previous article and what they've done about it.

Randomness and the Netscape Browser
Dr. Dobbs article on the infamous Netscape Browser security hole. David Wagner (one of the authors) created a web page with links to related resources on the Net.

Cracking traditional PRNGs

The brief summary of this section is as follows. Quoted from the online Sci.Crypt FAQ: 8.10. Can I use pseudo-random or chaotic numbers as a key stream?

"[...]Perhaps the simplest example is a linear congruential sequence, one of the most popular types of random number generators, where there is no obvious dependence between seeds and outputs. Unfortunately the graph of any such sequence will, in a high enough dimension, show up as a regular lattice. Mathematically this lattice corresponds to structure which is notoriously easy for cryptanalysts to exploit. More complicated generators have more complicated structure, which is why they make interesting pictures--- but a cryptographically strong sequence will have no computable structure at all."

Marsaglia, G. Random numbers fall mainly in the planes. Natl. Acad. Sci. Prec. 61 (Sept. 1968), 25-28.
This feature of linear congruential generators (hence known as Marsaglia Effect) depends heavily on the parameters you choose for the algorithm.

The Marsaglia Effect Java Applet
Understanding the Marsaglia Effect might not be easy for non-mathematically inclined readers. Just run this applet and you'll see it with your own eyes. Good stuff.

http://random.mat.sbg.ac.at/results/karl/server/server.html
In case the applet wasn't convincing enough, take a look at what they mean with regular lattice structure using some more computer graphics.

"Pseudo-Random" Number Generation within Cryptographic Algorithms: the DSS Case (1997).
This much cited article explains how a bad random number generator (i.e. LCRNG) can affect the security of the Digital Signature Standard. Written by Mihir Bellare, Shafi Goldwasser and Daniele Micciancio.

Some Usenet posts by Marsaglia and David Molnar on the Weakness of LCG style encryption.

Other important results in the history of LCRNGs can be found in the following papers:

Using stream ciphers

M.J.B. Robshaw in Stream Ciphers (1995) points out that any stream cipher working at 1 Mbyte/sec and with a 2^32 period will repeat itself after only 2^9 seconds (8.5 mins). This isn't acceptable for crytpographical purposes. He also says if you use DES in OFB mode, you need to use 64 bit feedback to get a 2^63 period.

Ross Anderson points out that two messages (M1 and M2) encrypted with the same stream K, have the following relations:

  1. M1+K=C1
  2. M2+K=C2
  3. this means C1-C2=M1-M2 and if the messages M1, M2 have sufficient redundancy they can be recovered (see the Venona project). That's why stream ciphers also use a seed that makes each stream unique.

Real World CPRNGs and code

Yarrow
Designed by members of the well known Counterpane Internet security company. An implementation is available from their web site, but it has a certain "unfinished work" feel to it. Still worth a look. The algorithm is described in Yarrow-160: Notes on the Design and Analysis of the Yarrow Cryptographic Pseudorandom Number Generator by J. Kelsey, B. Schneier, and N. Ferguson. Sixth Annual Workshop on Selected Areas in Cryptography, Springer Verlag, August 1999. As I said before, Yarrow is the design they came up with in order to avoid the problems described in Cryptanalytic Attacks on Pseudorandom Number Generators (1988) by John Kelsey, Bruce Schneier, David Wagner and Chris Hall.

Zero-Knowledge System's Yarrow Implementation
Haven't looked at it in detail, but seems to work on Win32 and UNIX.

EGADS: Entropy Gathering And Distribution System.
According to the authors (Kelsey and Viega) this entropy gathering daemon is based on the Tiny PRNG. Tiny itself is an evolution of Yarrow. As of today, the only description of the algorithm is John Viega's and Gary McGraw's Building Secure Software. A nice book that I also recommend, not only because of it's great coverage of random number generation.

Wei Dai's Crypto++.
This nice crypto library includes implementation of the ANSI X9.17 appendix C RNG and of PGP's RandPool. No entropy gathering code though.

librand
A random number package based on event interval variations, from Matt Blaze, Jack Lacy, and Don Mitchell. David Wagner's site also has an explanation of the algorithm by Matt Blaze himself. Originally written for UNIX, but includes an NT version.

Peter Gutmann's cryptlib
A very elaborate PRNG called "Continuously Seeded Pseudorandom Number Generator" (CSPRNG). The design is described in his Usenix98 paper.

The BeeCrypt crypto library.
Written by Bob Deblier of Virtual Unlimited, this library presents some interesting Win32 entropy gathering code base on Microsoft's waveform-audio input functions.

EGD: The Entropy Gathering Daemon
A user-space substitute for /dev/random, written in perl. UNIX.

PRNGD - Pseudo Random Number Generator Daemon
The author (Lutz Jänicke) says: "It offers an EGD compatible interface to obtain random data and is intended to be used as an entropy source to feed other software, especially software based on OpenSSL". Works on various UNIX systems.

Ocotillo: A Pseudo-Random Number Generator For Unix
"The Ocotillo PRNG is an attempt to create a cryptographically strong pseudo-random number generator for Unix implementations that do not have one".

The source code for Applied Cryptography.
The "offical" web page for the source code seems to be in Spain. As US export restrictions have changed lately, you can now also pay the author for it. Most of the code is now quite old (the book being published in 1996), but still interesting.

PRNG and Entropy Source Code at Wiretapped.net
Some useful source code in case you can't find it anywhere else. Includes egads and yarrow.

OpenSSL
The 0.9.6c version of the OpenSSL engine includes a random number generator.

Randomness source code @ funet.fi

Testing for Randomness

George Marsaglia's DIEHARD Test Suite.
I believe this one was everyone's favorite until the NIST suite made it's appearance. As as example see this RSA Bulletin that shows how they used Diehard to evaluate the BSAFE PRNG. As the original code was in Fortran and was automatically translated to C, there isn't a big chance of anybody actually figuring out what the code does. You'll just have to believe the documentation.
Marsaglia has also published several interesting articles:

The NIST Test Suite.
The Statistical Test Suite from the National Institute of Standards and Technology aims to be the suite to end all suites. Very comprehensive tests and with huge documentation (a over 200 page pdf file). The main problem is that the source code only run's on Solaris. I was able to hack the code to make it work on Windows, but can give no assurance that it actually works. The CSRC also has some good additional RNG resources.

ENT.
John Walker is the author of ENT: a Pseudorandom Number Sequence Test Program. ENT implements five simple tests.The main advantage is that it is fast, easy to run and to understand.

Ueli Maurer's Universal Test
Based on his publication A Universal Statistical Test for Random Bit Generators, Journal of Cryptology, vol. 5, no. 2, pp. 89-105, 1992. There is some controversy surrounding this test, in particular because of the misleading "Universal" in the title. From his paper I seem to understand that the parameter L means that the last L generated bits are used to determine what bit to generate next (he calls it memory). Most implementations of the test use L=8 as they use a table of size 2^L. This makes it hard to use the test for devices with 32 bit or more memory. I normally use David Honig's implementation. The source code for Applied Cryptography also includes a working implementation.

Bob Jenkins' Tests for Random Number Generators
As the author says "I've got my own suite of random number tests that I wrote before I was able to locate DIEHARD". He also has a nice web page on magnitudes that will help you realize just how big 2^512 is.

Robert Davies' Notes on random number generators
Very interesting article, where the author applies several statistical techniques to study the performance of various hardware RNGs, including the output of Marsaglia's random number CD.

Preliminary Analysis of the BSAFE 3.x Pseudorandom Number Generators.
RSA Bulletin Number 8 - September 3, 1998. Uses Marsaglia's Diehard test suite to analyze their own BSAFE PRNG. Shows how running the tests just once isn't enough.

Nick Szabo's The Abuse of Statistics in Cryptography
The author points out that using statistics to verify a PRNG is no substitute for analyzing the design. He's right and yet it would be silly not to make sure our PRNG passes the tests.

David W. Deley's Computer Generated Random Numbers
According to the author "This paper presents a number of techniques for analyzing a computer generated sequence of random numbers". I found sections 10 "How Good A Random Generator Do You Need?" and 11 "What Is A Random Number Generator?" particularly interesting. He briefly explains "zero-memory information sources and Markov information sources", which I found useful to understand Maurer's paper.

RandTest at SourceForge
Last time I looked it was still very much "work in progress".

Comscire's Select Bibliography of Random Number Generation, Analysis and Use
In case you want to read more.

Entropy and Uncertainty

Tom Schneider's Information Theory Primer.
Great way to get started. Short and easy to understand. Includes an appendix on logarithms as refresher. He also maintains a glossary for Molecular Information Theory that has some useful entries (i.e. bit or uncertainty). Also worth reading is his information.is.not.uncertainty and his I'm Confused: How Could Information Equal Entropy? Highly recommended, but don't get side-tracked by all the molecular biology stuff!

Claude Shannon's A mathematical theory of communication
First published in 1948 this paper is said to have started the whole field of Information Theory. This is the paper to read if you want to know what cryptographers mean by entropy. A quote from the article:

The choice of a logarithmic base corresponds to the choice of a unit for measuring information. If the base 2 is used the resulting units may be called binary digits, or more briefly bits, a word suggested by J. W. Tukey. A device with two stable positions, such as a relay or a flip-flop circuit, can store one bit of information. N such devices can store N bits, since the total number of possible states is 2N and log2 2N =N.

Other resources I haven't reviewed in detail:

Books

Bruce Schneier's Applied Cryptography
The ultimate cryptographic-algorithm reference book. Includes lot's of C source code and an impressing bibliography. Chapter 16 "Pseudo-Random-Sequence Generators and Stream Ciphers" discusses linear congruential generators, feedback shift registers and other stream generators. Chapter 17 "Other Stream Ciphers and Real Random-Sequence Generators" covers the basics of PRNGs including entropy estimation, gathering and distilling. The MD5 based entropy distilling source code in section 17.14 is quite influential.

Howard and LeBlanc's Writing Secure Code.
Although the book is quite general in scope, chapter 6 "Cryptographic Foibles" is entirely devoted to cryptography. Only around 6 pages are actually about random number generation. Still good coverage on using Microsoft's CryptGenRandom and some insight into how it might be implemented. Chapter 13 "Writing Secure .NET Code" briefly describes how to use the System.Security.Cryptography.RNGCryptoServiceProvider which is a .NET wrapper around Microsoft's CryptGenRandom API.

Building Secure Software: How to Avoid Security Problems the Right Way by John Viega, Gary McGraw.

Handbook of Applied Cryptography
Written by Menezes et al., Chapter 5 (Pseudorandom Bits and Sequences) is particularly relevant.

Foundations of Cryptography (Fragments of a Book), by Oded Goldreich.
Quite mathematical but contains some interesting proofs related to PRNGs.

Security Engineering
Ross Anderson's great book. Schneier says in the foreword "It's the first, and only, end-to-end modern security design and engineering book ever written." Regarding PRNGs I found the description of something called the "Random Oracle model" very useful.

Link farms

Randomness links at SecuritytechNet.com
Surprisingly good links to resources and papers related to cryptographic random numbers. I'd say this is the link farm that comes closest to ours. This might be a mirror.

Random Noise Sources from Diceware.com
Different focus than our page (more on HW sources), but similar in intent.

David Wagner's Randomness resources for crypto developers.
David Wagner wrote a nice article for Dr. Dobbs and maintains this link farm that includes links to source code and tests.

Peter Gutman's links on Random Numbers.
He is also the author of a very good crypto library and has published some papers on random number generation.

Terry Ritter's RandomnessLinks
His web page also includes copies of several related Usenet postings that are interesting to read. E.g. there is some discussion about how useful the Maurer test is.

Tom Dunigan's Random Number links

The Mandala Centre's Random number generation page

Standards

RFC 2828: Internet Security Glossary

FIPS PUB 140-1: Security Requirements For Cryptographic Modules

[...] provides a standard to be used by Federal organizations when these organizations specify that cryptographic-based security systems are to be used to provide protection for sensitive or valuable data.
Section "4.11.1 Power-Up Tests" includes some "Statistical random number generator tests". They are extremely simple to implement, e.g. The Monobit Test:
  1. Count the number of ones in the 20,000 bit stream. Denote this quantity by X.
  2. The test is passed if 9,654 < X < 10,346.
Greg Rose of Qualcomm has written a C implementation of the FIPS 140 tests. You can also find them here or here. FIPS 140-2 corrects some problems in the previous standard.

FIPS PUB 171: Key Management Using ANSI X9.17
"Specifies a particular selection of options for the automated distribution of keying material by the Federal Government when using the protocols of ANSI X9.17-1985. ANSI X9.17-1985 defines procedures for the manual and automated management of keying materials and utilizes the Data Encryption Standard to provide key management for a variety of operational environments."

FIPS PUB 181: Automated Password Generator
Describes an automated password generation algorithm based on the X9.17 PRNG. The on-line version doesn't include the C source code, but you can find a version that does in the source code for Applied Cryptography. For an real-life automated password generator using a very different approach take a look at the Diceware system.

FIPS PUB 112: Password Usage
The Appendix A "Password Usage Guidelines" includes some good information on how to decide on the construction, length and lifetime of passwords. Good if you want to learn how to be properly paranoid about passwords.

CSC-STD-002-85. Department of Defense. Password Management Guideline.
Similar in content to FIPS 112, Appendix A contains a simple PRNG based on DES in OFB mode that's somewhat similar to the X9.17 PRNG. Several appendixes show how to calculate the probability of password compromise, e.g. Appendix F "On the Probability of Guessing a Password". The guideline is also available here or here.

The ANSI X9.82 Random Number Generation Standard.
In June 1998, the American National Standards Institute (ANSI) X9F1 (Financial Services Industry) approved the creation of a standard addressing the needs for random number generation. Still in a state of flux.

The Intel Hardware RNG