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 publication contains the specification for three allegedly cryptographically secure pseudorandom number generators for use in cryptography: Hash DRBG (based on hash functions), HMAC DRBG (based on HMAC), and CTR DRBG (based on block ciphers in counter mode). Earlier versions included a fourth generator, Dual_EC_DRBG (based on elliptic curve cryptography). Dual_EC_DRBG was later reported to probably contain a kleptographic backdoor inserted by the United States National Security Agency (NSA).
History
NIST SP 800-90A was published by the National Institute of Standards and Technology in June 2006 as NIST SP 800-90 with the title Recommendation for Random Number Generation Using Deterministic Random Bit Generators. The publication contains the specification for three allegedly cryptographically secure pseudorandom number generators for use in cryptography: Hash DRBG (based on hash functions), HMAC DRBG (based on HMAC), and CTR DRBG (based on block ciphers in counter mode).
Since June 24, 2015, the current version of the publication is Revision 1. Earlier versions included a fourth generator, Dual_EC_DRBG (based on elliptic curve cryptography). Dual_EC_DRBG was later reported to probably contain a kleptographic backdoor inserted by the United States National Security Agency (NSA), while the other three random number generators are accepted as uncontroversial and secure by multiple cryptographers.
As a work of the US Federal Government, NIST SP 800-90A is in the public domain and freely available.
Security analysis
Dual_EC_DRBG
An attempted security proof for Dual_EC_DRBG states that it requires three problems to be mathematically hard in order for Dual_EC_DRBG to be secure: the decisional Diffie-Hellman problem, the x-logarithm problem, and the truncated point problem. The decisional Diffie-Hellman problem is widely accepted as hard. The x-logarithm problem is not widely accepted as hard. Some evidence is shown that this problem is hard but that evidence is not conclusive. The security proof is therefore questionable and would be proven invalid if the x-logarithm problem is shown to be efficiently solvable. The truncated point problem requires enough bits to be truncated from the point selected by Dual_EC_DRBG to make it indistinguishable from a truly random number. However, the truncation of 16 bits, the default specified by the Dual_EC_DRBG standard, has been shown to be insufficient to make the output indistinguishable from a true random number generator and therefore invalidates Dual_EC_DRBG's security proof when the default truncation value is used.
Backdoor in Dual_EC_DRBG
As part of the Bullrun program, NSA has inserted backdoors into cryptography systems. One such target was suggested in 2013 to be Dual_EC_DRBG. The NSA accomplished this by working during the standardization process to eventually become the sole editor of the standard. In getting Dual_EC_DRBG accepted into NIST SP 800-90A, NSA cited prominent security firm RSA Security's usage of Dual_EC_DRBG in their products. However, RSA Security had been paid $10 million by NSA to use Dual_EC_DRBG as default, in a deal that Reuters describes as "handled by business leaders rather than pure technologists". As the $10 million contract to get RSA Security to use Dual_EC_DRBG was described by Reuters as secret, the people involved in the process of accepting Dual_EC_DRBG into NIST SP 800-90A were presumably not made aware of this obvious conflict of interest. This might help explain how a random number generator later shown to be inferior to the alternatives (in addition to the back door) made it into the NIST SP 800-90A standard.
The potential for a backdoor in Dual_EC_DRBG had already been documented by Dan Shumow and Niels Ferguson in 2007, but continued to be used in practice by companies such as RSA Security until the 2013 revelation. Given the known flaws in Dual_EC_DRBG, there have subsequently been accusations that RSA Security knowingly inserted a NSA backdoor into its products. RSA has denied knowingly inserting a backdoor into its products.
Following the NSA backdoor revelation, NIST has reopened the public vetting process for the NIST SP 800-90A standard. A revised version of NIST SP 800-90A that removes Dual_EC_DRBG was published in June 2015.