| Ernesto Guisado's Website » Cryptographic Random Numbers | Articles | Miscellanea | |
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!
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."
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.
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.
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:
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:
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
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.
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:
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.
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
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:
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.