By Ryan Paul
According to security experts, an algorithm for generating random numbers that is included in an official standard documented by the National Institute of Standards and Technology (NIST) could potentially include a backdoor planted by the NSA.
In a recent blog entry, cryptographer Bruce Schneier describes research that was presented by his colleagues Niels Ferguson and Dan Shumow at the CRYPTO 2007 conference this past August. The security researchers have raised concerns about a potential backdoor in the Dual_EC_DRBG algorithm, which is documented in NIST’s 800-90 publication about deterministic random bit generators. Dual_EC_DRBG, which is based on elliptic curves, is said to be significantly slower to compute than the other algorithms in the standard and was supposedly only included at all because it has the strong support of the NSA.
Dual_EC_DRBG uses a seemingly arbitrary series of specific fixed numbers which are published in the standard to define the elliptic curve used for the algorithm. The origin of those numbers has not been revealed or explained but it is possible to use other numbers instead. The researchers realized that the fixed set of numbers used in Dual_EC_DRBG could have a mathematical relationship to a secret second set of numbers, which could then be used as a master key to decrypt content.
“[W]e have no way of knowing whether the NSA knows the secret numbers that break Dual_EC-DRBG,” wrote Schneier. “We have no way of knowing whether an NSA employee working on his own came up with the constants–and has the secret numbers. We don’t know if someone from NIST, or someone in the ANSI working group, has them. Maybe nobody does.”
Schneier also explains that the algorithm’s susceptibility to decryption via a secret number set presents broader risks. The party which holds the master key would be able to decrypt content that uses Dual_EC-DRBG, but if the key was leaked or if others managed to figure it out independently, all implementations of the algorithm that use the fixed numbers specified in 800-90 could be compromised.
“Even if no one knows the secret numbers, the fact that the backdoor is present makes Dual_EC_DRBG very fragile. If someone were to solve just one instance of the algorithm’s elliptic-curve problem, he would effectively have the keys to the kingdom,” wrote Schneier. “He could then use it for whatever nefarious purpose he wanted. Or he could publish his result, and render every implementation of the random-number generator completely insecure.”
Although the researchers present compelling evidence to support their argument that a master key could potentially exist, there is no evidence yet that such a key was intentionally formulated by the NSA and included as a backdoor. The NSA’s support for the algorithm does seem somewhat suspicious, particularly in light of its relative weaknesses compared to the others in the standard. Schneier recommends that developers avoid using Dual_EC-DRBG and notes that “both NIST and the NSA have some explaining to do.”