Re: [Cfrg] Adoption of draft-agl-cfrgcurve-00 as a RG document

[Robert Ransom <[e-mail]>]

On 1/5/15, Alexey Melnikov <[e-mail]> wrote:
> This message starts 2 weeks adoption call (ending on January 19th 2015) on:
>
> https://www.imperialviolet.org/cfrgcurve/cfrgcurve.xml
>
> as the starting point for the CFRG document which describes an algorithm
> for safe curve parameter generation for a particular security level and
> also recommends a specific curve (2^255-19) for the 128-bit security level.

My comments below are based on the document submitted to IETF and
published as the Internet draft draft-agl-cfrgcurve-00.  That document
is dated 2015-01-06, after you published your call for adoption.

I have not attempted to determine whether there are any other
differences between the draft posted at the URL you specify at the
time of the call for adoption and the Internet draft.

>
> Please reply to this message or directly to CFRG chairs, stating whether
> you support (or not) adoption of this document. If you do not support
> adoption of this document, please state whether you support adoption of
> any alternative document or whether you want a particular change be made
> to the document before adoption.

I strongly oppose adoption of this document:

* Adam Langley was listed as a co-author of draft-black-rpgecc-00 and
  draft-black-rpgecc-01.  No one who co-authored either of those two
  documents should be considered as an editor or co-editor of any
  future CFRG document.

* The curve selection procedures specified in draft-agl-cfrgcurve-00
  were derived from the curve selection process specified in
  <https://eprint.iacr.org/2014/130> (referenced by
  draft-black-rpgecc-00 as [MSR]), and accordingly, the authors of
  [MSR] may require that their paper be cited as a reference by
  draft-agl-cfrgcurve-00.  For reasons which have already been
  discussed, inclusion of [MSR] as a reference in any CFRG document is
  unacceptable.  Thus, these curve selection procedures must not be
  included in any CFRG document.

I also oppose adoption of this document for other reasons which have
previously been raised; see below.


I would support adoption of draft-turner-thecurve25519function,
provided that it is never changed to include in its text any curve
selection procedure derived from [MSR] or from any Internet-Draft by
the authors of [MSR].


>
> Chairs ask not to reiterate previously expressed technical opinions or
> arguments. But clarifying questions on the adoption call are welcome.

The following technical issues were raised prior to your call for
adoption of draft-agl-cfrgcurve-00:

* Curve3617 (also known as Curve41417) has cofactor 8, and is defined
  over a field of order congruent to 3 mod 4.  Accordingly, the curve
  selection procedure in draft-agl-cfrgcurve-00 will choose a
  different curve if applied to the field used for Curve3617.  (This
  point was previously raised to CFRG in
  <http://www.ietf.org/mail-archive/web/cfrg/current/msg05788.html>.)

  The curve selection procedure specified in draft-agl-cfrgcurve-00
  will instead choose a curve with d > 2^19 (found by D. J. Bernstein
  (et al. ?), found again by Mike Hamburg, and found yet again and
  published recently by David Leon Gil), compared to d=3617 < 2^12 for
  Curve3617.  The parameter value for the twist-secure curve with
  cofactor 4 is so much larger than the parameter value for cofactor 8
  that the performance of at least one implementation strategy of some
  significance would be harmed by insisting on cofactor 4: current
  FPGAs contain 18-bit multipliers, and d > 2^19 almost guarantees a
  greater cost to multiply by the curve parameter.

  With the point format specified in draft-agl-cfrgcurve-00, there is
  no technical benefit to switching to a curve with cofactor 4 over
  the field used for Curve3617.

* It is possible that the point format specified in section 9 of
  draft-agl-cfrgcurve-00 for ECDH (in order to match Curve25519 ECDH
  implementations) may be suboptimal for future curves.  Mike Hamburg
  has developed a compressed point format which can only represent
  points of odd order on curves with cofactor 4, and which seems to be
  compatible with the Montgomery ladder.  (This point was previously
  raised to CFRG in
  <http://www.ietf.org/mail-archive/web/cfrg/current/msg05654.html>.)

  A modern Schnorr-like signature (like EdDSA) usually consists of one
  group element and one scalar, to allow for batch verification.  On
  elliptic-curve groups of composite order, a malicious signer can
  generate signatures which will pass batch verification and fail the
  simplest, fastest single-signature verification procedure, and
  vice-versa.  Thus, implementors of single-signature verification
  have an engineering trade-off regarding whether to verify single
  signatures as quickly as possible or match the behaviour of batch
  verification; and implementors also have an engineering trade-off
  regarding whether to attempt to use batch verification at all.

  In some applications -- notably anonymity systems, but other systems
  are severely affected as well -- implementation-distinguishing
  attacks such as those can be quite severe.

  Mike Hamburg's new point format would eliminate those cofactor-based
  implementation-distinguishing attacks, but only for curves with
  cofactor 4.  Thus, it may be appropriate for CFRG to recommend a
  curve other than Curve25519 for signatures, in order to obtain this
  technical benefit.

  Note that ECDH can be designed (with careful attention to proper
  handling of edge cases) to not have implementation-distinguishing
  attacks.  Curve25519 ECDH, as it is currently widely implemented,
  has come to have an especially well-specified behaviour, and I
  believe that CFRG should not delay use of Curve25519 ECDH in
  IETF-controlled protocols further in the hope of switching to a
  different curve in order to use the new point format.

* The basepoint selection procedure specified in section 6.3 of
  draft-agl-cfrgcurve-00 generates a different basepoint for
  Curve25519 than the standard basepoint currently in use for
  Curve25519, which is specified implicitly in the draft in section
  9.1.  (This point was previously raised to CFRG in
  <http://www.ietf.org/mail-archive/web/cfrg/current/msg05709.html>.)

  The simplest implementation strategy for ECDH is to implement both
  key generation and shared-secret computation using the same
  variable-base single-scalar multiplication routine.  This
  implementation strategy can be made easier, simpler, and less
  error-prone to implement, at absolutely no cost to any other
  implementation strategy, by choosing the basepoint to have a simple
  form when expressed in the point format chosen for public keys.  For
  example, the Curve25519 standard basepoint is the number 9,
  expressed as a 32-byte little-endian integer.

  It appears to me that the basepoint selection procedure specified in
  draft-agl-cfrgcurve-00 will not generate a basepoint of a simple
  form for any point format which might plausibly be used, so that
  basepoint selection procedure should be discarded entirely.

* The curve selection procedure specified in draft-agl-cfrgcurve-00
  for fields of order congruent to 1 mod 4 was concocted, at the
  direction of the CFRG chairs, solely to reproduce a curve isogenous
  to Curve25519.  This is diametrically opposed to the purpose which
  the CFRG chairs claim that the curve selection procedure is supposed
  to perform.  (This point was previously raised to CFRG in
  <http://www.ietf.org/mail-archive/web/cfrg/current/msg05637.html>.)

  Including a curve selection procedure which has been evaluated
  solely based on whether it will reproduce one curve or a small
  number of curves in a CFRG document may cause harm to people who use
  that curve selection procedure to produce additional curves.

  This point has been raised to CFRG again during this call for
  adoption of draft-agl-cfrgcurve, in
  <http://www.ietf.org/mail-archive/web/cfrg/current/msg05860.html>,
  despite the chairs' request that technical issues previously brought
  to CFRG's attention not be raised again.

* The curve selection procedure specified in draft-agl-cfrgcurve-00
  for fields of order congruent to 1 mod 4 does not require that both
  the curve and twist subgroup orders be greater than a power of 2
  near q/8, even in fields of order sufficiently close to a power of 2
  that such a requirement is feasible and is sufficient to allow a
  simple bit-masking procedure to generate scalars which act as
  non-zero on all curve and twist points of large order.  (This point
  was previously raised to CFRG in
  <http://www.ietf.org/mail-archive/web/cfrg/current/msg05606.html>
  and
  <http://www.ietf.org/mail-archive/web/cfrg/current/msg05629.html>.)

  Over the specific field used for Curve25519, this property is
  implied by the other criteria already used in the curve selection
  procedure.  Since the CFRG chairs' goal was to create a curve
  selection procedure which would reproduce Curve25519, not to create
  a curve selection procedure for general use, they apparently did not
  realize that the curve selection procedure might retain this issue
  when used over other fields.

* If CFRG chooses the curve generation procedure, point format, and
  basepoint selection procedure specified in draft-agl-cfrgcurve-00
  based solely on the fact that they reproduce the current Curve25519
  ECDH protocol, as is currently the case, then CFRG's resulting
  document may make decisions that would be inappropriate for future
  curves.  (This point was previously raised to CFRG in
  <http://www.ietf.org/mail-archive/web/cfrg/current/msg05793.html>.)

I believe that each of these previously stated technical issues is
sufficient to oppose adoption of draft-agl-cfrgcurve-00.  Why have the
CFRG chairs asked that these issues not be discussed further?


Robert Ransom