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

Dan Brown <dbrown@certicom.com> Tue, 10 September 2013 01:22 UTC

Return-Path: <dbrown@certicom.com>
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 A3B3111E816D for <tls@ietfa.amsl.com>; Mon, 9 Sep 2013 18:22:58 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -6.599
X-Spam-Level:
X-Spam-Status: No, score=-6.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, 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 ED-GXs6dhGX9 for <tls@ietfa.amsl.com>; Mon, 9 Sep 2013 18:22:55 -0700 (PDT)
Received: from mhs061cnc.rim.net (mhs061cnc.rim.net [208.65.73.35]) by ietfa.amsl.com (Postfix) with ESMTP id 5DA6811E813D for <tls@ietf.org>; Mon, 9 Sep 2013 18:22:51 -0700 (PDT)
X-AuditID: 0a412830-b7f576d00000095e-78-522e74639fc5
Received: from XCT103CNC.rim.net (xct103cnc.rim.net [10.65.161.203]) (using TLS with cipher AES128-SHA (128/128 bits)) (Client did not present a certificate) by mhs061cnc.rim.net (SBG) with SMTP id 88.15.02398.3647E225; Mon, 9 Sep 2013 20:22:43 -0500 (CDT)
Received: from XCT113CNC.rim.net (10.65.161.213) by XCT103CNC.rim.net (10.65.161.203) with Microsoft SMTP Server (TLS) id 14.3.123.3; Mon, 9 Sep 2013 21:22:42 -0400
Received: from XMB117CNC.rim.net ([fe80::24f3:cc30:b596:7ca0]) by XCT113CNC.rim.net ([::1]) with mapi id 14.03.0123.003; Mon, 9 Sep 2013 21:22:42 -0400
From: Dan Brown <dbrown@certicom.com>
To: Douglas Stebila <stebila@qut.edu.au>, Nick Mathewson <nickm@torproject.org>
Thread-Topic: [TLS] Testing consensus for adding curve25519 to the EC named curve registry
Thread-Index: AQHOrPzUSgKBdqWRokmt5ggMXGJ/7Zm9g/qAgABVnwCAAHtwAIAAHIYA
Date: Tue, 10 Sep 2013 01:22:41 +0000
Message-ID: <20130910012240.5595281.33313.3530@certicom.com>
References: <a84d7bc61003011620i66fc7dfdre62b548fdd5ef7dd@mail.gmail.com> <522D25B9.7010506@funwithsoftware.org> <56C25B1D-C80F-495A-806C-5DD268731CD4@qut.edu.au> <CAKDKvuw_X4D0bhEUN5MQOeJUgPB8y6v7BspEk_p20Nw=QPgvpA@mail.gmail.com> <FAAC109A-AFAC-4BE3-B680-4E474E6072AD@qut.edu.au>
In-Reply-To: <FAAC109A-AFAC-4BE3-B680-4E474E6072AD@qut.edu.au>
Accept-Language: en-CA, en-US
Content-Language: en-CA
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
Content-Type: text/plain; charset="utf-8"
Content-ID: <8CFB774F62C2BC40BFE19B31438BCBF6@rim.com>
content-transfer-encoding: base64
MIME-Version: 1.0
X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFrrIKsWRmVeSWpSXmKPExsXC5bjwtG5yiV6QwZ8XkhYXjm5gtzi36T2T xafzXYwOzB5Llvxk8tiz/gubx+b1l9kCmKMaGG0S8/LySxJLUhVSUouTbZV8UtMTcxQCijLL EpMrFVwyi5NzEjNzU4uUFDJTbJVMlBQKchKTU3NT80pslRILClLzUpTsuBQwgA1QWWaeQmpe cn5KZl66rZJnsL+uhYWppa6hkp0uEkj4x53xrXsKc8Ec5Yr55+QaGFcodTFyckgImEg0Hz/D DmGLSVy4t56ti5GLQ0ignUni0fxuRghnBaPE+ZcXWSCc2YwSJ/5vZgNpYRNQlbh/9BxzFyMH h4hAoMSEK1YgYWYBRYn3l+axgNjCAtESv/43MYHYIgIxEmv/rIEqd5O4sa0axGQBmnJsYRhI Ba+AjcStSS9YITYtZJJ4+L0ZbBOngJ3Eh0e7wUYyCshK7D57nQlilbjEvvm7mSEeEJBYsuc8 lC0q8fLxP1aQ+cwCmhLrd+lDlJtJ7Do6iRnmyindD9kh9gpKnJz5BGy8kICCxJXr+1gmMErM QrJhFsKkWUgmzUIyaRaSSQsYWVcxCuZmFBuYGSbnJesVZebq5aWWbGIEJx8Ngx2M799bHGIU 4GBU4uHl8NMLEmJNLCuuzD3EKMHBrCTCu4EZKMSbklhZlVqUH19UmpNafIjRFRhWE5mluJPz gYkxryTe2MAAN0dJnNdV5UOgkEA6MNllp6YWpBbBzGHi4JRqYNz7+dtipq3rJTd0XuNdE/+i 5PaCe6daqvxn6O3muGgq9HyRSkdH4m8PQeaObzkS5q2KgpPe+Z9hlX90W+JezwV3/n21X5Y8 PXt030yJE1rTkmRLYnSjVhpIfzu4s3dtd+0Ge8sdZaseGv0/vO39pyeP7c3KJeptzecc/KzD bVhw6MnFxphvzbOVWIozEg21mIuKEwHtQg1eZAMAAA==
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: Tue, 10 Sep 2013 01:22:58 -0000

I'm the current editor of ANSI X9.62 and X9.63, but joined X9F1 a little later than the‎ time in question, so am not the best historical source.

‎Anyway, I had thought the 15 NIST curves were included in ANSI X9.63 in 2001, but most were not in X9.62 in its first 1998 version, and only added in the 2005 version.

The curve seed sources were not documented in ANSI or NIST docs. I've wondered about it a few times, but could never see a concrete problem. At least intuitively, it would only be a problem if:

1) a large fraction of elliptic curves were weak, or

2) sha1 preimages are easy to find and some unknown but rare class of elliptic curves are weak.

‎Both of these would undermine more than just the curve choice, and seem extremely unlikely.

An alternative would have been to select the seeds in a canonical way, eg as the smallest integer above some math constant causing the curve generated via the hash to be good. In this case, the curve could be said to be pseudorandom‎, but not random.

I welcome any points or info I've missed, and will gladly forward to the rest of X9F1.

...

The generators for the NIST curves are not verifiably random, but X9.62-2005 added a method to generate them that way, for new curves or algorithms (eg X9.92 uses this method).

ECDSA does not share the random self-reducibility property with ECDH‎, hence the check that r is not zero (and vr gens for new curves to supplement the r check ).

...

The ECRNG standards in question do have options for users to select verifiably random constants, which removes any doubts, unless sha512 is weak.

Given the importance of key generation, some might consider the cost of using an ECRNG. Others just need keys faster. Hence the options in standards, eg HMAC and AES based RNGs.



Sent from my BlackBerry 10 smartphone on the Rogers network.
From: Douglas Stebila
Sent: Monday, September 9, 2013 7:41 PM
To: Nick Mathewson
Cc: tls@ietf.org
Subject: Re: [TLS] Testing consensus for adding curve25519 to the EC named curve registry


On 2013/09/10, at 02:18, Nick Mathewson <nickm@torproject.org>; wrote:

> On Mon, Sep 9, 2013 at 7:12 AM, Douglas Stebila <stebila@qut.edu.au>; wrote:
> [...]
>> - 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 of http://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)
>
> A possibly foolish question, but I couldn't find the answer in any of
> the documents you listed:
>
> Is it documented how the seeds were chosen?

I haven't found any information on how the seeds were chosen. The earliest reference I have listing the seeds is a September 1998 draft of ANSI X9.62, a copy of which is available here: https://github.com/ANSSI-FR/parsifal/blob/master/docs/tls/X9-62-1998--ECDSA.pdf, but this provides no reason for the choice of seeds. Maybe there's someone from X9F on this mailing list who has some historical insight?

Douglas


_______________________________________________
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

---------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.