A cryptographically secure pseudorandom number generator (CSPRNG) or cryptographic pseudorandom number generator (CPRNG) is a
pseudorandom number generator
A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generate ...
(PRNG) with properties that make it suitable for use in
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
. It is also loosely known as a cryptographic random number generator (CRNG) (see
Random number generation § "True" vs. pseudo-random numbers).
Most
cryptographic applications require
random
In common usage, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence of events, symbols or steps often has no :wikt:order, order and does not follow an intelligible pattern or combination. Ind ...
numbers, for example:
*
key generation
Key generation is the process of generating keys in cryptography. A key is used to encrypt and decrypt whatever data is being encrypted/decrypted.
A device or program used to generate keys is called a key generator or keygen.
Generation in crypto ...
*
nonces
*
salts
In chemistry, a salt is a chemical compound consisting of an ionic assembly of positively charged cations and negatively charged anions, which results in a compound with no net electric charge. A common example is table salt, with positively cha ...
in certain signature schemes, including
ECDSA
In cryptography, the Elliptic Curve Digital Signature Algorithm (ECDSA) offers a variant of the Digital Signature Algorithm (DSA) which uses elliptic-curve cryptography.
Key and signature-size
As with elliptic-curve cryptography in general, the b ...
,
RSASSA-PSS
The "quality" of the randomness required for these applications varies.
For example, creating a
nonce in some
protocols
Protocol may refer to:
Sociology and politics
* Protocol (politics), a formal agreement between nation states
* Protocol (diplomacy), the etiquette of diplomacy and affairs of state
* Etiquette, a code of personal behavior
Science and technology
...
needs only uniqueness.
On the other hand, the generation of a master
key
Key or The Key may refer to:
Common meanings
* Key (cryptography), a piece of information that controls the operation of a cryptography algorithm
* Key (lock), device used to control access to places or facilities restricted by a lock
* Key (map ...
requires a higher quality, such as more
entropy
Entropy is a scientific concept, as well as a measurable physical property, that is most commonly associated with a state of disorder, randomness, or uncertainty. The term and the concept are used in diverse fields, from classical thermodynam ...
. And in the case of
one-time pad
In cryptography, the one-time pad (OTP) is an encryption technique that cannot be cracked, but requires the use of a single-use pre-shared key that is not smaller than the message being sent. In this technique, a plaintext is paired with a ran ...
s, the
information-theoretic
Information theory is the scientific study of the quantification, storage, and communication of information. The field was originally established by the works of Harry Nyquist and Ralph Hartley, in the 1920s, and Claude Shannon in the 1940s. T ...
guarantee of perfect secrecy only holds if the key material comes from a true random source with high entropy, and thus any kind of pseudorandom number generator is insufficient.
Ideally, the generation of random numbers in CSPRNGs uses entropy obtained from a high-quality source, generally the operating system's randomness
API
An application programming interface (API) is a way for two or more computer programs to communicate with each other. It is a type of software Interface (computing), interface, offering a service to other pieces of software. A document or standa ...
. However, 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.
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
A randomness test (or test for randomness), in data evaluation, is a test used to analyze the distribution of a set of data to see if it can be described as random (patternless). In stochastic modeling, as in some computer simulations, the hoped- ...
; 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
next-bit test
In cryptography and the theory of computation, the next-bit testAndrew Chi-Chih YaoTheory and applications of trapdoor functions In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, 1982. is a test against pseudo-random n ...
. That is, given the first
k bits of a random sequence, there is no
polynomial-time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
algorithm that can predict the (
k+1)th bit with probability of success non-negligibly better than 50%.
Andrew Yao
Andrew Chi-Chih Yao (; born December 24, 1946) is a Chinese computer scientist and computational theorist. He is currently a professor and the dean of Institute for Interdisciplinary Information Sciences (IIIS) at Tsinghua University. Yao use ...
proved in 1982 that a generator passing the next-bit test will pass all other polynomial-time statistical tests for randomness.
Andrew Chi-Chih Yao
Andrew Chi-Chih Yao (; born December 24, 1946) is a Chinese computer scientist and computational theorist. He is currently a professor and the dean of Institute for Interdisciplinary Information Sciences (IIIS) at Tsinghua University. Yao us ...
Theory and applications of trapdoor functions
In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, 1982.
*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 next-bit test and thus be statistically random, as π appears to be a random sequence. (This would be guaranteed if π is a
normal number
In mathematics, a real number is said to be simply normal in an integer base b if its infinite sequence of digits is distributed uniformly in the sense that each of the b digit values has the same natural density 1/b. A number is said to b ...
, 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
Cryptanalysis (from the Greek ''kryptós'', "hidden", and ''analýein'', "to analyze") refers to the process of analyzing information systems in order to understand hidden aspects of the systems. Cryptanalysis is used to breach cryptographic sec ...
.
Definitions
In the
asymptotic setting, a family of deterministic polynomial time computable functions
for some polynomial , is a pseudorandom number generator (PRNG, or PRG in some references), if it stretches the length of its input (
for any ), and if its output is
computationally indistinguishable
In Analysis of algorithms, computational complexity and cryptography, two families of distributions are computationally indistinguishable if no efficient algorithm can tell the difference between them except with negligible probability.
Formal def ...
from true randomness, i.e. for any probabilistic polynomial time algorithm , which outputs 1 or 0 as a distinguisher,
:
for some
negligible function In mathematics, a negligible function is a function \mu:\mathbb\to\mathbb such that for every positive integer ''c'' there exists an integer ''N'c'' such that for all ''x'' > ''N'c'',
:, \mu(x), 0 such that for all ''x'' ...
. (The notation
means that is chosen
uniformly
Uniform distribution may refer to:
* Continuous uniform distribution
* Discrete uniform distribution
* Uniform distribution (ecology)
* Equidistributed sequence In mathematics, a sequence (''s''1, ''s''2, ''s''3, ...) of real numbers is said to be ...
at random from the set .)
There is an equivalent characterization: For any function family
, is a PRNG if and only if the next output bit of cannot be predicted by a polynomial time algorithm.
A forward-secure PRNG with block length
is a PRNG
, where the input string
with length is the current state at period , and the output (
,
) consists of the next state
and the pseudorandom output block
of period , that withstands state compromise extensions in the following sense. If the initial state
is chosen uniformly at random from
, then for any , the sequence
must be computationally indistinguishable from
, in which the
are chosen uniformly at random from
.
Any PRNG
can be turned into a forward secure PRNG with block length
by splitting its output into the next state and the actual output. This is done by setting
, in which
and
; then is a forward secure PRNG with
as the next state and
as the pseudorandom output block of the current period.
Entropy extraction
Santha and Vazirani proved that several bit streams with weak randomness can be combined to produce a higher-quality quasi-random bit stream.
[
]
Even earlier,
John von Neumann
John von Neumann (; hu, Neumann János Lajos, ; December 28, 1903 – February 8, 1957) was a Hungarian-American mathematician, physicist, computer scientist, engineer and polymath. He was regarded as having perhaps the widest cove ...
proved that a
simple algorithm In computational fluid dynamics (CFD), the SIMPLE algorithm is a widely used numerical procedure to solve the Navier–Stokes equations. ''SIMPLE'' is an acronym for Semi-Implicit Method for Pressure Linked Equations.
The SIMPLE algorithm was dev ...
can remove a considerable amount of the bias in any bit stream,
[
] which should be applied to each bit stream before using any variation of the Santha–Vazirani design.
Designs
In the discussion below, CSPRNG designs are divided into three classes:
# those based on cryptographic primitives such as
cipher
In cryptography, a cipher (or cypher) is an algorithm for performing encryption or decryption—a series of well-defined steps that can be followed as a procedure. An alternative, less common term is ''encipherment''. To encipher or encode i ...
s and
cryptographic hash
A cryptographic hash function (CHF) is a hash algorithm (a map of an arbitrary binary string to a binary string with fixed size of n bits) that has special properties desirable for cryptography:
* the probability of a particular n-bit output re ...
es,
# those based upon mathematical problems thought to be hard, and
# special-purpose designs.
The last often introduces 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
In cryptography, a block cipher is a deterministic algorithm operating on fixed-length groups of bits, called ''blocks''. Block ciphers are specified cryptographic primitive, elementary components in the design of many cryptographic protocols and ...
can be converted into a CSPRNG by running it in
counter mode
In cryptography, a block cipher mode of operation is an algorithm that uses a block cipher to provide information security such as confidentiality or authenticity.
A block cipher by itself is only suitable for the secure cryptographic transforma ...
. This is done by choosing a
random
In common usage, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence of events, symbols or steps often has no :wikt:order, order and does not follow an intelligible pattern or combination. Ind ...
key and encrypting a 0, then encrypting a 1, then encrypting a 2, etc. The counter can also be started at an arbitrary number other than zero. Assuming an ''n''-bit block cipher the output can be distinguished from random data after around 2
''n''/2 blocks since, following the
birthday problem
In probability theory, the birthday problem asks for the probability that, in a set of randomly chosen people, at least two will share a birthday. The birthday paradox is that, counterintuitively, the probability of a shared birthday exceeds 5 ...
, colliding blocks should become likely at that point, whereas a block cipher in CTR mode will never output identical blocks. For 64-bit block ciphers this limits the safe output size to a few gigabytes, with 128-bit blocks the limitation is large enough not to impact typical applications. However, when used alone it does not meet all of the criteria of a CSPRNG (as stated above) since it is not strong against "state compromise extensions": with knowledge of the state (in this case a counter and a key) you can predict all past output.
* A cryptographically secure
hash of a counter might also act as a good CSPRNG in some cases. In this case, it is also 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.
[
]
* Most
stream cipher
stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream ...
s work by generating a pseudorandom stream of bits that are combined (almost always
XOR
Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false).
It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
ed) with the
plaintext
In cryptography, plaintext usually means unencrypted information pending input into cryptographic algorithms, usually encryption algorithms. This usually refers to data that is transmitted or stored unencrypted.
Overview
With the advent of comp ...
; running the cipher on a counter will return a new pseudorandom stream, possibly with a longer period. The cipher can only be secure if the original stream is a good CSPRNG, although this is not necessarily the case (see the
RC4 cipher
In cryptography, RC4 (Rivest Cipher 4, also known as ARC4 or ARCFOUR, meaning Alleged RC4, see below) is a stream cipher. While it is remarkable for its simplicity and speed in software, multiple vulnerabilities have been discovered in RC4, ren ...
). Again, the initial state must be kept secret.
Number-theoretic designs
* The
Blum Blum Shub
Blum Blum Shub (B.B.S.) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub that is derived from Michael O. Rabin's one-way function.
__TOC__
Blum Blum Shub takes the form
:x_ = x_n^2 \bmod M,
where ' ...
algorithm has a security proof based on the difficulty of the
quadratic residuosity problem The quadratic residuosity problem (QRP) in computational number theory is to decide, given integers a and N, whether a is a quadratic residue modulo N or not.
Here N = p_1 p_2 for two unknown primes p_1 and p_2, and a is among the numbers which are ...
. Since the only known way to solve that problem is to factor the modulus, it is generally regarded that the difficulty of
integer factorization
In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization.
When the numbers are suf ...
provides a conditional security proof for the Blum Blum Shub algorithm. However the algorithm is very inefficient and therefore impractical unless extreme security is needed.
* The
Blum–Micali algorithm The Blum–Micali algorithm is a cryptographically secure pseudorandom number generator. The algorithm gets its security from the difficulty of computing discrete logarithms.Bruce Schneier, ''Applied Cryptography: Protocols, Algorithms, and Source ...
has a security proof based on the difficulty of the
discrete logarithm problem
In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log''b'' ...
but is also very inefficient.
* Daniel Brown of
Certicom
BlackBerry Limited is a Canadian software company specializing in cybersecurity. Founded in 1984, it was originally known as Research In Motion (RIM). As RIM, it developed the BlackBerry brand of interactive pagers, smartphones, and tablets ...
has written a 2006 security proof for
Dual_EC_DRBG
Dual_EC_DRBG (Dual Elliptic Curve Deterministic Random Bit Generator) is an algorithm that was presented as a cryptographically secure pseudorandom number generator (CSPRNG) using methods in elliptic curve cryptography. Despite wide public criti ...
, based on the assumed hardness of the ''
Decisional Diffie–Hellman assumption The decisional Diffie–Hellman (DDH) assumption is a computational hardness assumption about a certain problem involving discrete logarithms in cyclic groups. It is used as the basis to prove the security of many cryptographic protocols, most notab ...
'', the ''x-logarithm problem'', and the ''truncated point problem''. The 2006 proof explicitly assumes a lower ''outlen'' than in the Dual_EC_DRBG standard, and that the P and Q in the Dual_EC_DRBG standard (which were revealed in 2013 to be probably backdoored by NSA) are replaced with non-backdoored values.
Special designs
There are a number of practical PRNGs that have been designed to be cryptographically secure, including
*the
Yarrow algorithm
The Yarrow algorithm is a family of cryptographic pseudorandom number generators (CPRNG) devised by John Kelsey, Bruce Schneier, and Niels Ferguson and published in 1999. The Yarrow algorithm is explicitly unpatented, royalty-free, and open sour ...
which attempts to evaluate the entropic quality of its inputs. Yarrow is used in
macOS
macOS (; previously OS X and originally Mac OS X) is a Unix operating system developed and marketed by Apple Inc. since 2001. It is the primary operating system for Apple's Mac computers. Within the market of desktop and lapt ...
and other Apple OS' up until about Dec. 2019. Apple has switched to Fortuna since then. (See
/dev/random).
*the
ChaCha20
Salsa20 and the closely related ChaCha are stream ciphers developed by Daniel J. Bernstein. Salsa20, the original cipher, was designed in 2005, then later submitted to the eSTREAM European Union cryptographic validation process by Bernstein. Ch ...
algorithm replaced
RC4
In cryptography, RC4 (Rivest Cipher 4, also known as ARC4 or ARCFOUR, meaning Alleged RC4, see below) is a stream cipher. While it is remarkable for its simplicity and speed in software, multiple vulnerabilities have been discovered in RC4, ren ...
in
OpenBSD
OpenBSD is a security-focused, free and open-source, Unix-like operating system based on the Berkeley Software Distribution (BSD). Theo de Raadt created OpenBSD in 1995 by forking NetBSD 1.0. According to the website, the OpenBSD project em ...
(version 5.4),
NetBSD
NetBSD is a free and open-source Unix operating system based on the Berkeley Software Distribution (BSD). It was the first open-source BSD descendant officially released after 386BSD was forked. It continues to be actively developed and is a ...
(version 7.0), and
FreeBSD
FreeBSD is a free and open-source Unix-like operating system descended from the Berkeley Software Distribution (BSD), which was based on Research Unix. The first version of FreeBSD was released in 1993. In 2005, FreeBSD was the most popular ...
(version 12.0).
*ChaCha20 also replaced
SHA-1
In cryptography, SHA-1 (Secure Hash Algorithm 1) is a cryptographically broken but still widely used hash function which takes an input and produces a 160-bit (20-byte) hash value known as a message digest – typically rendered as 40 hexadecima ...
in
Linux
Linux ( or ) is a family of open-source Unix-like operating systems based on the Linux kernel, an operating system kernel first released on September 17, 1991, by Linus Torvalds. Linux is typically packaged as a Linux distribution, which ...
in version 4.8.
*the
Fortuna algorithm, the successor to Yarrow, which does not attempt to evaluate the entropic quality of its inputs. Fortuna is used in FreeBSD. Apple changed to Fortuna for most or all Apple OS' beginning around Dec. 2019.
*the function
CryptGenRandom
CryptGenRandom is a deprecated cryptographically secure pseudorandom number generator function that is included in Microsoft CryptoAPI. In Win32 programs, Microsoft recommends its use anywhere random number generation is needed. A 2007 paper from ...
provided in
Microsoft
Microsoft Corporation is an American multinational technology corporation producing computer software, consumer electronics, personal computers, and related services headquartered at the Microsoft Redmond campus located in Redmond, Washing ...
's
Cryptographic Application Programming Interface
The Microsoft Windows platform specific Cryptographic Application Programming Interface (also known variously as CryptoAPI, Microsoft Cryptography API, MS-CAPI or simply CAPI) is an application programming interface included with Microsoft Windows ...
*
ISAAC
Isaac; grc, Ἰσαάκ, Isaák; ar, إسحٰق/إسحاق, Isḥāq; am, ይስሐቅ is one of the three patriarchs of the Israelites and an important figure in the Abrahamic religions, including Judaism, Christianity, and Islam. He was the ...
based on a variant of the
RC4
In cryptography, RC4 (Rivest Cipher 4, also known as ARC4 or ARCFOUR, meaning Alleged RC4, see below) is a stream cipher. While it is remarkable for its simplicity and speed in software, multiple vulnerabilities have been discovered in RC4, ren ...
cipher
*
Linear-feedback shift register
In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state.
The most commonly used linear function of single bits is exclusive-or (XOR). Thus, an LFSR is most often a sh ...
tuned with
evolutionary algorithm
In computational intelligence (CI), an evolutionary algorithm (EA) is a subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. An EA uses mechanisms inspired by biological evolution, such as reproduc ...
based on the
NIST
The National Institute of Standards and Technology (NIST) is an agency of the United States Department of Commerce whose mission is to promote American innovation and industrial competitiveness. NIST's activities are organized into physical sci ...
Statistical Test Suite.
*
arc4random
In cryptography, RC4 (Rivest Cipher 4, also known as ARC4 or ARCFOUR, meaning Alleged RC4, see below) is a stream cipher. While it is remarkable for its simplicity and speed in software, multiple vulnerabilities have been discovered in RC4, ren ...
*
AES-
CTR DRBG is often used as a random number generator in systems that use AES encryption.
*
ANSI
The American National Standards Institute (ANSI ) is a private non-profit organization that oversees the development of voluntary consensus standards for products, services, processes, systems, and personnel in the United States. The organi ...
X9.17 standard (''Financial Institution Key Management (wholesale)''), which has been adopted as a
FIPS standard as well. It takes as input a
TDEA (
keying option 2) key bundle ''k'' and (the initial value of) a 64-bit
random seed
A random seed (or seed state, or just seed) is a number (or vector) used to initialize a pseudorandom number generator.
For a seed to be used in a pseudorandom number generator, it does not need to be random. Because of the nature of number gene ...
''s''. Each time a random number is required it:
** Obtains the current date/time ''D'' to the maximum resolution possible.
** Computes a temporary value
** Computes the random value , where ⊕ denotes bitwise
exclusive or
Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false).
It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
.
** Updates the seed
:Obviously, the technique is easily generalized to any block cipher;
AES has been suggested.
[
]
Standards
Several CSPRNGs have been standardized. For example,
FIPS 186-4*
NIST SP 800-90A NIST SP 800-90A ("SP" stands for "''special publication''") is a publication by the National Institute of Standards and Technology with the title ''Recommendation for Random Number Generation Using Deterministic Random Bit Generators''. The publicat ...
:
:This withdrawn standard has four PRNGs. Two of them are uncontroversial and proven: CSPRNGs named Hash_DRBG and HMAC_DRBG.
:The third PRNG in this standard,
CTR DRBG NIST SP 800-90A ("SP" stands for "''special publication''") is a publication by the National Institute of Standards and Technology with the title ''Recommendation for Random Number Generation Using Deterministic Random Bit Generators''. The publicat ...
, is based on a
block cipher
In cryptography, a block cipher is a deterministic algorithm operating on fixed-length groups of bits, called ''blocks''. Block ciphers are specified cryptographic primitive, elementary components in the design of many cryptographic protocols and ...
running in
counter mode
In cryptography, a block cipher mode of operation is an algorithm that uses a block cipher to provide information security such as confidentiality or authenticity.
A block cipher by itself is only suitable for the secure cryptographic transforma ...
. It has an uncontroversial design but has been proven to be weaker in terms of distinguishing attack, than the
security level
In cryptography, security level is a measure of the strength that a cryptographic primitive — such as a cipher or hash function — achieves. Security level is usually expressed as a number of "bits of security" (also security strength ...
of the underlying block cipher when the number of bits output from this PRNG is greater than two to the power of the underlying block cipher's block size in bits.
:When the maximum number of bits output from this PRNG is equal to the 2
blocksize, the resulting output delivers the mathematically expected security level that the key size would be expected to generate, but the output is shown to not be indistinguishable from a true random number generator.
When the maximum number of bits output from this PRNG is less than it, the expected security level is delivered and the output appears to be indistinguishable from a true random number generator.
:It is noted in the next revision that claimed
security strength
In cryptography, security level is a measure of the strength that a cryptographic primitive — such as a cipher or hash function — achieves. Security level is usually expressed as a number of "bits of security" (also security strength) ...
for CTR_DRBG depends on limiting the total number of generate requests and the bits provided per generate request.
:The fourth and final PRNG in this standard is named
Dual_EC_DRBG
Dual_EC_DRBG (Dual Elliptic Curve Deterministic Random Bit Generator) is an algorithm that was presented as a cryptographically secure pseudorandom number generator (CSPRNG) using methods in elliptic curve cryptography. Despite wide public criti ...
. It has been shown to not be cryptographically secure and is believed to have a
kleptographic
Kleptography is the study of stealing information securely and subliminally. The term was introduced by Adam Young and Moti Yung in the Proceedings of Advances in Cryptology—Crypto '96.A. Young, M. Yung, "The Dark Side of Black-Box Cryptography, ...
NSA backdoor.
* NIST SP 800-90A Rev.1: This is essentially NIST SP 800-90A with Dual_EC_DRBG removed, and is the withdrawn standard's replacement.
* ANSI X9.17-1985 Appendix C
* ANSI X9.31-1998 Appendix A.2.4
* ANSI X9.62-1998 Annex A.4, obsoleted by ANSI X9.62-2005, Annex D (HMAC_DRBG)
A goo
referenceis maintained by
NIST
The National Institute of Standards and Technology (NIST) is an agency of the United States Department of Commerce whose mission is to promote American innovation and industrial competitiveness. NIST's activities are organized into physical sci ...
.
There are also standards for statistical testing of new CSPRNG designs:
* ''A Statistical Test Suite for Random and Pseudorandom Number Generators''
NIST Special Publication 800-22
NSA kleptographic backdoor in the Dual_EC_DRBG PRNG
''
The Guardian
''The Guardian'' is a British daily newspaper. It was founded in 1821 as ''The Manchester Guardian'', and changed its name in 1959. Along with its sister papers ''The Observer'' and ''The Guardian Weekly'', ''The Guardian'' is part of the Gu ...
'' and ''
The New York Times
''The New York Times'' (''the Times'', ''NYT'', or the Gray Lady) is a daily newspaper based in New York City with a worldwide readership reported in 2020 to comprise a declining 840,000 paid print subscribers, and a growing 6 million paid ...
'' have reported in 2013 that the
National Security Agency
The National Security Agency (NSA) is a national-level intelligence agency of the United States Department of Defense, under the authority of the Director of National Intelligence (DNI). The NSA is responsible for global monitoring, collecti ...
(NSA) inserted a
backdoor
A back door is a door in the rear of a building. Back door may also refer to:
Arts and media
* Back Door (jazz trio), a British group
* Porta dos Fundos (literally “Back Door” in Portuguese) Brazilian comedy YouTube channel.
* Works so title ...
into a
pseudorandom number generator
A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generate ...
(PRNG) of
NIST SP 800-90A NIST SP 800-90A ("SP" stands for "''special publication''") is a publication by the National Institute of Standards and Technology with the title ''Recommendation for Random Number Generation Using Deterministic Random Bit Generators''. The publicat ...
which allows the NSA to readily decrypt material that was encrypted with the aid of
Dual_EC_DRBG
Dual_EC_DRBG (Dual Elliptic Curve Deterministic Random Bit Generator) is an algorithm that was presented as a cryptographically secure pseudorandom number generator (CSPRNG) using methods in elliptic curve cryptography. Despite wide public criti ...
. Both papers report
that, as independent security experts long suspected, the NSA has been introducing weaknesses into CSPRNG standard 800-90; this being confirmed for the first time by one of the top secret documents leaked to the Guardian by
Edward Snowden
Edward Joseph Snowden (born June 21, 1983) is an American and naturalized Russian former computer intelligence consultant who leaked highly classified information from the National Security Agency (NSA) in 2013, when he was an employee and su ...
. The NSA worked covertly to get its own version of the NIST draft security standard approved for worldwide use in 2006. The leaked document states that "eventually, NSA became the sole editor." In spite of the known potential for a
kleptographic
Kleptography is the study of stealing information securely and subliminally. The term was introduced by Adam Young and Moti Yung in the Proceedings of Advances in Cryptology—Crypto '96.A. Young, M. Yung, "The Dark Side of Black-Box Cryptography, ...
backdoor and other known significant deficiencies with Dual_EC_DRBG, several companies such as
RSA Security
RSA Security LLC, formerly RSA Security, Inc. and doing business as RSA, is an American computer and network security company with a focus on encryption and encryption standards. RSA was named after the initials of its co-founders, Ron Rivest, ...
continued using Dual_EC_DRBG until the backdoor was confirmed in 2013.
RSA Security
RSA Security LLC, formerly RSA Security, Inc. and doing business as RSA, is an American computer and network security company with a focus on encryption and encryption standards. RSA was named after the initials of its co-founders, Ron Rivest, ...
received a $10 million payment from the NSA to do so.
Security flaws
DUHK attack
On October 23, 2017,
Shaanan Cohney,
Matthew Green, and
Nadia Heninger
Nadia Heninger (born 1982) is an American cryptographer, computer security expert, and computational number theorist at the University of California, San Diego.
Contributions
Heninger is known for her work on freezing powered-down security devic ...
,
cryptographer
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
s at The
University of Pennsylvania
The University of Pennsylvania (also known as Penn or UPenn) is a private research university in Philadelphia. It is the fourth-oldest institution of higher education in the United States and is ranked among the highest-regarded universitie ...
and
Johns Hopkins University
Johns Hopkins University (Johns Hopkins, Hopkins, or JHU) is a private university, private research university in Baltimore, Maryland. Founded in 1876, Johns Hopkins is the oldest research university in the United States and in the western hem ...
released details of the DUHK (Don't Use Hard-coded Keys) attack on
WPA2
Wi-Fi Protected Access (WPA), Wi-Fi Protected Access II (WPA2), and Wi-Fi Protected Access 3 (WPA3) are the three security and security certification programs developed after 2000 by the Wi-Fi Alliance to secure wireless computer networks. The All ...
where hardware vendors use a hardcoded seed key for the ANSI X9.31 RNG algorithm, stating "an attacker can brute-force encrypted data to discover the rest of the encryption parameters and deduce the master encryption key used to encrypt web sessions or
virtual private network
A virtual private network (VPN) extends a private network across a public network and enables users to send and receive data across shared or public networks as if their computing devices were directly connected to the private network. The be ...
(VPN) connections."
Japanese PURPLE cipher machine
During
World War II
World War II or the Second World War, often abbreviated as WWII or WW2, was a world war that lasted from 1939 to 1945. It involved the vast majority of the world's countries—including all of the great powers—forming two opposin ...
, Japan used a cipher machine for diplomatic communications; the United States was able to
crack it and read its messages, mostly because the "key values" used were insufficiently random.
References
External links
* , Randomness Requirements for Security
Java "entropy pool" for cryptographically secure unpredictable random numbers.
*
ttp://blogs.msdn.com/michael_howard/archive/2005/01/14/353379.aspx Cryptographically Secure Random number on Windows without using CryptoAPIConjectured Security of the ANSI-NIST Elliptic Curve RNG Daniel R. L. Brown, IACR ePrint 2006/117.
A Security Analysis of the NIST SP 800-90 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.
{{DEFAULTSORT:Cryptographically Secure Pseudorandom Number Generator
Cryptographic algorithms
Cryptographically secure pseudorandom number generators
Cryptographic primitives