NIST SP 800-90A

  1. Home
  2. Wiki

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).

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

History

[edit]

The predecessor to 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. This 2006 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 HMAC), CTR_DRBG (based on block ciphers in counter mode), and Dual_EC_DRBG (based on elliptic curve cryptography).[sp 1]

In March 2007, the publication NIST SP 800-90 Revised (800-90R) with the same title replaced the earlier version. Besides some minor textual clarification, there was a substantial change in the form of an additional step for Dual_EC_DRBG to provide backtracking resistance.[sp 2]

In January 2012, NIST SP 800-90A was published to replace NIST SP 800-90 Revised. The change notes mention that most of the revision was finished in August 2008, and that the recommednation was developed in concert with ANSI X9.82-3. Non-algorithmic changes included addition of explanations, definitions, and a rule against self-reseeding. The instantiation function for Dual_EC_DRBG was substantially revised; the appendix dedicated to justifying this DBRG received a new paragraph. The new hash functions from FIPS 180-4 were added in the discussion of hash-based [sp 3]

In June 2015, NIST 800-90A Revision 1 (800-90Ar1) was released. The most notable change is the removal of the dubious Dual_EC_DRBG algorithm.[sp 4]

Brief history of doubts cast on Dual_EC_DRBG

[edit]
Main article: Dual_EC_DRBG § Timeline of Dual_EC_DRBG

Dual_EC_DBRG was not first introduced to the public in NIST SP 800-90 of 2006. It was seen in an 2004 draft of ANSI X9.82-3 as well as the official version of ISO/IEC 18031:2005.[1] Its flaws were first proven in March 2006, when Kristian Gjøsteen published a method to predict the bias in the version found in the December 2015 draft of NIST SP 800-90. However, the subsequent publication in June 2006 did not address this flaw.[2]

In 2007, Dan Shumow and Niels Ferguson provided a much stronger attack with the ability to recover the entire internal state with just 32 bytes of output, predicting all its future output. The unexplained constants in Dual_EC_DRBG were hypothesized to act like a public key; an attacker would use a different set of numbers (analogous to a private key) to mount the attack. Shumow and Ferguson were not able to recover the NSA's key, but they were able to construct their own pair of keys for a demonstration. In November 2007, Bruce Schneier commented on the "strange" nature of the history of this random number generator and described the Shumow and Ferguson presentation in more accessible terms.[3]

Attention to Dual_EC_DRBG was raised again in September 2013 in light of an National Security Agency memo found in Edward Snowden's leak claiming a kleptographic backdoor.[4][5] Retroactive search of patents and papers associated with this DRBG revealed that the general technique used was already described in two 1997 papers.[6] Furthermore, a 2005 patent describes the exact technique used in the backdoor as well as a method to neutralize it.[7][1] However, the subtle formulation used in the standard meant that FIPS 140-2 compliance would preclude the use of any neutralization technique.[8]

NIST disavowed the use of Dual_EC_DRBG to RSA some time before February 26, 2014.[9] On April 21, 2014, NIST withdrew Dual_EC_DRBG from its draft guidance on random number generators recommending that "current users of Dual_EC_DRBG transition to one of the three remaining approved algorithms as quickly as possible".[10] This draft would become formalized as NIST SP 800-90A Revision 1 in June 2015.

Security analysis

[edit]

NIST claims that each of the four (revised to three) DBRGs are "backtracking resistant" and "prediction resistant". The former is the common notion of "forward secrecy" of PRNGs: in the event of a state compromise, the attacker cannot recover historical states and outputs. The latter means that if the state is compromised and subsequently re-seeded with sufficient entropy, security is restored.[11]

Dual_EC_DRBG

[edit]

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.[12] The decisional Diffie-Hellman problem is widely accepted as hard.[12] 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.[12] 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.[12] 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[13] and therefore invalidates Dual_EC_DRBG's security proof when the default truncation value is used.

Backdoor in Dual_EC_DRBG

[edit]
Main article: 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.[14] The NSA accomplished this by working during the standardization process to eventually become the sole editor of the standard.[15] 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.[16] 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,[17] but continued to be used in practice by companies such as RSA Security until the 2013 revelation.[5] 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.[18]

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

Hash_DRBG and HMAC_DRBG

[edit]

Hash_DRBG and HMAC_DRBG have security proofs for a single call to generate pseudorandom numbers.[21] 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.[21]

HMAC_DRBG also has a machine-verified security proof.[22] 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.[22]

Woodage and Shumow (2019) analyze the NIST schemes in more detail; specifically, they provide security proofs that take into account the initial seed generation and reseeding, which have not been analyzed at all before. Under random oracle model and assuming an oracle-independent entropy source:[11]

  • Hash_DBRG is robust in the sense of Dodis et al., i.e. meeting both of the NIST security claims.
  • HMAC_DBRG is robust given two conditions: it must be called with additional input entropy, and said entropy must satisfy additional conditions. All NIST-approved entropy sources satisfy these "additional conditions".
  • HMAC_DBRG is not forward-secure when called without additional input.

CTR_DRBG

[edit]

CTR_DRBG has been shown to have a theoretical imperfection when used with certain parameters because cryptographers did not consider the block size of the cipher when designing this pseudorandom number generator.[23] 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.[23] 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.[23] 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.[23] 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.[23]

There is currently no known method to exploit this issue when AES is used.

Key erasure

[edit]

The NIST CTR_DRBG scheme erases the key after the requested randomness is output by producing additional randomness to replace the key. This is wasteful from a performance perspective, but does not immediately cause issues with forward secrecy. However, realizing the performance implications, the NIST recommends an "extended AES-CTR-DRBG interface" for its Post-Quantum Cryptography Project submissions. This interface allows multiple sets of randomness to be generated without intervening erasure, only erasing when the user explicitly signals the end of requests. As a result, the key could remain in memory for an extended time if the "extended interface" is misused. An alternative proposed by Bernstein is to produce randomness to replace the key before the requested randomness is output, as done in "fast-key-erasure" RNGs.[24]

The security bounds reported by Campagna (2006) does not take into account any key replacement procedure.[24]

Woodage and Shumow (2019) provides a draft analyses of the situation mentioned by Bernstein, i.e. state leakage assuming large amounts of randomness (next) generated between re-keying (final).[11]


See also

[edit]

References

[edit]
  1. ^ a b Green, Matthew (2013-12-28). "A Few Thoughts on Cryptographic Engineering: A few more notes on NSA random number generators". Blog.cryptographyengineering.com. Archived from the original on 2016-01-26. Retrieved 2015-12-23.
  2. ^ Green, Matthew (2013-09-18). "The Many Flaws of Dual_EC_DRBG". Archived from the original on 2016-08-20. Retrieved 2013-09-22.
  3. ^ Schneier, Bruce (November 15, 2007). "The Strange Story of Dual_EC_DRBG". Retrieved November 25, 2016.
  4. ^ Perlroth, Nicole (10 September 2013). "Government Announces Steps to Restore Confidence on Encryption Standards". The New York Times. Archived from the original on 12 July 2014. Retrieved 11 September 2013.
  5. ^ a b Green, Matthew (2013-09-20). "RSA warns developers not to use RSA products". Retrieved 2014-08-23.
  6. ^ Young, Adam; Yung, Moti (1997-08-17). "The prevalence of kleptographic attacks on discrete-log based cryptosystems". Advances in Cryptology — CRYPTO '97. Lecture Notes in Computer Science. Vol. 1294. Springer, Berlin, Heidelberg. pp. 264–276. doi:10.1007/bfb0052241. ISBN 978-3-540-63384-6 – via ResearchGate.
  7. ^ US 2007189527, Brown, Daniel R. L. & Vanstone, Scott A., "Elliptic curve random number generation", assigned to Certicom Corp. 
  8. ^ "'Flaw in Dual EC DRBG (no, not that one)' – MARC". Marc.info. 2013-12-19. Archived from the original on 2014-10-16. Retrieved 2015-12-23.
  9. ^ Jeffrey Carr (2014-02-26). "Six Cryptographers Whose Work on Dual EC DRBG Were Deemed Without Merit by RSA Chief Art Coviello". Digital Dao. Archived from the original on 2014-03-03. Retrieved 2014-02-27.
  10. ^ "NIST Removes Cryptography Algorithm from Random Number Generator Recommendations". National Institute of Standards and Technology. 21 April 2014. Archived from the original on 29 August 2016. Retrieved 13 July 2017.
  11. ^ a b c Woodage, Joanne; Shumow, Dan (2019). "An Analysis of NIST SP 800-90A" (PDF). Advances in Cryptology – EUROCRYPT 2019. Vol. 11477. pp. 151–180. doi:10.1007/978-3-030-17656-3_6.
  12. ^ 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.
  13. ^ Schoenmakers, Berry; Sidorenko, Andrey (May 29, 2006). "Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator" (PDF). Retrieved November 20, 2016.
  14. ^ a b Perlroth, Nicole (2013-09-10). "Government Announces Steps to Restore Confidence on Encryption Standards". New York Times. Retrieved 2014-08-23.
  15. ^ 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.
  16. ^ Menn, Joseph (2013-12-20). "Exclusive: Secret contract tied NSA and security industry pioneer". Reuters. Retrieved 2014-08-23.
  17. ^ Bruce Schneier (2007-11-15). "Did NSA Put a Secret Backdoor in New Encryption Standard?". Wired News. Archived from the original on 2015-11-23. Retrieved 2014-08-23. Alt URL
  18. ^ Goodin, Dan (2013-09-20). "We don't enable backdoors in our crypto products, RSA tells customers". Ars Technica. Retrieved 2014-08-23.
  19. ^ "NIST Invites Comments on Draft SP 800-90A, Revision 1". National Institute of Standards and Technology. 2014-04-21. Archived from the original on 2014-07-23. Retrieved 2014-08-23.
  20. ^ 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.
  21. ^ a b Kan, Wilson (September 4, 2007). "Analysis of Underlying Assumptions in NIST DRBGs" (PDF). Retrieved November 19, 2016.
  22. ^ a b Ye, Katherine Qinru (April 2016). "The Notorious PRG: Formal verification of the HMAC-DRBG pseudorandom number generator" (PDF). Retrieved November 19, 2016.
  23. ^ 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.
  24. ^ a b Bernstein, Daniel J. "2017.07.23: Fast-key-erasure random-number generators: An effort to clean up several messes simultaneously. #rng #forwardsecrecy #urandom #cascade #hmac #rekeying #proofs".

Version history

[edit]
  1. ^ Barker, Elaine; Kelsey, John (June 2006). "NIST Special Publication 800-90: Recommendation for Random Number Generation Using Deterministic Random Bit Generators" (PDF). National Institute of Standards and Technology. Retrieved November 27, 2016. Withdrawn March 2007.
  2. ^ Barker, Elaine; Kelsey, John (March 2007). "NIST Special Publication 800-90: Recommendation for Random Number Generation Using Deterministic Random Bit Generators (Revised)" (PDF). National Institute of Standards and Technology. Retrieved November 27, 2016. Withdrawn January 2012.
  3. ^ Barker, Elaine; Kelsey, John (January 2012). "NIST Special Publication 800-90A: Recommendation for Random Number Generation Using Deterministic Random Bit Generators" (PDF). National Institute of Standards and Technology. doi:10.6028/NIST.SP.800-90A. Retrieved November 19, 2016. Withdrawn June 2015.
  4. ^ 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.