Re: [TLS] Testing consensus for adding curve25519 to the EC named curve registry
Dan Brown <dbrown@certicom.com> Wed, 11 September 2013 17:12 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 C6ED221F8497 for <tls@ietfa.amsl.com>; Wed, 11 Sep 2013 10:12:51 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -5.392
X-Spam-Level:
X-Spam-Status: No, score=-5.392 tagged_above=-999 required=5 tests=[AWL=-1.207, BAYES_40=-0.185, 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 FDRy19UjmtpO for <tls@ietfa.amsl.com>; Wed, 11 Sep 2013 10:12:39 -0700 (PDT)
Received: from mhs061cnc.rim.net (mhs061cnc.rim.net [208.65.73.35]) by ietfa.amsl.com (Postfix) with ESMTP id D9E2C11E81D7 for <tls@ietf.org>; Wed, 11 Sep 2013 10:12:22 -0700 (PDT)
X-AuditID: 0a412830-b7f576d00000095e-1b-5230a4677308
Received: from XCT101CNC.rim.net (xct101cnc.rim.net [10.65.161.201]) (using TLS with cipher AES128-SHA (128/128 bits)) (Client did not present a certificate) by mhs061cnc.rim.net (SBG) with SMTP id 0D.84.02398.764A0325; Wed, 11 Sep 2013 12:12:07 -0500 (CDT)
Received: from XCT114CNC.rim.net (10.65.161.214) by XCT101CNC.rim.net (10.65.161.201) with Microsoft SMTP Server (TLS) id 14.3.123.3; Wed, 11 Sep 2013 13:12:06 -0400
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT114CNC.rim.net ([::1]) with mapi id 14.03.0123.003; Wed, 11 Sep 2013 13:12:06 -0400
From: Dan Brown <dbrown@certicom.com>
To: "'nickm@torproject.org'" <nickm@torproject.org>
Thread-Topic: [TLS] Testing consensus for adding curve25519 to the EC named curve registry
Thread-Index: AQHOrPzUSgKBdqWRokmt5ggMXGJ/7Zm9g/qAgABVnwCAAHtwAIAAHIYAgAJ5mQD//8fn4A==
Date: Wed, 11 Sep 2013 17:12:05 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF5BCF149@XMB116CNC.rim.net>
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-CA, en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
x-originating-ip: [10.65.160.250]
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg="SHA1"; boundary="----=_NextPart_000_0000_01CEAEF0.830A2FB0"
MIME-Version: 1.0
X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFtrNJsWRmVeSWpSXmKPExsXC5bjwpG76EoMgg5nvRSwuHN3AbnFu03sm i0/nuxgdmD2WLPnJ5LFn/Rc2j83rL7MFMEeJ2KSk5mSWpRbp2yFYCSIZR6acYi3YmFLR/2An ewNjV0wXIyeHhICJxI7Dv5khbDGJC/fWs3UxcnEICbQzSWzetBPKWckosX/XI7AqIYHZjBLL dvKC2GwCqhL3j54Di4sIGEus/v0EzGYWCJLYsnAaE4gtLBAtsfvIalaImhiJtX/WQNWHSXy+ vA0szgI051JzI1g9r4CbROvrnYxQu5glbp+XBrE5BQIlOv72gMUZBWQldp+9zgSxS1zi1pP5 TBAfiEg8vHiaDcIWlXj5+B8rhK0ocWLZCrBnmAV6GSW2/1jKDLFMUOLkzCcsEMsUJK5c38cy gVF8FpK5s5D1zELSM4uRAyihJ9G2kRGiXl5i+9s5zBC2rcT+qyuhbEWJKd0P2SFsU4nXRz8y LmDkWMUomJtRbGBmmJyXrFeUmauXl1qyiREc2xoGOxjfv7c4xCjAwajEwysyzSBIiDWxrLgy 9xCjCtCMRxtWX2CUYsnLz0tVEuFtnwCU5k1JrKxKLcqPLyrNSS0+xPiZERimE5mluJPzgQkp ryTe2MCAWI4ojGNoZGluaGlmbGZqYmg2eISVxHldVT4ECgmkJ5akZqemFqQWwbzNxMEp1cDI tcrz9NMFu76qP7+gN6/XUMdXV7bonp2QAesVMSXtzbnmFu9az5Umc0/KP/Doga7bDZMF0d7f Jm1zTQ7Of1E9deljti39RW+EO6w6AnL29ExpVZj00cd27d3H0+W/fTs0J2r1uldrNwW+88o+ Lu4sktSfK3dePM5zAfcD4wI9h62VX481JL1SYinOSDTUYi4qTgQACLjY7c4DAAA=
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 17:12:52 -0000
> -----Original Message----- > From: nick.a.mathewson@gmail.com [mailto:nick.a.mathewson@gmail.com] On > Behalf Of Nick Mathewson > Sent: Wednesday, September 11, 2013 11:10 AM > To: Dan Brown > On Mon, Sep 9, 2013 at 9:22 PM, Dan Brown <dbrown@certicom.com> wrote: > > > > 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. > [DB] Good point. My colleague Randy Tsang mentioned a similar point to me yesterday. Your situation (3) is what I meant by my (1). By a "large fraction", I meant one with an inverse representing a feasible number of steps. I should have clarified this, because there are many other reasonable meanings of large fraction. Sorry. More importantly, I should clarify why I consider this to undermine more than just the curve choice. Firstly, if the hypothetical weakness was that the DLP was easy, then installing such a backdoor would be unwise, because it would backfire once somebody else discovers the weakness. I do not see how the hypothetical weakness could be a high-entropy trapdoor, unless SHA1 inversion was possible. (This would be analogous to my scenario #2.) So, an open backdoor would be feasible for somebody else to discover the weakness, only being a matter of insight. Secondly, if we take the view that an undiscovered classes of weak curves might exist, say with density 2^(-30), and needing research work 2^(40) to find, then we must reduce the claimed security level of any given curve, to a level appropriate to these levels, 70 bits in this example. Given that many people would be likely to use the same curve, this level may not be acceptable. In other words, the hypothesis of your scenario 3 above, also mildly jeopardizes other curves (but not to the same extent as a maliciously-chosen curve, of course). In other words, a simplistic viewpoint is to define security levels against best-known attacks, which excludes all the situations above. A more sophisticated type of security level attempts to anticipate as-yet-undiscovered or as-yet-undisclosed attacks, and by tracking the rate of discovery, inferring from evidence whether attacks are undisclosed, and so on. Aside: it should be comforting that NIST also recommends "Koblitz" curves which have no wiggle room, and hence no opportunity for a backdoor. (Some articles on efficient scalar multiplication of Koblitz curves are informative here.) Such curves are canonical, rather than verifiably random. I believe that Curve25519 is also canonical in a similar way in that it relies on small curve coefficients. One security argument against canonical curves is that they are special and would be more likely belong to some weak class (but see (*) below). (Similar special class: curves of order p defined over Fp are weak.) For various reasons, many have gravitated away from Koblitz curves. Perhaps the ideal is a combination of verifiably random and canonical, which I mentioned in my previous message. Again: hash a small value, or otherwise wiggle-free value, to obtain the curve of desirable order, etc. This might be worthwhile, though not tremendously worthwhile by the arguments above. (*) On the other hand, special cases may also resist some attacks. For example, Jao recently proposed using supersingular curves to avoid subexponential-time isogenies.
- [TLS] Testing consensus for adding curve25519 to … Adam Langley
- Re: [TLS] Testing consensus for adding curve25519… Russ Housley
- Re: [TLS] Testing consensus for adding curve25519… Rob P Williams
- Re: [TLS] Testing consensus for adding curve25519… Patrick Pelletier
- Re: [TLS] Testing consensus for adding curve25519… Douglas Stebila
- Re: [TLS] Testing consensus for adding curve25519… Douglas Stebila
- Re: [TLS] Testing consensus for adding curve25519… Nick Mathewson
- [TLS] Curve25519 in TLS Simon Josefsson
- Re: [TLS] Testing consensus for adding curve25519… Nico Williams
- Re: [TLS] Testing consensus for adding curve25519… Douglas Stebila
- Re: [TLS] Testing consensus for adding curve25519… Dan Brown
- Re: [TLS] Curve25519 in TLS Rob Stradling
- Re: [TLS] Testing consensus for adding curve25519… Nick Mathewson
- Re: [TLS] Testing consensus for adding curve25519… Dan Brown
- Re: [TLS] Curve25519 in TLS Simon Josefsson
- Re: [TLS] Testing consensus for adding curve25519… Douglas Stebila
- Re: [TLS] Curve25519 in TLS Kyle Hamilton
- Re: [TLS] Curve25519 in TLS Rob Stradling
- Re: [TLS] Curve25519 in TLS Yoav Nir
- Re: [TLS] Curve25519 in TLS Dan Brown
- Re: [TLS] Curve25519 in TLS Bodo Moeller
- [TLS] Koblitz curves [was RE: Curve25519 in TLS] Dan Brown
- Re: [TLS] Curve25519 in TLS Rob Stradling
- Re: [TLS] Curve25519 in TLS Simon Josefsson
- Re: [TLS] Curve25519 in TLS Rob Stradling
- Re: [TLS] Curve25519 in TLS Nico Williams
- Re: [TLS] Curve25519 in TLS Rob Stradling
- Re: [TLS] Curve25519 in TLS Paul Bakker
- Re: [TLS] Curve25519 in TLS Yoav Nir
- Re: [TLS] Curve25519 in TLS Rob Stradling
- [TLS] Curve25519 in TLS Simon Josefsson
- [TLS] Ed25519 for PKIX Simon Josefsson
- Re: [TLS] Ed25519 for PKIX Adam Langley
- Re: [TLS] Ed25519 for PKIX Simon Josefsson
- Re: [TLS] Curve25519 in TLS Manuel Pégourié-Gonnard
- Re: [TLS] Curve25519 in TLS Martin Rex
- Re: [TLS] Curve25519 in TLS Juho Vähä-Herttua
- Re: [TLS] Curve25519 in TLS Manuel Pégourié-Gonnard
- Re: [TLS] Curve25519 in TLS Watson Ladd
- Re: [TLS] Curve25519 in TLS Manuel Pégourié-Gonnard
- Re: [TLS] Curve25519 in TLS Simon Josefsson
- Re: [TLS] Curve25519 in TLS Martin Rex
- Re: [TLS] Curve25519 in TLS Nico Williams