November 2007

Dual_EC_DRBG Back Door?

Bruce Schneier reports that one of the pseudo-random number generators in the recently released NIST Special Publication 800-90 (.pdf) appears to include something that looks awfully like an intentional back door:

What Shumow and Ferguson showed is that these numbers have a relationship with a second, secret set of numbers that can act as a kind of skeleton key. If you know the secret numbers, you can predict the output of the random-number generator after collecting just 32 bytes of its output. To put that in real terms, you only need to monitor one TLS internet encryption connection in order to crack the security of that protocol. If you know the secret numbers, you can completely break any instantiation of Dual_EC_DRBG.

It's possible that this is accidental; if it is deliberate, the prime suspects are the NSA, who have been pushing to get this algorithm adopted for some time. So much for the usual outsider's paranoia about how the evil TLA might be compromising our cryptography for their own nefarious ends. That's not the scary part, though; the really scary part is the thought that perhaps that isn't what is going on:

If this story leaves you confused, join the club. I don't understand why the NSA was so insistent about including Dual_EC_DRBG in the standard. It makes no sense as a trap door: It's public, and rather obvious. It makes no sense from an engineering perspective: It's too slow for anyone to willingly use it. And it makes no sense from a backwards-compatibility perspective: Swapping one random-number generator for another is easy.

Shumow and Ferguson's presentation (.pdf) is short, and although there are some squiggly letters in it you don't need to understand the mathematics of elliptic curves to follow the argument.

I look forward to seeing how this one plays out.

(Via Schneier on Security.)