Jump to content

NIST SP 800-90A

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Jesse Viviano (talk | contribs) at 00:01, 29 November 2016 (Better wording). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

NIST SP 800-90A ("SP" stands for "special publication") is a withdrawn and superseded 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 four allegedly cryptographically secure pseudorandom number generators for use in cryptography: Hash_DRBG (based on hash functions), HMAC_DRBG (Based on Hash-based message authentication code), CTR_DRBG (based on block ciphers in counter mode), and Dual_EC_DRBG (based on elliptic curve cryptography). Dual_EC_DRBG was later reported to probably contain a kleptographic backdoor inserted by the National Security Agency, while the other three random number generators are accepted as uncontroversial and secure by multiple cryptographers.[1][2]

As a work of the US Federal Government, NIST SP 800-90A is in the public domain and freely available.

Backdoor in Dual_EC_DRBG

Main article: Dual_EC_DRBG

As part of the Bullrun program, NSA has been inserting backdoors into cryptography systems. One such target was suggested in 2013 to be Dual_EC_DRBG.[3] The NSA accomplished this by working during the standardization process to eventually become the sole editor of the standard.[4] 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.[5] 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,[6] but continued to be used in practice by companies such as RSA Security until the 2013 revelation.[1] 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.[7]

Following the NSA backdoor revelation, NIST has reopened the public vetting process for the NIST SP 800-90A standard.[3][8] A revised version of NIST SP 800-90A that removes Dual_EC_DRBG was published on June 2015.[9]

Security analysis

A 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.[10] The decisional Diffie-Hellman problem is widely accepted as hard.[10] The x-logarithm problem is not widely accepted as hard, but some evidence is shown that this problem is hard but does not prove that the problem is hard.[10] The security proof is therefore questionable and would be proven invalid if the x-logarithm problem is shown to be solvable instead of hard. 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.[10] 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[11] and therefore invalidates Dual_EC_DRBG's security proof when the default truncation value is used.

Hash_DRBG and HMAC_DRBG have security proofs for a single call to generate pseudorandom numbers.[12] The paper proving the security of Hash_DRBG and HMAC_DRBG does cite the attempted security proof for Dual_EC_DRBG used in the previous paragraph as a security proof to say that one should not use CTR_DRBG because it is the only DRBG in NIST SP 800-90A that lacks a security proof.[12]

HMAC_DRBG also has a machine-verified security proof.[13] The thesis containing the machine-verified security proof also proves that a compromise of a properly-implemented instance of HMAC_DRBG does not compromise the security of the numbers generated before the compromise.[13]

CTR_DRBG has been shown to have security problems when used with certain parameters because cryptographers failed to consider the block size of the cipher.[14] CTR_DRBG appears secure and indistinguishable from a true random source when AES is used as the underlying block cipher and 112 bits are taken from this pseudorandom number generator.[14] When AES is used as the underlying block cipher and 128 bits are taken from each instantiation, the required security level is delivered with the caveat that a 128-bit cipher's output in counter mode can be distinguished from a true random number generator.[14] When AES is used as the underlying block cipher and more than 128 bits are taken from this pseudorandom number generator, then the resulting security level is limited by the block size instead of the key size and therefore the actual security level is much less than the security level implied by the key size.[14] CTR_DRBG is also shown to fail to deliver the expected security level whenever Triple DES is used because its 64-bit block size is much less than the 112-bit key size used for Triple DES.[14]

NIST Special Publication 800-90A version history

References

  1. ^ a b Green, Matthew (2013-09-20). "RSA warns developers not to use RSA products". Retrieved 2014-08-23.
  2. ^ Schneier, Bruce (November 15, 2007). "The Strange Story of Dual_EC_DRBG". Retrieved November 25, 2016.
  3. ^ a b Perlroth, Nicole (2013-09-10). "Government Announces Steps to Restore Confidence on Encryption Standards". New York Times. Retrieved 2014-08-23.
  4. ^ Ball, James; Borger, Julian; Greenwald, Glenn (2013-09-05). "Revealed: how US and UK spy agencies defeat internet privacy and security". The Guardian. Retrieved 2014-08-23.
  5. ^ Menn, Joseph (2013-12-20). "Exclusive: Secret contract tied NSA and security industry pioneer". Reuters. Retrieved 2014-08-23.
  6. ^ Bruce Schneier (2007-11-15). "Did NSA Put a Secret Backdoor in New Encryption Standard?". Wired News. Archived from the original on 2007-11-15. Retrieved 2014-08-23.
  7. ^ Goodin, Dan (2013-09-20). "We don't enable backdoors in our crypto products, RSA tells customers". Ars Technica. Retrieved 2014-08-23.
  8. ^ "NIST Invites Comments on Draft SP 800-90A, Revision 1". National Institute of Standards and Technology. 2014-04-21. Retrieved 2014-08-23.
  9. ^ Barker, Elaine; Kelsey, John (June 2015). "NIST Released Special Publication (SP) 800-90A Revision 1: Recommendation for Random Number Generation Using Deterministic Random Bit Generators" (PDF). National Institute of Standards and Technology. doi:10.6028/NIST.SP.800-90Ar1. Retrieved November 19, 2016.
  10. ^ a b c d Brown, Daniel R. L.; Gjøsteen, Kristian (February 15, 2007). "A Security Analysis of the NIST SP 800-90 Elliptic Curve Random Number Generator" (PDF). Retrieved November 19, 2016.
  11. ^ Schoenmakers, Berry; Sidorenko, Andrey (May 29, 2006). "Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator" (PDF). Retrieved November 20, 2016.
  12. ^ a b Kan, Wilson (September 4, 2007). "Analysis of Underlying Assumptions in NIST DRBGs" (PDF). Retrieved November 19, 2016.
  13. ^ a b Ye, Katherine Qinru (April 2016). "The Notorious PRG: Formal verification of the HMAC-DRBG pseudorandom number generator" (PDF). Retrieved November 19, 2016.
  14. ^ a b c d e Campagna, Matthew J. (November 1, 2006). "Security Bounds for the NIST Codebook-based Deterministic Random Bit Generator" (PDF). Retrieved November 19, 2016.
Retrieved from "https://en.wikipedia.org/w/index.php?title=NIST_SP_800-90A&oldid=752006441"