From Wikipedia, the free encyclopedia
A cryptographically secure pseudorandom number
generator (CSPRNG) is a pseudorandom number generator (PRNG) with
properties that make it suitable for use in cryptography.
Many aspects of cryptography require random numbers, for
example:
The "quality" of the randomness required for these applications
varies. For example creating a nonce in some protocols needs only uniqueness.
On the other hand, generation of a master key
requires a higher quality, such as more entropy. And in the case of onetime pads, the informationtheoretic guarantee of
perfect secrecy only holds if the key material is obtained from a
true random source with high entropy.
Ideally, the generation of random numbers in CSPRNGs uses
entropy obtained from a high quality source, which might be a hardware random number
generator or perhaps unpredictable system processes —
though unexpected correlations have been found in several such
ostensibly independent processes. From an information theoretic
point of view, the amount of randomness, the entropy that can be
generated is equal to the entropy provided by the system. But
sometimes, in practical situations, more random numbers are needed
than there is entropy available. Also the processes to extract
randomness from a running system are slow in actual practice. In
such instances, a CSPRNG can sometimes be used. A CSPRNG can
"stretch" the available entropy over more bits.
When all the entropy we have is available before algorithm
execution begins, we really have a stream cipher. However some crypto system designs allow for the
addition of entropy during execution, in which case it is not a
stream cipher equivalent and cannot be used as one. Stream cipher
and CSPRNG design is thus closely related.
Requirements
The requirements of an ordinary PRNG are also satisfied by a
cryptographically secure PRNG, but the reverse is not true. CSPRNG
requirements fall into two groups: first, that they pass
statistical randomness tests; and secondly, that they hold up well
under serious attack, even when part of their initial or running
state becomes available to an attacker.
 Every CSPRNG should satisfy the "nextbit test". The nextbit
test is as follows: Given the first k bits of a random
sequence, there is no polynomialtime algorithm that can predict
the (k+1)th bit with probability of success better than
50%. Andrew Yao proved
in 1982 that a generator passing the nextbit test will pass all
other polynomialtime statistical tests for randomness.
 Every CSPRNG should withstand 'state compromise extensions'. In
the event that part or all of its state has been revealed (or
guessed correctly), it should be impossible to reconstruct the
stream of random numbers prior to the revelation. Additionally, if
there is an entropy input while running, it should be infeasible to
use knowledge of the input's state to predict future conditions of
the CSPRNG state.

 Example: If the CSPRNG under consideration produces output by
computing bits of π in sequence,
starting from some unknown point in the binary expansion, it may
well satisfy the nextbit test and thus be statistically random, as
π appears to be a random sequence. (This would be guaranteed if π
is a normal
number, for example.) However, this algorithm is not
cryptographically secure; an attacker who determines which bit of
pi (i.e. the state of the algorithm) is currently in use will be
able to calculate all preceding bits as well.
Most PRNGs are not suitable for use as CSPRNGs and will fail on
both counts. First, while most PRNGs outputs appear random to
assorted statistical tests, they do not resist determined reverse
engineering. Specialized statistical tests may be found specially
tuned to such a PRNG that shows the random numbers not to be truly
random. Second, for most PRNGs, when their state has been revealed,
all past random numbers can be retrodicted, allowing an attacker to
read all past messages, as well as future ones.
CSPRNGs are designed explicitly to resist this type of cryptanalysis.
Some
background
Santha and Vazirani proved that several bit streams with weak
randomness can be combined to produce a higherquality quasirandom
bit stream.^{[1]}
Even earlier, John von Neumann proved that a simple
algorithm can remove a considerable amount of the bias in any bit
stream^{[2]}
which should be applied to each bit stream before using any
variation of the SanthaVazirani design. The field is termed
entropy extraction and is the subject of active research
(e.g., N Nisan, S
Safra, R Shaltiel, A TaShma, C Umans, D Zuckerman).
Designs
In the discussion below, CSPRNG designs are divided into three
classes: 1) those based on cryptographic primitives such as ciphers and cryptographic hashes, 2) those based upon
mathematical problems thought to be hard, and 3) specialpurpose
designs. The last often introduce additional entropy when available
and, strictly speaking, are not "pure" pseudorandom number
generators, as their output is not completely determined by their
initial state. This addition can prevent attacks even if the
initial state is compromised.
Designs based on
cryptographic primitives
 A secure block
cipher can be converted into a CSPRNG by running it in counter mode. This is
done by choosing a random key and encrypting a zero, then
encrypting a 1, then encrypting a 2, etc. The counter can also be
started at an arbitrary number other than zero. Obviously, the
period will be 2^{n} for an nbit block
cipher; equally obviously, the initial values (ie, key and
"plaintext") must not
become known to an attacker lest, however good this CSPRNG
construction might be otherwise, all security be lost.
 A cryptographically secure hash of a counter might
also act as a good CSPRNG in some cases. In this case also, it is
necessary that the initial value of this counter is random and
secret. If the counter is a bignum, then the CSPRNG could have an
infinite period. However, there has been little study of these
algorithms for use in this manner, and at least some authors warn
against this use (Young and Yung, Malicious Cryptography, Wiley,
2004, sect 3.2).
 Most stream
ciphers work by generating a pseudorandom stream of bits that
are combined (almost always XORed) with the plaintext; running the cipher on a counter
will return a new pseudorandom stream, possibly with a longer
period. The cipher is only secure if the original stream is a good
CSPRNG (this is not always the case: see RC4 cipher). Again, the
initial state must be kept secret.
Number
theoretic designs
 The Blum Blum
Shub PRNG algorithm has a strong, though conditional, security
proof, based on the presumed difficulty of integer
factorization. However, implementations are slow compared to
some other designs.
Special
designs
There are a number of practical PRNGs that have been designed to
be cryptographically secure, including
 the Yarrow
algorithm which attempts to evaluate the entropic quality of
its inputs, and an updated version, Fortuna, which does not. Yarrow is used
in FreeBSD, OpenBSD and Mac OS X (also as /dev/random)
 the UNIX special file /dev/random, particularly the /dev/urandom
variant as implemented on Linux.
 the function CryptGenRandom provided in Microsoft's Cryptographic Application Programming
Interface
 the Python function
urandom in the os module, which uses /dev/urandom
on Unixbased systems, including OS X, and CryptGenRandom on
Windowsbased systems.[1]
 ISAAC
based on a variant of the RC4 cipher
 ANSI X9.17
standard (Financial Institution Key Management
(wholesale)), which has been adopted as a FIPS standard
as well. It takes as input a 64 bit random seed s, and a
TDEA (keying option 2) key
bundle k.^{[3]} Each
time a random number is required it:
 computes I = TDEA_{k}(D),
where D is the current date/time information (in the
maximum resolution available),
 outputs x = TDEA_{k}(I ⊕
s)
 updates the seed s to
TDEA_{k}(x ⊕ I), where ⊕ denotes
bitwise exclusive
or.
 It has been suggested that the X9.17 algorithm would be
improved by using AES instead of TDEA (Young
and Yung, op cit, sect 3.5.1).
Standards
Several CSPRNGs have been standardized. For example,
 FIPS 1862
 NIST SP 80090:
Hash_DRBG, HMAC_DRBG, CTR_DRBG and Dual EC DRBG.
 ANSI X9.171985 Appendix C
 ANSI X9.311998 Appendix A.2.4
 ANSI X9.621998 Annex A.4, obsoleted by ANSI X9.622005, Annex
D (HMAC_DRBG)
A good reference is maintained by
NIST.
There are also standards for statistical testing of new CSPRNG
designs:
References
External
links
 RFC 4086, Randomness
Requirements for Security
 Java "entropy pool" for cryptographicallysecure
unpredictable random numbers.
 Java standard class providing
a cryptographically strong pseudorandom number generator
(PRNG).
 Cryptographically Secure
Random number on Windows without using CryptoAPI
 Conjectured Security of the ANSINIST Elliptic Curve
RNG, Daniel R. L. Brown, IACR ePrint 2006/117.
 A Security Analysis of the NIST SP 80090 Elliptic
Curve Random Number Generator, Daniel R. L. Brown and Kristian
Gjosteen, IACR ePrint 2007/048. To appear in CRYPTO 2007.
 Cryptanalysis of the Dual Elliptic Curve
Pseudorandom Generator, Berry Schoenmakers and Andrey
Sidorenko, IACR ePrint 2006/190.
 Efficient Pseudorandom Generators Based on the DDH
Assumption, Reza Rezaeian Farashahi and Berry Schoenmakers and
Andrey Sidorenko, IACR ePrint 2006/321.
 Analysis of the Linux Random
Number Generator, Zvi Gutterman and Benny Pinkas and Tzachy
Reinman.
 An implementation of a
cryptographically safe shrinking pseudorandom number
generator.