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 
>