Dual EC DRBG - Controversy

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 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 is an asymmetric backdoor as defined in cryptovirology that uses 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. 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 allowing him to predict any future output. Yet for third parties, there is no way to detect the existence of the private key (nor to prove the non-existence of any such 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.