Re: [TLS] Safe ECC usage

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

Dan Brown writes:
> Five NIST curves are Koblitz curves, which do not have seeds at all.

Agreed. There's nothing unexplained in, e.g., the K-233 curve. However,
as I wrote in the Curve25519 paper in 2005, prime fields have "the
virtue of minimizing the number of security concerns for elliptic-curve
cryptography; see, e.g., [1998 Frey] and [2003 Diem]."

Maybe Frey's Weil-descent attack strategy has reached its limits, but
maybe not; see, e.g., http://eprint.iacr.org/2012/146. The performance
benefits of Koblitz curves aren't big enough to justify having to worry
about further developments in this area. It's best to use prime fields,
eliminating this entire class of attacks.

> I must have forgotten that aspect of the Brainpool standard.  If
> possible, please remind me of the issue, if only by link to the relevant
> document (and section thereof).

This is the second bullet item in the list of "major issues" stated at
the beginning of "ECC Brainpool Standard Curves and Curve Generation v.
1.0".

> a consistent treatment of ECC must mildly reduce, or at least revise,
> the claimed security of any EC curve if the treatment also posits that NIST
> curves have an undisclosed strong weakness.

No.

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. This wouldn't be
out of line with the spectrum of known ECC attacks, such as

   * the Pohlig--Hellman attack breaking most curve orders (this is why
     P1363 requires a large prime to divide the order),
   * twist attacks breaking most of the remaining curve orders in many
     protocols,
   * Weil descent breaking many curves for some field sizes,
   * the MOV attack on curves of order p-1 and p+1 and so on, and
   * an attack on curves of order p.

Suppose that NSA can recognize immediately from the group order whether
the attack will be successful---again a reasonable assumption. NSA could
then

   * have generated many billions of seeds until finding a
     P1363-compliant curve vulnerable to this attack (a feasible
     computation for NSA in the 1990s),

   * have standardized that curve as NIST P-256 (we already know that
     NIST took its curves from NSA), falsely claiming the curve to be
     "verifiably random", and

   * be applying the cost-2^64 attack to NIST P-256 users today.

You claim that such an attack would be a threat to "any EC curve". But
this claim is obviously not correct for curves that really are randomly
generated (and you have zero justification for making the same claim for
any particular curve). The correct comparison, under exactly the same
hypotheses, is simple:

   * Honest curve: NSA has _a one-in-a-billion chance_ that we obtained
     a weak curve, in which case NSA finds our keys with cost 2^64.

   * NIST curve: NSA is _guaranteed_ that we're using a weak curve, so
     NSA finds our keys with cost 2^64.

These are obviously not the same situation. The attack costs are the
same, but the success probabilities are on totally different scales.

I don't think there's a high risk of being in this situation---there
have been many years of intensive cryptanalysis of ECC, and for prime
fields the security story seems to have converged. But there's also no
reason for ECC users to expose themselves to risks that are so trivial
to avoid. There are also much larger risks that definitely bite people
(see http://cr.yp.to/talks/2013.05.31/slides-dan+tanja-20130531-4x3.pdf)
and that one can avoid by moving away from the NIST curves.

> I have argued on this list that
> Curve25519 is special in its use of small coefficients.

Well, yes, you've declared that y^2=x^3+486662x^2+x mod 2^255-19 is
"special", but you haven't actually given an argument for this---for
example, an attack strategy in which the size of the 486662 plays a
role. Index calculus sees sizes, but the whole point of ECC is to stop
index calculus. You could equally well declare that NIST P-256 is
"special" since its prime can be written as a low-degree polynomial in a
power of 2 with coefficients {-1,0,1}, or declare that brainpoolP256r1
is "special" since it contains the scary string BCCDC.

> Does Curve25519 ignore Cheon-type "attacks" (which are rather weak)?

Key derivation stops such attacks, and is easy to do securely, as
discussed in the Curve25519 paper. As far as I know, all Curve25519
deployment is using appropriate key derivation.

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