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

[Watson Ladd <[e-mail]>]

On Sun, Jul 27, 2014 at 6:40 PM, Andrey Jivsov <[e-mail]> wrote:
> 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.

The security of TLS is accidental: it was originally designed by a
summer intern. At the
core of the security is
>
>
>> (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
>
>



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