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.
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.
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 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.
It's past that point. Nobody we would want to run would win. If you're not in the two big parties you get no media attention, no money, it's significantly more difficult to get included in debates, etc. IOW it's a doomed candidacy.
"Ignorance more frequently begets confidence than does knowledge"
- Charles Darwin
I just found this new blog post from the NYT which gives a very small amount of additional context. It also explicitly names the NSA RNG as what they were talking about.
http://bits.blogs.nytimes.com/2013/09/10/government-announces-steps-to-restore-confidence-on-encryption-standards/
The Guardian, ProPublica, the NYT and Schneier all appear confident enough in what they've read to state assertively that it's a hacked standard. Also, why else would the NSA care so much about pushing a crap and slow RNG that we know can have a backdoor into international standards?
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 !
To give everyone a laugh at libertarian nerds who thought it was a great idea to invest in it.
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.
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.
This must be the reason my checking account never balances.....
Faster! Faster! Faster would be better!
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.
The US government is the most untrustworthy government - except for all the others.
:(