A Patent From 2004 Describes Dual EC As Key Escrow

https://twitter.com/eqe/status/417035396044697600

by tptacek • 13 years ago

109 39 13 years ago

tptacek8• 13 years ago

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.

JasonPunyon3• 13 years ago

Why didn't you come out with it?

maaku2• 13 years ago

Just speculating, but maybe he is a U.S. person justifiably concerned about sticking out his neck?

ig1• 13 years ago

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

tptacek8• 13 years ago

What a weird question.

acqq3• 13 years ago

http://security.stackexchange.com/questions/43164/which-prod...

Dual_EC_DRBG is actually used in real life products:

we know the RSA BSAFE library uses Dual_EC_DRBG (...) by default, I would guess that this would be the main vector. As for the use of BSAFE, I can easily find (hint: use your favourite search engine to search for the terms "This product includes" "RSA BSAFE") implementations, oddly skewed towards imaging and gaming devices: surprisingly many printer/copier/fax devices use BSAFE, though for unknown purposes. Including Ricoh, Minolta, Océ/Canon, Brother, Fuji/Xerox, Epson ... Your Playstation (PDF), PSP, or your Nintendo DS wifi (PDF) Software from Adobe, Hitachi, Oracle and HP Some Nokia phones(PDF)

tptacek8• 13 years ago

Once again, the easiest way for me to explain my thoughts about this is to refer back to Lucky Green. It's linked from the Reuters thread on HN.

pbsd• 13 years ago

Avoiding the backdoor does not require changing the points (and possibly getting in patent trouble). Even with malicious points, truncating enough bits out of each x coordinate is enough to thwart the attack. I don't know why this is not pointed out more often.

I'm honestly far more surprised by finding out that another factorization-based (Micali-Schnorr) DRBG standard comes with 'default' public keys.

Zigurd2• 13 years ago

Thankfully, that idea perished in the crypto wars of the '90s

Did Lotus Notes ever get rid of key escrow? IIRC they used BSAFE.

quasse• 13 years ago

Here's a link to the Google Patents page: http://www.google.com/patents/US8396213

Relevant lines are "Intentional use of escrow keys can provide for back up functionality. The relationship between P and Q is used as an escrow key and stored by for a security domain. The administrator logs the output of the generator to reconstruct the random number with the escrow key."

raverbashing3• 13 years ago

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

gwern• 13 years ago

So? No one mentioned this before Snowden that I ever saw. The secret was kept despite being available in OSI (if one knew where to look).

raverbashing3• 13 years ago

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

Not the first time something like this happens

adestefan• 13 years ago

It's actually possible to file a patent along with a secrecy order. This is done to protect the government in case someone else ever tries to patent the same idea at a later date. And before someone freaks out, this is not new. It was imposed during WW I, WW II, and then codified in the Invention Secrecy Act of 1952.

sanxiyn• 13 years ago

In particular, patent GB630726 by Leo Szilard, Producing neutrons, covering nuclear chain reaction, was one such secret patent. I think it probably was a good idea to keep that secret.

midas007• 13 years ago

More reading: https://www.fas.org/sgp/othergov/invention/program.html

raverbashing3• 13 years ago

Thanks for the information

But is this still needed since the government can bypass patents based on national security issues?

meowface• 13 years ago

Interestingly, the patent even mentions the actual use case:

Therefore, if the ECRNG is used to generate the encryption key K, then it may be possible that the escrow key e can be used to recover the encryption key K. Escrow keys can provide other functionality, such as for use in a wiretap. In this case, trusted law enforcement agents may need to decrypt encrypted traffic of criminals, and to do this they may want to be able to use an escrow key to recover an encryption key.

casca• 13 years ago

This patent was originally owned by Certicom, now part of Blackberry. One of the inventors was Scott Vanstone who's excellent book, Handbook of Applied Cryptography lives on my desk.

The patent seems to indicate that Dual EC is known to be usable for escrow, something that the NSA surely knew. But given the pedigree of the authors, it must have been known by a bunch of other people well before the March 2013 publication date.

There's something odd going on here.

Zigurd2• 13 years ago

But given the pedigree of the authors, it must have been known by a bunch of other people well before the March 2013 publication date

Unfortunately I cannot recall the details of key escrow as it was implemented in Lotus Notes. It is a fact Notes used BSAFE. And it appears to be true that key escrow, or key recovery, was an intentional feature of this RNG. But I did not learn, at the time, how key escrow was implemented in Notes.

middleclick• 13 years ago

Can anyone please explain what this means for someone who doesn't understand crypto?

owenmarshall2• 13 years ago

http://crypto.stackexchange.com/questions/10417/explaining-w... does a great job.

bm1362• 13 years ago

I'll give it a shot, but I have absolutely no experience with cryptography.

I found this video to help explain the concept:

http://www.youtube.com/watch?v=ulg_AHBOIQU&feature=c4-overvi...

The relationship between P and Q (two points on the elliptic curve, see the video) allows someone to predict the RNG behavior. This is alleged to be used by the NSA, and the paper above predicts this relationship being used to provide an escrow-like ability for a 3rd party to access encrypted data.

Someone please correct me if I am wrong, as I would like to further my understanding as well.

this_user• 13 years ago

Here's the video of the talk from 30c3 that I assume was referenced: http://www.youtube.com/watch?v=G-TM9ubxKIg

It's actually worth watching if you haven't been closely following all of the crypto related revelations this year.

A Patent From 2004 Describes Dual EC As Key Escrow

Related Stories