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