Suspect NIST crypto standard long thought to have a back door
Connecting state and local government leaders
The agency is advising against using an elliptic curve algorithm adopted in 2006 that has concerned cryptographers from the beginning.
While the National Institute of Standards and Technology reopens public review of several of its cryptographic standards, it is “strongly” advising against using one of the standards for elliptic curve cryptography — a standard that cryptographers have long suspected contained a back door, whether it was put there intentionally or not.
The standard in question, known as Dual_EC_DRBG, is included in Special Publication 800-90A, one of three publications NIST has reopened in wake of reports that the National Security Agency had tampered with their development. Although the initial reports in the Guardian, New York Times and ProPublica, based on the Snowden documents, didn’t say which standard or standards had been compromised, the Times subsequently reported that NSA had installed a back door in Dual_EC_DRBG during its development. NIST adopted the standard in 2006.
Dual_EC_DRBG — full name Dual Elliptic Curve Deterministic Random Bit Generation — is one of four algorithms included in SP 800-90A. The others are based on hashing, block cypher encryption and hash message authentication code (HMAC). SP 800-90A is titled Recommendations for Random Number Generation Using Deterministic Random Bit Generators. The other publications being reopened are 800-90B, which addresses entropy sources in random bit generators, and 800-90C, which addresses random bit generator constructions.
The news that NIST is recommending against using Dual_EC_DRBG likely isn’t a surprise to cryptographers, who have been wary of the algorithm from the beginning. In 2006, ProPublica reported researchers in the Netherlands had published a paper saying the algorithm was unsecure and could be attacked from an ordinary PC.
In 2007, cryptographer Bruce Schneier wrote that it is “three orders of magnitude slower” than the other algorithms in the publication, and that the random numbers it generated had a small bias, favoring some numbers over others, which could make its random numbers more predictable.
He also pointed to a paper by Dan Shumow and Niels Ferguson presented at the CRYPTO 2007 conference showing “that the algorithm contains a weakness that can only be described as a back door.” The researchers showed that the numbers used to generate the elliptic curve were linked to another, secret set of numbers that, if known, could be used to predict the outcome of the algorithm’s random number generation. Shumow and Ferguson did not say the apparent back door was intentional, only that it could be exploited if someone knew the second set of numbers.
“Cryptographers are a conservative bunch,” Schneier wrote. “We don't like to use algorithms that have even a whiff of a problem.” Those concerns, combined with Dual_EC_DRBG's slow speed, would seem to make it unlikely to be used much.
NIST maintains a list, most recently updated on Aug. 30, of 401 validated implementations (crypto modules and products from companies ranging from Apple to RSA) of SP 800-90 algorithms. Only 66 of them include Dual_EC_DRBG, and only six incorporate it exclusively; the others include at least one of the other options.
NIST has led development of many of the encryption standards used to protect data on the Internet, including the Advanced Encryption Standard and the Secure Hash Algorithms (currently up to version 3). It works with NSA in developing those standards, both because of NSA’s crypto expertise and because that collaboration is required by the Computer Security Act of 1987. But the standards agency has defended its development process as transparent and insisted it would not weaken a standard at the behest of NSA or any other agency.
“If vulnerabilities are found in these or any other NIST standards,” NIST said of the SP 800-90 review, “we will work with the cryptographic community to address them as quickly as possible.”