Dual_EC_DRBG or Dual Elliptic Curve Deterministic Random Bit Generator is a pseudorandom number generator that was promoted as a cryptographically secure pseudorandom number generator (CSPRNG) by the National Institute of Standards and Technology. It is based on the elliptic curve discrete logarithm problem (ECDLP) and is one of the four CSPRNGs standardized in NIST SP 800-90A. Shortly after the NIST publication, Bruce Schneier suggested that the RNG could be a kleptographic NSA backdoor based on discoveries made by Dan Shumow and Niels Ferguson. In 2013, The New York Times reported that internal NSA memos leaked by Edward Snowden suggest an RNG generated by the NSA which was used in the Dual_EC_DRBG standard does indeed contain a backdoor for the NSA.
The stated purpose of including the Dual_EC_DRBG in NIST SP 800-90A is that its security is based on a hard problem from number theory, such as the elliptic curve decisional Diffie–Hellman assumption. 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 raw output unsuitable for use as a stream cipher, and, arguably, for more general use.
- Its security requires a certain problem be hard, such as the computational Diffie–Hellman problem. One of the recommended configurations permits the possibility of the existence of a known secret key. Such a key, had it been retained, could help an attacker solve the hard problem more trivially. See the Controversy section for more discussion.
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 March 2006, it was written: "This proof makes essential use of Q being random. The reason for this is more than just to make the proof work. If Q is not random, then it may be the case the adversary knows a d such that dQ = P. Then dRi = dSi+1, so that such a distinguisher could immediately recover the secret prestates from the output. Once the distinguisher gets the prestates, it can easily distinguish the output from random. Therefore, it is generally preferable for Q to be chosen randomly, relative to P."
In August 2007, Dan Shumow and Niels Ferguson re-discovered this 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 these constants were deliberately crafted in a way which allows the designer to predict its output.
This is an asymmetric backdoor as defined in cryptovirology which uses public-key cryptography: the designer of the algorithm generates a key pair consisting of the public and private key; the public key is published as one of the algorithm's constants, while the private key is kept secret. It employs the discrete-log kleptogram introduced in Crypto 1997. Whenever the algorithm is being used, the holder of the private key can decrypt its output, revealing the state of the PRNG, and thereby allow him to predict future outputs. Yet for third parties, there is no way to prove that someone knows the private key (nor any way to prove that no one knows it). However, Appendix A.2 of the NIST document, which describes the weakness, does contain a method of generating a new key pair which will mitigate the backdoor if it exists.
On September 9, 2013, The NIST ITL announced, that in light of community security concerns, it was reissuing SP 800-90A as draft standard, and re-opening SP800-90B/C for public comment, and NIST now "strongly recommends" against the use of Dual_EC_DRBG, as specified in the January 2012 version of SP 800-90A.
On September 10, 2013, The New York Times wrote that "internal memos leaked by a former N.S.A. contractor, Edward Snowden, suggest that the N.S.A. generated one of the random number generators used in a 2006 N.I.S.T. standard — called the Dual EC DRBG standard — which contains a backdoor for the N.S.A." On September 10, 2013, The NIST Public Affairs Office director released a statement, saying that "NIST would not deliberately weaken a cryptographic standard."
Usage by RSA Security
As part of the Snowden leaks, it has been revealed that the US National Security Agency has been actively working to "insert vulnerabilities into commercial encryption systems, IT systems, networks, and endpoint communications devices used by targets" as part of the Bullrun program. Even though the Dual_EC_DRBG standard has been known to contain grave flaws since shortly after its release in 2006, the prominent security company RSA Security still used the standard as the default and recommended random number generator in the company's BSAFE toolkit and Data Protection Manager until September 2013. RSA has denied knowingly inserting a back door into its products.
After the 2013 backdoor revelation, RSA security Chief of Technology Sam Curry provided Ars Technica with a rationale for originally choosing the flawed Dual EC DRBG standard as default over the alternative random number generators. The technical accuracy of the statement was widely criticized by cryptographers including Johns Hopkins University professor Matthew Green and University of Pennsylvania professor Matt Blaze.
- Cryptographically secure pseudorandom number generator
- Nothing up my sleeve number
- Random number generator attack
- Recommendations for Random Number Generation Using Deterministic Random Bit Generators (Revised) (PDF). National Institute of Standards and Technology. 2012-01. NIST SP 800-90.
- Bruce Schneier (2007-11-15). "Did NSA Put a Secret Backdoor in New Encryption Standard?". Wired News.
- Perlroth, Nicole (September 10, 2013). "Government Announces Steps to Restore Confidence on Encryption Standards". The New York Times. Retrieved September 11, 2013.
- Kristian Gjøsteen. Comments on Dual-EC-DRBG/NIST SP 800-90
- Daniel R. L. Brown (2006). Conjectured Security of the ANSI-NIST Elliptic Curve RNG.
- Daniel R. L. Brown and Kristian Gjøsteen. A Security Analysis of the NIST SP 800-90 Elliptic Curve Random Number Generator, CRYPTO 2007, LNCS 4622, Springer, pp. 466–481. IACR ePrint version
- Berry Schoenmakers and Andrey Sidorenko. Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator, IACR ePrint 2006/190.
- Dan Shumow, Niels Ferguson (2007-08). "On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng" (PDF). CRYPTO Rump Session 2007. Microsoft.
- Adam L. Young, Moti Yung (1997). "The Prevalence of Kleptographic Attacks on Discrete-Log Based Cryptosystems". CRYPTO.
- "Secret Documents Reveal N.S.A. Campaign Against Encryption". New York Times.
- Matthew Green. "The Many Flaws of Dual_EC_DRBG".
- "We don’t enable backdoors in our crypto products, RSA tells customers". Ars Technica.
- "Stop using NSA-influenced code in our products, RSA tells customers". Ars Technica.
- Matthew Green (2013-09-20). "A Few Thoughts on Cryptographic Engineering: RSA warns developers not to use RSA products". Retrieved 2013-09-28.
- Menn, Joseph (December 20, 2013). "Exclusive: Secret contract tied NSA and security industry pioneer". San Francisco. Reuters. Retrieved December 20, 2013.