Slashdot Mirror
Are the NIST Standard Elliptic Curves Back-doored?
IamTheRealMike writes "In the wake of Bruce Schneier's statements that he no longer trusts the constants selected for elliptic curve cryptography, people have started trying to reproduce the process that led to those constants being selected ... and found it cannot be done. As background, the most basic standard elliptic curves used for digital signatures and other cryptography are called the SEC random curves (SEC is 'Standards for Efficient Cryptography'), a good example being secp256r1. The random numbers in these curve parameters were supposed to be selected via a "verifiably random" process (output of SHA1 on some seed), which is a reasonable way to obtain a nothing up my sleeve number if the input to the hash function is trustworthy, like a small counter or the digits of PI. Unfortunately it turns out the actual inputs used were opaque 256 bit numbers, chosen ad-hoc with no justifications provided. Worse, the curve parameters for SEC were generated by head of elliptic curve research at the NSA — opening the possibility that they were found via a brute force search for a publicly unknown class of weak curves. Although no attack against the selected values are currently known, it's common practice to never use unexplainable magic numbers in cryptography standards, especially when those numbers are being chosen by intelligence agencies. Now that the world received strong confirmation that the much more obscure and less widely used standard Dual_EC_DRBG was in fact an NSA undercover operation, NIST re-opened the confirmed-bad standards for public comment. Unless NIST/the NSA can explain why the random curve seed values are trustworthy, it might be time to re-evaluate all NIST based elliptic curve crypto in general."
As well as reviewing the standards themselves, I hope someone is reviewing the processes which allowed these weaknesses to get into the standards.
This shit will not end until this country is bankrupt completely, or taken over (from within or without).
Silence is a state of mime.
Color me ignorant, but could someone please explain that elliptic curve is more secure than RSA? Wikipedia even claims that a 128-bit EC key is equivalent to 3072-bit RSA key. Even if it's computation complexity brute forcing discrete log or integer factorization on a non-deterministic turing machine, it should differ by no more than a small constant factor, e.g. 512-bit versus 1024-bit, not by O(sqrt(n)) as Wikipedia claims. Wikipedia is simply quoting NSA.
I once had a signature.
Why are people even asking if it's been backdoored? It's already established that no one can explain the constants. It hasn't been shown to not be backdoored. That's enough to prove beyond the shadow of a doubt that it's wrong. Arguing about whether the standard is compromised by mere incompetence or malice, isn't worth spending time on.
If you don't know something is done right, then that alone is irrefutable proof that it has been done wrong. Even if they're good constants.
" Now that the world received strong confirmation that the much more obscure and less widely used standard Dual_EC_DRBG was in fact an NSA undercover operation,"
What confirmation? Really I fear slashdot has become pure click bait.
See my blog http://ilovecookes.blogspot.com/ for light hearted technical information.
The essence of what the NSA did, was to replace cryptographic security with security through obscurity. People who haven't found the back door yet don't know its there. Classic 'security via obscurity' that is the opposite of crypto.
Now everyone knows they're there, we need to replace them damn fast. Waiting for the backdoor to be verified is too late, by then bad actors (I mean ones other than General Alexander) could already have found it.
Replacing these takes time, and so the assumption should be they are vulnerable, because the NSA leaks show the NSA knows they are vulnerable, even if we don't quite know the micro detail of how, yet.
... A list of people had to be complicit in getting these "magic backdoor" numbers into the standards. The integrity of these people is now highly questionable
This, and many other expose, can only come to light, because of the courage of a single person - Mr. Edward Snowden.
If not for Mr. Snowden, would we ever discover the phenomenon of the "magic number" ?
If not because of Mr. Snowden, we wouldn't even begin to question the integrity of those previously highly regarded "very important people".
If not for his courage, how much more damage all of us have to suffer ?
And yet, inside the United States of America, there are still people equating Mr. Snowden as though he is a traitor.
And even here in Slashdot, we have posters posting very stinging attack on Mr. Snowden.
Our country is under attack, and the attacker is our own government, but yet, there are still Americans who will do everything to help deepen the tyranny, all in the name of "patriotism".
I, an American citizen, do owe my deepest thanks to Mr. Edward Snowden, and I do hope that more of my fellow Americans should start acknowledge something very very wrong has happened to America, the country we love so much, and that we should start doing something together, to RIGHT THE WRONGS.
There have been too many comments that essentially convey the message that we, the People of America, have no power to determine our own future, and that our government, is so overwhelmingly powerful that we are ready to become their slaves, rather than stand up and oppose the tyranny.
Is America still the land of the free, and the home of the braves ?
Or has American turned into the land of the enslaved, and the home of the cowards ?
The choice is on your hand, my fellow Americans.
Either we start righting the wrongs now, or we will end up handing over to our children a country of tyranny.
Are we going to let our children suffer because of our cowardice ?
You are the only one who can answer the question.
Muchas Gracias, Señor Edward Snowden !
Bitcoin uses what the SEC calls a Koblitz curve (secp256k1) for which there is much less design freedom and it seems much less likely that there is any way to back-door those curves. Unfortunately many ECC implementations don't support all the curves, just a few of the plain vanilla random ones. Actually I'm not aware of anything except Bitcoin that uses secp256k1.
Dear NSA,
Since I'm getting tired of these stories and it seems kind of unfair that you're getting all the heat recently, here is my suggestion how you could improve your PR image by doing something to our mutual benefit:
Please use your supercomputers for a few months to aggressively mine Bitcoins and Litecoins. That would make you (virtually) richer than you already are and free me and the rest of the world in future from annoying Bitcoin-mining stories.
If you like this idea, consider donating some Bitcoins to me. You know where to find me.
Thank you for your attention and best regards,
aaaaaaargh!
"secp256r1" just so happens to be the combination to my luggage.
I guess I should change that.
This shit is evidence that this country has *already* been taken over (from within and without)
Isn't it time we, the American Citizens, take back our own country from those fuckers ?
How much longer should we let those fuckers to ruin our country ?
How much longer do we want to be fooled by those fuckers ?
How much longer can our country last, under those fuckers ?
Muchas Gracias, Señor Edward Snowden !
The darker crypto history of the 1950-80's would point to long term weak export grade devices.
Why this generation of software and hardware would be allowed to be any different seems to have escaped a few people.
First the govs look at the private leadership, the firms, the brands - help stop communists....
If that fails, go for longterm staff with issues.
If that fails, set up a gov backed front company or standard out spending and undercutting any emerging private experts.
Looking back why did so few not see the lack of public gov interest after US crypto exports laws became more open (after public key cryptography?)
All the world was presented with was vague whispers of way too much unencrypted data with optical, internet and mobile phones...too expensive, too difficult..
The govs appetite never changed and funding in the past ~10 years was epic.
Domestic spying is now "Benign Information Gathering"
I think we are all going to have to be a lot more paranoid from now on about the public comments NIST gets on crypto standards. We can count on NSA to continue to try to mess with the standards, but they won't do it openly. They'll use proxies with no traceable connection to NSA. The crypto experts will have to examine these things a lot more carefully. Hanlon's razor won't cut it anymore.
The difference boils down to factoring integers versus computing discrete logarithms in elliptic curve groups. The best publicly known integer factorization algorithm is GNFS which runs in roughly O(2^(n^1/3)), whereas the best publicly known ECDLOG algorithm runs in O(2^(n^1/2)). That is why we need RSA keys that are so much larger than ECC keys.
That, of course, is a theoretical argument. In practice, there are other issues to consider. ECC has a lot of parameters and there are a lot of constraints on the curve you choose; this means there are a lot of things to get wrong. RSA is not technically secure on its own (and the construction used to make it secure is easy to get wrong), but related systems like Blum-Goldwasser (which is based on a related problem, the Quadratic Residuosity Problem) are and they have many fewer parameters. The code for such systems is also simpler, which makes it more straightforward to audit (and harder to hide backdoors).
Palm trees and 8
I was going to submit the same story. I'm glad I didn't; that summary is much better than what I had in mind. Nicely done, Unknown Lamer, IamTheRealMike, and any other editors who helped. Thank you for your effort on this important topic!
Stop-Prism.org: Opt Out of Surveillance
I only see people discussing the first-level implications to privacy and security of the NSA having chosen parameters that lead to a somehow-weak curve. Except - That doesn't take any special NSA magic, they just cheated up front.
Such discussion completely overlooks the much bigger problem here, however - The NSA chose parameters that give a weaker curve. Parameters generated as the output of hashing them with SHA1.
The ability to choose parameters strongly suggests that the NSA has a way to produce input texts that yield a desired SHA1 hash. That takes special NSA magic, and should really count as the FP story here, not the far less impressive trick of stacking the deck in their favor.
Ken Thompson's article "Reflections on Trusting Trust" seems to apply here.
http://cm.bell-labs.com/who/ken/trust.html
Even if the numbers are corrected, we have no guarantee that a lower-level system isn't undoing that work. Backdoors can (and probably do) exist in not only compilers, but in hardware. If this is the case, then broken encryption parameters are far less important. For example, git uses SHA1 for encryption. Assuming the scheme isn't already broken, it is likely possible to generate a collision with brute-force (especially if you need only one number). If some link in the git chain were thus broken, a replacement file with a backdoor payload could be injected (eg. in the confusion surrounding the gnu.org repos being hacked). As ken points out, once that initial injection is made (assuming it is of sufficent quality) it can be used to add anything to future compiled versions.
We need community and built and vetted algorithms, easy and in-built encryption that doesn't rely on a "trusted" third party infrastructure, e-mail encryption that just works, zrtp for all voice communications on by default, and a genuinely locked down android system with firewalling.
There are a lot of Google services we rely on that can be replaced with decentralized community replacements. Clearly, Google is working for the enemy. Clearly, Facebook is working for the enemy. Here we can look to TOR and Bitcoin for hints on how these kind of decentralized systems can work.
These days most of this starts with our phones. So we need a solid and secure community vetted android system that becomes the basis for all those root your phone/tablet guides in the world.
"Trust" has not been lost, but paranoia seems to be alive and well. Unless you can actually illustrate a possible attack (in the case of ECC the issue was that the PRNG could be hosting a public key as one of its magic numbers which would allow it to be predicted) then your just jumping at ... something less then a shadow.
There seem to be an awful lot of people with no cryptography expertise making grandiose statements, some probably running off to implement their own crypto which will be "NSA free" and so hilariously broken that if you had to pick a social-engineering attack to catch terrorists then this would be a good one.
So for the NSA to kick out the really problematic implementations, the really secure ones, those they didn't find a backdoor in yet, the NSA will just recommend them?
Has anyone checked out Russia's GOST standard Elliptic Curve cryptography standards to see if choice of seeds is a widely known way of weakening crypto?
Or could it be that the Russian standard is actually more secure?
The GOST Elliptic curve standards have been translated to English in RFC 4357 and 5832 http://tools.ietf.org/html/rfc4357 and http://tools.ietf.org/html/rfc5832
Kudos to IamTheRealMike for such an informative and well written summary.
Thank you Mr. Taco Cowboy (if that's your real name). The FBI should be visiting soon. Please hide your dogs, for their own sake.
Almost every single time I posted a comment that hits the bull's eye someone would counter it with a veil threat, like the above.
FYI, they know who I am.
I came from China, I am a naturalized citizen of the United States of America, and I am currently not living inside the U.S. of A.
In my younger days, I also was involved in some (still secret) military programs.
They have my dossier. They know where I am.
If they want to take me down, they can, any time.
But I am not important. I am expendable.
What is important is the future of my country, the United States of America.
As I said, I came from China, I had had first hand experienced the terror of Tyranny, with a capital "T".
What I, and millions of my former comrades in China had suffered through, I would NOT want you guys in America to go through.
The terror of Tyranny is much more than any Hollywood movie could ever convey.
Go ahead, threatening me more, if that is the thing that makes you feel good.
I have gone through the baptism of hell back when I was in China, death is nothing to be afraid of.
As I said, I am expendable, but the United States of America is not.
Muchas Gracias, Señor Edward Snowden !
I linked to that RFC for the text in the introduction section, from which I got the "chosen ad hoc" language. My point is not to cast suspicion on all ECC, which is a valid mathematical technique developed in the open by civilian academics. But rather, to provide more evidence for the fact that nobody seems to know how the seed values were generated (we know WHO generated them, but not HOW).
Is there anything really magic about those magic numbers, or are they just random numbers generated by a true RNG? If that's the case, why not just have Bruce Schneier or other trusted non-government party generate new ones? Or have a dozen trusted parties generate RNGs by a variety of methods (commercial RNG, home made RNG, monkeys typing on a keyboard, etc) and hash them all together to make the constants?
Since these constants are apparently known and part of the spec, is there any reason they can't be shared with encrypted files? Everyone can use their own magic numbers when they encrypt data.
But what we do know from the Snowden documents is that the NSA can not be trusted to obey the law. Anyone working in cryptography, particularly developing interoperability standards, should categorically reject the participation of any government officials in the standards process.
-jcr
The only title of honor that a tyrant can grant is "Enemy of the State."
To give everyone a laugh at libertarian nerds who thought it was a great idea to invest in it.
NIST is also required by statute to consult with the NSA.
NIST: "Here's what we are going to do."
NSA: "But, but, but......."
NIST: "Now fuck off and die. You have been consulted with."
Its either that or NIST should be out of the encryption standards loop.
Have gnu, will travel.
There is no effective, trustworthy, publicly available encryption. And I've been reliably hammered by the moderators and commenters for it on a steady basis..
GOD! I hate it when I'm right!
“He’s not deformed, he’s just drunk!”
Yep, because, obviously you are expert, we should what, believe you? Pleeease, done make mu laugh.
No one knows who Satoshi is. For all we know the NSA is Satoshi and Bitcoin is a NSA opperation.
Agree: make a new fully open process, open source encryption system, fully peer-reviewed, global internet participation possible, just like the Linux kernel.
Perhaps, like kernel.org, there can be FOE.org (Fully Open Encryption dot org) created.
Then that can be collaborated on via git, the developer community, and the security community. ...just my two cents.
Uh, Linux geek since 1999.
http://it.slashdot.org/story/07/11/15/184204/new-nsa-approved-encryption-standard-may-contain-backdoor I remember at the time it seemed to be confirmed that there IS a backdoor. The question of weather anyone knew the magic numbers to open that door seemed obvious at the time as well - the NSA chose the numbers. It would go against everything they stand for NOT to have the keys.
Side note: Contrary to what some folks claim, this does not make the system weak against any foreign enemy, criminals, or hackers. It makes it weak only to the NSA so long as no one else discovers the master key. Not that this makes it ok, just not as bad as some claim.
There may be a solution to the NSA problem:
Make a new fully open process, open source encryption system, fully peer-reviewed, global internet participation possible, global peer review possible.
Use the development of the Linux kernel as a model. Use the global participation of Debian as a model.
Perhaps, like kernel.org, there can be FOE.org (Fully Open Encryption dot org) created.
Then that FOE system and software can be collaborated on via git, the developer community, and the security community. ...just my two cents.
Uh, Linux geek since 1999.
'And even the numbers themselves shall bow down to our suzerainty.'
here are now also an awful lot of people with lots of cryptography expertise running off to implement their own crypto, which will be "NSA free" and peer reviewed. Some of them will be hilariously broken - as all new crypto is assumed to be, quite appropriately - and some will survive scrutiny.
Paranoia motivates review. That is a good thing. Thus, anyone who scoffs at paranoia simply sounds like an NSA shill. Did the NSA buy you lunch for your post, Electricity Likes Me? :)
The US government is the most untrustworthy government - except for all the others.
:(
You'd think that, but the people in charge understand "domestic enemies" to mean the American people.
Keep your eyes to the sky.
wonderful, curves with constant parameters chosen by the KGB would be so much superior.
I have been following the NSA revelations with keen interest. I am not a cryptologist. Advanced math escapes me. But I have understood enough to know that the NSA has been poisoning the well for our entire society. They, not Al Qaeda, not Iran, not China, pose the most existential threat to American freedom and the ability of my kids to grow up in peace. So I ask my fellow Americans and freedom-loving foreigners alike, can we not resolve to resist and bring down these criminals in any way we can? Whether it's better encryption, darknets, ostracism of the actual flesh-and-blood human beings practicing this tyranny on the rest of us, or many, many other measures, can't we all commit to doing what we can, where we can, to putting an end to them?
Do what you can, with what you have, where you are.
If all you want is random, you can get that (at a slow rate) from any geiger counter. Or from a hot diode. Or from many other places.
It's my understanding that these numbers aren't supposed to just be random, but to have some other important properties...probably not being prime, though that may be a part of it.
I think we've pushed this "anyone can grow up to be president" thing too far.
" it's common practice to never use unexplainable magic numbers in cryptography standards"
you don't need those last three words.
The Kruger Dunning explains most post on
Aside from going back to RSA with really large key sizes, what other options are there? Shamus Standard Curves were mentioned (here) but they seem to be obscure, to the point of not yet being within open source crypto, like PGP. Do we have open standards which the NSA hasn't touched?
See http://www.reddit.com/r/Bitcoin/comments/1m6twq/no_way_to_reproduce_some_key_numbers_used_in_the/cc6bfqb
:-)
Rudd-O - http://rudd-o.com/
How would that affect Ellictic Curve Diffie-Hellman Exchanges, which are the current preferred way to obtain Perfect Froward Secrecy (which means leak of the server private key does not help deciphering previously stored communications) in TLS?
Is it better to use slower DHE-RSA after all?