NIST SP 800-90A

Last updated

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

Contents

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. [1] 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. [2] [3]

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

Security analysis

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. [4]

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. [5] The decisional Diffie-Hellman problem is widely accepted as hard. [5] 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. [5] 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. [5] 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 [6] 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. [7] The NSA accomplished this by working during the standardization process to eventually become the sole editor of the standard. [8] 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. [9] 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, [10] but continued to be used in practice by companies such as RSA Security until the 2013 revelation. [2] 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. [11]

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

Hash_DRBG and HMAC_DRBG

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

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

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: [4]

CTR_DRBG

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. [16] 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. [16] 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. [16] 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. [16] 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. [16]

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

Key erasure

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. [17]

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

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). [4]

NIST SP 800-90A version history

See also

Related Research Articles

Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ECC allows smaller keys compared to non-EC cryptography to provide equivalent security.

A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generated sequence is not truly random, because it is completely determined by an initial value, called the PRNG's seed. Although sequences that are closer to truly random can be generated using hardware random number generators, pseudorandom number generators are important in practice for their speed in number generation and their reproducibility.

In cryptography, a block cipher mode of operation is an algorithm that uses a block cipher to provide information security such as confidentiality or authenticity. A block cipher by itself is only suitable for the secure cryptographic transformation of one fixed-length group of bits called a block. A mode of operation describes how to repeatedly apply a cipher's single-block operation to securely transform amounts of data larger than a block.

A cryptographically secure pseudorandom number generator (CSPRNG) or cryptographic pseudorandom number generator (CPRNG) is a pseudorandom number generator (PRNG) with properties that make it suitable for use in cryptography. It is also loosely known as a cryptographic random number generator (CRNG).

Niels T. Ferguson is a Dutch cryptographer and consultant who currently works for Microsoft. He has worked with others, including Bruce Schneier, designing cryptographic algorithms, testing algorithms and protocols, and writing papers and books. Among the designs Ferguson has contributed to is the AES finalist block cipher algorithm Twofish as well as the stream cipher Helix and the Skein hash function.

Articles related to cryptography include:

<span class="mw-page-title-main">RSA Security</span> American computer security company

RSA Security LLC, formerly RSA Security, Inc. and trade name RSA, is an American computer and network security company with a focus on encryption and encryption standards. RSA was named after the initials of its co-founders, Ron Rivest, Adi Shamir and Leonard Adleman, after whom the RSA public key cryptography algorithm was also named. Among its products is the SecurID authentication token. The BSAFE cryptography libraries were also initially owned by RSA. RSA is known for incorporating backdoors developed by the NSA in its products. It also organizes the annual RSA Conference, an information security conference.

<span class="mw-page-title-main">Nothing-up-my-sleeve number</span> Numbers used by cryptographers to show that they are working in good faith

In cryptography, nothing-up-my-sleeve numbers are any numbers which, by their construction, are above suspicion of hidden properties. They are used in creating cryptographic functions such as hashes and ciphers. These algorithms often need randomized constants for mixing or initialization purposes. The cryptographer may wish to pick these values in a way that demonstrates the constants were not selected for a nefarious purpose, for example, to create a backdoor to the algorithm. These fears can be allayed by using numbers created in a way that leaves little room for adjustment. An example would be the use of initial digits from the number π as the constants. Using digits of π millions of places after the decimal point would not be considered trustworthy because the algorithm designer might have selected that starting point because it created a secret weakness the designer could later exploit—though even with natural-seeming selections, enough entropy exists in the possible choices that the utility of these numbers has been questioned.

The security of cryptographic systems depends on some secret data that is known to authorized persons but unknown and unpredictable to others. To achieve this unpredictability, some randomization is typically employed. Modern cryptographic protocols often require frequent generation of random quantities. Cryptographic attacks that subvert or exploit weaknesses in this process are known as random number generator attacks.

In cryptography, PBKDF1 and PBKDF2 are key derivation functions with a sliding computational cost, used to reduce vulnerability to brute-force attacks.

Kleptography is the study of stealing information securely and subliminally. The term was introduced by Adam Young and Moti Yung in the Proceedings of Advances in Cryptology – Crypto '96. Kleptography is a subfield of cryptovirology and is a natural extension of the theory of subliminal channels that was pioneered by Gus Simmons while at Sandia National Laboratory. A kleptographic backdoor is synonymously referred to as an asymmetric backdoor. Kleptography encompasses secure and covert communications through cryptosystems and cryptographic protocols. This is reminiscent of, but not the same as steganography that studies covert communications through graphics, video, digital audio data, and so forth.

<span class="mw-page-title-main">Random number generation</span> Producing a sequence that cannot be predicted better than by random chance

Random number generation is a process by which, often by means of a random number generator (RNG), a sequence of numbers or symbols that cannot be reasonably predicted better than by random chance is generated. This means that the particular outcome sequence will contain some patterns detectable in hindsight but impossible to foresee. True random number generators can be hardware random-number generators (HRNGs), wherein each generation is a function of the current value of a physical environment's attribute that is constantly changing in a manner that is practically impossible to model. This would be in contrast to so-called "random number generations" done by pseudorandom number generators (PRNGs), which generate numbers that only look random but are in fact pre-determined—these generations can be reproduced simply by knowing the state of the PRNG.

The Microsoft Windows platform specific Cryptographic Application Programming Interface is an application programming interface included with Microsoft Windows operating systems that provides services to enable developers to secure Windows-based applications using cryptography. It is a set of dynamically linked libraries that provides an abstraction layer which isolates programmers from the code used to encrypt the data. The Crypto API was first introduced in Windows NT 4.0 and enhanced in subsequent versions.

Cryptovirology refers to the study of cryptography use in malware, such as ransomware and asymmetric backdoors. Traditionally, cryptography and its applications are defensive in nature, and provide privacy, authentication, and security to users. Cryptovirology employs a twist on cryptography, showing that it can also be used offensively. It can be used to mount extortion based attacks that cause loss of access to information, loss of confidentiality, and information leakage, tasks which cryptography typically prevents.

Dual_EC_DRBG is an algorithm that was presented as a cryptographically secure pseudorandom number generator (CSPRNG) using methods in elliptic curve cryptography. Despite wide public criticism, including the public identification of the possibility that the National Security Agency put a backdoor into a recommended implementation, it was for seven years one of four CSPRNGs standardized in NIST SP 800-90A as originally published circa June 2006, until it was withdrawn in 2014.

RDRAND is an instruction for returning random numbers from an Intel on-chip hardware random number generator which has been seeded by an on-chip entropy source. Intel introduced the feature around 2012, and AMD added support for the instruction in June 2015.

<span class="mw-page-title-main">Bullrun (decryption program)</span> Code name of a decryption program run by the NSA

Bullrun is a clandestine, highly classified program to crack encryption of online communications and data, which is run by the United States National Security Agency (NSA). The British Government Communications Headquarters (GCHQ) has a similar program codenamed Edgehill. According to the Bullrun classification guide published by The Guardian, the program uses multiple methods including computer network exploitation, interdiction, industry relationships, collaboration with other intelligence community entities, and advanced mathematical techniques.

Dell BSAFE, formerly known as RSA BSAFE, is a FIPS 140-2 validated cryptography library, available in both C and Java. BSAFE was initially created by RSA Security, which was purchased by EMC and then, in turn, by Dell. When Dell sold the RSA business to Symphony Technology Group in 2020, Dell elected to retain the BSAFE product line. BSAFE was one of the most common encryption toolkits before the RSA patent expired in September 2000. It also contained implementations of the RCx ciphers, with the most common one being RC4. From 2004 to 2013 the default random number generator in the library was a NIST-approved RNG standard, widely known to be insecure from at least 2006, containing a kleptographic backdoor from the American National Security Agency (NSA), as part of its secret Bullrun program. In 2013 Reuters revealed that RSA had received a payment of $10 million to set the compromised algorithm as the default option. The RNG standard was subsequently withdrawn in 2014, and the RNG removed from BSAFE beginning in 2015.

<span class="mw-page-title-main">Crypto Wars</span> Attempts to limit access to strong cryptography

Attempts, unofficially dubbed the "Crypto Wars", have been made by the United States (US) and allied governments to limit the public's and foreign nations' access to cryptography strong enough to thwart decryption by national intelligence agencies, especially the National Security Agency (NSA).

A mask generation function (MGF) is a cryptographic primitive similar to a cryptographic hash function except that while a hash function's output has a fixed size, a MGF supports output of a variable length. In this respect, a MGF can be viewed as a extendable-output function (XOF): it can accept input of any length and process it to produce output of any length. Mask generation functions are completely deterministic: for any given input and any desired output length the output is always the same.

References

  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.
  2. 1 2 Green, Matthew (2013-09-20). "RSA warns developers not to use RSA products" . Retrieved 2014-08-23.
  3. ↑ Schneier, Bruce (November 15, 2007). "The Strange Story of Dual_EC_DRBG" . Retrieved November 25, 2016.
  4. 1 2 3 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.
  5. 1 2 3 4 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.
  6. ↑ Schoenmakers, Berry; Sidorenko, Andrey (May 29, 2006). "Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator" (PDF). Retrieved November 20, 2016.
  7. 1 2 Perlroth, Nicole (2013-09-10). "Government Announces Steps to Restore Confidence on Encryption Standards". New York Times . Retrieved 2014-08-23.
  8. ↑ 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.
  9. ↑ Menn, Joseph (2013-12-20). "Exclusive: Secret contract tied NSA and security industry pioneer". Reuters . Retrieved 2014-08-23.
  10. ↑ 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
  11. ↑ Goodin, Dan (2013-09-20). "We don't enable backdoors in our crypto products, RSA tells customers". Ars Technica . Retrieved 2014-08-23.
  12. ↑ "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.
  13. ↑ 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.
  14. 1 2 Kan, Wilson (September 4, 2007). "Analysis of Underlying Assumptions in NIST DRBGs" (PDF). Retrieved November 19, 2016.
  15. 1 2 Ye, Katherine Qinru (April 2016). "The Notorious PRG: Formal verification of the HMAC-DRBG pseudorandom number generator" (PDF). Retrieved November 19, 2016.
  16. 1 2 3 4 5 Campagna, Matthew J. (November 1, 2006). "Security Bounds for the NIST Codebook-based Deterministic Random Bit Generator" (PDF). Retrieved November 19, 2016.
  17. 1 2 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".
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.