[Cfrg] Practical summary of ECDH in TLS regarding the curve features
Andrey Jivsov <crypto@brainhub.org> Sun, 27 July 2014 21:22 UTC
Return-Path: <crypto@brainhub.org>
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 00D0C1A0361 for <cfrg@ietfa.amsl.com>; Sun, 27 Jul 2014 14:22:10 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, 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 n2OlrrxhL3Cy for <cfrg@ietfa.amsl.com>; Sun, 27 Jul 2014 14:22:07 -0700 (PDT)
Received: from qmta14.emeryville.ca.mail.comcast.net (qmta14.emeryville.ca.mail.comcast.net [IPv6:2001:558:fe2d:44:76:96:27:212]) by ietfa.amsl.com (Postfix) with ESMTP id A12F91A037A for <cfrg@irtf.org>; Sun, 27 Jul 2014 14:22:07 -0700 (PDT)
Received: from omta14.emeryville.ca.mail.comcast.net ([76.96.30.60]) by qmta14.emeryville.ca.mail.comcast.net with comcast id XZ2o1o0031HpZEsAEZN7nY; Sun, 27 Jul 2014 21:22:07 +0000
Received: from [192.168.1.2] ([71.202.164.227]) by omta14.emeryville.ca.mail.comcast.net with comcast id XZN61o0014uhcbK8aZN60a; Sun, 27 Jul 2014 21:22:07 +0000
Message-ID: <53D56D7E.9050306@brainhub.org>
Date: Sun, 27 Jul 2014 14:22:06 -0700
From: Andrey Jivsov <crypto@brainhub.org>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.6.0
MIME-Version: 1.0
To: cfrg@irtf.org
Content-Type: text/plain; charset="ISO-8859-1"; format="flowed"
Content-Transfer-Encoding: 7bit
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20140121; t=1406496127; bh=q0xQWuMpW9KyXI1PGr3uvSjCUUvkRDDweVkZg5hV+2U=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=Jhnp4JNjlQpRTOlDU5GekLKv6Axw8F/VFtayGk6dpqjw4Vj9w6bdEm6LoyjoCulHz 5ac4wPjhV3f+AMLo4PjboVG2lojpaZz+2mYHXTNtnCwT7PhVE3ycMf8kyB16fgAo3J skAZ6ACjJXklZNkxp6/ZQs1Yg0ylcnzMEzRdHA8+DT8uP3rLHMRLFH63qSnMlbVq3/ YHoUUiPleXn4hbVBwmNtfGtnWe8Zg5CtjvWHTiHb02ObME31iZSkvoWq5h42cl/bIT /j5uMHe3+wF2EjubIHGHIG11ap7rwsOcm9LBM4g3LchHvJtvTB5OHS+IXOgSVkeB+U foEuc9BBxOqMw==
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/Eo7a31hH5Qz1EqEzirnDmEzh7Ps
Subject: [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 21:22:10 -0000
Here is my understanding of the threats that apply to ECDH TLS. (I believe that the analysts equally applies to IKE of IPSEC.) 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. First, consider the colluded peer+eavesdropper. DH protocol has no protection against a peer colluded with an eavesdropper. * trivially, either party can simply channel the plaintext stream somewhere else * "short private key". Each party can collude with an eavesdropper in a way which is impossible to detect (in the computational security model), as follows: - the peer agrees on a pre-shared secret and a PRF(i), i=0,1,2,... with an eavesdropper - the colluded peer uses the PRF(i) to generate private scalars (this may even qualify as a FIPS 140-2 compliant method) A variation of this problem assumes to prior arrangement/exchange with an evesedropper: a peer randomly picks private scalars from the range of 2...16; the eavesdropper finds a private key by brute-forcing the public key found in the KE payload, or a lookup within pre-computed values. 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. ) 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) Let's look closer at the motives why implementers of client or server code might want to reuse ephemeral keys. In this description we assume a typical scenario of "server" acting as TLS server and "client" as TLS client. It's easier to define the operating environment for the server: * there is a long-lived process/service * an implementation can count on availability of a global state (that can hold precomputed values, cached results) * it cares about: - maximum number of connections it can handle per second on a sustained basis - low latency / the ability to quickly handle short burst of TLS handshakes. The client environment is more diverse: * a common use is a localized function "do TLS from scratch", without global state; this means that no reuse DH1 is possible and it's more challenging to take advantage of fixed-base algorithms; think about a short-lived process or a javascript * long runs of back-to-back TLS handshakes are unlikely * in some environment the performance is not an issue: fast CPU with slow network; very fast CPU regardless of network speed In general, an end-device acting as a TLS client is not expected to perform a long sequence of handshakes back-to-back. It is often OK to perform fresh DH1 every time, for simplicity and security. In many other cases it is a reasonable assumption that a client should be able to generate its ephemeral key(s) in advance. 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. 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
- [Cfrg] Practical summary of ECDH in TLS regarding… Andrey Jivsov
- Re: [Cfrg] Practical summary of ECDH in TLS regar… Watson Ladd
- Re: [Cfrg] Practical summary of ECDH in TLS regar… Andrey Jivsov
- Re: [Cfrg] Practical summary of ECDH in TLS regar… Robert Ransom
- Re: [Cfrg] Practical summary of ECDH in TLS regar… Watson Ladd
- Re: [Cfrg] Practical summary of ECDH in TLS regar… Watson Ladd
- Re: [Cfrg] Practical summary of ECDH in TLS regar… Andrey Jivsov