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.
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.
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.
Yes, but they are using curve25519 which is not one of the curves recommended by NSA or NIST, and which does not have any unexplained magic numbers in its definition.
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 !
Sorry, I could have provided a link for that too. It was in the major Snowden story of last week that revealed the NSA was undermining public standards. The New York Times said this:
Although the NYT didn't explicitly name the bad standard, there's only one that fits the criteria given which is Dual_EC_DRBG.
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!
Bruce Schneier talked about DRBG being a probable backdoor back in 2007.
There are 4 boxes to use in the defense of liberty: soap, ballot, jury, ammo. Use in that order. Starting now.
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.
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.
I nominate Anonymous Coward.
We don't have a state-run media we have a media-run state.
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?
Because those are terrible ideas that will have zero effect.
The only way to beat a bureaucracy is at the polls, from the ground up:
1) download your local laws.
2) open in text editor.
3) hack to make them better.
4) get friends/randoms to run for city council with/for you based on those better laws.
5) campaign via social media/crowdfunding
6) win election. Enact laws. Acquire control of pre-built militarized police and tax money
7) use police to fight corruption, taxes to promote education, civic responsibility, transparent government
8) repeat for each city then county then state then nation.
9) ???
10) don't profit because you can't really take lobbying bribes for a distributed lawmaking system.
We don't have a state-run media we have a media-run state.
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.
The Swiss recently sold all the numbered account holders that didn't open their accounts prior to 1950 down the river.
The old money families (Kennedys, DuPonts etc) got to keep their secret accounts secret. Everybody else got fucked.
John McAfee 'It was like that time I hired that Bangkok prostitute; to do my taxes, while I fucked my accountant'
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.