Re: [TLS] Safe ECC usage

[Dan Brown <[e-mail]>]

> D. J. Bernstein writes
> 
> Dan Brown writes:
> > You noted that curve sizes p,p-1, and p+1 are weak.
> > These might be called special curve sizes, since for a random curve,
> > of order p+d, we expect |d| around p^(1/2), and for these d is much
> > smaller.
> 
> There is already overwhelming evidence that the size of d is not what
> matters. For example, the next attack that you should learn is one that

[DB] Thanks for the advice, but what I need to learn, or remember, is no
justification for the security of Curve25519.

> breaks group order p+6m+2 if p=12m^2-1; in this case the gap from p is

[DB] In case, anybody gets scared here, standards already have the MOV test
rule this class out.  In my weak defense, negligible fraction of p are
affected here.  More strongly, please remember that we are talking about
hypotheticals here: maybe there exists undiscovered attacks, e.g. against
P256 or Curve25519.  If the evidence is so overwhelming, then maybe we
should worry much less about P256?  That said, your argument is cogent, and
I take new, so this discussion has proven fruitful for improving the
justification Curve25519, at least to me.

> more than 80% of its maximum possible value.
> 
> What's actually going on is that the additive group F_p has order p;
> the multiplicative group F_p^* has order p-1; the group F_{p^2}^* has
> order p^2-1; the group F_{p^3}^* has order p^3-1; etc. For roughly the
> first dozen groups in this list we have discrete-logarithm algorithms
> fast enough to worry about. There are known methods to "transfer" ECDLP
> over F_p into these discrete-logarithm problems---but only if the EC
> group has order dividing p, p-1, p^2-1, p^3-1, etc. This is why p+1 is
> a problem (it divides p^2-1); it's why p+6m+2 is a problem if p=12m^2-1
> (p+6m+2 divides p^3-1); etc.

[DB] Excellent explanation, though not one I needed.

> 
> > Of course, it's a logical leap to
> > jump from small d to small curve coefficients,
> 
> It's even worse than a logical leap: CM theory shows that each d that
> isn't extremely close to +-2 sqrt(p) corresponds to a huge number of

[DB] Good point, the case for Curve25519 is growing yet stronger.  But how
much is huge?  I have much to learn, I know, but my understanding is that
there are about p isomorphism classes of curves, and on the order of p^(1/2)
of curve orders, so about p/^(1/2) curves per order.  I could be wrong, but
I think that a reasonable heuristic is for a random curve by isomorphism
class, its corresponding coefficient (if its equation is pushed into a
one-parameter family of equations) is approximately.  Hmm, let's see, so
what the smallest coefficient be, on average?  This problem is probably a
well known problem, but here is a crude approximation: p^(1/2).  Consider
the probability that all coefficients have size larger than p^(1/2).  For
each individual coefficient the chance is (p - p^(1/2))/p = 1 - p^(-1/2).
Now (1-p^(-1/2))^(p^(1/2)) is the probability that they all are larger, and
this e^(-1).

> different curve coefficients. There's overwhelming evidence that the
> correlation is negligible, making coefficient size useless as a
> predictor of the size of d---never mind the question of what any of
> this has to do with ECC security.
> 
> > but if we are going to be prudent, then why not avoid small
> > coefficients too?
> 
> Calling this "prudent" has zero justification from the extensive
> literature on ECC security analysis. You could, with exactly the same

[DB] I know, from the current literature, which is why I said I feel
Curve25519 is safe. Again, I am only talking about unanticipated
hypothetical attacks.

> amount of justification, claim that _large_ coefficients are more
> likely to be weak and that choosing small coefficients is the safest
> strategy.

[DB] Agreed to an extent: coefficient size is just an arbitrary way to test
pseudo-random uniformity.  For example, what is the P-value of the
coefficient size of Curve25519?  (Compared to random curves of any size).
You correctly argue that coefficient-size is not a concern based on current
literature, and that it improves efficiency, so therefore, it seems
economical to ignore a low P-value for this statistic.  Also, taking your
argument further, one could apply any other arbitrary statistic.  One could
then contrive some weird statistic with a low P-value to deliberate reject
some given curve.  The point of coefficient size as a statistic is just that
it is a nothing-up-my-sleeve statistic.  I thought all that was implicit in
what I said.

> 
> What actually matters is that taking large coefficients imposes an
> extra cost, both in cryptographic performance and in the human effort
> required to rule out back doors. These are resources taken away from

[DB] Back doors in the case P256, and pseudo-random curves, require
unpublished attacks, perhaps surprising ones.  (Aside: even if back doors
are inserted by adversary #1, it may be possible for adversary #2 to find
the attack too, so the concern may extend beyond the back door.)  I am
concentrating on the issue of unpublished attacks of elliptic curves,
because that is one of logical pre-requisite to a back door.  (An
alternative logical pre-requisite is an unpublished attack on SHA-1, or how
it is used in the generation of P256, but that is an orthogonal issue to
Curve25519.)

Brainpool and RFC 5639 recommends pseudo-random parameters to avoid
unanticipated attacks, and you are arguing against this recommendation by
anticipating from known attacks.

---------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.