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

Harry Halpin <hhalpin@w3.org> Fri, 19 December 2014 12:44 UTC

Return-Path: <hhalpin@w3.org>
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 50F001A888B for <cfrg@ietfa.amsl.com>; Fri, 19 Dec 2014 04:44:43 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -6.312
X-Spam-Level:
X-Spam-Status: No, score=-6.312 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, J_CHICKENPOX_12=0.6, RCVD_IN_DNSWL_HI=-5, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001, T_RP_MATCHES_RCVD=-0.01] 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 EjxFeC9EPNqp for <cfrg@ietfa.amsl.com>; Fri, 19 Dec 2014 04:44:38 -0800 (PST)
Received: from jay.w3.org (ssh.w3.org [128.30.52.60]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 718E91A8755 for <cfrg@irtf.org>; Fri, 19 Dec 2014 04:44:38 -0800 (PST)
Received: from men75-11-88-175-104-179.fbx.proxad.net ([88.175.104.179] helo=[192.168.1.48]) by jay.w3.org with esmtpsa (TLS1.0:DHE_RSA_AES_128_CBC_SHA1:16) (Exim 4.72) (envelope-from <hhalpin@w3.org>) id 1Y1wv5-0005v2-Dt; Fri, 19 Dec 2014 07:44:35 -0500
Message-ID: <54941DAC.7030208@w3.org>
Date: Fri, 19 Dec 2014 13:44:28 +0100
From: Harry Halpin <hhalpin@w3.org>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.0
MIME-Version: 1.0
To: "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk>, Watson Ladd <watsonbladd@gmail.com>
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> <D0B9A74B.3A60D%kenny.paterson@rhul.ac.uk>
In-Reply-To: <D0B9A74B.3A60D%kenny.paterson@rhul.ac.uk>
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/t46KqJsGMyJNU4vyPlmt6RHPdIM
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 12:44:43 -0000


On 12/19/2014 11:45 AM, Paterson, Kenny wrote:
> 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?

Indeed, I think this approach squares the circle by allowing Curve 25519
as well as the other "security levels" to be generated. If we could
*merge* the drafts and recommend Curve 25519 as a specific curve along
with the curves at other security levels, this might finally break the
deadlock.

Note that W3C Web Cryptography API has a deadline as well - our deadline
for CFRG making a firm decision in order for WebCrypto to add in any new
curves is March 12th, which would trigger another Last Call for us.

https://lists.w3.org/Archives/Member/chairs/2014OctDec/0181.html

Otherwise, WebCrypto will progress without them, possibly adding them in
later via an errata process.

Further details on the debate here under 1.3 "Adding new elliptic curves":

http://www.w3.org/2012/webcrypto/DispositionOfComments/WebCryptoDispositionOfComments.html

  cheers,
        harry

> 
>>
>> 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
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg
>