Re: [TLS] Safe ECC usage

[Dan Brown <[e-mail]>]

Watson Ladd wrote
> Dan Brown wrote
>
> > Based on this score, if I had to guess what the next attack would be,
> > then I would guess special.  An attack on random would be a
> breakthrough.
> > Therefore, trying to choose a random curve is a best guess approach.
> >
> ...
> >
> > Uncertainty, "no idea", about unknown attacks is a given, but we
> > should still try to resist them, even if that means making
> assumptions
> > and guessing.  Provably secure algorithm try to do this.  Previously
> unknown
> > attacks are known pop up, occasionally.   But, we also give weight to
> the
> > effort that people have exerted in trying to find attacks, to infer
> > the unlikelihood of new attacks being discovered.
> >
> So you agree that E(random curve falls to unknown attack)=E(Curve25519
> falls to random attacks). (This is is obvious unless cosmic conspiracy
> happens, and if it isn't, think about it). But now the question is

Sure, but confining ourselves to "random attacks' is way too optimistic. 
Future, and unknown, attacks will not necessarily be random.

Also, that is not at all what I was talking about in the text you quoted.  In 
fact, earlier in this thread, I mentioned this random attack argument as being 
almost circular, assuming one what one aims to establish, and that this was 
similar to what Koblitz, Koblitz and Menezes argued.

Well, maybe you mean something other than "random attacks"?


> whether the author of the random curve really picked it at random, vs
> specified a curve. And then the fact that DJB specified at most 17 bits
> or so is very important: a new attack would have to work on 2^{-17} of
> all curves to work on Curve25519.

Just curious: where's the 17 from?

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.

Sure, a new attack could work against just one brainpool curve too.  But for 
brainpool, there a three prongs against such a single curve attack: the ECC 
theory and experience, the use of SHA1 of in brainpool definitions, the use of 
Pi and e in the brainpool curves.  That would definitely be a "cosmic 
conspiracy".

The MOV and SASS worked on small fractions of curves.  If I recall correctly, 
in both cases there had already been proposals to use special curves (for 
efficiency and other convenience reasons) affected by these attacks, before 
the attacks were discovered.  The risk of this happening again for Curve25519 
is much smaller, because of the many intervening years of research into ECC. 
That's why I view Curve25519 as safe, but in the context of resisting unknown 
attacks, the evidence supports brainpool, or an honestly-generated P-256 as 
slightly safer.

...

The most compelling argument, at least to me, against my position is the 
Pohlig--Hellman attack, which DJB already raised a couple times.  I've exclude 
this attack from my evidence, because it is generic to DH/DL, and Curve25519, 
Brainpool and P256 all address PH attacks in the same way, with a low-pass 
filter.

Arguably, we could have boosted the group size, and resisted PH with a 
high-pass filter, resulting in DH/DL that belong to a larger class of groups. 
That would have been less efficient, but also not very compelling for security 
because is there is evidence of low-density generic DH/DL attacks, i.e. 
special groups, that need to be avoided.  Thus the decision to resist PH by 
using a low-pass filter (e.g. searching random orders until one nearly prime 
was found) does not seem to introduce a risk.  In the case of PH-protected 
ECC, the weak argument to avoid special curves is to avoid another MOV or 
SASS.

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