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

Watson Ladd <watsonbladd@gmail.com> Sun, 27 July 2014 22:53 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 2AAE91A0658 for <cfrg@ietfa.amsl.com>; Sun, 27 Jul 2014 15:53:10 -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 7DbAHLTy3HZ2 for <cfrg@ietfa.amsl.com>; Sun, 27 Jul 2014 15:53:08 -0700 (PDT)
Received: from mail-yh0-x235.google.com (mail-yh0-x235.google.com [IPv6:2607:f8b0:4002:c01::235]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id C2FC61A045B for <cfrg@irtf.org>; Sun, 27 Jul 2014 15:53:07 -0700 (PDT)
Received: by mail-yh0-f53.google.com with SMTP id c41so4340100yho.40 for <cfrg@irtf.org>; Sun, 27 Jul 2014 15:53:07 -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=XXRcdmHeDXr+IxKrbRL6o4jIi8wF9CAi+KH3XKi1EtU=; b=Uk6/68MclQOsDtmM59mHdPg1uF+cD3Auw/ktw2xdzGrWmE+jEzmgAT0C9LFhScNiey TatAav27342yYcvmIoBfabIrt43kLRsHewPqRBJgEn9L9VThFcjgRCUfL4Es4VqAmJPd YygZDbuwCWrB23IAi7fYnBwobvKb4sn4zNLt0hcSGmAnkh9yV8SaXQM1IZ7f73uQauCY eTpZ6e6EHuN/38KvGyhqYH7unj91rk9yiGLtFOiV0k22Q+sH4saaXJmWnIpLTfVAVvJH D2qyN/hGhu+vq9tdjTW1B1QZUHBAGjWnDx+UqLyEoniYpbZHsOUFyDk+gVL9w8kPIJMC U/VQ==
MIME-Version: 1.0
X-Received: by 10.236.74.101 with SMTP id w65mr7006678yhd.103.1406501587145; Sun, 27 Jul 2014 15:53:07 -0700 (PDT)
Received: by 10.170.202.8 with HTTP; Sun, 27 Jul 2014 15:53:07 -0700 (PDT)
In-Reply-To: <53D56D7E.9050306@brainhub.org>
References: <53D56D7E.9050306@brainhub.org>
Date: Sun, 27 Jul 2014 15:53:07 -0700
Message-ID: <CACsn0cnT_H7aqaBc-wEDjxAUNYoNW71uKNUdLsAC_Tuqeob+rA@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/OG9ur3lKVVtjL8AA0lBr2SM2eGI
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: Sun, 27 Jul 2014 22:53:10 -0000

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

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

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

Sincerely,
Watson Ladd

>
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> 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