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:

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?

  • 1
  • Do you ask about prime curves specifically or about ECs in general (including binary extension field curves and such)? – SEJPM Oct 28 '15 at 20:25
  • @SEJPM prime only, since they are used the most in applications – Oleg Gryb Oct 28 '15 at 20:26
  • 1
    I think I've found a candidate property. If your curve has as many points as your field has elements then the ECDLP can be broken easily. The number of points is dictated by A and B. Other weak curves are the supersingular ones where you can use Index-Calculus for breaking ECDLP. – SEJPM Oct 28 '15 at 21:05
  • 1
    Yes, it is possible to construct supersingular curves for all values of $p$. In particular, it is very easy if $p \equiv 2 \pmod 3$, then $Y^2 = X^3 + b$ is supersingular for all $b \not\equiv 0 \pmod p$. However, the probability that a randomly chosen curve is supersingular (or otherwise has low embedding degree) is very low. – fkraiem Oct 29 '15 at 16:07
up vote 5 down vote accepted

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:

  1. there exists a class of curves which is exponentially larger than all known classes of weak curves;
  2. NSA knew about this class 20 years ago, but nobody else has been able to discover it since then;
  3. 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!)

  • Jerome, this is a great explanation that clarifies many things and please pardon me for being harsh @ blogpost. That reaction comes from a huge pain inflicted by all ECC uncertainties. I like your reasoning, especially in the two last paragraphs. Three conclusions that I make from this: (1) weak EC classes do exist, (2) brute forcing described by Dan Brown won't work since 'w' is too big (p^1/2) for known weak classes, (3) we still don't know if larger weak classes exist and more research is required. Please let me know if/where I'm wrong. I accept your answer. – Oleg Gryb Oct 29 '15 at 17:22
  • Regarding your condition 1. I can't see why an exponentially larger class would be required. A constant factor larger would have sufficed, if the objective was to backdoor e.g. P-256 only (or more generally, curves up to a certain size). – otus Oct 29 '15 at 17:48
  • 1
    @OlegGryb The answers you drew are correct. I also add that, for all the known weak classes of curves, it is always possible to test whether a curve is weak (or: it is impossible to produce a "trapped" curve). This is, of course, not necessarily true for the unknown weak classes. – Circonflexe Oct 29 '15 at 18:21
  • 1
    @Circonflexe, my point is that the amount of effort needed only matters for the practical curves you would want to make weak, even if it is asymptotically intractable. – otus Oct 29 '15 at 19:26
  • 1
    @Circonflexe I believe the number of Elliptic Curves defined in $\mathbb{F}_p$ is about $2p$ not $p$. This is due to the fact that there are $p$ possible j-invariant and two curves per j-invariant (I'm considering here the non-trivial quadratic twist). The situation is different for j-invariant 0 and 1728, plus the trace of Frobenius could be zero but I think we can say it is "approximately $2p$". Am I missing something ? – Ruggero Nov 3 '15 at 12:41

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.