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