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.