Re: [Cfrg] revised requirements for new curves

["Paterson, Kenny" <[e-mail]>]

Hi William,

On 08/09/2014 14:49, "William Whyte" <[e-mail]> wrote:

>Hi Kenny,
>
>Couple of comments on the interoperability requirements. I'm struggling to
>see how they significantly distinguish between different candidates and
>wonder if they're requirements as such, rather than simply things that we
>should bear in mind. In more detail:

They are definitely of the latter flavour.

>
>IN1: I don't understand how a curve could be incompatible with a TLS RFC.
>A
>new curve would be a new ciphersuite: to support a new curve, you reserve
>a
>ciphersuite identifier and define behavior for that ciphersuite
>identifier.
>Any behavior that's well-defined seems like it should be compatible (and
>you
>hint at this in the requirements-with-rationale version). Do you have a
>concrete example of what would be ruled out by this requirement?

No, I don't have a concrete example. Rather, this was just meant to
contrast with the previous list of requirements from David.

>
>IN2: I don't like the word "minimize" here, because if strictly
>interpreted
>it would bind us to using existing OIDs. And if this was rephrased as
>"keep
>to a reasonable level the work needed to generate..." I think it loses any
>meaning, because generating new OIDs as such is trivial. Is it possible to
>rephrase this in terms of "not introducing significant numbers of new data
>types" or something of the sort, which I think is the intent?

That's a good suggestion. The work is relatively light, but we don't want
to expand it more than is necessary, especially as someone will have to
write the Internet Draft and shepherd it through IETF.

Thanks for the inputs,

Kenny 

>
>Cheers,
>
>William
>
>-----Original Message-----
>From: Cfrg [mailto:[e-mail]] On Behalf Of Paterson, Kenny
>Sent: Monday, September 08, 2014 6:23 AM
>To: [e-mail]
>Subject: Re: [Cfrg] revised requirements for new curves
>
>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" <[e-mail]> 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
>>
>
>_______________________________________________
>Cfrg mailing list
>[e-mail]
>http://www.irtf.org/mailman/listinfo/cfrg