Re: [TLS] Safe ECC usage

[Nico Williams <[e-mail]>]

On Thu, Oct 17, 2013 at 10:46 AM, Dan Brown <[e-mail]> wrote:
> Why couldn't a new attack just work on one curve, namely Curve25519?  If I
> understand correctly, DJB has argued that the ECC theory and experience would
> be evidence for a claim similar, but perhaps not as strong, as your claim.

Let's say that there are single-curve attacks.  We don't know how many
curves have such attacks, nor how hard it is to find such attacks for
specific curves, or specific curves with such attacks.  Perhaps DJB
does know, but either he got spectacularly lucky (if such attack/curve
pairs are rare) or such attack/curve pairs are very common.  The
latter would imply that all ECC is busted, in which case we needn't
worry about whether Curve25519 is weak because we have bigger
problems, so we must ignore this possibility when comparing curves to
one another.  That leaves the former, and now we need some estimate of
frequency of such attack/curve pairs in order to decide if any one
curve is weak.

We don't have such an estimate, but surely whatever that frequency is,
it's the same for all cryptographers.  That means that for any one
standard curve, the likelihood of it being weak this way is about the
same if the possible attacks for each curve were not known at the time
they were discovered.  Now we just need to know whether the curves in
question were selected with or without such knowledge, but we can't
know this [yet], so instead we must estimate the likelihood that the
authors selected a weak curve on purpose.  An estimate of weak curve
distribution/frequency would allow us to estimate the likelihood that
a curve was selected because it was weak.

If some curve required specifying N bits of information, then it must
have been picked from a range of 1..2^2N or so curves (the 2^2N upper
bound is an estimate), *roughly*.  The larger the N, the larger the
freedom the author has/had in selecting a weak curve.  Whatever the
frequency of weak curves, the smaller the N, the more luck an author
needs to pick a weak curve.

That, I think, is the argument for why DJB curves' selection criteria
are more rigid (i.e., less subject to manipulation) than Brainpool
curves.

Now, if one out of every 5 curves are weak, then clearly there's a
great chance that DJB curves are weak.  If, for small Ns, one out of
every 5 curves are weak, while for large Ns one out of every trillion
curves are weak, then Brainpool curves are stronger than DJB curves.
I.e., the distribution of weak curves matters.  We know nothing about
the distribution of such weak curves -- the associated attacks are not
known, they are merely conjectured for the sake of argument after all.

It seems unlikely that there's a class of attacks on curves where the
distribution of weak curves tails off as curve complexity (size of
constants) increases.  But we can't really know anything about this
conjectured class of attacks each limited to one or few curves.

I'm not sure what we should assume, but all else being equal my
conclusion is that we should prefer curves whose selection criteria
left very little freedom to those doing the selection.  This might
include Brainpool-like (i.e., with large constants) curves, but I'd
want the selection to work as follows: one small group of people
publicly select a hash function, another disjoint set of people
independently, publicly (videotaped), and concurrently select a short,
simple, and *meaningful* English language string ("hello world"), then
pick the largest constants smaller than bounds computed from that hash
applied to that string.  In the meantime DJB curves were clearly
selected with very little freedom to select for rare weak curves,
therefore I believe we can trust them.

Nico
--