A Patent From 2004 Describes Dual EC As Key Escrow(twitter.com)
twitter.com
A Patent From 2004 Describes Dual EC As Key Escrow
https://twitter.com/eqe/status/417035396044697600
40 comments
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.
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.
> 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.
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.
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.
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.
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)
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)
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.
Still it's misleading when you present it as something not important "because it's not used"! It is used. You don't give any arguments against that fact. Especially if we're serious about the crypto we shouldn't hand-wave but analyze the existing uses and take the steps to fix the issues.
Your insistence to the approach "nothing to see here move along" even after everything discovered up to now makes me wonder about your motives. Care to explain them? Almost as if there is even more that can be seen if we try to and you want to prevent that.
Your insistence to the approach "nothing to see here move along" even after everything discovered up to now makes me wonder about your motives. Care to explain them? Almost as if there is even more that can be seen if we try to and you want to prevent that.
Can you tell me why I'd care what you think of my motives? The question makes me think less of you already. Maybe we're better off not knowing each other any better.
We as humans try to find the patterns and discover the causes. My question to you was nothing more than the attempt to get the direct information regarding your insistence to the unusual approach (repeating the claims that it's unimportant, ignoring the explicit examples of the uses of the compromised mechanism) to the topic we comment to. My question reflects my (maybe false) belief that there must be a reason for that. I believed it's better asking you directly than trying to devise some theories like some other users already did.
"I'm just questioning your motives. At least I didn't present a fully-formed hypothesis about how evil you were, like everyone else does". Got it.
How about this: if you think I get facts wrong or disagree with my conclusions, you say so. If I'm wrong --- not outside the realm of possibility --- I'll thank you for the correction.
I don't care what you think about my motives and am not interested in discussing that topic.
How about this: if you think I get facts wrong or disagree with my conclusions, you say so. If I'm wrong --- not outside the realm of possibility --- I'll thank you for the correction.
I don't care what you think about my motives and am not interested in discussing that topic.
Alright kids, hug it out
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.
I'm honestly far more surprised by finding out that another factorization-based (Micali-Schnorr) DRBG standard comes with 'default' public keys.
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.
Sorry. I interpreted tptacek's first line as that he'd known about the patent and what it contained independently for "a little while". (It was a patent after all. Isn't that public information?)
Or was the news not the existence of the patent referenced on the tweet?
Or was the news not the existence of the patent referenced on the tweet?
I can't speak for tptacek, but what I think he means (when he says "Been waiting a little while for this one to come out.") is that he's been waiting a while for confirmation that Dual EC was explicitly designed as an RNG with an escrow system.
I don't think he meant that he knew about it - instead, he was saying that there was evidence to be found that would demonstrate this.
But I'm not tptacek, so who knows what he really means.
I don't think he meant that he knew about it - instead, he was saying that there was evidence to be found that would demonstrate this.
But I'm not tptacek, so who knows what he really means.
Just speculating, but maybe he is a U.S. person justifiably concerned about sticking out his neck?
What a weird question.
The first sentence of your post could be interpreted to mean that you knew about this for "a little while" but decided not to inform the rest of us, in which case I don't think it's that weird to ask "why didn't you tell us?"
Because I wasn't at liberty to.
Then why did you answer "What a weird question" instead of just saying so?
What other answer could there have been?
The initial comment was possibly ambiguous as to whether you had known about this specific thing.
Even after that is clarified, it could have been professional courtesy rather than 'not at liberty', and possibly other reasons would have worked too.
Even after that is clarified, it could have been professional courtesy rather than 'not at liberty', and possibly other reasons would have worked too.
[deleted]
It was the same question I had, in good faith, when I read your comment. In fact, it over rode (in my mind) everything else you wrote - I kept asking myself, "Why was he waiting for it to come out? Did he discover it, and not tell other people? Was he wondering whether this existed, but had not found it? Did he have a colleague tell him they were onto something, and he was waiting for them to publish. Has he known all about this the entire time, and was waiting for the other shoe to drop?"
To some degree, that one sentence, by itself at the head of your comment, captured all of my attention.
To some degree, that one sentence, by itself at the head of your comment, captured all of my attention.
Again, this is so weird. But: ok.
I'm absolutely certain that my brain is just fundamentally misreading your first sentence.
> Thankfully, that idea perished in the crypto wars of the '90s
Did Lotus Notes ever get rid of key escrow? IIRC they used BSAFE.
Did Lotus Notes ever get rid of key escrow? IIRC they used BSAFE.
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."
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."
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
This is why you don't patent stuff that's supposed to be secret, regardless of what other people think
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).
> The secret was kept despite being available in OSI (if one knew where to look).
Not the first time something like this happens
Not the first time something like this happens
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.
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.
Thanks for the information
But is this still needed since the government can bypass patents based on national security issues?
But is this still needed since the government can bypass patents based on national security issues?
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.
It's actually worth watching if you haven't been closely following all of the crypto related revelations this year.
Can anyone please explain what this means for someone who doesn't understand crypto?
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.
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.
>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.