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

[Watson Ladd <[e-mail]>]

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

On Sun, Jul 27, 2014 at 8:19 PM, Watson Ladd <[e-mail]> wrote:
> 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 contributory behavior,
which it doesn't possess.

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

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.

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



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