[Cryptography] Dual_EC_DRBG backdoor: a proof of concept

[John Kelsey]

On Jan 3, 2014, at 12:39 AM, ianG <iang at iang.org> wrote:

> * They know more about RNGs than we do -- it was them that pushed NIST in the direction of a deterministic output whitener/expander, the DRBG.  Until this came along, I don't think it was an understood concept, the open world was still working on the premise that we didn't want determinism.

No, Niels and Bruce and I were doing this in Yarrow-160 long before X9.82, and it was also how the RSAREF, ANSI X9.17 and DSA prngs worked even earlier.  I published a paper with Bruce, Niels, and Chris showing how this kind of PRNG can be attacked long before X9.82 had started, too.  This was one of about three models for doing random number generation floating around--alongside pool type designs like dev/random and hardware RNG designs.

> * They have 70 years of practice at sabotage.  It's their job.  They have the advantage when it comes to thinking like an attacker.

Right, but the apparent sabotage of dual ec drbg wasn't all that subtle--it involved getting on the standards editing committee, and being trusted by the other members of that committee.  In a world where lots of people (including me) thought they were working to make public crypto stronger, not weaker.  Putting a backdoor in a standard they worked on involved spending all the goodwill and trust they had built up over the last decade or more, with consequences that will go a decade or two into the future.  

> * They are known to attack the RNG.  They attacked Crypto AG's RNG, as Dave pointed out.  Spooks attack RNGs, nobody else does.  

That sounds silly to me.  Attackers use what they can find.  The NSA attacks that have come out aren't some kind of black magic, they're the same kind of stuff done by (or suspected of) other attackers, just with more resources.

> In complete contrast, we just don't get that practice.  I do not know of any real attack where someone has spiked the RNG in our open/commercial domain [0].  

There have been a lot of flawed
RNGs in the literature.  Were any intentional, or accidentally created but left in as a backdoor?  If so, by whom?  Absent an attack of conscience along the lines of Manning or Snowden, how would we know?  

> iang

--John