Re: [TLS] Safe ECC usage

[Nico Williams <[e-mail]>]

On Fri, Oct 18, 2013 at 1:42 PM, Dan Brown <[e-mail]> wrote:
> Nico Williams wrote:
>> Dan Brown <[e-mail]> wrote:
>> > Nico Williams wrote:
>>
>> Random attacks are the reason to want rigid curve selection processes.
>
> Yes, good point and sentence.
>
> Special attacks are the reason to want random curve selection.

But then you need to construct a random curve selection process that
everyone will be able to believe [years later!] was not manipulated.
That's very difficult.  Even if we eliminate the unreasonably paranoid
from "everyone".

And then what if the selected curves don't perform well?  Pick the
next closest well-performing curve?  How would such a procedure affect
the trustworthiness of the selection process?

At least with DJB's curves I only need to worry that DJB (et. al.) has
knowledge about cryptanalysis on said curves that he (they) are not
sharing, that DJB is mounting an attack on us.  You worry about
special attacks that are not known to the public nor DJB, but to me
that's the same as "random", and all I care about is that the curve
authors not have known about them a priori, because then we can reason
(with no data, granted, so it's all hand waving) about the density of
such attacks in the neighborhood of the curves in question.

>> 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.
>
> In addition to algorithm agility, random curve selection mitigates unknown
> weaknesses, e.g. Brainpool or P256 (but only if you trust its creator).

But since Dual_EC, we don't trust P256's creators.  That's a key
reason for this entire discussion.

> Hmm, maybe, I am missing your point about "curve class".

s/class/family/.

> I believe that, elsewhere in this thread, I said algorithm agility would be a
> very good reason for including Curve25519, in addition to Brainpool.

OK, good.

> Algorithm agility, though, does not help much, in general, against untold
> attacks (mainly helping against newly announced attacks).

Unless you also have enough diversity of algorithms to begin with.
That's why a number of algorithms would have to be required to
implement (quite a few, actually, considering your doubts anyways, and
assuming we can't get good consensus on just two; you might have
doubts about just two different algorithms).

> In particular, we don't want to TLS to become laissez-faire roll any algorithm
> you want, i.e. the ultimate in algorithm agility?  At some point, TLS
> considers the evidence and picks a few good algorithms, right?  The choice
> governing this selection of each algorithm is not primarily algorithm agility.

But it should be -- it should be about ability to survive
cryptanalytic advances.  We've experienced this w.r.t. chained IV CBC
cipher modes in SSHv2, for example, where having deployed counter
modes saved our collective bacon once.

> For example, AES was chosen for inclusion in TLS, not because of algorithm
> agility but because of the extensive analysis it underwent.  TLS did not, and
> still does not, adopt every single newly proposed algorithm in the name of
> algorithm agility.  So, something other than algorithm agility seems to be
> protecting TLS.

I understand this.  And given the time we've had to cryptanalyze AES
maybe we feel really good about it, so maybe we don't need so many
symmetric ciphers.  But your arguments, assuming they carry the day,
argue for having several key exchange and signature algorithms -- I
don't see how else to interpret what you're saying.

> Also, separately from but similary to algorithm agility, algorithm X is not
> usually adopted in TLS just on the grounds that we know of no attack, else
> each new proposal would be adopted.  So, it is inconsistent to consider only
> about known attacks.  TLS has to consider what evidence there is against
> unknown attacks.

There's only so much we can do about unknown attacks.  Algorithm
agility + lots of algorithms (each from a different family).

> - random curves have slightly more assurance than special
> - if the threat against P256 is serious, then we had better seriously consider
> non-ECC

You lost me with the second point.

As to the first, the problem is that assurance for random selection is
difficult -- aside from that I'd agree.

> The evidence set for the two points is similar, which may cause me to look
> like an arguing for one point, when I am trying to argue the other.
>
> Put another way, what's the point in comparing curves to each other, if we
> believe there's a bigger problem of ECC being busted.

Yes, we need non-ECC algorithms too, well, at least for as long as
they are practical (i.e., RSA with 16KB keys are not).  But anyways,
we also need ECC because of its performance benefits.  At least until
quantum computers become sufficiently powerful that we have to drop
this entire field of cryptography anyways.

>> 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?
>
> Hmm, as an end user, I might go for the safest possible that can run on my
> device.

Well, OK, but we have a large diversity of devices and device
capabilities.  If we're going to wind down this thread with a
conclusion, we should get more specific.

> My own intuition: I think ECC is safe, and that in the very unlikely case of
> any untold attacks, they will be at most similar in impact to MOVFR and SASS.

OK, thanks.  My own intuition is that DJB's curves are safe from
as-yet unknown attacks.  It's just intuition.

> My advice: definitely don't worry about Brainpool.  Don't worry about P256,
> unless you view its creator as an adversary and you are somehow required to
> use ECC, almost against your will, instead of some alternative like RSA or
> integer DH.  Consider Curve25519 mainly if you really want efficiency, or
> don't trust the reliability of your implementation, and maybe also have dim
> view on the security of ECC alternatives.

DJB argues cogently that the NIST curves are not safe enough.  I'm OK
with Brainpool, but there are still significant advantages to DJB's
curves.

> TLS can safely adopt all these EC choices.
>
> At some point, though, TLS may not want to allow too many choices.

Well, I think we're way past that point as to non-required to
implement algorithms.  The problem there is the cartesian product
explosion of cipher suite IDs.  As for required to implement
algorithms, we're not.

Nico
--