Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Consensus and a way forward]

"Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk> Fri, 19 December 2014 10:46 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 4E6FA1A87E2 for <cfrg@ietfa.amsl.com>; Fri, 19 Dec 2014 02:46:14 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.302
X-Spam-Level:
X-Spam-Status: No, score=-1.302 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, J_CHICKENPOX_12=0.6, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=no
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 uZNsZrNNRuIB for <cfrg@ietfa.amsl.com>; Fri, 19 Dec 2014 02:46:10 -0800 (PST)
Received: from emea01-am1-obe.outbound.protection.outlook.com (mail-am1on0600.outbound.protection.outlook.com [IPv6:2a01:111:f400:fe00::600]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id A660F1A87E0 for <cfrg@irtf.org>; Fri, 19 Dec 2014 02:46:09 -0800 (PST)
Received: from DBXPR03MB383.eurprd03.prod.outlook.com (10.141.10.15) by AM3PR03MB371.eurprd03.prod.outlook.com (10.242.18.23) with Microsoft SMTP Server (TLS) id 15.1.36.23; Fri, 19 Dec 2014 10:45:45 +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.01.0049.002; Fri, 19 Dec 2014 10:45:45 +0000
From: "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk>
To: Watson Ladd <watsonbladd@gmail.com>
Thread-Topic: [Cfrg] draft-black-rpgecc-00-.txt [was: Consensus and a way forward]
Thread-Index: AQHQCg+AA9nvrrBncE2keVevceo8V5x0EbQAgAYJNgCAALPwgIAAqAqAgAAkFICAACxOgIAASVqAgAo/CICABgrbAIAAdduAgALh4gCABkJWgIAAhmwAgABitgA=
Date: Fri, 19 Dec 2014 10:45:45 +0000
Message-ID: <D0B9A74B.3A60D%kenny.paterson@rhul.ac.uk>
References: <CA+Vbu7ye3bytMZ-j8pfZixrjF8irTOoWmRo_GwjB0LphwjXq+Q@mail.gmail.com> <20141202092847.29027.qmail@cr.yp.to> <CA+Vbu7yQoYf3ei3MADhJ1iV6BcuqVUmkg8SkQ4ud=8m7pz7AvQ@mail.gmail.com> <D0B0DC9F.39BD0%kenny.paterson@rhul.ac.uk> <CACsn0c=uyPT6xa4CsXPeAV31QeeO+HfsCXAxt7Ba6NOt_Y2hiA@mail.gmail.com> <CABqy+sr1T-VwQx1NaRA+xvnqVn7smjs2+YrG2Uz1Q+8M6c3hng@mail.gmail.com> <D0B8EDCF.3A504%kenny.paterson@rhul.ac.uk> <CACsn0cnkdjEPGZ5Q1Nm+6OZJVdoj6X-ksc0X_atavQ+610MkXA@mail.gmail.com>
In-Reply-To: <CACsn0cnkdjEPGZ5Q1Nm+6OZJVdoj6X-ksc0X_atavQ+610MkXA@mail.gmail.com>
Accept-Language: en-GB, en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
user-agent: Microsoft-MacOutlook/14.4.7.141117
x-originating-ip: [134.219.148.47]
authentication-results: spf=none (sender IP is ) smtp.mailfrom=Kenny.Paterson@rhul.ac.uk;
x-microsoft-antispam: BCL:0;PCL:0;RULEID:;SRVR:AM3PR03MB371;
x-exchange-antispam-report-test: UriScan:;
x-exchange-antispam-report-cfa-test: BCL:0;PCL:0;RULEID:;SRVR:AM3PR03MB371;
x-forefront-prvs: 0430FA5CB7
x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(6009001)(51704005)(46034005)(189002)(377424004)(479174004)(199003)(377454003)(24454002)(76104003)(76176999)(40100003)(31966008)(64706001)(87936001)(54356999)(46102003)(74482002)(66066001)(2656002)(20776003)(92566001)(1411001)(86362001)(36756003)(50986999)(15975445007)(77096005)(4396001)(102836002)(1720100001)(2900100001)(68736005)(107046002)(106116001)(2950100001)(97736003)(19580395003)(83506001)(105586002)(110136001)(19580405001)(99396003)(93886004)(122556002)(120916001)(106356001)(77156002)(230783001)(21056001)(62966003)(101416001); DIR:OUT; SFP:1101; SCL:1; SRVR:AM3PR03MB371; H:DBXPR03MB383.eurprd03.prod.outlook.com; FPR:; SPF:None; MLV:sfv; PTR:InfoNoRecords; MX:1; A:1; LANG:en;
received-spf: None (protection.outlook.com: rhul.ac.uk does not designate permitted sender hosts)
Content-Type: text/plain; charset="utf-8"
Content-ID: <C28324AE4C7FC94998DEF89DE01C5EF8@eurprd03.prod.outlook.com>
Content-Transfer-Encoding: base64
MIME-Version: 1.0
X-OriginatorOrg: rhul.ac.uk
X-MS-Exchange-CrossTenant-originalarrivaltime: 19 Dec 2014 10:45:45.3207 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 2efd699a-1922-4e69-b601-108008d28a2e
X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM3PR03MB371
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/SbR5VGDPEUsT-6D3JonyzgwiMpA
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Consensus and a way forward]
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: Fri, 19 Dec 2014 10:46:14 -0000

Dear Watson,

On 19/12/2014 04:52, "Watson Ladd" <watsonbladd@gmail.com>; wrote:

>On Dec 18, 2014 12:52 PM, "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk>;
>wrote:
>>
>> Dear Robert,
>>
>> I am going to respond to some of the early points in your message below
>>on
>> behalf of the chairs. Separately, Alexei will respond to some of the
>>other
>> points. Between us, we may not cover everything in your long e-mail. I
>> apologise in advance if this is the case.
>>
>> On 14/12/2014 21:16, "Robert Ransom" <rransom.8774@gmail.com>; wrote:
>>
>> >I second Watson Ladd's concern about the chairs' apparent preference
>> >for adopting a document based on draft-black-rpgecc-00 instead of
>> >draft-turner-thecurve25519function-01.
>>
>> Note that the documents are not directly comparable, as you seem to
>>imply
>> here. draft-turner-thecurve25519function-01 specifies a particular
>> key-agreement scheme based on Curve25519. draft-black-rpgecc-00
>>specifies
>> a curve generation method that can, inter alia, generate curves at a
>> variety of security levels. Its output is not directly usable by
>> implementors, of course, and more work would be needed by this group to
>> take its output and make it suitable for delivery to the TLS WG,
>>assuming
>> that this is the direction CFRG wants to go in (an assumption I am not
>> making at this stage, but something that I will happily admit that I do
>> hope will happen given the way in which this group has been deadlocked
>>for
>> some time now).
>
>The requested modification to draft black makes it generate curve25519
>as I understand, but with potentially different generators. If this
>request is met, and we add the description of the algorithms, we will
>arrive at the contents of draft-turner25519. Why not start there?

We could indeed have done that. On the other hand, I believe it's more
appealing to agree on a rigid curve generation method and then recommend
its outputs, delivering that along with appropriate implementation advice.
Perhaps we can even borrow some text from draft-turner25519 to speed
things along? Is some of that reusable, do you think?

>
>We have 6 days, or we will have missed a deadline for the second time.

Indeed.

>
>> >draft-black-rpgecc-00 omits several technical details of ECDH (the
>> >precise point format and handling of Œinvalid¹ public-key bitstring
>> >inputs) which the extensive implementation experience of Curve25519
>> >has shown are needed to ensure interoperability and forward
>> >compatibility and to protect the privacy of users of ECDH
>> >implementations on the Internet.
>> >draft-turner-thecurve25519function-01 includes those technical
>> >details.
>> >
>>
>> Let me repeat. This is correct, but I don't believe it to be relevant
>>for
>> a document that is focussed on curve generation.
>
>That's not the document we were asked to produce, and it's not a
>document that will help implementors. How does a generation method
>help with addressing the request for two or three curves, at security
>levels we feel are relevant?

It's a document that will produce what we were asked to produce, in a way
whose rigidity can be demonstrated (modulo the selection of input primes).
This is important to some people here.

I know there are people who will object to the fact that the method was
tweaked and that the primes have been changed. Personally, though, I don't
see that tweaking in order to improve security, as motivated by remarks
made by Dan Bernstein, is a bad thing. As for the primes, there we can
argue about performance, as you eloquently do below. If there are
compelling performance reasons to change the 192-bit level prime, then we
should consider doing it. See below for more on this.

>
>>
>>
>> >
>> >Adopting draft-black-rpgecc-00 (or a revised version) as a CFRG
>> >document, instead of (a version of) the previously existing
>> >draft-turner-thecurve25519function-01, would raise two serious
>> >concerns:
>> >
>> >* As Watson Ladd has noted, draft-black-rpgecc-00 would require more
>> >  effort, and thus more time, for CFRG to modify it into a useful
>> >  product than draft-turner-thecurve25519function-01 would.
>>
>> But draft-turner-thecurve25519function-01 only specifies a single ECDH
>> algorithm for a single curve. And this is not what the RG has been asked
>> to produce for recommendation to the TLS WG. Rather, we were asked for
>> curves at different security levels (and implicitly, recommendations
>>about
>> how to use those curves to do key exchange and signatures). So
>>substantial
>> work would also be needed to turn draft-turner-thecurve25519function-01
>> into what the RG needs to produce.
>
>Changing a single constant or two is not "substantial work". I've
>asked repeatedly for input on what signature format would be
>preferred,  and gotten little response: my plan this weekend was to
>write a version with signatures or a separate document.

Timing is everything in I*TF. I think you were asking for the input at the
wrong point in the process. Worth reflecting on for the next time, perhaps.

>
>>
>> In short, you are comparing apples and aardvarks here.
>>
>> >
>> >* Adoption of draft-black-rpgecc-00 would reward its authors, both by
>> >  crediting them as authors of CFRG's resulting document and by giving
>> >  them greater control over CFRG's product.  It is inappropriate for
>> >  IETF to reward the authors of draft-black-rpgecc-00 for submitting a
>> >  document to CFRG that they knew to be inferior to a previous
>> >  submission.
>>
>> This is not about rewards. It's about meeting the request of the TLS WG.
>> And I contend that it's not inferior to
>> draft-turner-thecurve25519function-01,
>> but a different beast entirely.
>
>Which one is closer to meeting the express desires of the TLS WG? The
>TLS WG does not want a generation method, but rather new curves. And
>they don't want new "curves" but rather want us to do the hard work of
>specifying a better mechanism. We've already ruled out random primes,
>and short Weierstrass cofactor 1, in some cases in the face of
>determined opposition. What's so special about the minority holding
>out for slow choices of c that we need to appease them also?

I don't think it's really a minority - things seem more balanced than that
to me, based on my reading of the list.

A minute ago you said that it was not hard work to specify multiple curves
and algorithms - just a matter of changing some constants! If that's the
case, then great, I'd hope you'd get involved in developing
draft-black-rpgecc-00-.txt and help do that work there, to turn it into
what you think we need to deliver.


>
>>
>> >
>> >The CFRG chairs have expressed a preference for adopting a version of
>> >draft-black-rpgecc, instead of a version of
>> >draft-turner-thecurve25519function.  Given the above concerns, why do
>> >the chairs believe that adoption of draft-black-rpgecc as a CFRG
>> >document is in the best interests of CFRG and of the Internet as a
>> >whole?
>>
>> See above. In summary: we believe that, with some modifications to
>>enhance
>> security (to which MGN have agreed), and additional work to provide
>> guidance as to how to use these curves in specific algorithms (ECDH and
>> signatures), we can produce a document (or documents) that meet(s) the
>> request from the TLS WG.
>
>And that work has been largely done for Curve25519.
>
>Are the chairs committed to the choice of Curve 25519 at the 256 size
>at this point? Or would they like until Purim for a revised version of
>the generation method, an argument about the generators, some debate
>over picking a different protocol, and further impatience from the
>multiple working groups now blocked on our work? If we can get the
>Curve25519 work out the door, with the promise that the larger curve
>will use a similar protocol, this should buy us more time to consider
>the higher security levels.

That would be one way of skinning this particular cat. Another way would
be to get involved with draft-black-rpgecc-00-.txt and help push it
forward. That's what the chairs are proposing.

>
>>
>> >
>> >>I'm also surprised that we aren't using 2^389-21 for the same reasons
>> >>cited for using 2^255-19. We do not need complete agreement to go
>> >>forward. If we want a consensus result we'll still have gratuitous
>> >>incompatibilities and an unforced loss of additional performance, in
>> >>order to get one particular group on board. A process justified as
>> >>being driven by technical criteria has devolved into an openly
>> >>political horse trade, where we're supposed to be happy that the
>> >>2^255-19 prime is used, and ignore the issues with 2^384-317.
>> >
>> >I second this concern as well.  I have seen very little support in the
>> >CFRG for the 384-bit curve specified in draft-black-rpgecc-00, and I
>> >do not believe that the short discussion of 2^389-21 as a modulus for
>> >elliptic-curve cryptography constitutes a consensus of CFRG or shows
>> >that 2^389-21 is technically superior to or has implementation
>> >experience comparable to 2^414-17 or 2^448-2^224-1 as moduli for ECC.
>> >
>>
>> Here I agree with you that the specific prime 2^389-21 has not had much
>> discussion and therefore not gained consensus in CFRG. But I'm not aware
>> of any specific security or implementation concerns about it that would
>> not also apply to other "sparse" primes. Can you point to some? For
>> example, is there any reason to believe it will be any more difficult to
>> make secure against side-channel attacks than other choices at roughly
>>the
>> same security level? Is it the case that the "implementation experience"
>> that you cite for primes 2^414-17 or 2^448-2^224-1, or any other
>> pseudo-Mersenne primes, would NOT transfer to this choice of prime? It
>> would be really helpful to the group if you could be more specific in
>> expressing your concerns here.
>
>One set of concerns is how efficient it will be compared to Ed448. We
>have guesses: there is no substitute for implementations.
>
>Furthermore, the choice of bitlengths is not set in stone. If Ed448
>could offer the same performance as the 384 bit prime, there would be
>no reason not to go for the larger, effectively free length. It
>probably won't, but until we have working implementations we don't
>know.
>
>Furthermore, accepting the black draft does not mean picking 2^389-21.
>It means picking 2^384-big, where big is sufficiently large to make
>Ed448 approximately as fast, and make vectorized implementations slow.

Sorry, I mis-wrote here. You are quite right that the draft proposes
2^384-317. That's what you get when your chairs are working late at night
after long days doing their day jobs....

I'd be grateful if the folks from the MGN team could say more on the list
why they chose this particular prime, and give some insight into the
performance impact of choosing it over near neighbours such as 2^389-21.

Others should chime in too - for example, people should feel free to
repeat performance numbers from earlier in our discussions (they are out
there in the archive somewhere!).

Please let's collaborate and see if we can swiftly resolve whether there
is a significant performance impact or not.

>
>>
>> >
>> >I have a further concern regarding the intentional omission of point
>> >addition and scalar multiplication algorithms from the text of
>> >draft-black-rpgecc-00.
>>
>> I expect this *was* intentional on the part of the authors, given my
>> assumption that it was their intention to provide a clean document that
>> focusses on curve generation rather than low level details of their
>>usage
>> in cryptographic primitives. But reading on further in your message, I
>> think you mean to imply something more sinister here.
>>
>> >
>> >Instead of providing such algorithms in the text of the draft,
>> >draft-black-rpgecc-00 lists <https://eprint.iacr.org/2014/130.pdf>;,
>> >which contains several scalar multiplication algorithms for those
>> >curves, as an informative reference (listed as [MSR] in the draft).
>> >(I reviewed each of the draft's references (non-RFC references were
>> >accessed on 2014-12-10); no other document listed as a reference
>> >contains a point addition algorithm for Edwards curves, and no other
>> >document that I was able to retrieve contains a scalar multiplication
>> >algorithm for any type of elliptic curve.)
>>
>> Perhaps the draft's authors would consider adding further references to
>> the extensive literature on ECC implementation, particular papers by Dan
>> Bernstein, Tanja Lange, and their co-authors (who have done so much to
>> spur the development of elliptic curve cryptography in its modern form).
>> However, I don't believe that's really the point here - this draft is
>> about specifying curves, not operations for those curves.
>
>And once again, the final product needs to be about providing working
>algorithms. Several issues with original draft for Curve25519 in TLS
>stemmed from the absence of a description of the Curve25519 function
>except in a paper of Daniel J. Bernstein. A document that merely
>contains curves, without the algorithms, does not satisfy the request.

Agreed.

>
>Furthermore, we still need to determine what points are sent on what
>model. Our job will not be done if we simply accept the Black et al.
>draft.

Agreed. No-one was saying this, as far as I recall. Certainly not me.
(Please reread my messages carefully.)

>
>>
>> However, I'd also point out - and I think this is key - that (based on
>>my
>> own reading of this patent, and heavily caveated by the usual
>>disclaimers
>> about none of us being lawyers) it's perfectly possible to implement the
>> basic arithmetic procedures (point addition, scalar multiplication) and
>> higher level algorithms (ECDH, signatures) for the curves produced by
>>the
>> MGN procedure (as for any other similar curves) without having to use
>>any
>> of the techniques that might be covered by this patent. After all, the
>> curves it produces are Edwards form, or twisted Edwards form, so I would
>> assume that the extensive code that is available under generous open
>> source licences would be directly usable here.
>
>Much of that code assumes that the addition law is complete. On the
>new curves in the recent draft, I believe this assumption is
>satisfied. However, the original NUMS submission presented an
>algorithm that infringed on the patent. While it would be possible to
>avoid the patent, the cited reference and presentation made in April
>suggested an algorithm that ran smack into the patent. The new draft
>makes it substantially easier to avoid the patent, by permitting
>complete addition laws.

Well, that's good then, no?

>
><snip>
>>
>> It's not about rewarding any one or any organisation with anything.
>
>Really? The entire argument for this "compromise" assumes that the
>authors of the NUMS draft have something to offer in return for our
>accepting a slower prime at the 384 bit level. They don't:

I think the draft does have something to offer: a well-defined, repeatable
process for generating curves that meet all the identified security
criteria. The choice of prime then becomes a performance question (given
the current state-of-the-art in our knowledge about the DLOG problem).

But you are right to ask what the performance impact is of the particular
choice of prime 2^384-317. Let's try to hash that out with solid numbers.

>IETF
>working groups (and I imagine IRTF working groups) regularly reach
>conclusions in the face of vocal opposition, in most cases far more
>valid than the objections of Benjamin Black to special primes. For
>example, this working group has decided to proceed with a last call on
>a PAKE that doesn't have a security proof. The TLS WG decided to
>pursue ALPN over NPN, despite concerns about client fingerprinting vs.
>server fingerprinting. I am certain there are more decisions of a
>similar nature to be found. I don't think these are commendable
>actions, but I do think that we should consider the relative merits of
>2^384-big vs 2^389-21, regardless of the loudness of the supporters of
>one side or the other, and should be aware of what the basis for
>making a decision actually is.

I agree. I was temporarily confused about which prime was in
draft-black-rpgecc-00-.txt. That was really unhelpful of me.

>
>Remember that we are effectively committed to recommending Curve25519.
>Any argument about the superior "rigidity" of 2^384-big has to imagine
>someone unwilling to accept 2^389-21 for exactly the same reasons they
>accepted 2^255-19, namely the extremely limited number of primes of
>this shape.

I agree. (Wow, all this agreement suddenly breaking out!). Above, I've
asked for a discussion on this very point, focussing on the relative
performance of the options 2^389-21 and 2^384-317. Let's see if we can
resolve this quickly.

>
>If the leadership is committed to compromise for the sake of
>compromise, so be it. But logrolling is not the same as rough
>consensus, and the IETF rules clearly and explicitly point this out.
>Nothing has changed about the relative performance of 2^384-big vs
>Ed448 since April. The choice of 2^389-21 vs. Ed448 is more difficult:
>my instinct suggests the smaller,

Let's get past instinct to hard numbers.

>with Ed448 and E521 as options for
>those who desire significantly more security.
>
>Sincerely,
>Watson Ladd

Likewise,

Kenny


>
>>
>>
>> >
>> >
>> >Robert Ransom
>>
>> Regards,
>>
>> Kenny (on behalf of the chairs)
>>
>>
>>
>> _______________________________________________
>> Cfrg mailing list
>>Cfrg@irtf.org
>>http://www.irtf.org/mailman/listinfo/cfrg