A Patent From 2004 Describes Dual EC As Key Escrow

Been waiting a little while for this one to come out.

Key escrow schemes were the establishment answer to the problem of crypto enabling crime. The idea was that strong crypto would be outlawed, and the government would instead provide regulated crypto that would include overt backdoors for lawful access. Thankfully, that idea perished in the crypto wars of the '90s.

One line of reasoning about Dual EC, the PKRNG that is believed to be the backdoor referenced by the NSA BULLRUN leak, is that it could have been innocuous and suffering merely from bad optics: while there would in the universe be ECC points that would allow attackers to "decrypt" random numbers and recover PKRNG state, those numbers had been generated and discarded honestly.

The presence of this patent and its explicit claims on key escrow applications grievously harms that argument. It's circumstantially but potently damning.

For whatever it's worth to you: while I don't believe that it had much real-world impact (I think pretty much exactly what Lucky Green said about Dual EC in the most recent Reuters discussion), I'm 99% convinced Dual EC was intended as a backdoor. There is at least one scenario where it actually made sense in practice --- that is, where it could plausibly have been deployed.

The PKRNG "escrow" scheme is especially damning, because it's intrinsically surreptitious. Conventional key escrow schemes presume that all users know their keys are escrowed. A PKRNG escrow scheme kicks in even in systems that assume they aren't escrowed. It's an evil idea.

There is at least one plausible (though I think dumb) argument for PKRNG (it allows you to compose a whole cryptosystem in terms of a smaller number of primitives --- if you need the PK primitives anyways, it might be nice in a formal sense to have the CSPRNG rely on those same primitives). But there are no practical arguments in favor of a CSPRNG having PK structure. CSPRNGs based on stream ciphers, for instance, regularly rekey: their outputs aren't all bound under a static root secret. PKRNG is such a goofy idea that it was hard to take it seriously as a backdoor to begin with.

If the whole Twitter thread doesn't pop up for you like it does for me, here's the link to the actual patent:

http://www.freshpatents.com/Elliptic-curve-random-number-gen...

Tanja Lange makes another devious point: since ECC PKRNGs are patented, there's a financial disincentive to ever using alternate parameters for it, because tuning your ECC PKRNG and using (presumably) non-backdoored points could result in your system being royalty-encumbered. Man. Ick.

See this ladies and gentlemen?

This is why you don't patent stuff that's supposed to be secret, regardless of what other people think

Why didn't you come out with it?

I imagine professional courtesy, it's considered incredibly rude to disclose another researchers discovery before they've announced it.

> The secret was kept despite being available in OSI (if one knew where to look).

Not the first time something like this happens