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

Re:Reference?

[IamTheRealMike]

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:

Simultaneously, the N.S.A. has been deliberately weakening the international encryption standards adopted by developers. One goal in the agency’s 2013 budget request was to “influence policies, standards and specifications for commercial public key technologies,” the most common encryption method.

Cryptographers have long suspected that the agency planted vulnerabilities in a standard adopted in 2006 by the National Institute of Standards and Technology and later by the International Organization for Standardization, which has 163 countries as members.

Classified N.S.A. memos appear to confirm that the fatal weakness, discovered by two Microsoft cryptographers in 2007, was engineered by the agency. The N.S.A. wrote the standard and aggressively pushed it on the international group, privately calling the effort “a challenge in finesse.”

“Eventually, N.S.A. became the sole editor,” the memo says.

Although the NYT didn't explicitly name the bad standard, there's only one that fits the criteria given which is Dual_EC_DRBG.

Re:Why is EC more secure than RSA?

[Anonymous Coward]

The number field sieve relies on the smoothness of the integers modulo n. Using an elliptic curve group rather than the integers modulo n removes this smoothness, so the fastest algorithms available to determine the discrete logarithms are much slower (I believe they're based on Pollard's rho algorithm).

If that made no sense to you, go brush up on your number theory.

If you don't want to learn number theory, then accept that you are incapable of having an informed opinion on asymmetrical cryptography standards. (Which is okay, we can't all have an informed opinion on every issue; your brain can only hold so much stuff, right?)

Re:We owe our thanks to Mr. Snowden

[j3thr0]

Except that this came to light back in 2007. http://www.wired.com/politics/security/commentary/securitymatters/2007/11/securitymatters_1115

Re:Meta review

[afidel]

Suspicious yes, but not necessarily bad, remember that the NSA also manipulated the s-box values for DES to make them more resistant to differential cryptanalysis, a technique not yet known by the wider community.

Re:We owe our thanks to Mr. Snowden

[IamTheRealMike]

That story is about Dual_EC_DRBG which was indeed strongly suspected of being an NSA back door back in 2007. Snowden confirmed the suspicion. However this story is not about that algorithm. It's about the SEC random curves that are used for signing and other crypto, not random number generation. There are two different algorithms under discussion here.

Re:Meta review

[Carewolf]

Iranians are NOT semitic, they are Aryan, the name Iran literally means home of the Aryans. Named so because that is the one common thing that separates the various Iranian people from their semitic neighbours the Arabs.