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."

Comments

Meta review

[pr0nbot]

As well as reviewing the standards themselves, I hope someone is reviewing the processes which allowed these weaknesses to get into the standards.

Re:Meta review

[postbigbang]

Even when pi or rho or other "random" numbers are used for seeds as "magic" numbers, additional hashing and rehashing is needed to give further difficulty to decryption by those NOT having the key numbers.

With each new algorithm there is an army chomping at the bit (pardon the pun) to decrypt it, if not for fun or enlightenment, for the profit of the decrypted information value-- if any.

The problem here is trust. The NSA has blown its trust completely, beyond identifiability. Other initiatives, like SELinux, and security initiatives are now also in question, as well as anything the NSA has touched. They're dirty, and make Americans and the world not trust in their own government. We were supposed to be the good guys, we Yanks, and guess what? It was all a lie. Now the NSA has made an enemy of civil people, and civil people will need to protect themselves extra-governmentally, because the government has proven it's not protecting the interests of its citizenry.

Sorry to astroturf, but seeds are no longer the problem. The problem is trust.

Re:Meta review

[Dan Ost]

Because the designers of the Linux random number generator code designed things such that if RdRand is compromised, it doesn't reduce the strength of the random number generated. However, if it is not compromised, then the randomness is stronger.

Why should we give up a potential benefit if there is no possible harm?

Why is EC more secure than RSA?

[pikine]

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.

Re:Why is EC more secure than RSA?

[lordlod]

The elliptic-curve algorithm is much slower for future quantum based attacks. So it's future-proofing, which is required if you want your secrets to stay secret.

You could get similar results by adopting a 15000 bit RSA key... but that's getting rather large.

A paper with some classical and quantum time estimates, Elliptic-Curve vs RSA: http://arxiv.org/pdf/quant-ph/0301141v2.pdf

Re:hmmm

[Anonymous Coward]

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.

And because having worked for NSA or NSA-linked contractors is seen as a black mark on one's academic career, NSA has also jeopardized its own ability to recruit the next generation of cryptographers.

There's give and take between the SIGINT and COMSEC missions, and nobody here (or within the IC) is privy to all the information. I fear that by the time it's all declassified in 25 years and can be analyzed in context, the decisions made over the past 12 years will have proven to be gross strategic errors that did far more harm than any harm they prevented.

Not paranoid *enough* ?

[pla]

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.