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

Douglas Stebila <stebila@qut.edu.au> Wed, 11 September 2013 23:33 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 A895221F9A6C for <tls@ietfa.amsl.com>; Wed, 11 Sep 2013 16:33:28 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.484
X-Spam-Level:
X-Spam-Status: No, score=-4.484 tagged_above=-999 required=5 tests=[AWL=-0.078, BAYES_05=-1.11, 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 PrlzX2Zcb8qw for <tls@ietfa.amsl.com>; Wed, 11 Sep 2013 16:33:22 -0700 (PDT)
Received: from QUTEXEDGE04.qut.edu.au (qutexedge04.qut.edu.au [131.181.191.21]) by ietfa.amsl.com (Postfix) with ESMTP id E2F0511E8116 for <tls@ietf.org>; Wed, 11 Sep 2013 16:33:21 -0700 (PDT)
Received: from QUTEXHUB04.qut.edu.au (131.181.186.100) by qutexedge04.qut.edu.au (131.181.191.21) with Microsoft SMTP Server (TLS) id 14.2.247.3; Thu, 12 Sep 2013 09:33:20 +1000
Received: from QUTEXMBX01.qut.edu.au ([131.181.107.108]) by QUTEXHUB04.qut.edu.au ([131.181.186.100]) with mapi; Thu, 12 Sep 2013 09:32:57 +1000
From: Douglas Stebila <stebila@qut.edu.au>
To: Nick Mathewson <nickm@torproject.org>
Date: Thu, 12 Sep 2013 09:32:57 +1000
Thread-Topic: [TLS] Testing consensus for adding curve25519 to the EC named curve registry
Thread-Index: Ac6vRz7KkXi7q2yET0CiH4ksrYgQpw==
Message-ID: <834B655C-1C07-412F-B190-AE5DDE2942F1@qut.edu.au>
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> <20130910012240.5595281.33313.3530@certicom.com> <CAKDKvuxYQOxCaO5XN_53721xdwEjHiRveMRVVPjfx9oLd2tkMg@mail.gmail.com>
In-Reply-To: <CAKDKvuxYQOxCaO5XN_53721xdwEjHiRveMRVVPjfx9oLd2tkMg@mail.gmail.com>
Accept-Language: en-US, en-AU
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
acceptlanguage: en-US, en-AU
Content-Type: text/plain; charset="iso-8859-1"
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: Wed, 11 Sep 2013 23:33:28 -0000

On the topic of a smallish fraction of elliptic curves being weak, I asked Alfred Menezes, a prof at Waterloo who knows a lot about elliptic curves and was active in the development of ECC in the late 90s; he wrote this to me:

> The idea at the time was to rule out the possibility of someone choosing
> *very* special curves. For example, if one knows that elliptic curves
> of a certain order N over a certain prime field GF(p) are weak, then it
> would not be possible to find a seed which gave such a curve. It was felt 
> that if a significant proportion of elliptic curves (e.g. 1/10000000) over 
> a fixed field GF(p) or GF(2^m) (with m prime) which meet the standard 
> requirements (e.g. group order divisible by a large prime, sufficiently 
> large embedding degree, etc.) was found to be weak, then that would in 
> any case spell the end of ECC. Certainly if one has a weak curve then 
> one can produce a much larger family of weak curves by low-degree 
> isogeny walks.

This is quite similar to what Dan has said in his reply to your email, that existence of a non-negligibly sized class of weak curves would jeopardize other randomly selected curves.

I agree with you that it would be more comforting to know where the seeds came from.  Alfred told me he didn't know.  And I can't see any discernible pattern in the seeds (nothing obvious in ASCII; not in the first few million decimal digits of e or the first 200 million decimal digits of pi).  

But I also find convincing the argument that even one in 2^50 or 2^60 randomly selected curves being weak would cause major doubts about the security of random 256-bit curves.  There are at least distinct 2^256 elliptic curves over a 256-bit prime, and if even one in 2^60 was weak, then there would be roughly 2^200 weak elliptic curves over that prime.  

To me, this is saying that either you reject all randomly generated curves of (near) prime order over a prime field, or you believe there is no non-negligbly sized class of weak curves.  

Douglas


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

> On Mon, Sep 9, 2013 at 9:22 PM, Dan Brown <dbrown@certicom.com>; wrote:
>> 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.
> 
> That's true, so long as "large fraction" and "rare" are defined
> appropriately.  But I think what most of the people who worry about
> this are worried about is something like:
> 
> 3) A small-ish fraction of elliptic curves (say, one in every
> quadrillion or quintillion or so) has some as-yet-unknown weakness,
> and building a sha1 brute-forcing engine to find seeds that would
> produce such curves was economically viable the late 1990s.
> 
> After a little time investigating SHA1 speeds on late-1990s FPGAs,
> special-purpose chips, and general purpose CPUs, a
> back-of-the-envelope calculation suggests that, given about ten
> million dollars of hardware and about half a year's worth of
> processing time, searching quintillions of seeds to find curves with
> desired properties wouldn't have been unrealistic.
> 
> Now, none of this means that the seeds in question actually _were_
> chosen in any hostile way, of course. But it would make it more
> comforting if anybody could point out where the seeds actually came
> from.
> 
> best wishes,
> -- 
> Nick Mathewson