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."
it's common practice to never use unexplainable magic numbers in cryptography standards, especially when those numbers are being chosen by intelligence agencies.
Well then, how do we explain the common practice of using magic numbers in cryptography standard, then?
As well as reviewing the standards themselves, I hope someone is reviewing the processes which allowed these weaknesses to get into the standards.
Exactly. 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, and they should be put to task over the issue, removed from decision making posts and in the worst cases, professionally shunned by the community and excluded from all standards processes... the cost of not doing this is a return to business as usual once things settle down.
The sad thing is that there is no way to ever put Humpty Dumpty back together again. The U.S. just permanently lost any position as a leading internet innovator. Nothing the U.S. leaders of industry can do now will ever earn back the trust of the rest of the world. No country or company in their right mind will ever trust a U.S. company with sensitive data ever again, and most of the companies that currently do are likely just biding time until they can find a non-U.S. based alternative (or some way to heavily encrypt their data).
The cow says "Moo." The dog says "Woof." The Timothy says "Thanks, valued customer. We appreciate your input."
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.
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 !
A 1024 bit RSA key can trivially be cracked in 2^512 operations. An algorithm that uses 2^341 operations (cube root) and involves no more than high school maths was found about 1975. Then we need to go into deep maths, but there are algorithms that are significantly faster, and there is no good reason to think that more progress couldn't be made. 128 vs 3072 is a bit much, but factoring 1024 bit numbers in 2^128 operations doesn't seem impossible.
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.
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 think that American users have more to fear from US government spying than foreign users do. Frankly I don't care if the Chinese government has access to all of my personal data - they have very little ability to or interest in interfering with my life. The US government on the other hand is much more likely to act against me in response to my (hypothetical) online mis-behavior. In the same way Chinese citizens have little to fear from the US government but a lot to fear from their own.
The very important exception to this is when you are dealing with industry trade secrets it is quite possible that foreign governments with links to industry represent a larger threat than your own. Of course while the NSA as an organization almost certainly does not sell trade secrets that they have obtained, it is possible that individuals working for the NSA might do so. Snowdon stole a bunch of information and turned it public, another man in the same situation might well have sold it.