Dual EC DRBG
Encyclopedia
Dual_EC_DRBG or Dual Elliptic Curve Deterministic Random Bit Generator is a controversial pseudorandom number generator
(PRNG) designed and published by the National Security Agency
. It is based on the elliptic curve
discrete logarithm problem (ECDLP) and is one of the four PRNGs standardized in the NIST Special Publication 800-90. Shortly after the NIST publication, it was suggested that the RNG could be a kleptographic NSA backdoor.
Subsequent to publication of the Dual_EC_DRBG algorithm, various researchers have reported certain security issues with the properties of the Dual_EC_DRBG:
In August 2007, Dan Shumow and Niels Ferguson
discovered that the algorithm has a vulnerability which could be used as a backdoor. Given the wide applications of PRNGs in cryptography
, this vulnerability could be used to defeat practically any cryptosystem relying on it. The algorithm uses several constants
which determine the output; it is possible that these constants are deliberately crafted in a way that allows the designer to predict its output.
This backdoor would work analogously to public-key encryption: the designer of the algorithm generates a keypair consisting of the public and private key; the public key is published as the algorithm's constants, while the private key is kept secret. Whenever the algorithm is being used, the holder of the private key can decrypt its output, revealing the state of the PRNG, and thereby allowing him to predict any future output. Yet for third parties, there is no way to prove the existence (or non-existence) of the private key. However, Appendix A.2 of the NIST document, which describes the weakness, does contain a method of generating a new keypair which will repair the backdoor if it exists.
Pseudorandom number generator
A pseudorandom number generator , also known as a deterministic random bit generator , is an algorithm for generating a sequence of numbers that approximates the properties of random numbers...
(PRNG) designed and published by the National Security Agency
National Security Agency
The National Security Agency/Central Security Service is a cryptologic intelligence agency of the United States Department of Defense responsible for the collection and analysis of foreign communications and foreign signals intelligence, as well as protecting U.S...
. It is based on the elliptic curve
Elliptic curve
In mathematics, an elliptic curve is a smooth, projective algebraic curve of genus one, on which there is a specified point O. An elliptic curve is in fact an abelian variety — that is, it has a multiplication defined algebraically with respect to which it is a group — and O serves as the identity...
discrete logarithm problem (ECDLP) and is one of the four PRNGs standardized in the NIST Special Publication 800-90. Shortly after the NIST publication, it was suggested that the RNG could be a kleptographic NSA backdoor.
Security
This stated purpose of including the Dual_EC_DRBG in NIST SP 800-90 is that its security is based on a hard problem from number theory, such as the elliptic curve Decision Diffie-Hellman problem. Given the importance of having secure random number generators in cryptography, in certain cases it may be desirable to sacrifice speed for security.Subsequent to publication of the Dual_EC_DRBG algorithm, various researchers have reported certain security issues with the properties of the Dual_EC_DRBG:
- The intermediate values it generates, a sequence of elliptic curve points, should, under certain reasonable assumptions, such as the Decision Diffie-Hellman problem, be indistinguishable from uniformly random elliptic curve points.
- The sequence of bits generated from the Dual_EC_DRBG, under certain parameter choices, can be distinguished from uniformly random bits, making its output unsuitable for use as a stream cipherStream cipherIn cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream . In a stream cipher the plaintext digits are encrypted one at a time, and the transformation of successive digits varies during the encryption...
, and, arguably, for more general use.
- Its security requires that a certain problem be hard, such as the computational Diffie-Hellman problemDiffie-Hellman problemThe Diffie–Hellman problem is a mathematical problem first proposed by Whitfield Diffie and Martin Hellman in the context of cryptography. The motivation for this problem is that many security systems use mathematical operations that are fast to compute, but hard to reverse. For example, they...
, but one of the recommended configurations of the Dual_EC_DRBG permits the possibility that a key, which facilitates solution of the problem, has been retained. See the Controversy section for more discussion.
Controversy
This PRNG has been controversial because it was published in the NIST standard despite being three orders of magnitude slower than the other three standardized algorithms, and containing several weaknesses which have been identified since its standardization.In August 2007, Dan Shumow and Niels Ferguson
Niels Ferguson
Niels T. Ferguson is a Dutch cryptographer and consultant who currently works for Microsoft. He has worked with others, including Bruce Schneier, designing cryptographic algorithms, testing algorithms and protocols, and writing papers and books...
discovered that the algorithm has a vulnerability which could be used as a backdoor. Given the wide applications of PRNGs in cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, this vulnerability could be used to defeat practically any cryptosystem relying on it. The algorithm uses several constants
Constant (programming)
In computer programming, a constant is an identifier whose associated value cannot typically be altered by the program during its execution...
which determine the output; it is possible that these constants are deliberately crafted in a way that allows the designer to predict its output.
This backdoor would work analogously to public-key encryption: the designer of the algorithm generates a keypair consisting of the public and private key; the public key is published as the algorithm's constants, while the private key is kept secret. Whenever the algorithm is being used, the holder of the private key can decrypt its output, revealing the state of the PRNG, and thereby allowing him to predict any future output. Yet for third parties, there is no way to prove the existence (or non-existence) of the private key. However, Appendix A.2 of the NIST document, which describes the weakness, does contain a method of generating a new keypair which will repair the backdoor if it exists.
See also
- Cryptographically secure pseudorandom number generatorCryptographically secure pseudorandom number generatorA cryptographically secure pseudo-random number generator is a pseudo-random number generator with properties that make it suitable for use in cryptography.Many aspects of cryptography require random numbers, for example:...
- Nothing up my sleeve numberNothing up my sleeve numberIn cryptography, nothing up my sleeve numbers are any numbers which, by their construction, are above suspicion of hidden properties. They are used in creating cryptographic functions such as hashes and ciphers. These algorithms often need randomized constants for mixing or initialization purposes...
- Random number generator attackRandom number generator attackThe security of cryptographic systems depends on some secret data that is known to authorized persons but unknown and unpredictable to others. To achieve this unpredictability, some randomization is typically employed...