Posts
Six Cryptographers Whose Work on Dual EC DRBG Were Deemed Without Merit by RSA Chief Art Coviello
"When, last September, it became possible that concerns raised in 2007 might have merit as part of a strategy of exploitation, NIST as the relevant standards body issued new guidance to stop the use of this algorithm. We immediately acted upon that guidance, notified our customers, and took steps to remove the algorithm from use." - Art Coviello RSAC 2014 Keynote speechThree things about Art Coviello's keynote speech today jumped out at me:
- He attempted to paint NSA as the sole bad guy in the Dual EC DRBG debacle.
- He carefully avoided any mention of why RSA trusted the NSA in 2004 when the agency wasn't trusted by RSA even five years earlier.
- He believed that the published warnings of six independent and respected cryptographers in 2006 and 2007 had no merit.
Comments on Dual-EC-DRBG/NIST SP 800-90, Draft December 2005 by Kristian Gjøsteen* (March 16, 2006)
Abstract: "We analyse the Dual-EC deterministic pseudo-random bit generator (DRBG) proposed in draft of NIST SP 800-90 published December 2005. The generator consists of two parts, one that generates a sequence of points and one that extracts a bit string from the point sequence. We show that the first part is essentially cryptographically sound, while the second is not."
*Associate professor at The Norwegian University of Science and Technology, Department of Mathematical Sciences.
Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator
Berry Schoenmakers and Andrey Sidorenko
Dept. of Mathematics and Computer Science, TU Eindhoven,
P.O. Box 513, 5600 MB Eindhoven, The Netherlands.
berry@win.tue.nl, a.sidorenko@tue.nl
29 May 2006
"The Dual Elliptic Curve Pseudorandom Generator (DEC PRG) is proposed by Barker and Kelsey [2].
It is claimed (see Section 10.3.1 of [2]) that the pseudorandom generator is secure unless the adversary can solve the elliptic curve discrete logarithm problem (ECDLP) for the corresponding elliptic curve.
The claim is supported only by an informal discussion. No security reduction is given, that is, it is not shown that an adversary that breaks the pseudorandom generator implies a solver for the ECDLP.
Our experimental results and also empirical argument show that the DEC PRG is insecure. The attack does not imply solving the ECDLP for the corresponding elliptic curve. The attack is very efficient. It can be run on an ordinary PC. Actually, the generator is insecure because pseudorandom bits are extracted from points of the elliptic curve improperly."
On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng by Dan Shumow and Niels Ferguson (Microsoft)
Bruce Schneier "Did NSA Put a Secret Backdoor in New Encryption Standard?" Wired, November 15, 2007.
Art Coviello failed to explain why the work of any of the above researchers didn't merit an investigation into the algorithm which the NSA wanted him to adopt two years earlier. I hope that RSA customers pay attention to Art Coviello's clumsy attempt to whitewash RSA's responsibility in this matter and find other, more trustworthy vendors to take their business to.
You (and the RSA speech) missed one example of a warning. "Missed", in the case of the RSA speech.
ReplyDeleteAccording to John Kelsey, who is listed as an author on the NIST standard, the possible backdoor was also discussed in a 2005 ANSI meeting on the same standard. There were three RSA Security employees listed as members of that committee. See http://blog.cryptographyengineering.com/2013/12/a-few-more-notes-on-nsa-random-number.html
From the keynote:
ReplyDelete> A method that became a NIST standard in 2006 with little opposition
He apparently doesn't count all the research papers with "no merit" calling the algorithm fx "cryptographically unsound", which was published before Dual_EC_DRBG became a NIST standard, as opposition.
RSA Security seems to be using the "we are too stupid to form our own evaluations" defense. The only point where they consider trusting the research papers is when NSA (accidentally) tells them they might be true - actually considering the papers on their own merits apparently doesn't cross RSA Security's minds.
Given that RSA Security was part of the ANSI committee which accepted Dual_EC_DRBG, I wonder who he imagine would provide the opposition, if not them or the independent researchers? Note that Daniel Brown of Certicom, who was also on the ANSI committee and seem very central to all this, acknowledged both the backdoor and non-randomness as being true concerns in his 2006 security proof for Dual_EC_DRBG (the proof relied on non-standard values). And was RSA also part of the NIST standard committee, the one that New York Times wrote was basically taken over by the NSA?
There are other interesting bits from that keynote:
ReplyDelete"A method [Dual_EC_DRBG] that became a NIST standard in 2006 with little opposition"
If you ignore all the strong independent research that called the algorithm unsound. How does he define "little opposition", given the widespread incredulity when people found out RSA Security had used a standard that everybody else considered obviously defect?
"Recognizing that reality, and encryption's inevitable shrinking contribution to our business, we worked to establish an approach to standards setting that was based on the input of the larger community rather than the intellectual property of any one vendor. We put out weight and trust behind a number of standards bodies - ANSI X9 and yes, the National Institute of Standards and Technology (NIST). We saw our new role, not as the driver, but as a contributor to and beneficiary of open standards that would be stronger due to the input of the larger community."
That sound like a standard high-value brand scam. Take a high-value brand that has fallen on hard times, fire everybody skilled (and therefore expensive) who used to work for that brand, and then sell the cheapest lowest-effort poor quality goods possible under that brand. People think that the RSA brand means independently checked quality encryption, but get blindly implemented NSA backdoors. And double-dip by taking $10,000,000 from NSA to use the backdoor, though he fails to mention that.
That section is actually surprisingly straight talk from RSA Security Executive Chairman Art Coviello. "We are all completely incompetent here at RSA Security". Not that I believe him anyway - somebody at RSA Security has to have known.