Six Cryptographers Whose Work on Dual EC DRBG Were Deemed Without Merit by RSA C...

"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 speech

Three things about Art Coviello's keynote speech today jumped out at me:

1. He attempted to paint NSA as the sole bad guy in the Dual EC DRBG debacle. 
2. 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.
3. He believed that the published warnings of six independent and respected cryptographers in 2006 and 2007 had no merit.

It's the last bullet point that this blog post is about. I've listed the research papers published in 2006 and 2007 which described the same weakness (aka backdoor) in Dual EC DRBG; the encryption algorithm that the NSA was pushing for RSA to incorporate into its BSAFE product as a default in 2004. This body of work is what Coviello chose to ignore at the time and for another six years until The New York Times broke the story in September 2013; the same body of work that Coviello today was referring to when he said "that concerns raised in 2007 might have 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.
[email protected], [email protected]
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.