Re: [TLS] Safe ECC usage

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

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
breaks group order p+6m+2 if p=12m^2-1; in this case the gap from p is
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.

> 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
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
amount of justification, claim that _large_ coefficients are more likely
to be weak and that choosing small coefficients is the safest strategy.

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 things that
actually matter for security. If this were the only bad cryptographic
decision then it wouldn't be a huge problem, but unfortunately it's just
one of many things that people screw up.

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