Re: [Cfrg] Practical summary of ECDH in TLS regarding the curve features

[Watson Ladd <[e-mail]>]

On Sun, Jul 27, 2014 at 2:22 PM, Andrey Jivsov <[e-mail]> wrote:
> Here is my understanding of the threats that apply to ECDH TLS. (I believe
> that the analysts equally applies to IKE of IPSEC.)

It doesn't: IKE is much better designed than TLS.

>
> Assumptions: In DH we consider passive eavesdroppers. DH is a symmetric
> protocol, thus everything said here about one peer applies to either of
> them. While it's true that a TLS client connects to the server, allowing the
> TLS server be exploited as an oracle, TLS renegotiation allows the server to
> assume the role of a client after the initial handshake and exploit the
> original client as an oracle as well.
>
> 1. Assuming no reuse of ephemeral keys:
>     * the point validation doesn't matter (neither does the curve's twist
> security)
>     * the curve cofactor > 1 doesn't matter
>     * an availability of side channel attacks doesn't matter.

This is wrong, and I am finally allowed to say why publically.

If the point is not validated, a malicious server can carry out small
subgroup confinement attack, and do the same on a server.
If the resulting master secrets are the same, Triple Handshake
happens. This affects Bouncycastle 1.50, and is fixed in 1.51.
(There are other implications; static ECDH certs get private keys
spilled, ECIES does the same, etc.)

I mentioned this issue with non-contributory behavior on the TLS mailing list.

The rest of your email is (mostly) pointless: we do security proofs
that reduce a protocol like TLS to ECDH, then evaluate the security of
ECDH. The absence of such a reduction for TLS is the real problem here.

(If points are signed, small-subgroup confinement fails. However,
"channel binding" over anonymous channels requires care)
>
> First, consider the colluded peer+eavesdropper.

There is a standard set of models and definitions for key agreement security.

>
> Second, consider how a rogue participant might attack another peer.
>
> * Invalid point attacks lead to:
>   - An attack on another peer's key. This requires many runs of the DH
> protocol to recover another peer's static key. This concern doesn't apply to
> truly ephemeral keys
>   - Predictable shared secret. A peer can force the use of a small subgroup,
> either by choosing a point in the small subgroup corresponding to the
> cofactor or using a point x,y on a different curve (presumably such a point
> has  a small order too). This allows an eavesdropper to force the shared
> secret to the one that's easy calculate for an eavesdropper. However, the
> described earlier "short private key" methods work equally well.
>
> * side channel attacks by the peer require multiple runs of the DH protocol,
> thus they should not be relevant to the TLS ECDHE with fresh ephemeral keys.
>
> ( It looks like that breaking ECDH in this setting is equivalent to solving
> the ECDLP problem. )

Only loosely, and by taking advantage of pairings. Or one could use
the direct, common conjecture
on ECDH security.

>
> 2. Reused ephemeral keys = static ECDH keys (and all the published attacks
> apply)
>
> In the remainder of this email DH1 stands for the generation of the peer's
> ephemeral key, DH2 -- for the final calculation of the shared key.
>
> For reused ephemeral keys the following EC features matter:
> * point validation
> * twist security
> * side channels
>
> The following doesn't matter:
> * performance (of a single scalar multiplication)

<snip>

>
> On the server side, however, requiring a fresh DH1 is a harder sell. As an
> extreme but practical example, consider a TLS terminator that serves a set
> of HTTP servers. One can expect the TLS traffic terminator to be, on
> average, saturated with handshake requests. It's too tempting to cut the ECC
> cost by half by not doing the DH1.

So performance doesn't matter, until it does? Performance matters:
it's why traffic goes
unencrypted. There are no security costs with reuse of ephemeral connections.

>
> Let's look closer at how this sums regarding a likely DH strategy for the
> client and the server. The following description indicates where fixed-base
> v.s. variable base scalar multiplication applies (view the following as a
> 4-cell 2x2 table).
>
>    client  (DH1/DH2): fixed-base, possibly done in advance (latency ~0) or
> reused (cost ~0) / variable base
>    server (DH1/DH2): likely reused (cost ~0) / variable base
>
> * Variable base calculation in DH2 is unavoidable for both a client and a
> server.
> * Unless fixed-base calculation is (something like 5+ times) faster than
> variable-base, there is an incentive to reuse ephemeral keys on the server
> * fixed-base EC on the client is nice to have, but is unclear if it is a
> universally beneficial feature
> * fresh ephemeral keys boost security; example: a curve at 128 bit security
> level and fresh ephemeral keys may be a reasonable match with a P-384 X.509
> certs

This last conclusion is just wrong. An attacker who wants to intercept
the traffic does 0.866*2^128 calculations
to recover the discrete logarithm of an ephemeral value, and uses it
to read the traffic. Reuse of ephemeral keys
doesn't change this calculation: recovering even one connection is a
significant problem.

Sincerely,
Watson Ladd

>
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin