Re: [TLS] Testing consensus for adding curve25519 to the EC named curve registry

Douglas Stebila <stebila@qut.edu.au> Mon, 09 September 2013 11:12 UTC

Return-Path: <stebila@qut.edu.au>
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 907E621E8187 for <tls@ietfa.amsl.com>; Mon, 9 Sep 2013 04:12:50 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -3.895
X-Spam-Level:
X-Spam-Status: No, score=-3.895 tagged_above=-999 required=5 tests=[AWL=2.000, BAYES_00=-2.599, HELO_EQ_AU=0.377, HOST_EQ_AU=0.327, RCVD_IN_DNSWL_MED=-4]
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 fU2N0z2VCbQ0 for <tls@ietfa.amsl.com>; Mon, 9 Sep 2013 04:12:38 -0700 (PDT)
Received: from qutexedge02.qut.edu.au (qutexedge02.qut.edu.au [131.181.191.3]) by ietfa.amsl.com (Postfix) with ESMTP id 30B4A21E80F5 for <tls@ietf.org>; Mon, 9 Sep 2013 04:12:22 -0700 (PDT)
Received: from qutexhub01.qut.edu.au (131.181.107.106) by qutexedge02.qut.edu.au (131.181.191.3) with Microsoft SMTP Server (TLS) id 8.3.83.0; Mon, 9 Sep 2013 21:12:18 +1000
Received: from QUTEXMBX01.qut.edu.au ([131.181.107.108]) by qutexhub01.qut.edu.au ([131.181.107.106]) with mapi; Mon, 9 Sep 2013 21:12:21 +1000
From: Douglas Stebila <stebila@qut.edu.au>
To: Patrick Pelletier <code@funwithsoftware.org>
Date: Mon, 9 Sep 2013 21:12:19 +1000
Thread-Topic: [TLS] Testing consensus for adding curve25519 to the EC named curve registry
Thread-Index: Ac6tTXNjhVCfgpLOSCWVFeTvERexzw==
Message-ID: <56C25B1D-C80F-495A-806C-5DD268731CD4@qut.edu.au>
References: <a84d7bc61003011620i66fc7dfdre62b548fdd5ef7dd@mail.gmail.com> <522D25B9.7010506@funwithsoftware.org>
In-Reply-To: <522D25B9.7010506@funwithsoftware.org>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
acceptlanguage: en-US
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Cc: "tls@ietf.org" <tls@ietf.org>
Subject: Re: [TLS] Testing consensus for adding curve25519 to the EC named curve registry
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: Mon, 09 Sep 2013 11:12:50 -0000

Recent news has highlighted doubts on a particular elliptic curve-based pseudorandom number generation algorithm, Dual_EC_DRBG, in which a particular point is used for which no explanation is given on how the point was generated. If it was generated so that its discrete logarithm is known with respect to another point, then a backdoor exists that can recover the seed.  (http://rump2007.cr.yp.to/15-shumow.pdf)

The NIST-standardized elliptic curves p256/p384/p512 are not related to this particular issue. 
- The prime p for each field has a special form chosen for efficiency (http://cacr.uwaterloo.ca/techreports/1999/corr99-39.pdf), not entirely unlike how the prime 2^155-19 was chosen for efficiency in curve25519.  There are no results that suggest that one prime is weaker than another prime for elliptic curve cryptography.
- The curve parameters were generated "verifiably at random", meaning a seed was chosen, and then the curve parameters a and b were generated by hashing the seed a pre-determined number of times using SHA-1.  (Appendix 4 ofhttp://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf, or Section 3.1.3.1 of SEC1 http://secg.org, or ANSI X9.62)  
- I don't think it's specified how the generator was chosen, but the Diffie-Hellman problem is self-reducible, so there are no weak generators.

There are other reasons to support curve25519, including efficiency and resistance to side-channel attacks because constant-time implementations.  But not because of concerns over backdoors in p256/p384/p512.

Douglas


On 2013-09-09, at 11:34 AM, Patrick Pelletier <code@funwithsoftware.org> wrote:

> Given the doubt that's recently been cast on the NIST curves, is it time to revive the idea of adding curve25519 as a named curve?
> 
> --Patrick
> 
> 
> On 3/1/10 4:20 PM, Adam Langley wrote:
>> We would like to start testing EC DHE in order to give our users
>> forward-secrecy.
>> 
>> In order to do this cheaply, one of the curves that we would like to
>> test with is curve25519[1]. There are several implementations of it
>> [2][3][4] and it's 3-4x faster than NIST's p256 (as implemented in
>> OpenSSL), while being constant-time.
>> 
>> Curve25519 doesn't currently appear on IANA's list of named curves[5]
>> and we would like to see it included.
>> 
>> As a first step I'd like to ask if there are any objections?
>> 
>> 
>> Cheers
>> 
>> AGL
>> 
>> 
>> [1] http://cr.yp.to/ecdh/curve25519-20060209.pdf
>> [2] http://cr.yp.to/ecdh.html
>> [3] http://code.google.com/p/curve25519-donna/
>> [4] http://bench.cr.yp.to/results-dh.html
>> [5] http://www.iana.org/assignments/tls-parameters/