[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