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

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.