Re: [Cfrg] revised requirements for new curves
"Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk> Mon, 08 September 2014 10:23 UTC
Return-Path: <Kenny.Paterson@rhul.ac.uk>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 53BCC1A7002 for <cfrg@ietfa.amsl.com>; Mon, 8 Sep 2014 03:23:24 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.098
X-Spam-Level:
X-Spam-Status: No, score=0.098 tagged_above=-999 required=5 tests=[BAYES_50=0.8, RCVD_IN_DNSWL_LOW=-0.7, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Ss8fhtRieMON for <cfrg@ietfa.amsl.com>; Mon, 8 Sep 2014 03:23:20 -0700 (PDT)
Received: from emea01-am1-obe.outbound.protection.outlook.com (mail-am1lrp0015.outbound.protection.outlook.com [213.199.154.15]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 270DA1A6FC9 for <cfrg@irtf.org>; Mon, 8 Sep 2014 03:23:16 -0700 (PDT)
Received: from DBXPR03MB383.eurprd03.prod.outlook.com (10.141.10.15) by DBXPR03MB383.eurprd03.prod.outlook.com (10.141.10.15) with Microsoft SMTP Server (TLS) id 15.0.1015.19; Mon, 8 Sep 2014 10:23:14 +0000
Received: from DBXPR03MB383.eurprd03.prod.outlook.com ([10.141.10.15]) by DBXPR03MB383.eurprd03.prod.outlook.com ([10.141.10.15]) with mapi id 15.00.1015.018; Mon, 8 Sep 2014 10:23:14 +0000
From: "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk>
To: "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: revised requirements for new curves
Thread-Index: AQHPy07l29iFHJb+W02/iURsgQFUOw==
Date: Mon, 08 Sep 2014 10:23:14 +0000
Message-ID: <D0333B6F.2C8CF%kenny.paterson@rhul.ac.uk>
Accept-Language: en-GB, en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
user-agent: Microsoft-MacOutlook/14.4.3.140616
x-ms-exchange-transport-fromentityheader: Hosted
x-originating-ip: [134.219.199.37]
x-microsoft-antispam: BCL:0;PCL:0;RULEID:;UriScan:;
x-forefront-prvs: 03283976A6
x-forefront-antispam-report: SFV:NSPM; SFS:(6009001)(51704005)(24454002)(479174003)(199003)(189002)(64706001)(80022001)(46102001)(15975445006)(74662001)(54356999)(86362001)(90102001)(87936001)(110136001)(2656002)(66066001)(83072002)(92726001)(74482001)(21056001)(74502001)(83506001)(50986999)(2501002)(92566001)(15202345003)(97736003)(561944003)(99396002)(20776003)(85306004)(85852003)(77982001)(19580395003)(101416001)(36756003)(4396001)(83322001)(107046002)(107886001)(76482001)(105586002)(106356001)(2351001)(31966008)(81342001)(79102001)(106116001)(19580405001)(81542001)(95666004); DIR:OUT; SFP:; SCL:1; SRVR:DBXPR03MB383; H:DBXPR03MB383.eurprd03.prod.outlook.com; FPR:; MLV:sfv; PTR:InfoNoRecords; A:1; MX:1; LANG:en;
Content-Type: text/plain; charset="us-ascii"
Content-ID: <0C11435822FFCF48A04E7689D9ED80EA@eurprd03.prod.outlook.com>
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-OriginatorOrg: rhul.ac.uk
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/4p-Qoy4gfNvI0SICyVjLwrdENvk
Subject: Re: [Cfrg] revised requirements for new curves
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Mon, 08 Sep 2014 10:23:24 -0000
Dear All, After much deliberation, I've developed a set of requirements that I believe fairly reflect the discussions we've had as a community on the CFRG list, and at IETF 89, during the CFRG interim meeting and at IETF 90. I'm including them below, in two formats: 1. A clean list of requirements, with no rationale. 2. A list of requirements, interspersed with rationale and explanation of how I got to them from David McGrew's original list of requirements (which can be found here: http://www.ietf.org/mail-archive/web/cfrg/current/msg04655.html). Please read and reflect before posting (note that there is no prize for being the first to post). You may disagree with one, many, or maybe even all (!) the requirements I've listed. However, I believe they *do* represent a consensus view or rough consensus view (in all but one case, SE6), and it is a consensus-seeking approach that we are engaged in here. So to be explicit: please do not simply post "I do not agree with X or Y" - we've already had that debate. Instead, you are encouraged to post things like "I do not believe X was the majority view" or "I think we should modify X to say Y because that reflects better the consensus view". I would now propose that we discuss these requirements for a short period of time, to give everyone time to comment. We can then refine or change them as necessary. Regards, Kenny (for the CFRG chairs) Short version: -------------- Key to labelling of requirements: [C] - we've achieved consensus on this requirement (put another way, there's no serious disagreement on this point). [RC] - we've achieved rough consensus on this requirement (put another way, there's significant opposition to this requirement, but the majority view supports it). [NC] - the debate is fairly balanced, but we need to continue to make progress, and the chairs are recommending this requirement be adopted. Performance PE1. Required: amenable to both compact and fast implementations of curve operations in software, across a wide range of processor types. [C] PE2. Desired: amenable to both compact and fast implementations of curve operations in hardware. [RC] Security SE1. Required: the selected curves should be secure against reasonable and well-understood threats, including (but not necessarily limited to) Pollard rho attack, MOV/FR attacks, Smart-ASS attack, invalid-curve attacks, and twist attacks. [C] SE2. Required: curve operations (incorporating underlying field arithmetic) should be amenable to efficient, implementation in software whilst avoiding all data flow from secret values to timing. [C] SE3. Desired: curve operations (incorporating underlying field arithmetic) should be amenable to efficient implementation in hardware whilst avoiding all data flow from secret values to timing. [C] SE4. Desired: curve operations (incorporating underlying field arithmetic) should be amenable to efficient implementation in software and hardware whilst avoiding other known forms of side channel attack. [C] SE5. Required: each set of curve parameters should be generated by a well-defined procedure that allows only a limited and quantified amount of flexibility. If the selected procedure involves the choice of an initial seed, then the seed will be selected by multiple independent parties using a procedure having the property that no collusion of all but one or fewer of the parties can exert any control over the chosen seed. [RC] SE6. Required: the selected curves should provide levels of security that match to a good approximation 128-bit, 192-bit and 256-bit security levels, as these levels are currently commonly understood in the wider security community. [NC] Intellectual Property IP1. Required: securely, simply and efficiently implementable world-wide under royalty-free licensing terms. [C] IP2. Desired: securely, simply and efficiently implementable world-wide in a patent-free manner. [RC] Interoperability IN1. Required: compatible with current and forthcoming IETF RFCs for TLS. [C] IN2. Required: minimise work needed to generate suitable OBJECT IDENTIFIERs for Subject Public Key Information Fields, as defined in RFC 5480 (PKIX). [C] IN2. Desired: usable with minimal changes to existing IETF RFCs for CMS, SSH, IKE, IKEv2, Kerberos PKINIT. [RC] Longer version (with rationale): -------------------------------- Key to labelling of requirements: [C] - we've achieved consensus on this requirement (put another way, there's no serious disagreement on this point). [RC] - we've achieved rough consensus on this requirement (put another way, there's significant opposition to this requirement, but the majority view supports it). [NC] - the debate is fairly balanced, but we need to continue to make progress, and the chairs are recommending this requirement be adopted. Performance PE1. Required: amenable to both compact and fast implementations of curve operations in software, across a wide range of processor types. [C] PE2. Desired: amenable to both compact and fast implementations of curve operations in hardware. [RC] [Hardware speed is secondary to software speed for this exercise; also do not demand reuse of code or hardware, as it handicaps performance. The main curve operations of interest are: - Scalar multiplication, fixed base, variable base and double-base (important in ECDHE and ECDSA); - Point addition (needed in ECDSA).] [Removed: "R3: Desired: re-use components between signatures and key exchange algorithms"; this seems likely to happen naturally to some extent, by picking a single curve at a given security level or by selecting curves at a given security level that share a prime p and reusing code for field arithmetic. Moreover, the original request from the TLS WG signalled that different curves would be acceptable for different cryptographic functions. There's been a lot of discussion on the list related to this point; the lack of a hard requirement for a single curve at each security level seems to represent a majority view of list participants.] Security SE1. Required: the selected curves should be secure against reasonable and well-understood threats, including (but not necessarily limited to) Pollard rho attack, MOV/FR attacks, Smart-ASS attack, invalid-curve attacks, and twist attacks. [C] SE2. Required: curve operations (incorporating underlying field arithmetic) should be amenable to efficient, implementation in software whilst avoiding all data flow from secret values to timing. [C] SE3. Desired: curve operations (incorporating underlying field arithmetic) should be amenable to efficient implementation in hardware whilst avoiding all data flow from secret values to timing. [C] [SE2 and SE3: aka constant time implementation. These requirements reflect the view that timing attacks are the most important class of side channel for TLS environments. A harder requirement for software is notwithstanding the wide range of hardware-focussed environments in which TLS is currently being used or will in future be used.] SE4. Desired: curve operations (incorporating underlying field arithmetic) should be amenable to efficient implementation in software and hardware whilst avoiding other known forms of side channel attack. [C] [Removed: R8. Required: amenable to constant-time implementations, to avoid side channel attacks. R9. Required: resist twist attacks. as these are now incorporated under SE1 and SE2, SE3, SE4.] SE5. Required: each set of curve parameters should be generated by a well-defined procedure that allows only a limited and quantified amount of flexibility. If the selected procedure involves the choice of an initial seed, then the seed will be selected by multiple independent parties using a procedure having the property that no collusion of all but one or fewer of the parties can exert any control over the chosen seed. [RC] [This requirement refines a previous requirement: R10. Required: curve parameters should have good provenance; random curves should be provably pseudorandom. The amount of flexibility can be used as a criterion for selecting between different proposals; it does not seem helpful to put a hard bound on it at this stage.] SE6. Required: the selected curves should provide levels of security that match to a good approximation 128-bit, 192-bit and 256-bit security levels, as these levels are currently commonly understood in the wider security community. [NC] [This requirement comes from the original TLS WG request, strengthened to mandate the selection of curve(s) at the 192-bit security level. While we did not achieve even rough consensus that the choices we make need to be easily explainable by us and others to less sophisticated consumers of cryptography, the emphasis on "as these levels are currently commonly understood in the wider community" is deliberate on my part; in other words, I recognise the lack of consensus on this point, but I am proposing this wording in order to enable us to make progress. If SE6 were to be adopted, we would need to reach a common view on what "to a good approximation" means; I'd suggest "at most 4 bits either way for Pollard rho" so as to reduce potential conflict with SE5.] Intellectual Property IP1. Required: securely, simply and efficiently implementable world-wide under royalty-free licensing terms. [C] IP2. Desired: securely, simply and efficiently implementable world-wide in a patent-free manner. [RC] [We quickly reached consensus (respectively, rough consensus) on these points on the list.] Interoperability [What follows replaces: "R6. Desired: can be used with current software implementations (using different curve parameters) of TLS, PKIX, SSH, and IKE [4] R7. Desired: can be used within current ECC standards of TLS, PKIX, SSH, and IKE [4]" The rationale for replacing these is based on CFRG discussions pointing to the fact that significant performance and security benefits may accrue by using different curves, e.g. relative ease of protecting E/tE-form curve operations against timing attacks as compared to W-form curves. However, such choices are unlikely to allow for significant software reuse. Moreover, adopting such curves will require extensions to existing PKIX RFCs, notably RFC 5480, if we want to use ECDSA certs for new curves.] IN1. Required: compatible with current and forthcoming IETF RFCs for TLS. [C] [We've been asked by TLS WG to conduct this exercise; our primary goal is to come up with curves that they can easily use in currently deployed and anticipated future versions of TLS. In practice, this is a relatively easy requirement to meet because of the flexibility that the TLS WG has signalled is available to CFRG in terms of curves and wire formats.] IN2. Required: minimise work needed to generate suitable OBJECT IDENTIFIERs for Subject Public Key Information Fields, as defined in RFC 5480 (PKIX). [C] [This requirement is more a reminder to us that this work will need to be done in order to be able to issue ECDSA certificates using the new curves. Discussion on list: http://www.ietf.org/mail-archive/web/cfrg/current/msg04874.html.] IN2. Desired: usable with minimal changes to existing IETF RFCs for CMS, SSH, IKE, IKEv2, Kerberos PKINIT. [RC] ["desired" rather than "required" because our main focus is TLS in this exercise, rather than other protocols. Still, we should be aware that what we recommend as alternatives to NIST curves in CFRG is likely to be picked up by other groups. More discussion is needed to determine what the implications of our selections would be for other IETF applications.] On 31/08/2014 22:05, "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk> wrote: >Dear all, > >I've spent today reviewing all the messages to CFRG on new curves - those >concerning requirements (our current phase of enquiry), and more >generally. It's been interesting and informative. I want to thank everyone >who has participated to date. It seems (to me at least) that almost >everything that could be said about requirements has now been said. The >traffic on the list on this topic has also slowed markedly, another sign >that this phase is reaching a natural conclusion. > >In the next day or two, I will send to the list a proposal for a list of >requirements that we will use for the second phase of our investigation: >selecting curves to recommend to the TLS WG. I've made careful notes on >all the contributions to the requirements discussion, and my sense it that >we do have a rough consensus concerning what these requirements should be. > >NB: I use the word "rough" deliberately here - in looking over the >messages to the list, of course I can see frequent disagreements about >requirements, but in each case, sufficiently many independent views have >been expressed one way or another that a *rough* consensus is clear on >pretty much every issue of substance, even if a perfect harmony of views >has not been expressed. > >So, more news from me soon... > >Best regards, > >Kenny >
- Re: [Cfrg] revised requirements for new curves Paterson, Kenny
- Re: [Cfrg] revised requirements for new curves William Whyte
- Re: [Cfrg] revised requirements for new curves Manuel Pégourié-Gonnard
- Re: [Cfrg] revised requirements for new curves Phillip Hallam-Baker
- Re: [Cfrg] revised requirements for new curves Stephen Farrell
- Re: [Cfrg] revised requirements for new curves Paterson, Kenny
- Re: [Cfrg] revised requirements for new curves Paterson, Kenny
- Re: [Cfrg] revised requirements for new curves Watson Ladd
- Re: [Cfrg] revised requirements for new curves Paterson, Kenny
- Re: [Cfrg] revised requirements for new curves David Jacobson
- Re: [Cfrg] revised requirements for new curves Manuel Pégourié-Gonnard
- Re: [Cfrg] revised requirements for new curves D. J. Bernstein
- Re: [Cfrg] revised requirements for new curves Michael Hamburg
- Re: [Cfrg] revised requirements for new curves Paterson, Kenny
- Re: [Cfrg] revised requirements for new curves Adam Langley
- Re: [Cfrg] revised requirements for new curves Paterson, Kenny
- Re: [Cfrg] revised requirements for new curves Adam Langley
- Re: [Cfrg] revised requirements for new curves Damien Miller
- Re: [Cfrg] revised requirements for new curves Damien Miller
- Re: [Cfrg] revised requirements for new curves Torsten Schuetze
- Re: [Cfrg] revised requirements for new curves Eric Rescorla
- Re: [Cfrg] revised requirements for new curves Markulf Kohlweiss
- Re: [Cfrg] revised requirements for new curves Phillip Hallam-Baker
- Re: [Cfrg] revised requirements for new curves Alyssa Rowan
- Re: [Cfrg] revised requirements for new curves Michael Hamburg
- Re: [Cfrg] revised requirements for new curves Phillip Hallam-Baker
- Re: [Cfrg] revised requirements for new curves Michael Hamburg
- Re: [Cfrg] revised requirements for new curves Andrey Jivsov
- Re: [Cfrg] revised requirements for new curves Andrey Jivsov