8
$\begingroup$

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?

Improve this question
$\endgroup$
12
  • 2
    $\begingroup$ Related: Should we trust the NIST-recommended ECC parameters? $\endgroup$
    – otus
    Oct 28, 2015 at 18:54
  • 1
    $\begingroup$ 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. $\endgroup$
    – SEJPM
    Oct 28, 2015 at 21:05
  • 1
    $\begingroup$ 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. $\endgroup$
    – fkraiem
    Oct 29, 2015 at 16:07
  • 1
    $\begingroup$ @Kurt It's not a curve's weakness, it's a flaw in the implementation that doesn't check if a point is on the curve. All contemporary OpenSSL implementations do have this check, so what you're writing about is an Oracle specific problem only. $\endgroup$
    – Oleg Gryb
    Oct 30, 2015 at 6:17
  • 1
    $\begingroup$ @Oleg and BouncyCastle sadly. And probably others... $\endgroup$
    – Kurt
    Oct 31, 2015 at 15:07

2 Answers 2

Reset to default
8
$\begingroup$

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!)

Improve this answer
$\endgroup$
20
  • $\begingroup$ 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. $\endgroup$
    – Oleg Gryb
    Oct 29, 2015 at 17:22
  • $\begingroup$ 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). $\endgroup$
    – otus
    Oct 29, 2015 at 17:48
  • 1
    $\begingroup$ @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. $\endgroup$
    – Circonflexe
    Oct 29, 2015 at 18:21
  • 1
    $\begingroup$ @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. $\endgroup$
    – otus
    Oct 29, 2015 at 19:26
  • 2
    $\begingroup$ @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 ? $\endgroup$
    – Ruggero
    Nov 3, 2015 at 12:41
0
$\begingroup$

The assumption that the second pre-image property is to be used here might be wrong. Using the possibility of alternate representations of a given weak curve (using the mapping from $a,b$ to $a',b'$ curve), one could compute many seeds $a/b$ value following FIPS, with many $a'/b'$ target weak curves to search for a single collision from seed set to target weak ECC set. A $2^{80}$ time memory tradeoff may be reachable today. While it was certainly not the case 20 years ago, keeping SHA1 for the FIPS 186-5 for the ECC parameter generation draft is not reasonable.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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