Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Consensus and a way forward]
Watson Ladd <watsonbladd@gmail.com> Fri, 19 December 2014 04:52 UTC
Return-Path: <watsonbladd@gmail.com>
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 6FB941ACCE7 for <cfrg@ietfa.amsl.com>; Thu, 18 Dec 2014 20:52:23 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=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 TS40-TSsSYmy for <cfrg@ietfa.amsl.com>; Thu, 18 Dec 2014 20:52:19 -0800 (PST)
Received: from mail-yh0-x22a.google.com (mail-yh0-x22a.google.com [IPv6:2607:f8b0:4002:c01::22a]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 6771D1ACCE6 for <cfrg@irtf.org>; Thu, 18 Dec 2014 20:52:19 -0800 (PST)
Received: by mail-yh0-f42.google.com with SMTP id v1so62889yhn.1 for <cfrg@irtf.org>; Thu, 18 Dec 2014 20:52:18 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=AAwA/JN2sQsEDqKBk/Zyk32y/wIVsoVGldZY56QdiII=; b=ZASPOe67R/uitOGrdvGi6RWlwdRN1J+5UhcP6LRmIYbbhfRsWROIkurRA3Aybv35rp wHghC3ag8+/7LukhFxSwukcKCkfVPW8kAF6C88BDljpzGCG0sjabGZXTjB4K8r/WpocC 9w9KYZ46oMxKwS0DH4HyD5XlsF1qGFAIxhuvpkenIwiDauWhh4MdZaQ6R9/rD4CMZ9aa ovYKOOsHdMjUNOkcgF94AGZmNkAo8sBbwTvEZGAJKWTBFpZjcCQ9naDCQhA4O+zl2Wi5 UIhp84P6wHnqwwTJSvt+frB2H4RN+FFBx8zKlhzKy1QZzcoIk4VWHl0FiZPhT6LRJwj/ a2wQ==
MIME-Version: 1.0
X-Received: by 10.236.22.36 with SMTP id s24mr4993304yhs.138.1418964738569; Thu, 18 Dec 2014 20:52:18 -0800 (PST)
Received: by 10.170.195.21 with HTTP; Thu, 18 Dec 2014 20:52:18 -0800 (PST)
In-Reply-To: <D0B8EDCF.3A504%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>
Date: Thu, 18 Dec 2014 20:52:18 -0800
Message-ID: <CACsn0cnkdjEPGZ5Q1Nm+6OZJVdoj6X-ksc0X_atavQ+610MkXA@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/RPWNV_R3K4v3ZOlr7-4mRyFa-4A
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 04:52:23 -0000
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 have 6 days, or we will have missed a deadline for the second time. > >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? > > > > > >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. > > 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? > > > > >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. > > > > >>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. > > > > >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. 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. > > 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. <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: 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. 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. 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, with Ed448 and E521 as options for those who desire significantly more security. Sincerely, Watson Ladd > > > > > > > >Robert Ransom > > Regards, > > Kenny (on behalf of the chairs) > > > > _______________________________________________ > Cfrg mailing list >Cfrg@irtf.org >http://www.irtf.org/mailman/listinfo/cfrg
- [Cfrg] Consensus and a way forward Benjamin Black
- Re: [Cfrg] Consensus and a way forward Watson Ladd
- Re: [Cfrg] Consensus and a way forward Joppe Bos
- Re: [Cfrg] Consensus and a way forward Hannes Tschofenig
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Alyssa Rowan
- Re: [Cfrg] Consensus and a way forward Ilari Liusvaara
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Adam Langley
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Alyssa Rowan
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Mike Hamburg
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Alyssa Rowan
- Re: [Cfrg] Consensus and a way forward Paterson, Kenny
- Re: [Cfrg] Consensus and a way forward Paterson, Kenny
- Re: [Cfrg] Consensus and a way forward Paterson, Kenny
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Benjamin Black
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Alexey Melnikov
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Michael Hamburg
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Benjamin Black
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Alyssa Rowan
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Robert Ransom
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Adam Langley
- Re: [Cfrg] Consensus and a way forward Lochter, Manfred
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Ilari Liusvaara
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Robert Ransom
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Benjamin Black
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Watson Ladd
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Tony Arcieri
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Benjamin Black
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Alyssa Rowan
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… D. J. Bernstein
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Robert Ransom
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Benjamin Black
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Watson Ladd
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Paterson, Kenny
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Alyssa Rowan
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Watson Ladd
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Benjamin Black
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Robert Ransom
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Paul Hoffman
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Alexey Melnikov
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Paterson, Kenny
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Alexey Melnikov
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Watson Ladd
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Paterson, Kenny
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Harry Halpin
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Paul Hoffman
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Watson Ladd
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Tanja Lange
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Salz, Rich
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Tony Arcieri
- Re: [Cfrg] Mishandling twist attacks D. J. Bernstein
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Paterson, Kenny
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Tanja Lange
- Re: [Cfrg] Mishandling twist attacks Paterson, Kenny
- Re: [Cfrg] Mishandling twist attacks D. J. Bernstein
- Re: [Cfrg] Mishandling twist attacks Salz, Rich
- Re: [Cfrg] Mishandling twist attacks Stephen Farrell
- Re: [Cfrg] Mishandling twist attacks Adam Back