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

[Robert Ransom <[e-mail]>]

On 12/12/14, Watson Ladd <[e-mail]> wrote:
> On Fri, Dec 12, 2014 at 2:13 AM, Paterson, Kenny
> <[e-mail]> wrote:
>> Dear Ben,
>>
>> Thanks for your continued contributions to this discussion. I think you
>> make quite powerful arguments for keeping  draft-black-rpgecc-00 the way
>> it is and not adding an extra criterion concerning divisibility of
>> co-factors.
>>
>> Nevertheless, based on previous discussions on list (and discussions off
>> list that Alexei and I have been having in our role as co-chairs), we have
>> reason to believe that we will have a strong chance of making progress as
>> a group, and unblocking our current logjam, if your team were to add this
>> criterion to the draft.
>>
>> If you were also to add explicit isogenies enabling mapping to Montgomery
>> form curves for the specific primes/curves at the 128-bit and 192-bit
>> security levels, then this would also help move things along too.
>>
>> As co-chairs, then, we would like to strongly recommend that your team
>> take these two significant steps to modify your draft. Modulo my
>> understanding of IRTF processes, we would then be in a position to call
>> for consensus on formal adoption of the draft by CFRG.
>
> Why can't the turner-curve25519 draft be adopted? We could add the
> curves for the 2^389-21 prime that Ilari has computed. As one of the
> coauthors I'm surprised that no discussion of the shortcomings of this
> draft, has taken place, instead we've been modifying a draft that was
> further from being useful until it can be adopted.

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.  By the authors' own public
statements, draft-black-rpgecc-00 was knowingly and intentionally
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>)

* 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>)

* 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)

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


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.

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

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?



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



I have a further concern regarding the intentional omission of point
addition and scalar multiplication algorithms from the text of
draft-black-rpgecc-00.

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

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

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


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

    (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?

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



Robert Ransom