Re: [TLS] Safe ECC usage

["D. J. Bernstein" <[e-mail]>]

Dan Brown writes:
> if an attack affects all random curves, excluding
> Curve25519, then basically ECC would be no more,

Here are six examples of attacks that already affect the security level
of the vast majority of elliptic curves:

   * Shanks's baby-step-giant-step attack. Drastic reduction in the
     number of arithmetic operations required to break ECDLP. There's no
     defense against this attack.

   * The Pohlig--Hellman attack. Further drastic reduction in the number
     of arithmetic operations required for _most_ curves---but not all;
     there are occasional special curves that resist the attack.

   * Twist attacks. Again applicable to _most_ curves---but, again, not
     all; again there are occasional special curves that resist the
     attack.

   * Negating rho. Okay, it's just a 1.4x attack speedup, but I can't
     see any justification for you to ignore it. There's no defense
     against this attack.

   * Pollard's rho attack. Drastic reduction in _memory_ consumption,
     making elliptic curves much easier to break (in reality, and in
     sensible cost metrics). There's no defense against this attack.

   * The van Oorschot--Wiener parallel rho attack. Drastic reduction in
     _communication_, allowing efficient parallelization, again making
     elliptic curves much easier to break. There's no defense against
     this attack.

So you're wrong in implying that there haven't already been attacks that
affect "random curves". Do we respond by discarding ECC, as you suggest?
Of course not. We respond by choosing parameters to resist the attacks:

   * Choose _extremely_ special curves (we're talking about one curve in
     a thousand here!) that defend against twist attacks and the
     Pohlig--Hellman attack.

   * Choose primes far above 200 bits to defend against the other four
     attacks.

Of course, we also take time to further investigate and build confidence
that the security story is stable. All of these attacks have been known
for more than ten years (three of them even before ECC was published),
as have the two attacks that you mentioned for extremely rare curves.
People working on attacks have found interesting improvements for
extension fields, higher genus, etc., but seem to have run out of ideas
for attacking prime-field ECC.

> So far, there no are 0 (*) attacks against random curves, and 2 against
> special curves: the MOV and SASS attacks.  I view this as quite good
> evidence in favour of random curves, over special curves.

That's because you're simply ignoring all the contrary evidence. For
example, if you insist on using random curves then Pohlig--Hellman will
damage your security, probably quite severely. That's why everyone is
actually using rare curves that resist the Pohlig--Hellman attack.

In other words, rather than taking the uniform distribution over all
elliptic curves of whatever size, ECC users are massively biasing the
distribution of elliptic curves. The biased distribution discards the
vast majority of elliptic curves: at least the curves vulnerable to
Pohlig--Hellman, and nowadays also the curves that aren't twist-secure.
Every sane risk analysis will conclude that this bias is a good idea.

I say that it's a good idea to narrow the distribution even more, in
fact down to a single curve, by taking the _smallest_ curve coefficient
within the usual massively biased distribution. That's what Curve25519
does. This isn't just a performance win; it also prevents the sort of
manipulation that's clearly possible for someone who claims to be
"randomly" choosing curves from the wider distribution.

Now imagine that there's no manipulation. How does this single-curve
distribution compare in security to the larger (massively biased)
distribution against some unknown attack? The correct answer is that we
have no idea---maybe it's more secure, maybe it's less secure, maybe
it's the same.

You keep trying to trivialize this question by promoting the myth that
more uniformity is safer. You present this as some sort of ill-defined
dichotomy between "random" and "special", with "random" clearly being
better. You take every break of a small curve class as support for your
position, retroactively declaring the curves in the class to be
"special", while you ignore the glaring counterexamples such as
Pohlig--Hellman.

> You gave an example that, under reasonable assumptions, with 2^(-30)
> probability the ECDLP in Curve25519 could be solved in 2^64
> computations.

No. What I actually wrote was "Suppose NSA knows---and knew in the late
1990s---a cost-2^64 attack that breaks one P1363-compliant 256-bit curve
in a billion". I gave examples to illustrate that this "wouldn't be out
of line with the spectrum of known ECC attacks". I then explained how
this attack would have allowed NSA to _guarantee_ weakness of the NIST
P-256 curve, while for an honestly generated curve the situation is
obviously quite different.

By misstating my assumptions as being specific to Curve25519, you're
omitting the critical security impact on NIST P-256, and you're also
promoting a misconception that ECC security analysis is curve-specific.

> I do not see how those assumptions are reasonable, but even so, if
> 2^30 people use Curve25519, then is that a good risk?

I have no idea what you think you mean by "a good risk" (and I also have
no idea why you're talking about the number of people---the discussion
is about weak curves, not weak keys). In the situation that I actually
described, there's no reason to think that the risk is different for
Curve25519 and for an _honestly_ generated NIST P-256. The problem is
that we don't know whether NIST P-256 was honestly generated.

> Do you feel that the system-wide risk for RSA, or integer DH is comparable?

There are improvements in index calculus all the time. Those have been
continually dragging down the security level of RSA, which in turn has
been dragging down the performance of RSA, which is exactly why modern
RSA is so much slower than ECC.

---D. J. Bernstein
   Research Professor, Computer Science, University of Illinois at Chicago