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

Nick Mathewson <nickm@torproject.org> Wed, 11 September 2013 15:10 UTC

Return-Path: <nick.a.mathewson@gmail.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 A2CCE21E8118 for <tls@ietfa.amsl.com>; Wed, 11 Sep 2013 08:10:25 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.978
X-Spam-Level:
X-Spam-Status: No, score=-1.978 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, FM_FORGED_GMAIL=0.622, NO_RELAYS=-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 3DNOzKCeTXEi for <tls@ietfa.amsl.com>; Wed, 11 Sep 2013 08:10:25 -0700 (PDT)
Received: from mail-qe0-x230.google.com (mail-qe0-x230.google.com [IPv6:2607:f8b0:400d:c02::230]) by ietfa.amsl.com (Postfix) with ESMTP id 1C1B711E81B3 for <tls@ietf.org>; Wed, 11 Sep 2013 08:10:24 -0700 (PDT)
Received: by mail-qe0-f48.google.com with SMTP id nd7so4518517qeb.21 for <tls@ietf.org>; Wed, 11 Sep 2013 08:10:24 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; bh=ldjMmi/gC69s9X66kpD9oge2Ky+yVpS8UKitQM0Mmlc=; b=E0opElzNAma0ZqATe3ZA/PWwI3b9LjA3ZXbJBagNmLAb8veGALGZiVj6uWJwhNZmfS qc9pIxWjpNorI9p3N5bInw0nKaVPCKl8EBK/fnsib6Z8564M1d7NBG9yg5mRdQk3Cxkb 0veAryAACQEnHSK1Y8IQVvozjKRcpuWgOL+/vOgDDj/CecvbFEuBoqCYFxRnINlpSKUu SwjQHMav6p1xbizWTkDs+eMsDzfkkkNkXxTKkyIsOUUJUOlxTjYJWfrXyDktMGbMzazo 4I+XhduI13SVdwwSELm0DA9RFhLR3UnbvuX8Kr9O65352xLg83hdav9u7qEOuu7NNDnI mw5A==
MIME-Version: 1.0
X-Received: by 10.49.1.9 with SMTP id 9mr3920832qei.51.1378912224515; Wed, 11 Sep 2013 08:10:24 -0700 (PDT)
Sender: nick.a.mathewson@gmail.com
Received: by 10.140.22.81 with HTTP; Wed, 11 Sep 2013 08:10:24 -0700 (PDT)
In-Reply-To: <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> <20130910012240.5595281.33313.3530@certicom.com>
Date: Wed, 11 Sep 2013 11:10:24 -0400
X-Google-Sender-Auth: tuRikIhrx4iarglgWAPMaK4tkVY
Message-ID: <CAKDKvuxYQOxCaO5XN_53721xdwEjHiRveMRVVPjfx9oLd2tkMg@mail.gmail.com>
From: Nick Mathewson <nickm@torproject.org>
To: Dan Brown <dbrown@certicom.com>
Content-Type: text/plain; charset=ISO-8859-1
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 15:10:25 -0000

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