Is there a feasible method by which NIST ECC curves over prime fields could be intentionally rigged?

The NIST elliptic curves P-192, P-224, P-256, P-384, and P-521, prescribed in FIPS 186-4 appendix D.1.2, are generated according to a well defined process, but using an arbitrary random-looking seed value of 160 bits. For this reason a page of DJB's website calls them

Manipulatable: The curve-generation process has a large unexplained input, giving the curve generator a large space of curves to choose from. Consider, for example, a curve-generation process that takes $y^2=x^3-3x+H(s)$ meeting various security criteria, where $s$ is a large random "seed" and $H$ is a hash function. No matter how strong $H$ is, a malicious curve generator can search through many choices of $s$, checking each $y^2=x^3-3x+H(s)$ for vulnerability to a secret attack; this works if the secret attack applies to (e.g.) one curve in a billion.

Is that feasible? More precisely, is there an openly known method making that feasible? If not (as I suspect), is there additional rational argument (or even informed opinion) about the feasibility, or in-feasibility, of such intentional rigging, and the associated effort? Or perhaps, some more info on how the seeds have been chosen?

Note: I have not found a deep study of that precise point in the answers to these related questions.

• The only thing that comes close to what you are asking is Edlyn Teske's isogeny trick, mentioned in the other question. Apart from that, there is only speculation about unknown weaknesses. – Samuel Neves Jan 13 '14 at 23:57
• If they wanted to be transparent, the seed would be hash("ECC_CURVE_nnn_i"), where n is the curve size and i is increased from 0 until the generated seed produces a curve that meets some openly stated criteria. – Brock Hansen Feb 12 '14 at 17:47
• See also the same question: Should we trust the NIST-recommended ECC parameters? – rugk Aug 13 '16 at 20:51

I'd say that the whole argument hinges around a "secret attack" that possibly the NSA may know of, enabling them to break some instances of elliptic curves that the rest of the World considers as safe, because the secret attack is, well, secret.

This yields to the only possible answer to your question: since secret attacks are secret, they are not known to people who are not in the know (duh), and thus there is no "openly known method making that feasible", by definition. Since we don't know, in a mathematically strong sense, whether such a thing as a "secure elliptic curve" can exist at all, "no known attack" is about the best kind of security assumption that you will ever get.

Now if we look closely, we may note that the NIST curves have been generated with a strong PRNG: given a seed value $s$, the curve is $y^2 = x^3 + ax + H(s)$ with $a = -3$ (a classic value for this parameter; it gives a slight performance improvement for point doubling in Jacobian coordinates) and $H$ a deterministic PRNG. Here, the PRNG is what is described in ANSI X9.62 (section A.3.3.1) and is based on an underlying hash function, SHA-1 in the case of the NIST curves. For practical purposes, we can consider this PRNG to act as a random oracle. What this means is that even if NSA knows of some secret method to break some elliptic curves, they would still have had to do quite some work in order to find a seed which yields a curve which "looks good" (in particular, a curve with a prime order) and yet is among the set of "breakable curves". For instance, if only one curve in $2^{100}$ is weak against this unknown attack, then NSA would have faced an average of $2^{100}$ SHA-1 invocations (at least), a ludicrously high number.

Therefore, unless we add to the speculation another "unknown attack", this time against SHA-1 (specifically, the PRNG of X9.62 A.3.3.1 with SHA-1 as hash function), we must assume that if the NSA knows of a secret breaking method for some elliptic curves and used it to rig the NIST curves, then that method must be able to break a non-trivial proportion of possible curves. So we are not talking about a handful of special-format weak curves, but something really devastating.

We have no proof that elliptic curves are inherently strong, however we have some "intuition" that the apparent strength of curves against discrete logarithm is linked to the notion of canonical height (see also this presentation). If that intuition is correct, then there cannot be more than a very small proportion of "weak curves" (e.g. the curve $y^2 = x^3 + ax$ is weak if the base field is a 256-bit field); chances of hitting a week curve with a randomly generated $b$ parameter would be extremely remote. In that sense, the postulated "unknown attack" of NSA, in order to be usable to rig generation of the NIST curves, would also have to prove wrong the intuition of many mathematicians specialized at elliptic curves.

I think that the paragraph above is the closest you can get to a mathematical rational argument about why the NIST curves are not rigged.

I do have a second argument, though, which I find rational, though it is from economics, not mathematics: we cannot measure how secret a secret attack can be. Remember that the primary users of US-government-specified cryptographic parameters are US corporations; a primary goal of NSA is to protect these corporations against foreign enemies (competitors). Purposely pushing the use of rigged curves, where the rigging uses the knowledge of some as yet unpublished attack, is very risky: this will hold only as long as some half-crazed mathematician from the deepest of Siberia does not find the same attack. As Leibniz explained, scientific discoveries seem to happen to the whole World at the same time; everybody thinks the same things simultaneously. That's a notion which is well-known to academics: publish fast or perish.

So if the NSA does its official job properly, then it must not promote the use by US businesses of tools which are known to be flaky and thus potentially exploitable by anybody. NSA cannot ensure that it has a monopoly on mathematics...

This contrasts with the DualEC_DRBG backdoor, where there is a known method to rig it (by careful choice of the two involved curve points), but, crucially, it is equally obvious that people who did not get to choose the curve points cannot exploit the backdoor. That is the kind of backdoor that NSA can safely promote, because they know they can keep it under their exclusive control.

This also contrasts with the 56-bit DES key, where the backdoor was obvious (key amenable to exhaustive search) but could be exploited only through accumulation of sheer processing power; in the 1970s, USA had a known big advantage over USSR in that field, and they knew it. When computing power became available too generally, they switched strategies and decided to promote strong encryption methods (3DES, then AES): they prefer it when their enemies cannot break encryption, even if that means that they cannot break it either.

• I especially like the contrast with DualEC_DRBG: the key to that backdoor is one in the (asymmetric) cryptographic sense, not a scientific progress as the key to the hypothetical backdoor in P-XXX would be. – fgrieu Jan 14 '14 at 19:49
• Since NSA's TAO folks exploit zero-days in seemingly every piece of software on the planet, I am not so confident that NSA would prioritize COMSEC over SIGINT when writing global standards. – Matt Nordhoff Jan 15 '14 at 15:18
• "Dual_EC_DRBG...is the kind of backdoor that NSA can safely promote, because they know they can keep it under their exclusive control." Yes, exploitation requires knowledge of a secret integer. But one wonders if an NSA insider hasn't spilled that secret integer to some interested party other than the press. – Brock Hansen Feb 12 '14 at 17:35
• "So if the NSA does its official job properly, then it must not promote the use by US businesses of tools which are known to be flaky and thus potentially exploitable by anybody." True. But what if almost everyone involved is actually only out for themselves, short-term and long-term? With little real supervision or concern about actual effects... – Patriot Jul 1 at 3:50

This has been basically asked already: Should we trust the NIST recommended ECC parameters?

History

Once it was found that NSA allegedly had inserted backdoor to a cryptographic standard, people started thinking what standard it was.

The most common guess is that the Dual EC DRBG is the backdoored standard. However, some amount of (possibly justified) paranoia got triggered and people started trying to consider what else could be backdoored.

NIST P-XXX

NIST P-XXX curves were considered to be suspect, as it was found there is one value that appears to be random, and has been chosen by NSA.

The mathematics behind Elliptic Curves are not well understood, and if NSA knew a lot more on EC than general public, it is possible they could have found a way to create weaker curves. This would not be first time NSA is 15 years ahead academic knowledge (differential cryptanalysis).

The reaction has been that some high profile parties (like Bruce Schneier: "I no longer trust the constants. I believe the NSA has manipulated them through their relationships with industry.") decided they won't use Elliptic Curve just to be safe.

On the other hand, many other parties have chosen to trust NIST P-XXX groups regardless of this controversy, because it would appear that using weak groups would not be in best interest of US national security (US government is using these algorithms to secure Top Secret materials).

To avoid this kind of scandals, certain other standards, like some IKE/DH groups used Nothing Up Me Sleeve Numbers. In the retrospect, so should have been used in creation of the NIST P-XXX curves, apparently. It appears that it'll be impossible to explain the origin of those few seed numbers. This is maybe flaw in EC standards: they do not require very auditable process for EC curve generation.

Controversy

Presentation by DJB and Tanja Lange: Security dangers of the NIST curves summarizes (lot of) the concerns they have on NIST curves. The point they are making is that lot of design for NIST curves is based on efficiency of implementation, but regardless of that they fail to be as efficient as some other curves.

DJB and Tanja are very good in pointing out some critic towards NIST P curves and their chosen parameters and design.

Safe Curves the page from DJB considers different EC standards and their underlying design and existence or lack of magic numbers. This is good to use when comparing NIST P-XXX with other curves. (Somebody could say that this is also about DJB's self-promotion: he has been designing excellent Curve25519, which is somewhat different than NIST curves, and for this reason less known and less supported.)

Weak Hash function

NIST themselves (FIPS 186-3/4) requires new Elliptic Curve parameters to use an approved hash function at least as large as the curve in generation. The EC curves were generated before SHA-2 was recommended for EC, so the curves use 160-bit values, with SHA-2 against the newer recommendations.

Going forwards

All things summarized, it is up to reader to decide how serious the risks are. Nothing as major as the Dual EC-DRBG backdoor is known. In fact, there is a reason to suspect the opposite: the obvious Dual EC-DRBG backdoor would have made little sense if NSA had ingenious backdoor on NIST P curves.

It seems that going forwards one of these may happen, to restore some trust:

• NIST+NSA is able to come up with some information that will clear any existing doubt over their groups.
• Some consensus finds some of the existing curves good enough and some other curves than NIST P-XXX curves become standard.
• New replacing curves will be created, this time using hash functions at least as strong as the curve like recommended by FIPS 186-3 and NOSL numbers.
• My question links to the one that is cited in this answer. And while this answer addresses that other question, it does not directly address my question, which is focused on the techniques than could be used to rig P-192 and friends. – fgrieu Jan 13 '14 at 21:11
• @fgrieu: I briefly addressed the other question. The speculation is: NSA knows a weakness in curves, something that is specific to 1 in million or 1 in billion curves. As far as I understand the underlying mathematics, this is not very likely, but then again, NSA if anybody would be the party who had capability for this. I'm sorry that my answer lacks the actual mechanism NSA could have used, especially as the speculation is that they know more than the others. – user4982 Jan 13 '14 at 22:57