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

From: Andrey Jivsov <[email-masked]>
Date: Sun, 27 Jul 2014 14:22:06 -0700

Here is my understanding of the threats that apply to ECDH TLS. (I 
believe that the analysts equally applies to IKE of IPSEC.)

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.

First, consider the colluded peer+eavesdropper.

DH protocol has no protection against a peer colluded with an eavesdropper.
* trivially, either party can simply channel the plaintext stream 
somewhere else
* "short private key". Each party can collude with an eavesdropper in a 
way which is impossible to detect (in the computational security model), 
as follows:
     - the peer agrees on a pre-shared secret and a PRF(i), i=0,1,2,... 
with an eavesdropper
     - the colluded peer uses the PRF(i) to generate private scalars 
(this may even qualify as a FIPS 140-2 compliant method)
   A variation of this problem assumes to prior arrangement/exchange 
with an evesedropper: a peer randomly picks private scalars from the 
range of 2...16; the eavesdropper finds a private key by brute-forcing 
the public key found in the KE payload, or a lookup within pre-computed 
values.

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

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)

Let's look closer at the motives why implementers of client or server 
code might want to reuse ephemeral keys. In this description we assume a 
typical scenario of "server" acting as TLS server and "client" as TLS 
client.

It's easier to define the operating environment for the server:
* there is a long-lived process/service
* an implementation can count on availability of a global state (that 
can hold precomputed values, cached results)
* it cares about:
     - maximum number of connections it can handle per second on a 
sustained basis
     - low latency / the ability to quickly handle short burst of TLS 
handshakes.

The client environment is more diverse:
* a common use is a localized function "do TLS from scratch", without 
global state;
    this means that no reuse DH1 is possible and it's more challenging 
to take advantage of fixed-base algorithms; think about a short-lived 
process or a javascript
* long runs of back-to-back TLS handshakes are unlikely
* in some environment the performance is not an issue: fast CPU with 
slow network; very fast CPU regardless of network speed

In general, an end-device acting as a TLS client is not expected to 
perform a long sequence of handshakes back-to-back. It is often OK to 
perform fresh DH1 every time, for simplicity and security. In many other 
cases it is a reasonable assumption that a client should be able to 
generate its ephemeral key(s) in advance.

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.

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

---

From: Watson Ladd <[email-masked]>
Date: Sun, 27 Jul 2014 15:53:07 -0700

On Sun, Jul 27, 2014 at 2:22 PM, Andrey Jivsov <[email-masked]> 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.

> 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.
>
>     * the point validation doesn't matter (neither does the curve's twist
> security)

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.

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

<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
> * Variable base calculation in DH2 is unavoidable for both a client and a
> server.
> * 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
> [email-masked]
> 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

---

From: Andrey Jivsov <[email-masked]>
Date: Sun, 27 Jul 2014 18:40:34 -0700

> happens. This affects Bouncycastle 1.50, and is fixed in 1.51.

Interesting. Good point.

However, was the ECDHE intended as a solution to channel binding? It is 
great that it helps, but this looks accidental.

> spilled, ECIES does the same, etc.)

The comment in brackets is in the wrong section. It applies to my 
section #2 (reused ephemeral keys). I agree with this in reference to 
reused ephemeral keys.

> unencrypted. There are no security costs with reuse of ephemeral connections.

My point is that fresh ephemeral keys, with the exception of the lack of 
channel binding that you noted, which is to be fixed in TLS, seem to be 
very forgiving regarding the properties of curves and quality of 
implementations.

Reuse of ephemeral keys makes them static and this brings all the 
well-known troubles. Assuming channel binding is fixed, fresh ephemeral 
keys appear to be beneficial for security of ECDHE in TLS.

The use of fresh ephemeral keys has cost resulting in lower performance. 
You can't beat (amortized) zero-time DH1.

> doesn't change this calculation: recovering even one connection is a

I wasn't stating that this should be done, but compare two cases:

* an attacker can only recover one connection and must do so by doing 
ECDLP on two Ps (one is peer's k*G, another is k*his_PK) v.s.

* an attacker may have a signing oracle, exploiting all the possible 
bugs and side channels
* once he gets the private key, he can forge the signatures

---

From: Robert Ransom <[email-masked]>
Date: Sun, 27 Jul 2014 19:11:09 -0700

> ECDLP on two Ps (one is peer's k*G, another is k*his_PK) v.s.

An attacker only needs to learn the secret key of one of the keypairs
in order to recover an ECDH(E) shared secret.

Robert Ransom

---

From: Watson Ladd <[email-masked]>
Date: Sun, 27 Jul 2014 20:19:13 -0700

On Sun, Jul 27, 2014 at 6:40 PM, Andrey Jivsov <[email-masked]> wrote:
>>> believe
>>> the
>>> twist

The security of TLS is accidental: it was originally designed by a
summer intern. At the
core of the security is
> The comment in brackets is in the wrong section. It applies to my section #2
> (reused ephemeral keys). I agree with this in reference to reused ephemeral
> keys.
>
>
>>
>>> subgroup,
>>> protocol,
>>> attacks
>>> peer's
>>> an
> channel binding that you noted, which is to be fixed in TLS, seem to be very
> forgiving regarding the properties of curves and quality of implementations.
>
> Reuse of ephemeral keys makes them static and this brings all the well-known
> troubles. Assuming channel binding is fixed, fresh ephemeral keys appear to
> be beneficial for security of ECDHE in TLS.
>
> The use of fresh ephemeral keys has cost resulting in lower performance. You
> can't beat (amortized) zero-time DH1.
>
>
>>
>>>
>>> security
> * an attacker can only recover one connection and must do so by doing ECDLP
> on two Ps (one is peer's k*G, another is k*his_PK) v.s.
>
> * an attacker may have a signing oracle, exploiting all the possible bugs
> and side channels

---

From: Watson Ladd <[email-masked]>
Date: Sun, 27 Jul 2014 20:22:55 -0700

Sorry, I hit send instead of cancel while editing the message.

 The security of TLS is accidental: it was originally designed by a
summer intern. At the core of the security is contributory behavior,
which it doesn't possess.

>> can't beat (amortized) zero-time DH1.

This is true. But why waste time making bad curves when we can make
good ones? The
argument that side channels don't matter for signatures and ECDH
ignores quite a few practical
issues:
-determinism in signatures lets you reuse a side channel by getting
repeated signatures on the same message.
-side-channels are not bounded: I could leak almost all the bits from
a side channel, leaving a very small number
to guess.

---

From: Andrey Jivsov <[email-masked]>
Date: Sun, 27 Jul 2014 22:25:12 -0700

On 07/27/2014 08:22 PM, Watson Ladd wrote:
> good ones?

Certainly. My 4-cell table of likely ephemeral key strategies for client 
and servers meant to show that the reuse of ephemeral DH is expected at 
least for TLS servers. Some TLS clients are actually (computer) servers 
connecting to many TLS servers, and so I am against prohibiting the 
reuse for TLS clients too.

This means that curves must be capable to handle static DH (i.e. reused 
ephemeral DH) and therefore good curves are beneficial for TLS.

The
> a side channel, leaving a very small number

I wasn't looking at signatures, which use static keys.

I should clarify my comment about the side channel. I was thinking about 
a sidechannel in a network device sense (either a timing channel or an 
error channel).

It's true that if an ECDH scalar multiplication leaks reliably whether 
or not it does double or add, a single ECDH operation implemented that 
way might be hypothetically sufficient to recover the scalar. Would it 
end up in the same feasibility bucket as the 0.866*2^128 ECDLP attack?