Re: [TLS] Safe ECC usage

[Nico Williams <[e-mail]>]

On Fri, Oct 18, 2013 at 9:21 AM, Dan Brown <[e-mail]> wrote:
> Nico Williams wrote:
>> Dan Brown  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
>
> Well, you've assumed here, just like others, that attacks are random.  If you
> assume that attacks are random, then you are right that manipulation is the
> main threat.

I assumed all of: random attacks ("[w]ed don't know how many") and
attacks where one knows how to create a curve so it will be vulnerable
("[w]e don't know ... how hard it is to find ... specific curves with
such attacks").

> I've argued a few times that assuming random attacks is too optimistic, and
> also close to circular reasoning, and not supported by the evidence.

Random attacks are the reason to want rigid curve selection processes.

That leaves the other possibility, that the curve author knows how to
create curves that will be vulnerable to some class of attacks without
a random search.  Here we can use curve selection criteria that
involve parameter selections that no one person/entity can control --
verifiably.

Surely that was your point, no?  That curve25519 might be "special"
(as in specially weak) in some way that you (and I) don't know.

> Remember, Curve25519, though free from the potential of malicious
> manipulation, is chosen, in part, for its special efficiency properties.
>
> These special properties may also given an attacker special advantages.  DJB
> has already argued, based on the existing attacks  -- not random attacks --
> that this is unlikely.   And I agreed.
>
> Consider the ECC history.  After resisting all generic attacks, we have the
> following
>
> Miyaji proposed special trace 1 curves.  A few years later, these were broken
> by the SASS attack.
>
> Various proposed supersingular curves.  Later, they were broken by the MOVFR
> attacks.
>
> But ever since then, it has been fairly quiet on the prime-field side of ECC.

We can look at things other than the constants in curve25519 (and
curve 1174, and curve3617) -- the class(es) of curve(s) that it (they)
fits.. separately from the curve selection criteria.  How do we
mitigate unknown weaknesses in each curve class?  The only thing I
know is: algorithm agility.

As for selection criteria, I think I'd prefer a verifiably random
selection process over the smallest freedom approach, but where
there's doubt about the random selection process' verifiability I
prefer the latter over the former.  The problem is that as time passes
it becomes more difficult to verify that a long-ago random selection
process was not manipulated -- we have to trust records of history in
order to believe that it wasn't.

>> 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.
>
> Furthermore, if we admit this possibility, i.e. to justify that the ECDLP over
> P256, then we should not just ignore it, but consider alternatives to ECC.

I didn't mean that we should flat out ignore that possibility.  I was
very specific: "... so we must ignore this possibility WHEN COMPARING
CURVES TO ONE ANOTHER".  I said nothing about comparing ECC to
non-ECC.  Once more, the only way I know of to mitigate against
unknown attacks is algorithm agility.

For ephemeral DH algorithm agility is relatively simple: require to
implement N different DH algorithms, make it easy to turn off any of
them if they get broken.

For other ECC uses algorithm agility is much harder: it involves
re-keying.  We could require that principals have N public keys (in
PKI cases, that all N certs have the same names and so on, issued by
the same issuer), so that it's possible to drop any one that gets
broken later.  But even this, I think, may be too much to ask for.

So at some point we have to pick something.  At some point, in spite
of uncertainty, we have to select some algorithm as the one we're
going to rely on the most for authentication.  Which would you rather
use?

>> 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.
>
> Of course, it's very hard to make such estimates.  Even so, there is merit in
> making such estimates.  They have to been based on evidence.  There two types
> of evidence here:
>
> 1.  The lack of new attacks, despite efforts and incentives.
>
> 2.  The existing attacks, e.g. MOVFR and SASS.
>
> Intuition might entirely dismiss inferring estimates from this evidence set,
> as wild speculation.  More formally, intuition would be saying the inference
> drawn from the set have low confidence.

So do nothing?  Ignore the whole field?  I'm not sure where you're
going with this.  What specific advice are you giving us?

Nico
--