Re: [TLS] Safe ECC usage

[Dan Brown <[e-mail]>]

> D. J. Bernstein writes
> 
> 
> Peter Gutmann writes:
> > potentially NSA-influenced values like P256
> 
> There is indisputably an unexplained seed c49d3608 86e70493 6a6678e1
> 139d26b7 819f7e90 for the NIST P-256 curve mod 2^256-2^224+2^192+2^96-
> 1, and similarly for the other NIST curves. This was identified by the

[DB] Five NIST curves are Koblitz curves, which do not have seeds at all.
They also use small curve coefficients, which is similar to Curve25519.

> 2005 Brainpool standard as a major issue for the NIST curves; it has
> also been highlighted recently by Bruce Schneier.

[DB] 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).  In particular, I already tried to summarize
on this list (in response to a message from Douglas Stebila) an argument
that 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.  I may have missed an something
important.  To further elaborate my argument: it is possible to formulate
one's suspicion in such that way that one needs only to boost one's curve
size accordingly.  For example, if one suspects an undisclosed class of
curves whose density is say n^(1/8) where n is the curve size, then, to
resist falling into this class, one can choose n large enough, so that the
risk is small enough.  Such risk should be somehow calibrated with claimed
security levels: e.g. if we want the adversary to incur computational cost
of 2^128 at success rate near 1, we may be satisfied with success rate
2^(-48) at cost near 1.  With these settings might choose a 384-bit curve
instead of 256-bit curve.  This doesn't protect against constant density
classes, but is at least worth something.  Of course, I made up the n^(1/8).
One might look at the densities of the current weak classes: one has n^(1/2)
and the other (MOV) has, hmm, I have to study it some more, I just remember
a result that says it's low.  

If I recall correctly, the Brainpool documents recommended against, or at
least avoided, special classes of curves.  I have argued on this list that
Curve25519 is special in its use of small coefficients.  What's your thought
on the risk of this?  So far, the main two weak classes of prime-field
curves are negligible density.  If the future reveals such classes, then it
seems that attempting to select curves verifiably at random is a more solid
way to avoid falling into such a class than choosing a special curve.  If I
recall correctly, the MNT curves were special curves chosen for desirable
characteristics, that later fell into one of these classes.  

> 
> Fortunately, one can design high-security elliptic curves that don't
> have any unexplained constants. That's what I did with Curve25519.

[DB] Wasn't this well-known already for Koblitz curves, or are they broken?
I may have lost track, since there has been recent improvements in (EC)DLP
over extension fields.  I had thought that maybe Koblitz curves remained
unaffected.  (Also, some standards, e.g. ANSI X9.63 have long prohibited
such extension-field curves, which might be a good case of anticipation, or
perhaps just promotion of interoperability).

> Curve25519 is the curve y^2=x^3+486662x^2+x mod 2^255-19; every number
> here is completely explained in the Curve25519 paper.

[DB] Does Curve25519 ignore Cheon-type "attacks" (which are rather weak)?
If so, that's probably fine for TLS, because the attacks do not affect TLS,
unless the TLS-PRF is much weaker than we think, and DH private keys are
very heavily re-used.  So, I mainly ask for completeness.  Also, the NIST
curves and the Brainpool curves do not incorporate any countermeasures to
these attacks (the Brainpool deliberately so).

> 
> > even without NSA skullduggery make a nice single target for attack.
> 
> There have already been several detailed studies of the cost of finding
> multiple discrete logs on the same curve (authors: Escott, Sager,
> Selkirk, Tsapakidis, Kuhn, Struik, Hitchcock, Montague, Carter, Dawson,
> Lee, Cheon, Hong, Bernstein, Lange). Basically, if finding one ECC key
> costs 2^128, then finding 1000000 keys costs 1000*2^128, and the first
> key found will still cost 2^128. For comparison, finding 1000000 AES
> keys costs the same 2^128 as finding a single key, and the first AES
> key will be found with cost only 2^128/1000000.
> 

[DB] Good point. 

I had interpreted the comment differently to refer to attacking the curve
itsel (which would support using a random curve for each TLS handshake, for
example).  A typical response to the comment (under my interpretation) is
that AES and SHA2 are also nice single targets, and well maybe, that's a
good thing, with incentives, publicity, and so on.

---------------------------------------------------------------------
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.