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

Re:hmmm

[Anonymous Coward]

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.

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 [nytimes.com]:

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:Reference?

[afidel]

Bruce Schneier talked about DRBG being a probable backdoor back in 2007 [schneier.com].

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 [wired.com]

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:Why is EC more secure than RSA?

[Anonymous Coward]

Public key cryptography is based on mathematical operations which are easy to do but difficult to do in reverse. For example, it is easy to multiply two big prime numbers, but it is difficult to factorize the product. There are multiple such easy-difficult pairs. Currently none of the supposedly difficult problems has been proven to be difficult. It is just assumed that they are difficult because nobody has found an easy way, but people are working on making the difficult problem easier to solve, and advances in that regard weaken the associated cryptographic systems. Significant advances have been made in solving the difficult problem at the heart of RSA (but it's not publicly broken yet.) That's the reason for the recommendation to switch to a different easy-difficult pair for public key cryptography. The different key sizes are the result of the kinds of numbers which form the public and private keys in these different algorithms.

Re:Why is EC more secure than RSA?

[Anonymous Coward]

The discrete log problem on an elliptic curve is believed to be more computationally intensive than the discrete log problem in a ring of integers. For example, see http://www.ams.org/journals/mcom/1987-48-177/S0025-5718-1987-0866109-5/S0025-5718-1987-0866109-5.pdf and http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=F220DD223483B78B72C9CE243A62ADD7?doi=10.1.1.39.4125&rep=rep1&type=pdf

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:Isn't it time we take back our own country ?

[meta-monkey]

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.

Re:Meta review

[daremonai]

Iran is not a semitic country, by and large. The majority of the population is ethnic Persians who speak Farsi, an Indo-European language. The second largest group is the Azerbaijanis, who speak a Turkic language. I don't think the semitic population (mostly Arab and Assyrian) amounts to more than 10%.

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.

Re:hmmm

[HornWumpus]

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.