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

[Andrey Jivsov <[e-mail]>]

On 07/27/2014 03:53 PM, Watson Ladd wrote:
> 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.

Interesting. Good point.

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

> (There are other implications; static ECDH certs get private keys
> 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.

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

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.

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

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