Do Weak Elliptic Curves Exist? I'm running into very contradictory opinions when try to understand if weak elliptic curves exist. I'm not interested in the case when a curve's weakness is attributed to properties of an EC's prime, because those cases have been already explored, e.g. here: http://wstein.org/edu/2010/414/projects/novotney.pdf

I want to understand if there is a known proven weakness attributed to parameters a or b of a short Weierstrass equation.   

Dan Brown introduced a hypothesis of "spectral weakness" here:


https://www.ietf.org/mail-archive/web/tls/current/msg10393.html
https://www.ietf.org/mail-archive/web/cfrg/current/msg03952.html


DJB went even further and dubbed curves with unclear parameter's generation method "manipulative" at http://safecurves.cr.yp.to/rigid.html

Both major and popular ECC standards such as NIST and Brainpool have a "verifiable random" requirement for the curve's parameters.

At the same time I've learned just yesterday that there is a strong opinion that "spectral weakness" (attributed to the parameters) doesn't exist (see comments to this blog: http://ogryb.blogspot.com/2014/11/why-i-dont-trust-nist-p-256.html)

If no weak curves have been discovered yet, how big the threat of "spectral weakness" is?
The following is more or less a copy-paste of a comment I made on the related ArsTechnica thread. Indeed, StackExchange is probably one of the better places to debate this.

A few reminders first:  


there are approximately $p$ elliptic curves over the finite field of integers $\pmod{p}$;  
of these curves, only those with (almost) prime order are of cryptographic interest (I will write only about prime order, for simplicity): there are approximately $p/\log p$ such curves;  
among these prime curves, there are some known conditions which happen rarely and make the curve insecure;  
the "Suite B" generation procedure is basically: pick some seed $\sigma$ (randomly or maliciously; assume that it is malicious), hash it with a cryptographic hash function (and more particularly, a preimage-resistant hash function), and derive curve parameters from this.


The largest class of "subtly weak" curves (with prime order) that we know is the set of supersingular curves, which has a size of about $\sqrt{p}$ and therefore a probability of occurrence of $1/\sqrt{p}$ (neglecting the logarithmic factor). So finding one via the Suite B generation procedure, even in the malicious case, should take about $\sqrt{p}$ tries - which, coincidentally, is exactly as long as solving ECDLP in the first place. (Besides, this class is easy to detect anyway, but that's not the point).

So any useable (by the NSA) class of weak curves would need to be much (= exponentially) larger than this; this is, much larger than all known classes of weak curves.

Then: if such a class exists, then how does the NSA exploit it? Because of hashing, (assuming SHA-1 to be preimage-resistant, which seems plausible), they cannot have inserted backdoor info in the curve: any trap that they use is computable from the curve itself without knowing the seed $\sigma$. This means that such a backdoor is available to any good mathematician (no need to steal NSA secrets!).

So the Suite B curves can be considered as dangerous only if you believe all three following conditions:


there exists a class of curves which is exponentially larger than all known classes of weak curves;
NSA knew about this class 20 years ago, but nobody else has been able to discover it since then;  
they deliberately published, and use for themselves, a curve which they know to be weak to anybody else.
I personnally do not believe either (2) or (3), and tend not to believe (1) either. This is why I still believe P-256 to be safe.


Actually, even the DUAL_EC_DRBG scandal makes a strong case that both the P-256 curve (vs. ECDLP) and SHA-1 (vs. preimage computation) are probably safe: if the NSA had had, at the time of the DUAL_EC_DRGB parameter generation, a mean to either compute a SHA-1 preimage OR an elliptic curve discrete logarithm, then they would have been able to publish the seeds $\sigma_P, \sigma_Q$ for both points $P, Q$ while still knowing the discrete logarithm $\log(Q)/\log(P)$. They would have gained the same powers of prediction of the DRBG without leaving such a mess.

Of course, the preceding paragraph does not rule out that the whole DUAL_EC_DRBG scandal could have been deliberate misinformation from the NSA, and that Snowden could be a double agent. But this is leaving the crypto domain for the tinfoil-hat domain...

So why did NIST not use a verifiable method for generating the "Suite B" curves? Again, this is only borderline crypto, but my opinion on this is: nobody asked them to at the time, and it is only post-DUAL_EC_DRBG that we, the crypto community, have matured enough to require verifiability in all published parameters (which is a good thing, but does not mean by itself that P-256, or even worse, ECC in general, is broken!)