[Cfrg] Curve manipulation, revisited

["D. J. Bernstein" <[e-mail]>]

Once upon a time, Microsoft said that it was a "requirement" to have
"rigid parameter generation for primes and curve constants" given the
"security level". Microsoft also said that the "mandatory" security
levels were "128-bit and 256-bit", and that 192-bit was optional.
Microsoft's accompanying paper listed their "chosen twisted Edwards
curves" for seven different bit lengths of primes at these "levels":

   * "ed-255-mers" ("128"): -x^2+y^2 = 1+60055x^2y^2 mod 2^255-765;
   * "ed-256-mers" ("128"): -x^2+y^2 = 1+15342x^2y^2 mod 2^256-189;
   * "ed-383-mers" ("192"): -x^2+y^2 = 1+523990x^2y^2 mod 2^383-421;
   * "ed-384-mers" ("192"): -x^2+y^2 = 1+333194x^2y^2 mod 2^384-317;
   * "ed-511-mers" ("256"): -x^2+y^2 = 1+1097597x^2y^2 mod 2^511-481;
   * "ed-512-mers" ("256"): -x^2+y^2 = 1+637608x^2y^2 mod 2^512-569;
   * "ed-521-mers" ("256"): -x^2+y^2 = 1+550440x^2y^2 mod 2^521-1; and
   * six curves for additional "mont" primes at these bit lengths.

On top of that they listed 13 more Weierstrass curves, for a total of 26
"chosen" curves.

Microsoft chose 6 of these curves as "Nothing Up My Sleeves" curves.
2^255-765, 2^383-421, 2^511-481, and 2^521-1 were discarded: Microsoft
made the (quite puzzling) claim that prime bit lengths not divisible by
8 "introduce interoperability and implementation problems". (The "mont"
primes were also discarded in favor of the "mers" primes, also with
highly unclear justification.)

Suddenly, a few weeks ago, Microsoft changed almost every detail of its
recommendations:

   * Security levels: The examples in the new document are at "128-bit"
     and "192-bit" security levels. The accompanying email says that
     "256-bit" security can be handled "if" there is "strong interest"
     and states what the resulting curve would be.
     
     For comparison, previously 128-bit and 256-bit were "mandatory".
     Where's Microsoft's explanation of its switch from 256 to 192?

   * Relationship between bit length and security level: For 192-bit
     security Microsoft chooses 384-bit primes as before, but for
     128-bit security it has switched its choice from 256 to 255 (1 bit
     smaller), and for 256-bit security it has switched its choice from
     512 to 521 (9 bits larger). What rule is Microsoft applying here?
     What happened to "independently-verifiable provenance"?

     Very few primes achieve truly top performance; see, e.g.,
     https://www.ietf.org/mail-archive/web/cfrg/current/msg04894.html and
     https://www.ietf.org/mail-archive/web/cfrg/current/msg05087.html.
     These include a 255-bit prime and a 521-bit prime, namely 2^255-19
     and 2^521-1. These don't, however, include a 384-bit prime.

   * Primes: The first "security requirement" in the old document was
     for all "domain parameters" to be "generated in a simple,
     deterministic manner, without any secret or random inputs". The
     first listed "parameter" was the prime, and the old document states
     a procedure to generate the prime from the security level.

     The new document lists the same "security requirement"---but omits
     the prime from the list of "parameters", and doesn't state any
     procedure to generate primes. What happened to "rigid parameter
     generation for primes"?
     
     Certainly Microsoft isn't following its original procedure: for
     example, for a bit length of 255, previously Microsoft used
     2^255-765 ("ed-255-mers"), whereas now it uses 2^255-19.

   * Curve coefficients: There's _zero_ overlap between Microsoft's new
     list of curves and its original list of 26 curves.
     
     For 255 bits this isn't surprising since the prime has changed. For
     384 bits, however, the old curve was -x^2+y^2 = 1+333194x^2y^2, and
     the new curve is -x^2+y^2 = 1-11556x^2y^2. For 521 bits, the old
     curve was -x^2+y^2 = 1+550440x^2y^2, and the new curve is x^2+y^2
     = 1-376014x^2y^2.

This remarkable list of changes makes clear that Microsoft's approach is
less rigid than the truly-top-performance approach taken by other people
generating curves. For example, the truly-top-performance approach has
never allowed this sort of fine-grained manipulation of bit lengths; it
has always rejected most bit lengths.

Of course, Microsoft has always said that its "choices" are related to
performance---but the subtle details of this relationship are now being
manipulated. The performance flexibility exploited here is on top of any
flexibility that one can obtain by exploiting variations in security
criteria for curves (e.g., picking PinkBikeShed instead of Curve25519).

"Isn't Microsoft doing the right thing?" some people will ask at this
point. "They've even made the news for endorsing Curve25519!" Indeed, it
does seem that Microsoft is joining the truly-top-performance approach
in endorsing Curve25519 and E-521. However, Microsoft is going beyond
these two curves, and asking CFRG to endorse

   * a prime list that doesn't have any explanation (with the mediocre
     prime 2^384-317 sticking out like a sore thumb next to top primes
     2^255-19 and 2^521-1), and

   * a coefficient-generation _procedure_ that we've all seen being
     manipulated for non-transparent reasons (changing, e.g., the
     "chosen" curve mod 2^521-1).

How would CFRG be able to explain these highly questionable choices?

The draft curve-requirements list from the chairs months ago said that
curves "should be generated by a well-defined procedure that allows only
a limited and quantified amount of flexibility". What we're seeing here
is that Microsoft's procedure

   * doesn't have a stable definition,
   * has never quantified its amount of flexibility,
   * is no longer even trying to explain or limit prime choices, and
   * is flexible enough to allow all 26 previous curves to disappear.

At the beginning a few people seemed to assume that, since Microsoft was
emphasizing rigidity so strongly, Microsoft's proposals were surely more
rigid than anything else could possibly be. For example, Phillip
Hallam-Baker characterized Microsoft's Toronto presentation as

   The most important thing is to assure people there is no special
   reason for the choice of curve and so we must eliminate subjective
   choices completely.

Phillip seemed to believe that Microsoft's curves were particularly
rigid, and seemed to think that this was a good argument for ed-512-mers
(which Microsoft no longer mentions as a bit length in the document or
in the email) at the "256-bit" security level (which Microsoft no longer
mentions in the document). I'm curious whether these people are still
taking Microsoft's rigidity arguments seriously now that all of the
Microsoft curves have changed. If so, can someone please explain what
the rigidity argument for Microsoft's curves is supposed to be?

---Dan

P.S. I don't mean to exaggerate the importance of rigidity compared to
other curve criteria. ECC security has been intensively studied for many
years, and a major new security weakness in conservative prime-field ECC
would be extremely surprising. I'm more concerned with all the _known_
security weaknesses---problems that we've known for years how to fix by
choosing better curves and choosing better protocols. See, e.g.,
http://blog.cr.yp.to/20140323-ecdsa.html.

This process began in September 2013, after news of NSA sabotage of
cryptographic standards: Patrick Pelletier wrote

   Given the doubt that's recently been cast on the NIST curves, is it
   time to revive the idea of adding curve25519 as a named curve?

on the TLS mailing list. Doug Stebila followed up to say that the
reasons to support Curve25519 were "efficiency and resistance to
side-channel attacks" rather than concerns about backdoors. Nick
Mathewson wrote

   In the FOSS cryptography world nowadays, I see many more new users of
   curve25519 than of the NIST curves, because of efficiency and
   ease-of-implementation issues.

Nico Williams wrote

   Agreed, we need curve25519 cipher suites because of its technical
   advantages, not due to any FUD about the other ECDH curves that we
   have.

Simon Josefsson wrote an Internet-Draft. Active discussion ensued,
spreading to CFRG. Rigidity has certainly been a big issue for some
people throughout this process, but has never been the most important
driver of this process.

P.P.S. I fully realize that not all of the authors of the new document
are from Microsoft. The two exceptions are (1) Joppe Bos, who moved from
Microsoft to NXP during CFRG's deliberations, and (2) Adam Langley from
Google, who has always been quite clear about his reasons for joining
the document ("I think the prevalence of Curve25519 alone is enough that
the CFRG should adopt it. PinkBikeShed isn't what I want, but it's close
and it's something that I can live with in order to move forward") and
who has never endorsed Microsoft's claims regarding rigidity.