Should we trust the NIST-recommended ECC parameters? Recent articles in the media, based upon Snowden documents, have suggested that the NSA has actively tried to enable surveillance by embedding weaknesses in commercially-deployed technology -- including at least one NIST standard.

The NIST FIPS 186-3 standard provides recommended parameters for curves that can be used for elliptic curve cryptography.  These recommended parameters are widely used; it is widely presumed that they are a reasonable choice.

My question. Can we trust these parameters?  Is there any way to verify that they were generated in an honest way, in a way that makes it unlikely they contain backdoors?

Reasons for concern.
Bruce Schneier has written that he has seen a bunch of secret Snowden documents, and after seeing them, he recommends classical integer discrete log-based cryptosystems over elliptic curve cryptography.  When asked to elaborate on why he thinks we should avoid elliptic-curve cryptography, he writes:


  I no longer trust the constants. I believe the NSA has manipulated them through their relationships with industry.


This suggests we should look closely at how the "constants" (the curve parameters) have been chosen, if we use ECC.  This is where things look concerning.  I recently read a message on the tor-talk mailing list that seems to suggest the NIST curve parameters were not generated in a verifiable way.  That message examines how the parameters were generated:


  I looked at the random seed values for the P-xxxr curves. For
  example, P-256r's seed is c49d360886e704936a6678e1139d26b7819f7e90.  No justification is given for that value.


and ultimately concludes:


  I now personally consider this to be smoking evidence that the
  parameters are cooked.


Based upon my reading of FIPS 186-3, this appears to be an accurate description of the process by which the P-xxxr curves were generated.  So, should people be concerned about this?  Or is this just paranoia based upon loss of trust in the NSA?

See also these slides from Dan Bernstein and Tanja Lange, particularly pp.6-7, 8-10, 14-17 for further discussion about the NIST parameter choices.
Edit: I have made some tests and I found something weird. See at the end.



Initial answer:

At least the Koblitz curves (K-163, K-233... in NIST terminology) cannot have been specially "cooked", since the whole process is quite transparent:


Begin with a binary field $GF(2^m)$. For every m there is only one such field (you can have several representations, but they are all isomorphic).
Restrict yourself to prime values of m to avoid possible weaknesses by plunging into sub-fields.
Consider curves $Y^2+XY=X^3+aX^2+b$ where $b \ne 0$; this is the normal form of non-supersingular curves in binary fields.
You only want curves where $a = a^2$ and $b = b^2$, so that you can speed up computations with the Frobenius endomorphism (basically, you replace point doublings with simply squaring both coordinates, which is very fast).
When $a = 0$, the curve order is necessarily a multiple of 4; when $a = 1$, necessarily a multiple of 2.


Then you want a curve order which is "as prime as possible", i.e. equal to $2p$ or $4p$ for a prime $p$ (depending on whether $a = 1$ or $0$). For $m$ ranging in the "interesting range" (say 160 to 768), you will not find a lot of suitable curves (I don't remember the exact count, but it is something like 6 or 7 curves). NIST simply took the 5 of them corresponding to the $m$ values which were closest to (but not lower then) their "security levels" (80, 112, 128, 192 and 256-bit "equivalent strength"). There is no room for "cooking" here.

So I would say that at least Koblitz curves are demonstrably free from all these "cooking" rumours. Of course, some other people argue that Koblitz curves have some special structure which might be leveraged for faster attacks; and that's true in two ways:


Faster computations mean faster attacks, mechanically;
One can solve discrete logarithm "modulo the Frobenius endomorphism" which means that K-233 is about as strong as a 225-bit curve (because 233 is an 8-bit number).


I still consider such curves to be reasonable candidates for serious cryptographic work. They have been "in the wild" for more at least 15 years and are still unscathed, which is not bad, as these things go.



Edit: I have made a few tests, enumerating all Koblitz curves in $GF(2^m)$ for $m$ ranging from 3 to 1200. For each $m$, there are two curves to test, for $a = 0$ and $a = 1$. We consider the curve "appropriate" if its order is equal to $4p$ (for $a = 0$) or $2p$ (for $a = 1$) with $p$ prime (this is the "best possible" since the curve is always an extension of the same curve in $GF(2)$, so the curve order is necessarily a multiple of the curve in $GF(2)$, and that's 4 or 2, depending on $a$). For the "interesting range" of $m$ between 160 and 768, there are fourteen appropriate curves:


$m = 163$, $a = 1$
$m = 233$, $a = 0$
$m = 239$, $a = 0$
$m = 277$, $a = 0$
$m = 283$, $a = 0$
$m = 283$, $a = 1$
$m = 311$, $a = 1$
$m = 331$, $a = 1$
$m = 347$, $a = 1$
$m = 349$, $a = 0$
$m = 359$, $a = 1$
$m = 409$, $a = 0$
$m = 571$, $a = 0$
$m = 701$, $a = 1$


NIST's target was their five "security levels" of 80, 112, 128, 192 and 256 bits, and a curve would match that level only if its size is at least twice the level. So the standard curve for each level ought to be the smallest curve which is large enough for that level. This should yield Koblitz curves in fields of size 163, 233, 277, 409 and 571 bits, respectively.

Strangely enough, this matches NIST's choices except for the "128-bit" level, in which they chose $m = 283$ instead of $m = 277$. I don't know the reason for this. For both field sizes, the smallest possible reduction polynomial is a pentanomial ($X^{277}+X^{12}+X^{6}+X^{3}+1$ for $m = 277$, $X^{283}+X^{12}+X^{7}+X^{5}+1$ for $m = 283$), so neither field is at a computational advantage on the other is using polynomial bases (well, the 277-bit field is a bit shorter, so a bit faster). With normal bases, the 277-bit field is actually more efficient, because it accepts a "type 4" Gaussian normal basis, while the 283-bit field is a "type 6" (smaller types are better for performance). The list of all suitable Koblitz curves is easy to rebuild and, indeed, NIST / NSA did it (e.g. see this article from NSA-employed J. A. Solinas -- search for "277").

Why they chose the 283-bit field is mysterious to me. I still deem it very improbable that this constitutes "cooking"; this is a backdoor only if NIST (or NSA) knows how to break Koblitz curves in a 283-bit field and not in a 277-bit field, which not only requires an assumption of "unpublished big cryptanalytic advance", but also requires that supposed novel breaking technique to be quite weird.