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

Watson Ladd <watsonbladd@gmail.com> Mon, 28 July 2014 03:19 UTC

Return-Path: <watsonbladd@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id A607E1A004A for <cfrg@ietfa.amsl.com>; Sun, 27 Jul 2014 20:19:16 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id OHZP1EXo5yTB for <cfrg@ietfa.amsl.com>; Sun, 27 Jul 2014 20:19:14 -0700 (PDT)
Received: from mail-yh0-x232.google.com (mail-yh0-x232.google.com [IPv6:2607:f8b0:4002:c01::232]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 221761A0019 for <cfrg@irtf.org>; Sun, 27 Jul 2014 20:19:14 -0700 (PDT)
Received: by mail-yh0-f50.google.com with SMTP id v1so4474048yhn.23 for <cfrg@irtf.org>; Sun, 27 Jul 2014 20:19:13 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=GSKPQeI+XZECt762x7JAST/kKkT2aPK4UxUIAtlNkV0=; b=XP+SvFdoPfpx+124ZNm7T+rfEautAe3+l588oXRUguGdPUJZrD3iZGlYdRHmRTnTFs VN3DN+QRrTnrv05gWYu+lO3lWOcd6DWFldOrlGMYjvG/S3M5JSUwAR8eIxImSxhN/jbZ JD3oHkRP0TxhfOSKBwMP0gaP+wnmukBJOT86UBbf4jfdmhfD+f03r4iEGW14cbaXUHXN dif47WbR8oOr5sJ01vZDLskrCRwmgSonbzssO2gfOsTrWG9i/GvF7WNIMHbVQhMdy/kX bU64zUeGO0/CS1pGmH9gvdrgvcy0WyS4a/H9I2Z5+J+CoZFdbZ/SDB3wvArcXd6bIwfv IP2A==
MIME-Version: 1.0
X-Received: by 10.236.129.3 with SMTP id g3mr46272363yhi.67.1406517553478; Sun, 27 Jul 2014 20:19:13 -0700 (PDT)
Received: by 10.170.202.8 with HTTP; Sun, 27 Jul 2014 20:19:13 -0700 (PDT)
In-Reply-To: <53D5AA12.7020002@brainhub.org>
References: <53D56D7E.9050306@brainhub.org> <CACsn0cnT_H7aqaBc-wEDjxAUNYoNW71uKNUdLsAC_Tuqeob+rA@mail.gmail.com> <53D5AA12.7020002@brainhub.org>
Date: Sun, 27 Jul 2014 20:19:13 -0700
Message-ID: <CACsn0ckeORqNyM3G017k_8EOq8rE_xzdZ9USSr1Xy1WbdR0=fA@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Andrey Jivsov <crypto@brainhub.org>
Content-Type: text/plain; charset=UTF-8
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/sjQb7esU72uQnADFuDqHoE3oKM4
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Practical summary of ECDH in TLS regarding the curve features
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Mon, 28 Jul 2014 03:19:16 -0000

On Sun, Jul 27, 2014 at 6:40 PM, Andrey Jivsov <crypto@brainhub.org> wrote:
> On 07/27/2014 03:53 PM, Watson Ladd wrote:
>>
>> On Sun, Jul 27, 2014 at 2:22 PM, Andrey Jivsov <crypto@brainhub.org>
>> 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