Dual_EC_DRBG Backdoor: a Proof of Concept

New submitter Reliable Windmill sends this followup to the report that RSA took money from the NSA to use backdoored tech for random number generation in encryption software. From the article: "Dual_EC_DRBG is an pseudo-random number generator promoted by NIST in NIST SP 800-90A and created by NSA. This algorithm is problematic because it has been made mandatory by the FIPS norm (and should be implemented in every FIPS approved software) and some vendors even promoted this algorithm as first source of randomness in their applications. If you still believe Dual_EC_DRBG was not backdoored on purpose, please keep reading. ... It is quite obvious in light of the recent revelations from Snowden that this weakness was introduced by purpose by the NSA. It is very elegant and leaks its complete internal state in only 32 bytes of output, which is very impressive knowing it takes 32 bytes of input as a seed. It is obviously complete madness to use the reference implementation from NIST"

Comments

Bah

[colinrichardday]

Who can you trust?

Re:Bah

[1s44c]

Theo de Raadt.

OpenBSD is trustworthy but you have to be suspicious of the BIOS it runs under and every network it connects to.

So just like xorshift64 then

[Anonymous Coward]

xorshift64 is a simple random number generator with a period of 2**64 - 1 (you cannot use 0).
The 64 bit random number that it produces is the same as its complete state.

How long until someone cracks the backdoor key?

[gman003]

Actually read TFA, enough flew over my head that I can't personally verify the math, but if true, well holy fucking shit. Once someone brute-forces the backdoor "key" used by the NSA, it looks like the entire system is cracked. Even if it takes a while to brute-force, once you have that you can open any encryption using that curve.

Given that cracking this open would be so useful to both other monitoring agencies, and to criminal hackers, it's sure to happen eventually, if it hasn't already. I'm sure China could throw one of their supercomputers at it.

I'd be curious to know just how hard it would be to brute-force the backdoor key itself. There didn't seem to be anything in TFA about that, and I can't figure out the math myself.

Re: OpenBSD

[Richard_at_work]

No, because OpenBSD doesn't just use this PRNG as the source of randomness for its encryption implementations, it has used other sources mixed in for a long time. There was a recent story about FreeBSD switching to other sources and De Raadt being all cocky about other people finally doing what OpenBSD has done for years.

Re:Amish

[cold fjord]

shun anything electronic, or electric for that matter. Substinance farm and read dead-tree books for leasure.

Spooked by NSA, Russia reverts to paper documents
Kremlin returns to typewriters to avoid computer leaks

Only one of the many "benefits" from the leaks, not to mention:

Snowden revelations lead Russia to push for more spying on its own people