[Cryptography] Dual_EC_DRBG backdoor: a proof of concept

[ianG]

(apologies, late reply, had to think about it!)



On 3/01/14 22:45 PM, John Kelsey wrote:
> 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.


OK, I stand corrected!  I'll have to see if I can find that reference to 
NSA saying using a non-deterministic RNG is a state of sin.


>> * 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.


If you are going to sabotage a standard, then it pretty much involves 
being ... at the meetings, and wielding power to direct efforts.  This 
might not involve much pushing, or it might involve a lot of pushing.

For example, the GSM committees that designed their A3, A5 algorithms 
were pushed, but only gently.  Spooks were at some meetings, but they 
said little.  As they were all telcos at heart, and as their threat 
model was paparazzi snooping and billing theft, and as they were 
Europeans and traditionally were in bed with the agencies, they really 
didn't care that much.  Only a small amount of pushing was required to 
set the key at 40 bits, the famous 8 * 0 bytes plus the 
checksum-of-deception copied from DES.

An open group preparing standards for open industry has much broader 
threat models.  GSM had theirs quite clear and narrow, vertically 
integrated, but when you are building a general tool, you have to more 
or less consider every threat ... or you have to come up with a stylised 
perfect design model (like SSL did with their perfect secure connection).

Then, influencing such a group as a NIST committee requires a lot less 
subtlety and a lot more deception.  And taking much bigger risks.


> 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.


Right.  You might ask why they took that risk.  What we do know is that 
they take these risks, in general, they have the mindset, it is here, in 
black and white:

http://financialcryptography.com/mt/archives/001455.html
http://financialcryptography.com/mt/archives/001458.html

Why did they take that particular risk?  (assuming they did?)  knowing 
or should-knowing that the consequences would be disastrous?  For that I 
guess we have to look at the history of the last decade.

One open question is whether they took that risk particularly with 
NIST/DUAL_EC, as asked by Jon and you and many others.

That's a judgement call, we'll 'know for certain' in 50 years when they 
declassify.  Until then ... what matters is that they are taking that 
risk, in general, everywhere they can.

So we have to act "as if" the NIST standards are under attack.

This is a useful thing, as it also has consequences.  It protects the 
NSA from blundering again -- if they know we all act "as if" the NSA is 
going to pervert the NIST standards, then they are much less likely to 
do it.  OTOH, if we act "as if" this is unlikely, silly, implausible, 
unsubtle or whatever, then the prize is sitting there .. they are more 
likely to give it a go.


>> * 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.


Yes, interesting counterpoint:  the Android/Java RNG hack to steal bitcoins.



iang