Cryptographically secure pseudorandom number generator
this wiki
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:
 Key generation
 Nonces
 Onetime pads
 Salts in certain signature schemes, including ECDSA, RSASSAPSS.
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.
RequirementsEdit
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 backgroundEdit
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).
DesignsEdit
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 primitivesEdit
 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. However, there has been little study of these algorithms for use in this manner, and at least some authors warn against this use^{[3]}.
 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 designsEdit
 The Blum Blum Shub 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.
 The BlumMicali algorithm has a security proof based on the difficulty of the discrete logarithm problem.
Special designsEdit
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. Yarrow is used in FreeBSD, OpenBSD and Mac OS X (also as /dev/random)
 the Fortuna algorithm, the successor to Yarrow, which does not attempt to evaluate the entropic quality of its inputs.
 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.^{[4]} 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).
StandardsEdit
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:
 A Statistical Test Suite for Random and Pseudorandom Number Generators, NIST Special Publication 80022.
ReferencesEdit
External linksEdit
 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.

es:Generador de números pseudoaleatorios criptográficamente seguro he:מחולל פסבדו אקראי קריפטוגרפי ja:暗号論的擬似乱数生成器 pt:CSPRNG