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

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

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" <[e-mail]> 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).

>By the authors' own public
>statements, draft-black-rpgecc-00 was knowingly and intentionally

In my opinion, this is unhelpful language. I believe that your arguments
would have greater impact if you were to try to approach matters in a less
inflammatory way.



>technically inferior to draft-turner-thecurve25519function-01 in each
>of the following ways:
>
>* draft-black-rpgecc-00 specifies a curve modulo the prime 2^255-19
>  which is neither isomorphic nor isogenous to the widely deployed
>  Curve25519, and which thus is not compatible with the many existing
>  independent, interoperable implementations of ECDH on Curve25519.
>  This incompatibility is likely to prevent the reuse of much of the
>  implementation experience which Curve25519 has acquired.
>
>  (<http://www.ietf.org/mail-archive/web/cfrg/current/msg05606.html>
>  and
>  <http://www.ietf.org/mail-archive/web/cfrg/current/msg05631.html>;
>  see also
>  <http://www.ietf.org/mail-archive/web/cfrg/current/msg05629.html>
>  and
>  <http://www.ietf.org/mail-archive/web/cfrg/current/msg05646.html>
><http://www.ietf.org/mail-archive/web/cfrg/current/msg05646.html%3E>)

Whether this makes it technically inferior or not depends on your
definition of "technical". Personally, I don't consider the existence of
existing implementations for Curve25519 to be a *technical* issue. It's
certainly a consideration for this RG in adopting the MGN proposal. Also,
see my point immediately below.

>
>* draft-black-rpgecc-00 specifies a curve modulo the prime 2^255-19
>  which introduces a security vulnerability into implementations of
>  ECDH (and some implementations of other protocols) which rely on the
>  simplest implementation strategy, i.e. the Montgomery ladder, which
>  does not exist for the existing, widely implemented and deployed
>  Curve25519.
>
>  (<http://www.ietf.org/mail-archive/web/cfrg/current/msg05606.html>;
>  see also
>  <http://www.ietf.org/mail-archive/web/cfrg/current/msg05629.html>
><http://www.ietf.org/mail-archive/web/cfrg/current/msg05629.html%3E>)

The chairs have asked MGN to address this weakness, and they have agreed
to do so. This point will therefore soon be moot.

>
>* draft-black-rpgecc-00 does not state, in the text of the draft
>  itself, any algorithms to perform point addition or scalar
>  multiplication on the curves that it specifies.
>
>  (<http://www.ietf.org/mail-archive/web/cfrg/current/msg05631.html>
>  states that this omission is a flaw in draft-black-rpgecc-00;
>  <http://www.ietf.org/mail-archive/web/cfrg/current/msg05637.html>
>  states that the omission of such algorithms is intentional)

This is correct, but I don't believe it is relevant for a document that
is focussed on curve generation. As noted above, if CFRG adopts this
draft, then more work could be put into making it easily usable for
implementors. That is an area where your evidently extensive experience
of ECC implementation could be put to very great use.


>* Section 10 (ŒIntellectual Property Rights¹) of draft-black-rpgecc-00
>  makes a general statement about the IPR status of the curves
>  specified in the document.  Although that is not a statement about
>  Œspecific IPR¹, which section 11 of RFC 3979 (BCP 79) explicitly
>  forbids, I believe that the IPR statement in draft-black-rpgecc-00
>  raises some of the same concerns which section 11 of RFC 3979 states
>  as the rationale for forbidding IETF Documents and RFC Editor
>  Documents from including statements about Œspecific IPR¹.  Thus, I
>  believe that section 10 of draft-black-rpgecc-00 is in violation of
>  BCP 79.  The authors of draft-black-rpgecc-00 stated in the draft
>  that it was Œsubmitted in full conformance with the provisions of
>  BCP 78 and BCP 79¹.
>
>
>In addition to the above flaws which were known to and intended by the
>authors of draft-black-rpgecc-00 at the time that they submitted it,

Again, your use of the word "intended" is unhelpful here. I can't speak
for the authors of the draft, but I'd point out that the flaw is
Relatively minor, leaks at most one bit of a private value, and only
then in certain protocols.

Yes, it would be preferable to avoid the defect if we can, but your
message, more specifically, its somewhat hyperbolic language, might
well lead experts to think that "the sky is falling". I'd urge you
to exercise more restraint.

>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.


>
>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.

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.

>
>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.

>
>>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.

>
>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.

>
>Mike Hamburg has informed the CFRG that he believes the fixed-base
>scalar multiplication algorithm stated in [MSR] and used in Microsoft
>Corporation's software implemented based on [MSR] is Covered by patent
>US7602907.  That patent is assigned to Microsoft Corporation, and thus
>meets the conditions of section 6.6 of RFC 3979 (part of BCP 79) for
>each employee of Microsoft Corporation or its subsidiary Microsoft
>Research.
>
>I believe that patent US7602907, which Covers an algorithm to be used
>in elliptic-curve cryptography, was Œreasonably and personally known¹,
>as defined in BCP 79, to each Microsoft Corporation employee who
>participated in this IETF Internet Standards Process regarding
>elliptic-curve cryptography throughout their participation.
>
>Further, each of the authors of draft-black-rpgecc-00 has actually
>known of patent US7602907, and of Mike Hamburg's belief that it Covers
>an algorithm stated in [MSR] and used in Microsoft's software, since
>no later than Mike Hamburg's public statement to CFRG on 2014-09-16.
>
>(<http://www.ietf.org/mail-archive/web/cfrg/current/msg05130.html> and
><http://www.ietf.org/mail-archive/web/cfrg/current/msg05132.html>
><http://www.ietf.org/mail-archive/web/cfrg/current/msg05132.html%3E>)
>
>It is troubling to me that the authors of draft-black-rpgecc-00 would
>direct readers of their draft to [MSR] as the only source of point
>addition or scalar multiplication algorithms for the curves specified
>in the draft, given that they indisputably knew at the time that they
>submitted the draft that [MSR] contains an algorithm which some of the
>authors would clearly be required, by the text of section 6.1.1 of RFC
>3979 (BCP 79), to provide an IPR disclosure for if they had included
>it in the text of their draft.
>
>
>Given the patent situation regarding [MSR], it is also troubling to me
>that two of the intentional technical flaws of draft-black-rpgecc-00

Once again, I would request that you desist from the use of such strong
language. Not only because it is unhelpful, but also because (I believe)
it undermines the arguments you are trying to make.

>-- incompatibility with existing Curve25519 software, and an
>unnecessary security vulnerability in implementations based on the
>simple Montgomery-ladder algorithm -- would have made readers of the
>draft more likely to write new implementations of the curve specified
>therein, and thus more likely to rely on the implementation guidance
>provided in [MSR].
>
>
>I learned of this patent Covering an algorithm specified in [MSR]
>during an off-list conversation that I initiated with Marsh Ray of
>Microsoft Corporation on 2014-09-04.  I placed Mike Hamburg, Alyssa
>Rowan, and another person on the CC list of my message, with the
>intent that they serve as witnesses to that off-list conversation.
>Marsh Ray included Brian LaMacchia and Benjamin Black into that
>conversation when he replied; Mike Hamburg and Alyssa Rowan also
>participated in the conversation.
>
>I learned of patent US7602907 and its connection to [MSR] from Mike
>Hamburg on 2014-09-08, in the course of that off-list conversation.
>Marsh Ray, Brian LaMacchia, and Benjamin Black also received that
>message on 2014-09-08, eight days before Mike Hamburg provided that
>information to CFRG.  I was not aware of any effort by those
>participants to provide that information to CFRG.
>
>I believe that neither I nor CFRG would have learned of patent
>US7602907 and its connection to [MSR] if I had not initiated that
>off-list conversation, or if I had not included Mike Hamburg in that
>conversation, or if Mike Hamburg had not previously performed a search
>for patents relevant to ECC in order to write software that would not
>be Covered by them.
>

If this is the case, then you will have made a useful contribution to the
work of the group for which I would like to publicly thank you.

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.

>
>I have two questions on this matter for the CFRG chairs:
>
>* Do the chairs believe that it is ethically acceptable for the
>  authors of an Internet draft to
>
>    (a) list as a reference a document which they authored themselves,
>        knowing that if they had included the contents of the
>        reference into the Internet draft itself, they would have been
>        indisputably required by section 6 of RFC 3979 (BCP 79) to
>        submit an IPR disclosure regarding that material; and

I think that would be ethically unacceptable. But I don't believe it's
what has happened here.

>
>    (b) make other technical decisions in the contents of the Internet
>        draft which are likely to cause the draft's readers to rely on
>        the contents of the reference Covered by IPR?

I think that would be ethically unacceptable. But I don't believe it's
what has happened here.


>
>* Do the chairs believe that such conduct should be rewarded by
>  adoption of the resulting Internet draft as a group document?
>

It's not about rewarding any one or any organisation with anything.


>
>
>Robert Ransom

Regards,

Kenny (on behalf of the chairs)