[TLS] Safe ECC usage

"D. J. Bernstein" <djb@cr.yp.to> Thu, 26 September 2013 15:28 UTC

Return-Path: <57756671618275-ietf-tls@sublist.cr.yp.to>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 450DE21F9FB0 for <tls@ietfa.amsl.com>; Thu, 26 Sep 2013 08:28:35 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.339
X-Spam-Level:
X-Spam-Status: No, score=0.339 tagged_above=-999 required=5 tests=[AWL=0.277, BAYES_20=-0.74, SARE_BAYES_5x8=0.8, UNPARSEABLE_RELAY=0.001]
Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Bf1OScwge+e8 for <tls@ietfa.amsl.com>; Thu, 26 Sep 2013 08:28:28 -0700 (PDT)
Received: from mace.cs.uic.edu (mace.cs.uic.edu [131.193.32.224]) by ietfa.amsl.com (Postfix) with SMTP id D27CB21F9D18 for <tls@ietf.org>; Thu, 26 Sep 2013 08:28:18 -0700 (PDT)
Received: (qmail 27820 invoked by uid 1011); 26 Sep 2013 15:28:06 -0000
Received: from unknown (unknown) by unknown with QMTP; 26 Sep 2013 15:28:06 -0000
Received: (qmail 15843 invoked by uid 1001); 26 Sep 2013 15:27:57 -0000
Date: 26 Sep 2013 15:27:57 -0000
Message-ID: <20130926152757.15842.qmail@cr.yp.to>
From: "D. J. Bernstein" <djb@cr.yp.to>
To: tls@ietf.org
Mail-Followup-To: tls@ietf.org
Automatic-Legal-Notices: See http://cr.yp.to/mailcopyright.html.
References: <523E176F.3050304@gmail.com> <9A043F3CF02CD34C8E74AC1594475C7355674EE0@uxcn10-6.UoA.auckland.ac.nz>
Subject: [TLS] Safe ECC usage
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/tls>, <mailto:tls-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/tls>
List-Post: <mailto:tls@ietf.org>
List-Help: <mailto:tls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Thu, 26 Sep 2013 15:28:59 -0000

Modern elliptic-curve cryptography solidly takes care of all of the
"brittleness" mentioned in this thread, and is much easier than RSA to
implement securely. Compare https://twitter.com/tweetnacl to the amount
of code required to implement similar functionality in OpenSSL.

Peter Gutmann writes:
> potentially NSA-influenced values like P256

There is indisputably an unexplained seed c49d3608 86e70493 6a6678e1
139d26b7 819f7e90 for the NIST P-256 curve mod 2^256-2^224+2^192+2^96-1,
and similarly for the other NIST curves. This was identified by the 2005
Brainpool standard as a major issue for the NIST curves; it has also
been highlighted recently by Bruce Schneier.

Fortunately, one can design high-security elliptic curves that don't
have any unexplained constants. That's what I did with Curve25519.
Curve25519 is the curve y^2=x^3+486662x^2+x mod 2^255-19; every number
here is completely explained in the Curve25519 paper.

> even without NSA skullduggery make a nice single target for attack.

There have already been several detailed studies of the cost of finding
multiple discrete logs on the same curve (authors: Escott, Sager,
Selkirk, Tsapakidis, Kuhn, Struik, Hitchcock, Montague, Carter, Dawson,
Lee, Cheon, Hong, Bernstein, Lange). Basically, if finding one ECC key
costs 2^128, then finding 1000000 keys costs 1000*2^128, and the first
key found will still cost 2^128. For comparison, finding 1000000 AES
keys costs the same 2^128 as finding a single key, and the first AES key
will be found with cost only 2^128/1000000.

Yaron Sheffer writes:
> The recipient needs to test that the received point is actually on
> the relevant curve.

This is certainly an issue for the NIST curves. Fortunately, this test
is completely unnecessary for x-coordinate ECC using twist-secure curves
such as Curve25519. I introduced this approach at ECC 2001, using the
smaller curve y^2=x^3+7530x^2+x mod 2^226-5 as an illustration.

Peter Gutmann writes:
> For example if you used the recommended (until not too long ago) way
> to generate your k for (EC)DSA then you'd leak a tiny bit of your
> private key on each signature (again, that nasty propensity of DLP
> algorithms to leak the private key).

Ed25519 has three levels of defense against this type of problem.

First, k is chosen as a random 512-bit string, many bits larger than the
group order l (around 2^252). This is overkill (compare to the 64 bits
in Algorithm 2 in Section 4.1.1 of BSI Technical Guideline TR-03111) but
also an inexpensive and comprehensive defense.

Second, the group order l is very close to a power of 2, specifically
within 2^125 of 2^252, so the bias would be unnoticeable even if k were
as small as 256 bits.

Third, k is actually produced in a deterministic way as a secret hash,
so the k-generation mechanism is fully testable---there's no need to
worry about the implementor accidentally choosing a biased RNG.

---D. J. Bernstein
   Research Professor, Computer Science, University of Illinois at Chicago