Re: [Cfrg] Progress on curve recommendations for TLS WG

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

Less rigidity means a larger collection of curves available for secret
selection by the curve generator. This is important in the following
scenario, which shouldn't be exaggerated but also shouldn't be ignored:

   * the curve generator is malicious;
   * the curve generator knows an attack that the public doesn't know;
   * some curve in the larger collection is vulnerable to the attack;
   * no curves in the smaller collection are vulnerable to the attack.

A much simpler issue is that any curve, even an honestly generated one,
might turn out to be vulnerable to a secret attack. We do _not_ have any
way to protect against this---but, again, it's not the same issue. What
we _do_ have are ways to stop the curve generator from amplifying a
one-in-a-million secret attack into a guaranteed attack. Dan Brown is
confusing these two issues when he says that "rigidity alone" does not
ensure safety "against secret attacks".

One way to achieve a reasonable level of rigidity is to choose the curve
that is as _small_ as possible---while obeying public security criteria,
obviously. (My experience is that defining "small" as "smallest cost",
averaged in any plausible way across platforms, minimizes wiggle room:
it's vastly more difficult to reach truly top speed than to merely come
close. But that isn't the topic of this message.)

What do we know, for various definitions of "small", about the security
of taking the smallest curve? Answer: Maybe it's more secure than
others. Maybe it's less. We simply don't know. The literature has

   * examples of attacks where the smallest curve resisting other
     attacks is _more_ secure than average and

   * examples of attacks where the smallest curve resisting other
     attacks is _less_ secure than average.

Maybe a secret attack would be of the first type, or maybe it would be
of the second type. In a previous message I pointed to seven known
examples of the first type (for various notions of smallness) and two
known examples of the second type. Koblitz, Koblitz (the co-inventor of
ECC), and Menezes wrote a long paper http://eprint.iacr.org/2008/390
with a section devoted to this issue:

   11.1. Special or random selection of parameters?

   A general philosophy one often encounters in cryptography is that
   whenever possible parameters should be chosen by some random process.
   If a special choice is made to increase efficiency, there is always
   the risk that the same property that made the choice so attractive
   will also lead to vulnerability to an unanticipated attack.

   [... several pages describing five detailed examples of how special
   choices can _improve_ security ...]
   
   Our purpose in giving these examples is not to lobby for the use of
   special curves in preference to random ones. Rather, our point is
   that conventional wisdom may turn out to be wrong and that, as far as
   anyone knows, either choice has risks. The decision about what kind
   of curve to use in ECC is a subjective one based on the user's best
   guess about future vulnerabilities.

   As frequently happens in cryptography, a close examination of a
   commonly accepted viewpoint on security issues reveals that opposing
   opinions or interpretations cannot be ruled out. Much as we might
   wish to convey to the outside world an impression of self-confidence
   and mathematical certainty about our recommendations (see Section 2),
   there is ample reason to wonder whether this self-confidence is
   justified.

Brown keeps claiming, incorrectly, that the risks are entirely on one
side. His argument consists of pointing to the well-documented risks on
that side (such as MOV, one of the examples I had given) while ignoring
the well-documented risks on the other side.

---Dan