So now that RSA Security has urged developers to back away from the table and stop using the maligned Dual Elliptic Curve Deterministic Random Bit Generation (Dual EC DRBG) algorithm, the question begging to be asked is why did RSA use it in the first place?
Going back to 2007 and a seminal presentation at the CRYPTO conference by Dan Shumow and Niels Ferguson, there have been suspicions about Dual EC DRBG primarily because it was backed by the National Security Agency, which initially proposed the algorithm as a standard. Cryptographer Bruce Schneier wrote in a 2007 essay that the algorithm contains a weakness that “can only be described as a backdoor.”
Given the current climate and revelations about NSA surveillance of Americans, and implications the spy agency manipulated standards efforts, in particular those overseen by NIST, Dual EC DRBG and other crypto standards are going to be scrutinized top to bottom—not to mention the deterioration of trust in any product built on that standard.
“I wrote about it in 2007 and said it was suspect. I didn’t like it back then because it was from the government,” Schneier told Threatpost today. “It was designed so that it could contain a backdoor. Back then I was suspicious, now I’m terrified.
“We don’t know what’s been tampered with. Nothing can be trusted. Everything is suspect,” Schneier said.
Iin his essay, Schneier wrote that not only was the algorithm derided as slow compared to better available algorithms, but it had a bias, meaning that the random numbers it generates aren’t so random. Dual EC DRBG was one of four approved random bit generators in NIST Special Publication 800-90, but it sticks out like a sore thumb.
“What Shumow and Ferguson showed is that these numbers have a relationship with a second, secret set of numbers that can act as a kind of skeleton key. If you know the secret numbers, you can predict the output of the random-number generator after collecting just 32 bytes of its output,” Schneier wrote. “To put that in real terms, you only need to monitor one TLS Internet encryption connection in order to crack the security of that protocol. If you know the secret numbers, you can completely break any instantiation of Dual_EC_DRBG.
“The researchers don’t know what the secret numbers are,” Schneier said. “But because of the way the algorithm works, the person who produced the constants might know; he had the mathematical opportunity to produce the constants and the secret numbers in tandem.”
RSA advised its developer customers via email yesterday to no longer use the algorithm, following a similar NIST recommendation last week. The algorithm is the default pseudo random number generator in a number of RSA products, including the RSA BSAFE libraries and RSA’s key management product RSA Data Protection Manager. BSAFE is embedded in many applications, providing cryptography, digital certificates and TLS security. RSA said the current product documentation can help developers change the PRNG in their respective implementations. RSA also said it would review its products to determine where the algorithm is in use and make the appropriate changes.
RSA CTO Sam Curry told Wired magazine, which first reported the story yesterday, the algorithm has been part of RSA libraries since 2004, two years before it was approved by NIST.
“Every product that we at RSA make, if it has a crypto function, we may or may not ourselves have decided to use this algorithm,” Curry told Wired. “So we’re also going to go through and make sure that we ourselves follow our own advice and aren’t using this algorithm.”
Matthew Green, a cryptographer and research professor at Johns Hopkins University, said RSA had no good reason to use the algorithm, and its decision to do so puts the security of any product using the BSAFE library into question.
“There’s no good reason whatsoever, just none,” Green said. “There was no good reason before the [Crypto 2007] backdoor presentation. It was a poor decision then, and afterwards I kind of think it was malpractice. People have known about this for a long time.”
RSA’s core product, its SecurID two-factor authentication tokens, was breached in 2011 and data stolen in that attack was used to attack Lockheed Martin and others in the defense industry. RSA said it spent more than $66 million cleaning up from the attack and helping customers. An untold number of RSA SecurID tokens were recalled and replaced. A source close to the matter told Threatpost that SecurID currently does not use the Dual EC DRBG random number generator, nor did it prior to the 2011 attack.
In the meantime, the immediate fallout is that we should expect more technology companies to make similar announcements about NIST-approved and NSA-influenced encryption. Experts are concerned too about the damage being inflicted upon NIST as a standards body. It’s likely these revelations will force greater scrutiny on the NIST-NSA relationship and nudge users and providers away from the standard in time.
“The U.S. has had an enormous influence on crypto around the world because we have NIST,” Green said in an interview before the RSA news broke. “You could see people break away from NIST, which would hurt everyone, and move to regional standards. That stuff is a problem.
“We trust NIST because there are a lot smart people there. If you split up into regions, it’s possible things could get less secure,” Green added. “You could end up with more vulnerabilities; standards get weaker the less effort you put into it.”
Schneier agreed that scrutiny will tighten on NIST.
“The fact is, NIST has been tarnished badly, and we really need them,” he said. “This is the biggest problem: The NSA has broken the fundamental social contract of the Internet.”