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.
Elliptic curve cryptography runs Bitcoin. Does the NSA have the ability to steal Bitcoin at will?
Now's your time to shine dan
Round up a few cryptographers who, at a given time and place must disclose a random (or not) password they have chosen and kept secret until then. Encourage international participation, maybe hundreds of people.
Concatenate all the strings, append a numeric index and hash the result with SHA3. You will get an indexed list of 512 bit values that are provably random, unless all cryptographers of the world are in a grand conspiracy - since each person contributing an input has the possibility to undo any collusion of the others.
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 !
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 !
http://www.techdirt.com/articles/20130910/10470024468/flying-pig-nsa-is-running-man-middle-attacks-imitating-googles-servers.shtml
If you missed this one, one of the slides shows NSA & GCHQ has been impersonating Google and similar US services to avoid the need for an on-the-record request.
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.
If they change these values, I bet it will not be possible to decrypt these text using the same algorithm. So future implementations will have to a) detect version b) use the weak bad-constant version for old text and the new version with good-constants. If theres no way to detect version, this will break a lot of text that will be "unreadable"?
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
Do we think bitcoin is still safe then?
(There was some discussion a while ago about it being an NSA creation, as in this report http://groups.csail.mit.edu/mac/classes/6.805/articles/money/nsamint/nsamint.htm )
Could they have backdoored the protocol itself somehow? Or any of the libraries it relies on in implementation?
If so, does that mean there will come a day when they can just round up all the terrorists, drug dealers etc who have been using it for years ?
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.
Considering most browsers use NSS, and NSS supports SEC curves, how do we disable them?
Same question applies to OpenSSL
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
The idea of publishing a cryptographic standard without prior peer review of its design rationale is utter nonsense.
In cryptography, security is impossible without full disclosure of the design. Obviously, we need new standards that come with a full published analysis of the security -- including a rationale for the selection of the mathematical constants used.
Kudos to IamTheRealMike for such an informative and well written summary.
http://tools.ietf.org/html/rfc5639 Is actually the _ONE GOOD_ ECC curve set. Rather than doing the mysterious sausage thing, they stared out their random digit generator with digits from pi, and then they incremented their search one at a time. Unlike the NIST curves, these really are convincingly random.
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 !
From the cited NIST public statement:
NIST is also required by statute to consult with the NSA.
I didn't know that was the case. I thought it was just a courtesy.
This will herald an amazing period in computer science and computer products. Sadly, people with heavy emotional and career investments in various products will have to undergo a grieving period as trust in their products, and the standards upon which these products are based, have compromised credibility. People, product managers, developers, tech writers, companies and investors will try to salvage their code investments but basically, yep, new code will have to be written.
I'd anticipate that there will be an uptick in escrow services where companies compare source to delivered binaries.
Routers, switches and firewalls will start to be manufactured in the west again. In fact, for some countries, I'd imagine that sensitive IP products would demand that networking equipment be controlled and audited. I seem to recall that in Sweden or someplace, there was a company that made routers that were touted as designed and built in Europe that were sold to the defense industries.
The Snowden documents may also be the think that finally kickstarts a reform of SMTP. How the 'in the clear' and 'secure' modes will work, I guess like the farmer with a boat having to transfer a hen, bag of grain and dog over the river transaction. Dunno, I'll leave that to others but surely we'll also get some basic spam controls built in now, which would be a plus.
No, I think this will ultimately be excellent for the industry and users but there will be a lot of people for whom this will result in collapsed sales -- MS's credibility may be shot -- and the need to jettison career paths.
Everyone will have to swim like Canadians. You know, grit your teeth and say 'It's not so bad once you're in and keep moving.'
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."
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!”
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.
"I solemnly swear I will defend the Constitution of the United States against all enemies, foreign and domestic..."
Heads should roll!
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.'
Focus.
The US government is the most untrustworthy government - except for all the others.
:(
random.org uses radio background noise to grab random numbers.
Just grab a handful of random numbers or sequences and run with it.
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.
" 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?
Then claim the bitcoin economy for yourself, Internet Cryptography Warrior. It's all just there for the taking, right? No strong crypto to be found! Less of a hand wave, and more of an eye roll.
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?
I'm not sure about the psuedo-random NIST curves, but at least the non random standard NIST curves p-192,p-256, p-384, and p-521 were chosen with good reasons. These use psuedo Mersenne prime moduli which have some nice properties and allow for more efficient modular arithmetic algorithms. Efficiency isn't a big deal for PCs which have lots of computing power but it is a major problem for embedded systems or smart cards because of limited computing power and resources. The curve moduli for the NIST primes are psuedo-Mersenne primes, which means you can use the Solinas fast reduction algorithm. The Solinas fast modular reduction algorithm is very nice and fast, its just a few 32 bit integer additions and subtractions. To compute a modular multiplication you can just do a full integer multiplication and then use the NIST fast reduction algorithm on the full product. This is especially nice in embedded systems/FPGAs if you have embedded hardware multipliers to do the integer multiplication. If the modulus isn't a psuedo-Mersenne prime, reduction of a large number is much harder to do, so you have to do something like the double add and reduce algorithm to keep the numbers small enough as you calculate it, or use Montgomery multiplication which has some extra overhead.
The NIST prime curves also have prime order n, or the number of points which lie on the curve. The order n is used as the modulus in a few of the operations in ECDSA and ECDH and a prime modulus makes these operations easier too. A prime order is also important for other reasons. The curves also have chosen a=-3 which allows more efficient operations in projective coordinates.
At least the use of these parameters have some justification. Of course if you want efficiency, the binary and koblitz curves are much easier to implement anyway.