Subject: [Cfrg] Curve manipulation, revisited

From: "D. J. Bernstein" <[email-masked]>
Date: 24 Dec 2014 22:47:08 -0000

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.

---

From: Adam Langley <[email-masked]>
Date: Thu, 25 Dec 2014 12:14:33 +0000

> side-channel attacks" rather than concerns about backdoors. Nick

Nobody knowledgeable in ECC (that I know of) seriously believes that
the NIST curves are backdoored. But I've observed that the less
knowledgeable people are, the more likely they are to believe it.

Dual-EC had the subtlety of Wile E. Coyote leaving a pile of "Free
Bird Seed" on the road but, prior to 2013, I think most people
(certainly including myself) applied Hanlon's razor and disbelief that
the NSA would do something so stupid and concluded that there was
likely an innocent explanation for it. But many outside of
cryptography circles draw strong parallels between Dual-EC and NIST
curves, I think because they can't see the huge difference: there was
clearly room for a backdoor in Dual-EC, the question was "would they
really?", but a backdoor in P-256 would be alien technology.

Because of this, I suspect that Microsoft feel a need to assuage the
worries of their customers (who will generally fall into the
"less-knowledgeable" group) and provide a "NIST free" option for them.
However, because they are a US company, I imagine that they also feel
the need to demonstrate that they can't have "cooked" the alternative.
(This is all presumption—I'm obviously not familiar with Microsoft's
customer relations nor deliberations.)

But I think this (and a soupçon of ego; something that applies to
everyone) explains Microsoft's continuing strong preference for
"rigidity" in their curves. A conflict arises because Microsoft's
original drive for "rigidity" excluded everything else; including
applying any intelligence to the choice of prime or assigning any
weight to existing practice.

Yourself, myself and others want to replace P-256 not to assuage
backdoor fears, but because a replacement can be significantly faster,
safer and simpler. And we're not hand cuffing ourselves because we're
afraid of being accused of having cards up our sleeves. Finally,
although curve25519 is now pretty common in our world (SSH, OpenPGP,
QUIC etc), it has no presence in the Microsoft ecosystem at all.

You've pointed out, with bada55, that claims of rigidity are, in
general, rather limited and you're correct that Microsoft's movements
towards curve25519 and other changes are highlighting that. But that's
because we didn't accept the choices that were based on their fitness
function. I think they are trying to maintain their larger curve as
being more "rigid" (which, remember, is to convince people who don't
really understand) while accepting something more reasonable (to us)
at the 128-bit level in the hopes of getting the RFC done.

And it would be good to get something done. At present, it's unclear
whether this WG effort will manage to produce anything at all and
failure would mostly benefit P-256. Curve25519 certainly has
increasing presence, but that's in places that will do the smart thing
anyway. But there are lot of places that are less visible to
cryptographers that go with P-256 because it's "standard".
(BluetoothLE-based systems keep popping up in my view.) A failure of
this WG will probably ensure that continues.

It would be also be good to have Microsoft onboard. Microsoft software
is pretty common after all, even if people like us don't see it much.
Although I think we pass the IETF/IRTF bar of "rough consensus"
without them, I don't know if the chairs agree and it would be sad
outcome even if they did.

Curve25519 is sufficiently common now (in our side of the world, at
least) that it's not going away and each different curve supported is
quite a lot of work. (More, I think, than most people realise.) So I
want something very close (or equal) to curve25519 at ~128-bits in
order to minimise implementation, confusion and code size and achieve
the speed, simplicity and robustness that were the point of the whole
exercise.

I'm skeptical that a larger curve is actually useful. I think ~128 and
~192 bit curves have shared fate to the point where the risks from
supporting any extra curve outweigh the benefits. I don't plan on
supporting any larger curve that this WG may produce (even more so if
it's an "ugly" curve). If nothing else, P-384 isn't going away.

So I would be happy with this WG producing curve25519 and a "rigid"
curve at ~192 that Microsoft need. But, even to get there (and it's
unclear whether anyone else would be happy with that) there are still
questions at the ~128 bit level. At the moment, although Kenny has
asked MS to adopt the curve/twist cofactor criteria that results in
curve25519 being produced, Microsoft's generation procedure results in
a different base point and has an isogenous Edwards curve while the
rest of the world uses an isomorphic one. Ed25519 already has a number
of public, private and signature formats[1] however, so perhaps the
isogeny/isomorphism doesn't matter if the conversion can be done "for
free" when converting to affine anyway, but I'm not a cryptographer
and am not comfortable concluding anything here.

[1] https://blog.mozilla.org/warner/files/2011/11/key-formats.png

Cheers

AGL

---

From: Watson Ladd <[email-masked]>
Date: Thu, 25 Dec 2014 14:33:36 -0500

> knowledgeable people are, the more likely they are to believe it.

We're tasked with using our expertise on behalf of those who don't
have it, not making the same mistakes as they would make. They can do
that last part themselves perfectly well.

> weight to existing practice.

It's important not to confuse "rigidity" with actually constraining
the choice of curve meaningfully. The question is not how many curves
can be generated, but how many curves the user will accept. A user who
accepts a curve generated by taking a mathematical constant, and
running it through a hash function to generate a prime and parameters,
is in fact accepting billions of potential curves.  A user who
accepted the NUMS method is accepting potentially far more curves than
one who demands high performance with numerically minimal parameters.

By contrast it is extremely hard to generate high performance primes.
Even superficially good choices can fall short.

> at the 128-bit level in the hopes of getting the RFC done.

Even someone who doesn't really understand ECC should recognize the
impact of gotchas in standards. But Microsoft in April was putting
forward short Weierstrass form and an incomplete formula for Edwards,
arguing that the compatibility of short Weierstrass form outweighed
the performance and simplicity advantages. By August they had
abandoned the Weierstrass curves, and it is unclear to me at what
point the use of incomplete coordinates was abandoned. In short,
Microsoft's original proposal was considerably worse than the
alternative, and their new proposal is not better than the
alternative, even on criteria they claim to be using.

> this WG will probably ensure that continues.

Exactly. It is now the deadline: are we going to miss it because we
cannot get the 128 bit level out, despite unanimity on what it should
be?

The option to proceed with the 128 bit level first has always existed:
I hope the chairs see fit to exercise it, and leave the
higher-security level discussion for later.

In 9 months, not a single security issue with the original Curve25519
proposal has been found. It is high time we produce something.

> the speed, simplicity and robustness that were the point of the whole

Basepoints and isogenies don't change security: if the Microsoft curve
is isogenous to Curve25519, why not use Curve25519?

> it's an "ugly" curve). If nothing else, P-384 isn't going away.

I don't think this is quite right. Imagine we could improve the square
root in Pollard rho to cube root via some algebraic geometry. Then
255/3=85, but 448/3=150. Even ignoring the possibility of algorithmic
improvements, progress in computing power may mean data that has to be
confidential for centuries needs a larger curve. The NSA did pick P384
for a reason.

But we can always select E521 as the large curve, or Ed448, for people
who *actually are using larger Edwards curves today*. The suggestion
to use 2^389-21 is not as good as once seemed: there are other primes
which seem much better, including Goldilocks. Sadly, the absence of a
reasonably optimized portable NUMS implementation, or a Supercop
submission, is making getting hard numbers from identical test
conditions difficult. Differences in the point format Ed448 uses are
another annoyance with getting hard numbers out.

> and am not comfortable concluding anything here.

Basepoints don't affect security. As for the Ed25519 signature format,
I'd note that Supercop and Nacl attach the signature to the message,
while Py-ed25519 isn't: this is the major difference. The private key
format for NaCl in the diagram seems to be the right choice, as it
doesn't require an extra hash before using, but opinions may vary. (I
make no statement about the sanity of the NaCl format for signed
messages, only to note that it does make use of simple hash function
interface possible)

Despite the stated need for rigidity, Microsoft is now endorsing a
proposal that is different from the one they did earlier, even with
the same choice of primes.  A user who thinks that NUMS is better than
the alternative for rigidity has to ask how much flexibility there
really is. Certainly not none, probably nowhere near enough to get
more than "BAD", and almost certainly not "BADA".

Sincerely,
Watson Ladd

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: David Gil <[email-masked]>
Date: Thu, 25 Dec 2014 20:38:05 +0000 (UTC)

On Thursday, December 25, 2014 4:15 AM, Adam Langley
<[email-masked]> wrote: [reordered]

> I don't plan on supporting any larger curve that this WG may
> produce (even more so if it's an "ugly" curve). If nothing
> else, P-384 isn't going away.

I will.

In particular, w.r.t. Yahoo's eventual release of an End-to-End
messaging extension, we will generate EC keys for extension users
on a curve subgroup with log2(#K) >= 376. The additional computational expense is, frankly, negligible.

(And this will likely be a larger deployment, w.r.t. number
of keys, than even TLS -- though vastly smaller in number of
crypto operations.)

--

> I'm skeptical that a larger curve is actually useful. I think
> ~128 and ~192 bit [security strength] curves have shared fate
> to the point where the risks from supporting any extra curve
> outweigh the benefits.

I disagree.

It's absurd to ignore the fact that the organization with the most mathematicians working on ECC[^fbfw] does not trust a bit-length
256 curve for data they consider important. See [NSA Suite B
Cryptography][suiteb].

Do we have any reason to believe that we're so much smarter than
them?

--

[^fbfw]: I would say "for better or for worse", but it is clearly
for the worse.

[suiteb]: https://www.nsa.gov/ia/programs/suiteb_cryptography/

---

From: Adam Langley <[email-masked]>
Date: Thu, 25 Dec 2014 20:51:25 +0000

On Thu, Dec 25, 2014 at 7:33 PM, Watson Ladd <[email-masked]> wrote:
> can be generated, but how many curves the user will accept.

Certainly. Indeed, rejecting curve25519 because of "rigidity" appears
to me to imply accepting that:

1) There are numerous, devastating pitfalls in the space of
sensible-looking curves.
2) And yet, nobody has ever caught even a glimpse of them.
3) And yet, they are dense enough that someone could easily steer a
curve into one.
4) And yet, not so dense that one can't steer a "rigid" curve into one.

That seems like codswallop to me, and possibly to Microsoft too.
However, I think it's understandable if Microsoft have a bunch of
customers who do not specialise in cryptography and yet look with
suspicion at every decision Microsoft make in this area, and thus MS
want to make as few as possible. (I wish MS had generally been more
communicative about their motivations on the list so that I didn't
have to guess.)

It would be nice if we didn't have to worry about such shoddy
suspicions. (Microsoft might feel the same.) But, as I mentioned,
failing to reach agreement with Microsoft would be a bad outcome.

> cannot get the 128 bit level out, despite unanimity on what it should

I would very much welcome it if we could work on trying to get
curve25519 out the door. I'm sure that there are still things that
people can disagree about but everyone appears to be within an isogeny
of a common place.

> is isogenous to Curve25519, why not use Curve25519?

At the moment, because of a desire for a single curve-generation
procedure, I think. Adding special cases to steer the output to match
curve25519 is distasteful and looks like rigging the procedure. (Of
course, from a security point of view, that's nonsense. I've also not
seen anyone outside of MS express the opinion that a curve-generation
procedure is even desirable. But, to make progress, people need to try
and understand Microsoft's position.)

(I'll deal with the argument about the value of a large curve in a
different email becasue Davil Gil has a reply on that topic too.)

Cheers

AGL

---

From: "Salz, Rich" <[email-masked]>
Date: Thu, 25 Dec 2014 15:55:07 -0500

> desirable. But, to make progress, people need to try and understand
> Microsoft's position.)

Then perhaps, as you stated earlier in the note, it would be good if we didn't have to guess.

It's kinda funny that NUMS curve has us now wanting a NUMS rationale.  But perhaps funny isn't the right word, maybe sad or pathetic is.

---

From: David Gil <[email-masked]>
Date: Thu, 25 Dec 2014 21:02:50 +0000 (UTC)

Frankly, I think that the difficulty here is that there really is
little difference between any of the curve proposals.

They are all rigid enough. They are all fast enough. Most are safe
enough.

I'd suggest that the right thing for the CFRG to do is this:

Issue a recommendation that:

  - states the safety criteria for curves,
  - defines a point-format for curves that do not already have one
    defined,
  - notes existing curves that meet the safety criteria,
  - and recommends that WGs adopt curves from that list
    as appropriate for their protocols' needs.

-dlg

---

From: Adam Langley <[email-masked]>
Date: Thu, 25 Dec 2014 21:05:27 +0000

> confidential for centuries needs a larger curve. The NSA did pick P384

If we are positing a cube root algorithm for discrete-log, can't we
posit a 4th root one?

But, yes, there is a possibility of an attack that's *just* right:
weak enough not to break a larger curve but strong enough to break a
smaller one. On the other hand, each additional curve dilutes
implementation resources and implementation bugs happen. I'm judging
that the risk of a bug due to the additional curve is larger than the
benefit of hedging against that specific sort of analytic breakthough.

And, if you want to keep data safe for centuries, isn't post-quantum a
requirement?

> on a curve subgroup with log2(#K) >= 376. The additional computational expense is, frankly, negligible.

I think my argument here is the same as above. (Although, in this
situation, you would have the advantage of being able to use the
simplest, clearest code possible because performance isn't a concern.)

> 256 curve for data they consider important. See [NSA Suite B

TOP SECRET just needed to have a bigger number than SECRET :)

Cheers

AGL

-- 
Adam Langley [email-masked] https://www.imperialviolet.org

---

From: Benjamin Black <[email-masked]>
Date: Sun, 28 Dec 2014 23:57:21 -0800

Adam has accurately described our position, and thanks to him for taking up
the slack while many of us were on holiday.

The request might've come from the TLS-WG, but it is almost inconceivable
that something CFRG recommended to TLS-WG would not be quickly adopted by
many other WGs. It is disingenuous to argue that since the request came
from TLS-WG nothing outside TLS-WG should be a consideration while also
arguing that things like cofactors for 1 (mod 4)  curves must be exactly
(8,4) without giving an example of how it matters to TLS-WG. The latter is
an implicit acknowledgement that the scope extends beyond TLS-WG.
Similarly, suggesting that TLS-WG could be given only X25519 without
Ed25519 being pulled in is either naive or an attempt to sneak them both in
the back door.

My use of the term "compromise" when presenting the current draft seems to
have opened the door to some misunderstanding. I used the term in the sense
of finding common ground rather than in the sense of introducing flaws. I
would not expect anyone in this process to find it acceptable to introduce
what they believe to be a security flaw, conspiracy theorists aside. As
Adam said, it would be a failure if the consensus that emerged from CFRG
did not include Microsoft, as it would be if it didn't include Google or
Akamai or anyone else with direct responsibility for protecting a billion
people online. We have chosen to move some on what is acceptable to us
because it is more important that there is a result that includes enough of
the things we believe are essential for delivering that protection than
that we get to be "right".

I've included more specific responses below.

Thanks,
b

--

The view voiced by several people that the 128-bit security level curve in
the draft is Curve25519 is a bit off base. First, the draft describes
generation of (twisted) Edwards curves and the 128-bit curve has minimal d
(given the addition of the newly manufactured cofactor constraint), while
Ed25519 does not. This is an advantage for both performance and rigidity
with a tiny reduction in simplicity of implementation, achieving a better
balance between security, performance, and simplicity. Second, the
specified base point is not the same and can't be the same without forcing
the (arbitrary) choice. The result is that it is straightforward to modify
existing Curve25519 implementations to use the new curve, but modification
is likely required.

On Wed, Dec 24, 2014 at 2:47 PM, D. J. Bernstein <[email-masked]> wrote:

> "security level".

Once upon a time, Dan said that is was a "requirement" to use single
coordinate ladders to eliminate invalid curve attacks against DH
implementations:

On Tue, Dec 2, 2014 at 1:28 AM, D. J. Bernstein <[email-masked]> wrote:
>
> Invalid-curve attacks completely break the simplest DH implementations
> in Montgomery coordinates _and_ in Edwards coordinates. Rather than
> blaming the implementor, we eliminate these security failures by
>
>    * adding twist security, for both Montgomery and Edwards, and
>    * switching to single-coordinate ladders.
>

Yet for Curve41417, ladders suddenly become optional, just as we've said
all along they should be:

"We use a windowing method with fixed window width for constant-time
single-scalar multiplication on Curve41417 in Edwards form. Our analysis
also
allows good estimates of, e.g., the cost of signature verification using
Curve41417.
Another option for single-scalar multiplication is the Montgomery ladder
for the
Montgomery form of Curve41417; this is not quite as fast as the Edwards form
but has the advantage of fitting the computation into less SRAM."

It seems performance is the real priority here and you will happily discard
things you insist are necessary for security when they conflict with
performance. At the 128-bit security level the ladder can be faster. At the
200-bit+ security levels the ladder is slower. Should we blame the
implementor who elects not to use a single-coordinate ladder? Should we
wonder why you would choose not to eliminate these security failures?

This section of your paper raises another interesting point. It seems a
slight performance drop in exchange for consuming less SRAM can be a
desirable property to you. In Adam's Faster Curve25519 post (
https://www.imperialviolet.org/2013/05/10/fastercurve25519.html), he
achieves significant performance improvements at a cost of 24KB of cache
for tables. Our NUMS 256 curve performs slightly slower than this, but only
requires 9KB for tables. The 15KB difference represents almost 25% of the
64KB L1 cache in a typical Xeon and almost 50% of the 32KB L1 data cache in
a typical ARM. It's not quite as fast but has the advantage of fitting the
computation into less SRAM.

On Mon, Dec 22, 2014 at 5:54 PM, Tanja Lange <[email-masked]>
 wrote:
>
> I think a competition has more to offer than a 'collaboration' where
> parties get more influence by having more people send emails to the list.
>

I'm not sure what point you are trying to make here. The people who haven't
submitted curves should remain silent? That is antithetical to the IETF
process. If you are suggesting it shouldn't be a process whereby a minority
attempts to "stuff the ballot box" by getting a few people to yell loud and
often to drown out differing opinions, then I agree. However, I don't think
we would agree on who might be doing that.

> What should count are the merits of papers, implementations, and internet
> drafts so that proposals get more influence by being objectively better.
>

"Objectively better" is unrealistic as it depends on which implementation,
which architectures, which benchmarks and which priorities people have for
various properties of the curves. The example above for different L1 cache
footprint shows how slippery "objectively better" can be. Another example
would be the large d in Ed25519 compared to the minimal d in the rpgecc
draft. The smaller d is "objectively better" both in terms of performance
and rigidity, but isn't quite as simple to move between twisted Edwards and
Montgomery.

On Thu, Dec 25, 2014 at 12:55 PM, Salz, Rich <[email-masked]> wrote:
>It's kinda funny that NUMS curve has us now wanting a NUMS rationale.  But
perhaps funny isn't the right word, maybe sad or >pathetic is.

You've been in this from the start, so I find it odd you don't recall any
of the numerous times this has been covered, Rich. We don't see the small
potential performance gains as worth the additional flexibility introduced
by manipulating prime selection like this. You are of course free to
disagree, but there is no "objectively better" answer as it is a trade-off.
You might also consider not calling things you don't understand or with
which you disagree "sad" or "pathetic".

On Mon, Nov 3, 2014 at 8:37 AM, Watson Ladd <[email-masked]> wrote:

> On Mon, Nov 3, 2014 at 8:18 AM, Paterson, Kenny
> <[email-masked]> wrote:
> > Alyssa,
> >
> <snip>
> >
> > However, if there's a reasonably simple way to ensure the highest
> possible
> > levels of trustworthiness in our recommendations with unduly compromising
> > efficiency and security, then I am prepared to sacrifice some extra time
> > to achieve it.
>
> That assumes that picking a generation method would "ensure the
> highest possible levels of trustworthiness". It's not clear to me that
> it would. Opponents of the performance approach can demonstrate the
> flexibility they insist exists by putting BADA55 in the hexadecimal
> form of the coefficients obtained by taking the minimal equation
> satisfying reasonable constraints on a performance-oriented prime.

There are at least two, possibly three, fallacies present in this
challenge. The first is that the enormous flexibility required to insert
such a string in the coefficients is at all a relevant metric. The second
is that the BADA55 work used what anyone who wasn't pushing a very
particular agenda would call "reasonable constraints". The third is that
the "performance approach" represents much additional performance, that the
performance gains are certain regardless of architecture or protocol, or
that any additional performance is free.

It's worth noting that we have at least two rather different
interpretations of BADA55 present in these discussions. Your interpretation
seems to be that if you can't insert BADA55 in the coefficients then the
process is rigid. Adam's interpretation (which might match Dan's) is that
any claim of rigidity in generation is necessarily limited.

---

From: Alyssa Rowan <[email-masked]>
Date: Mon, 29 Dec 2014 10:41:40 +0000

On 29/12/2014 07:57, Benjamin Black wrote:

> The view voiced by several people that the 128-bit security level 
> curve in the draft is Curve25519 is a bit off base.

Thanks; I'd missed that.

My tentative support for the draft was strictly conditional on the
resultant 128-bit curve being (birationally) equivalent to Curve25519,
because I feel that would resolve our disagreement on curve choice.

As I said before, your draft is so close to it that any remaining
discrepancy is poorly justified, and simply gratuitously incompatible.

> First, the draft describes generation of (twisted) Edwards curves 
> and the 128-bit curve has minimal d (given the addition of the
> newly manufactured cofactor constraint), while Ed25519 does not.
> This is an advantage for both performance and rigidity with a tiny
> reduction in simplicity of implementation, achieving a better
> balance between security, performance, and simplicity.

Rigidity is largely qualitative. Rigidity means clearly and soundly
explaining, documenting and justifying all of your choices; quantifiably
eliminating them is impractical: as the BADA55 paper points out, there
are always choices.

And I don't think your curve _not_ being Curve25519 is a justifiable
choice now. Even one of your co-authors very clearly prefers Curve25519
(and will move without you if he absolutely has to), and the other wants
a different curve with random primes for his RSA multiplier anyway.

> Second, the specified base point is not the same and can't be the 
> same without forcing the (arbitrary) choice.

Correct me if I'm wrong, as it's before breakfast (and I'm notoriously
unreliable before breakfast!) - but given the cleared cofactors, is the
base point x=9 the smallest point on Curve25519 in Montgomery form?

> The result is that it is straightforward to modify existing 
> Curve25519 implementations to use the new curve, but modification
> is likely required.

My position is that modification _of the draft_ is likely required to
resolve the remaining discrepancies.

In fact, it appears to me at this point that _only you_ at Microsoft
Research want this as it stands; almost everyone else choosing a new
128-bit curve has considered the alternatives and chosen Curve25519 or
(for the hardware-with-an-RSA-multiplier people) a random-prime curve
analogue; and everyone on the group (including the chairs, I think!)
would just like this whole thing over with. (Missing #31c3 was just
embarrassing.)

My strong impression is that our clear preference as a group for a
128-bit non-NIST elliptic curve is Curve25519, and (although I wasn't
there) has been so even before the TLS WG's request, at the meeting in
Hawaii. Maybe we should wait until January before asking the chairs to
call for consensus, due to holidays. But please let's get something out
of the door - and, well, you know what we can agree on. Do we need to
resurrect the Turner draft instead?

That would at least give us a solid base for methodology for the
larger curve; then I feel we're largely discussing the choice of
primes and the relatively poor security::performance ratio of primes
in the ~2^384 region.

As we're already pretty late now, if you don't mind, I'm probably just
going to go ahead and use Curve25519/X25519/Ed25519 now - like the
running code in Tor, I2P, GNUnet, TextSecure, iOS, GnuPG, OpenSSH,
OpenBSD and a whole bunch of other things. They are not merely good
enough, they're great. I see no good reason to arbitrarily change that
just because CFRG said otherwise - and I suspect, neither will they.

- -- 
/akr

---

From: "Salz, Rich" <[email-masked]>
Date: Mon, 29 Dec 2014 08:12:56 -0500

>  Similarly, suggesting that TLS-WG could be given only X25519 without Ed25519 being pulled in is either naive or an attempt to sneak them both in the back door.

Without commenting on the rest of your points (which I don't feel qualified), I strongly disagree with this.  But maybe my naivete is showing.

As a member of the TLS WG, the OpenSSL development team, and security-focused employee of Akamai, I just want X25519.  (I'm also a co-author of the Turner I-D and have resisted multiple requests to merge Ed25519 into it.)

	/r$

---

From: Adam Langley <[email-masked]>
Date: Mon, 29 Dec 2014 13:31:13 +0000

> wonder why you would choose not to eliminate these security failures?

Montgomery ladders allow for very simple, robust implementations of
scalar-mult. Sometimes an implementation might want to trade off cache
pressure for speed, but certainly not all will. If we accept that
supporting Montgomery ladders is a requirement, then we can easily
meet that by sending the Montgomery-x value in ECDH protocols because
windowed methods can easily output this. Thus these are not in
conflict.

(An implementation that wants to use a windowed method with a
Montgomery-X *input* will need to perform a square-root first, but
that's the same cost as a design where compressed Edwards points are
sent. Note: smarter people than I might be able to eliminate the
square-root but I don't see it)

> desirable property to you. In Adam's Faster Curve25519 post
> (https://www.imperialviolet.org/2013/05/10/fastercurve25519.html), he
> achieves significant performance improvements at a cost of 24KB of cache for
> tables.

Keep in mind that this was mostly the result of me needing to explain
windowed methods to someone. The practical benefit to ECDH systems is
minimal since the base-point multiplication can be amortised. (Fast
signatures, however, obviously can benefit, but there's no danger of
an invalid-curve attack when multiplying by the base point.)

> process.

I think Tanja is commenting on the fact that the IETF process is alien
to most cryptographers. Cryptographers often run competitions (e.g.
the AES and SHA-3 competitions) where teams submit candidates and a
winner is decided. That's very different to the more "collaborative"
method common at the IETF.

Cheers

AGL

---

From: Watson Ladd <[email-masked]>
Date: Mon, 29 Dec 2014 08:36:27 -0500

On Mon, Dec 29, 2014 at 2:57 AM, Benjamin Black <[email-masked]> wrote:
> many other WGs. It is disingenuous to argue that since the request came from
> TLS-WG nothing outside TLS-WG should be a consideration while also arguing
> that things like cofactors for 1 (mod 4)  curves must be exactly (8,4)
> without giving an example of how it matters to TLS-WG. The latter is an
> implicit acknowledgement that the scope extends beyond TLS-WG. Similarly,
> suggesting that TLS-WG could be given only X25519 without Ed25519 being
> pulled in is either naive or an attempt to sneak them both in the back door.

What do you think we should do about signatures? The Microsoft
proposal of ECDSA with Edwards points has all the disadvantages of
ECDSA and none of the "advantages" of being already standardized. It's
remarkable that when presenting a draft after the deadline, you
haven't discussed fundamental details of what you want the result to
look like. What goes on the wire?

> what they believe to be a security flaw, conspiracy theorists aside. As Adam
> said, it would be a failure if the consensus that emerged from CFRG did not
> include Microsoft, as it would be if it didn't include Google or Akamai or
> anyone else with direct responsibility for protecting a billion people
> online. We have chosen to move some on what is acceptable to us because it
> is more important that there is a result that includes enough of the things
> we believe are essential for delivering that protection than that we get to
> be "right".

You've said repeatedly you're committed to supporting the result:
seems to me that we can pick whatever we like. Horse trading and
logrolling is not the way to do things.

> balance between security, performance, and simplicity. Second, the specified
> base point is not the same and can't be the same without forcing the
> (arbitrary) choice. The result is that it is straightforward to modify

I don't think this is right: I seem to remember the difference being
explained by isogeny vs. isomorphism.

Base points do not affect ECDH security. Why wouldn't you change it
for backwards compatibility?

You've changed the 128 bit prime to increase performance. Why not
apply the same logic to the choice of 384 bit prime?

The question is not about changing the logic of the proposals: rather
it's about applying that logic inconsistently, and gratuitously
breaking deployed implementations.

> Yet for Curve41417, ladders suddenly become optional, just as we've said all
> along they should be:
>
> Another option for single-scalar multiplication is the Montgomery ladder for
> the

DJB sent a lengthy email to the list titled "Curves, Coordinates, and
Computations". In this email he explained that what an implementation
written by highly skilled and careful implementors for the ultimate in
performance does is not the same as one written for a maximum of
simplicity. The sentence you quoted had the word simple in it: that
word has a meaning you happily ignored.

Tweetnacl.c is probably the most widely used Curve25519
implementation. It's been translated into just about every language I
can think of. It can be very simple because it uses the Montgomery
ladder.

Should I take this email as saying you won't make the changes needed
to get Curve25519?

> tables. Our NUMS 256 curve performs slightly slower than this, but only

This is not a property of the curves, but of your implementation: the
same comb table optimization could be used by a Curve25519 optimized
implementation. That is, if it wasn't patented by Microsoft.

AGL's described implementation uses a table with 512 entries,
representing x^{16^(2*i+1)j} for i zero, j potentially zero. But one
can also use 512 entries to store a comb of 8 bits: the LSB of each
exponent byte, the 2nd to LSB of each exponent byte, etc, as the
Microsoft implementation of NUMS whatever does, and use 8 additions
and 8 doublings to compute the result. This has nothing to do with the
choice of curve or prime.

(There is a cost to what I outlined: the table has to be read in its
entirety each time through. There are several better choices here

> You've been in this from the start, so I find it odd you don't recall any of
> the numerous times this has been covered, Rich. We don't see the small

What about the additional flexibility introduced by your new draft? A
user who listened to your old draft's claims of rigidity, shouldn't
accept the new drafts. Or is it that the "rigidity" claims have far
more to do with marketing than reality?

> There are at least two, possibly three, fallacies present in this challenge.
> The first is that the enormous flexibility required to insert such a string
> in the coefficients is at all a relevant metric. The second is that the
> BADA55 work used what anyone who wasn't pushing a very particular agenda
> would call "reasonable constraints". The third is that the "performance
> approach" represents much additional performance, that the performance gains
> are certain regardless of architecture or protocol, or that any additional
> performance is free.

I think the entire idea that one can backdoor curves involves "alien
technology". But even granting that, if 1/2 of all curves are weak,
even a completely rigid process (assuming one exists) isn't much
better. It's only interesting when rare properties are being targeted.

If you actually read the BADA55 paper you would see they targeted
Brainpool, which had used the hash of a fundamental constant to
generate parameters.

By contrast there are only 100 primes or so meeting the kinds of
performance constraints we have. Shake up the requirements, maybe we
get 4 curves on each prime, so about 400 curves. This is a wild
overestimate.

With the NUMS approach, despite rhetoric of "a single curve for each
security level", users will actually accept a great deal more curves.

The additional performance of 2^255-19 vs 2^256-big costs nothing. It
exists on hardware ranging from 64 bit desktop machines to 32 bit
embedded processors and 18 bit FPGA and GPU multipliers. (GPUs got
better recently). In exchange for this hit you give us exactly
nothing.

>
> It's worth noting that we have at least two rather different interpretations
> of BADA55 present in these discussions. Your interpretation seems to be that
> if you can't insert BADA55 in the coefficients then the process is rigid.
> Adam's interpretation (which might match Dan's) is that any claim of
> rigidity in generation is necessarily limited.
>
>

---

From: Yoav Nir <[email-masked]>
Date: Mon, 29 Dec 2014 15:36:27 +0200

> On Dec 29, 2014, at 3:12 PM, Salz, Rich <[email-masked]> wrote:
> 

Hi, Rich

May I ask why?  If we can make key agreement faster by using X25519 instead of P-256, it stands to reason that we can make signatures faster by using Ed25519 instead of P-256.

Obviously we can’t abandon P-256 signatures for the same reasons it will take a long time to abandon RSA signatures. But what is the rationale for not including Ed25519?

Thanks,

Yoav

---

From: Benjamin Black <[email-masked]>
Date: Mon, 29 Dec 2014 09:14:15 -0800

> windowed methods can easily output this. Thus these are not in
After Yarov and Benger I don't know how robust anyone should assume ladders
are, though that might be beside the point. Had Dan been insisting that
ladders be _allowed_ then I would agree with you, as I have said the same
(in the line just before the part you quoted, even). What Dan said is that
single-coordinate ladders are _required_. They are not (or, to quote Dan
again, "False."). X-only on the wire has clear advantages and I support
that recommendation, but that does not force use of ladders.

> for
My point was that space/time trade-offs like that seem to be acceptable or
unacceptable to Dan depending on what is being argued.

> method common at the IETF.
I'm experiencing a similar cultural impedance problem.

b

---

From: Benjamin Black <[email-masked]>
Date: Mon, 29 Dec 2014 10:25:01 -0800

> look like. What goes on the wire?
The proposal to use ECDSA with Edwards points allows use of the new curves
with the only EC-based signature scheme currently supported by TLS.
Proposing that does not preclude a new signature scheme and I expect such a
scheme would be welcome. I don't see that there needs to be one draft with
the kitchen sink.

> Adam
We will continue to implement things as appropriate for our customers and
our business, neither of which are problems you have. We would prefer those
things be what we believe are best. I don't see horse trading here, I see
debate and collaboration. I understand in academia things are usually more
adversarial.

> specified
Curve25519 is the isogenous Montgomery curve to the generated twisted
Edwards curve. Perhaps we are getting crossed by the confused and confusing
naming and renaming of the various parts of Curve25519?

> for backwards compatibility?
I said it is an issue, as did Adam. I didn't say anything beyond that.

> apply the same logic to the choice of 384 bit prime?
We did not change the prime to increase performance.

> breaking deployed implementations.
You side-stepped every fact in my earlier email enumerating many
inconsistencies in Dan's choices and continue to do so. The differences
between the draft and twisted Edwards Curve25519 are because the draft is
consistent. You are demanding consistency and then complaining when it
doesn't produce the result you wanted. If Curve25519 were being designed
today, based on the last 7 years of advancement, it would look like what is
in the draft.

> all
Dan said single-coordinate ladders are required, full stop: "Rather
than blaming
the implementor, we eliminate these security failures by...switching to
single-coordinate ladders." I'm not ignoring any part of the quoted text.
Whether the the ladder is simpler has no bearing.

> can think of. It can be very simple because it uses the Montgomery
donna is the most widely used implementation.

> Should I take this email as saying you won't make the changes needed
What changes do you mean?

> implementation. That is, if it wasn't patented by Microsoft.
You aren't a lawyer and you, and everyone else on this list, needs to stop
speculating in public about patents and how a given implementation might
infringe them.

> choice of curve or prime.
Yes, a given curve performs differently depending on the exact
implementation techniques used. Different techniques deliver different
space/time trade-offs. That makes statements like "objectively better"
dependent on the specifics of a given scenario, not some abstract Platonic
ideal.

> more to do with marketing than reality?
What flexibility exactly?

> challenge.

> Brainpool, which had used the hash of a fundamental constant to
Brainpool uses the two most common constants. BADA55 relies on carefully
picking far less common constants. It's great marketing if your goal is to
discredit work you think competes with your own. But if Brainpool is
compromised, why would I trust anything from anyone responsible for
producing it?

> security level", users will actually accept a great deal more curves.
The draft is not NUMS.

> better recently). In exchange for this hit you give us exactly
The draft has 2^255-19, what are you talking about?

b

---

From: "Salz, Rich" <[email-masked]>
Date: Mon, 29 Dec 2014 13:25:25 -0500

> May I ask why?  If we can make key agreement faster by using X25519
> instead of P-256, it stands to reason that we can make signatures faster by
> using Ed25519 instead of P-256.

TLS only needs a key exchange.  (X509 certificates are signed, of course, but that's a separable issue.)

I wanted to focus on the one simple requirement. 

--  
Principal Security Engineer, Akamai Technologies
IM: [email-masked] Twitter: RichSalz

---

From: Michael Hamburg <[email-masked]>
Date: Mon, 29 Dec 2014 10:34:45 -0800

> On Dec 29, 2014, at 9:14 AM, Benjamin Black <[email-masked]> wrote:
> Had Dan been insisting that ladders be _allowed_ then I would agree with you, as I have said the same (in the line just before the part you quoted, even). What Dan said is that single-coordinate ladders are _required_.

[…]

> My point was that space/time trade-offs like that seem to be acceptable or unacceptable to Dan depending on what is being argued.

That’s because Dan has been arguing the opposite of what you claim he’s arguing.

You claim he said that only one implementation strategy — ladders —is acceptable.  But in fact, he’s been arguing that the curve/encoding/protocol should be chosen so that multiple implementation strategies — ladders, combs, whatever — will be possible.

That way, an implementor can decide what trade-offs are acceptable for his or her own implementation.  And if we make an especially good choice of curve/encoding/protocol, most of those trade-offs can be good choices instead of pitfalls.

— Mike

---

From: Yoav Nir <[email-masked]>
Date: Mon, 29 Dec 2014 20:47:48 +0200

> On Dec 29, 2014, at 8:25 PM, Salz, Rich <[email-masked]> wrote:
> 

The signatures on X509 certificates are a separable issue. But the signatures in the ServerKeyExchange using the private key associated with the public key in the X509 certificates are very much a part of TLS.

When measuring the performance of the TLS handshakes, the ECDHE derivation takes a similar amount of time as the ECDSA signature. That is the reason for moving away from RSA public keys to ECDSA public keys. If we can use public keys which will be even faster, that’s a net win.

So again, why not?

Yoav

---

From: "Salz, Rich" <[email-masked]>
Date: Mon, 29 Dec 2014 13:54:52 -0500

> The signatures on X509 certificates are a separable issue. But the signatures
> in the ServerKeyExchange using the private key associated with the public
> key in the X509 certificates are very much a part of TLS.

True, yes, foggy from too much eggnog, I guess.
 
> When measuring the performance of the TLS handshakes, the ECDHE
> derivation takes a similar amount of time as the ECDSA signature. That is the
> reason for moving away from RSA public keys to ECDSA public keys. If we can
> use public keys which will be even faster, that’s a net win.
> 
> So again, why not?

Two major reasons.  X25519 is useful by itself without Ed25519 so there's no reason to tie them together.  Having them separate docs lets them progress at their own, natural, rate.  Which brings me to my second reason: I think there are no valid reasons to delay X25519, while the discussion around Ed25519 is, well, let's just say it's still at the pre-consensus state. :)  Does that make sense?

---

From: Benjamin Black <[email-masked]>
Date: Mon, 29 Dec 2014 10:59:55 -0800

On Mon, Dec 29, 2014 at 10:34 AM, Michael Hamburg <[email-masked]>
wrote:

> > Had Dan been insisting that ladders be _allowed_ then I would agree with
> you, as I have said the same (in the line just before the part you quoted,
> even). What Dan said is that single-coordinate ladders are _required_.
>
> […]
>
> > My point was that space/time trade-offs like that seem to be acceptable
> or unacceptable to Dan depending on what is being argued.
>
> You claim he said that only one implementation strategy — ladders —is
> acceptable.  But in fact, he’s been arguing that the
> curve/encoding/protocol should be chosen so that multiple implementation
> strategies — ladders, combs, whatever — will be possible.
>
> That way, an implementor can decide what trade-offs are acceptable for his
> or her own implementation.  And if we make an especially good choice of
> curve/encoding/protocol, most of those trade-offs can be good choices
> instead of pitfalls.
>
> — Mike

I can only go on the things he puts in writing and they say the opposite.

>Rather than

That is not a suggestion folks be allowed to implement the ladder if they
choose to. It is a requirement that they not be allowed to use anything
else. If they are allowed to use anything but single-coordinate ladders,
then, in his own words, we have not eliminated these "security failures"
and will be back to "blaming the implementor". If he means something else
he should say something else.

b

---

From: Benjamin Black <[email-masked]>
Date: Mon, 29 Dec 2014 11:02:05 -0800

On Mon, Dec 29, 2014 at 10:54 AM, Salz, Rich <[email-masked]> wrote:

> Two major reasons.  X25519 is useful by itself without Ed25519 so there's
> no reason to tie them together.  Having them separate docs lets them
> progress at their own, natural, rate.  Which brings me to my second reason:
> I think there are no valid reasons to delay X25519, while the discussion
> around Ed25519 is, well, let's just say it's still at the pre-consensus
> state. :)  Does that make sense?
>
>
Not to get all Watson on you, but does that mean you don't have a strong
opinion on the twisted Edwards form?

b

---

From: "Salz, Rich" <[email-masked]>
Date: Mon, 29 Dec 2014 14:53:00 -0500

> Not to get all Watson on you, but does that mean you don't have a strong opinion on the twisted Edwards form? 

I don't consider myself qualified enough to have an opinion worth stating.

	/r$

---

From: Watson Ladd <[email-masked]>
Date: Mon, 29 Dec 2014 15:04:13 -0500

> scheme would be welcome. I don't see that there needs to be one draft with

The problem is that ECDSA requires Weierstrass curves. It's not ECDSA
if you do what you propose. I understand the idea, but I think it is
too clever by half.

As it is, given the use of X-Montgomery coordinates for the key
exchange, it will no longer be possible to use exactly the same
implementations for signatures and key exchange. We could finesse the
issue by using short Weierstrass points, but no one has an appetite
for that.

> debate and collaboration. I understand in academia things are usually more

Are you saying that customers won't use Curve25519, but will use your
proposed PinkBikeShed? What is the reason that PinkBikeShed is fine
and Curve25519 isn't?

About 6 months ago you insisted that Curve25519 wasn't acceptable to
your customers, and that Montgomery form wasn't either. Now magically
they are. Is this because your customer's views changed, or you invoke
them to support your own views, and never actually talked to them?

As for debate and collaboration, your current proposal uses the same
384 bit curve as before, despite the same issues as the old 256 bit
curve, which has been almost entirely replaced by Curve25519. Far from
deciding on an agreeable set of principles, you decide to make the low
security option more performant, and not change the higher security
option, while tacitly accepting E521, all choices which you had
previously strenuously argued against.

> naming and renaming of the various parts of Curve25519?

I thought that was PinkBikeShed. To be clear: you have added the (8,4)
requirement to the draft, and so get a curve whose isogenous
Montgomery curve is Curve25519, but haven't updated the draft yet?

> We did not change the prime to increase performance.

In original NUMS the prime was 2^256-189. In the rpg-00 draft it is
2^255-19. Looks like a performance motivated change to me. But at 384
the choice remains the same.

> today, based on the last 7 years of advancement, it would look like what is

Oddly enough, the Montgomery form in the draft is PinkBikeShed, which
was examined and rejected for Curve25519.

> Dan said single-coordinate ladders are required, full stop: "Rather than
> blaming the implementor, we eliminate these security failures by...switching
> to single-coordinate ladders." I'm not ignoring any part of the quoted text.

Eeh, we could go back and forth on this one: Tor vs. everyone using tweetnacl.js

> What changes do you mean?

Cofactor requirements to go from PinkBikeShed to Curve25519, and
changes to the basepoint.

> dependent on the specifics of a given scenario, not some abstract Platonic

No, all curves with the same shape can use the same formulas and
coordinates and algorithms for computing scalar multiplies. The big
difference will be field arithmetic and size of constants. Which
techniques are used are orthogonal to which curves are picked.

Of course, if you want to unscrupulously promote a particular curve,
you can insist that well known optimizations for any group will only
apply to some groups, avoid using publicly verifiable benchmarks, and
make certain to implement optimizations for one curve that could be
applied to another, and screw up the benchmarking by borking the
setup.

Benchmarking is extremely tricky: all of the above can be done by
accident, and I've done them by accident.

> What flexibility exactly?

A user who accepted NUMS, and now accepts this draft, is accepting how
many curves? Earlier you claimed that users who accepted Curve25519
were accepting too many curves. Now they aren't. Unless, that is, that
rigidity as you use it, has nothing to do with resistance to
backdooring, nothing to do with what users will accept, nothing to do
with how BADA55 defined it, and everything to do with marketing.

> compromised, why would I trust anything from anyone responsible for

So you don't actually think actual rigidity matters, just how good a
marketing job you can do? Do you think the definition in BADA55 is
correct, or not?

> The draft has 2^255-19, what are you talking about?

You are correct, I meant 2^384-big vs. 2^383-31 or 2^389-21. But
neither of these are as good as 2^448-2^224-1: there are no good
choices of prime around 2^384. I and Mike Hamburg gave 2^389-21 a try,
and we couldn't compare to your listed numbers for 2^384-big directly:
I think we concluded they were in the same ballpark. We can get a lot
more security for very little drop in speed with 2^448-2^224-1.

To be clear, I don't like the fact that x-coordinate Montgomery isn't
mentioned in the draft, the poor choice of high security prime, and
gratuitous differences from existing software.

Sincerely,
Watson Ladd

---

From: Yoav Nir <[email-masked]>
Date: Mon, 29 Dec 2014 22:08:41 +0200

> On Dec 29, 2014, at 9:53 PM, Salz, Rich <[email-masked]> wrote:
> 

Me neither, but I would like the CFRG to come up with a signature algorithm and compatible curves for TLS / IKE / SSH. Deployment will be far slower. We need CFRG to recommend before TLS specifies, and TLS will specify before the browsers implement, and the CAs won’t sign certificates with such keys before the vast majority of browsers support. This is not like a new ECDHE curve where anyone can add it to their implementation.

Yoav

---

From: Watson Ladd <[email-masked]>
Date: Mon, 29 Dec 2014 15:25:18 -0500

On Mon, Dec 29, 2014 at 1:59 PM, Benjamin Black <[email-masked]> wrote:
>> acceptable.  But in fact, he’s been arguing that the curve/encoding/protocol
>> should be chosen so that multiple implementation strategies — ladders,
>> combs, whatever — will be possible.
>>
> then, in his own words, we have not eliminated these "security failures" and
> will be back to "blaming the implementor". If he means something else he
> should say something else.

I don't see how this quote supports your reading exclusively. In
particular, when looking at other messages to the list from DJB, I see
the position Mike describes.

RFC 6080, and the Suite B implementors guide don't describe many
common optimizations. Are these "not allowed"?

We can and should blame the implementor for security flaws. But when
we don't provide enough guidance in standards to avoid flaws, and make
the result overly complex in ways that invite errors, we're
responsible.

I also don't see why this matters: now that Montgomery x form and
complete coordinates for signatures are being used, there isn't a
difference between the rival proposals on this point.

Sincerely,
Watson Ladd

---

From: Benjamin Black <[email-masked]>
Date: Mon, 29 Dec 2014 12:36:34 -0800

> difference between the rival proposals on this point.
Does this mean you find the draft with the additions of x-only and the
cofactor constraint acceptable?

b

---

From: Mike Hamburg <[email-masked]>
Date: Mon, 29 Dec 2014 13:02:08 -0800

On 12/29/2014 10:59 AM, Benjamin Black wrote:
> That is not a suggestion folks be allowed to implement the ladder if 
> they choose to. It is a requirement that they not be allowed to use 
> anything else. If they are allowed to use anything but 
> single-coordinate ladders, then, in his own words, we have not 
> eliminated these "security failures" and will be back to "blaming the 
> implementor". If he means something else he should say something else.
>
>
> b

Look, do you really want to argue one single message to death?  If so, 
maybe you should at least quote the whole message.  DJB wrote:
> Benjamin Black writes:
> > The concerns do not apply to the twisted Edwards curve we generated,
> > only to the isogenous Montgomery curve.
>
> False.
>
> This is the primary motivation for twist security (and a closer look,
> as I've explained in detail, shows a twist-security criterion that's met
> by Curve25519 and not by PinkBikeShed). This has nothing to do with the
> superficial differences between the Montgomery x and the Edwards y, both
> of which support ladders.
>
> If you disagree, please explain why you're requiring _any_ type of twist
> security for Edwards curves. Why aren't you saying something like "The
> larger d forced by 'twist security' is a violation of rigidity" and
> objecting to the whole concept of twist security for Edwards curves?
>
> ---Dan
This is in the context of an argument against a cofactor-4 curve with a 
cofactor-8 twist (with Z8 torsion).  It is not about requiring ladders 
vs windows or combs.  The argument is that twist security is part of a 
strategy to secure single-coordinate ladders, so we should make sure 
that it actually does that.

To be clear, I'm ambivalent on this particular argument.  But if you 
read it as an argument that every implementation of ECDH should be 
banned except for single-coordinate ladders, then I believe that you are 
intentionally and obstinately misreading it.

And to think, I used to wonder why standards committees are so slow.

-- Mike

---

From: Benjamin Black <[email-masked]>
Date: Mon, 29 Dec 2014 13:07:21 -0800

Sorry, Mike, that's how I read it. Let's agree to disagree.

On Mon, Dec 29, 2014 at 1:02 PM, Mike Hamburg <[email-masked]> wrote:

> anything else. If they are allowed to use anything but single-coordinate
> ladders, then, in his own words, we have not eliminated these "security
> failures" and will be back to "blaming the implementor". If he means
> something else he should say something else.
>
>
>  b
>
>
> cofactor-8 twist (with Z8 torsion).  It is not about requiring ladders vs
> windows or combs.  The argument is that twist security is part of a
> strategy to secure single-coordinate ladders, so we should make sure that
> it actually does that.
>
> To be clear, I'm ambivalent on this particular argument.  But if you read
> it as an argument that every implementation of ECDH should be banned except
> for single-coordinate ladders, then I believe that you are intentionally
> and obstinately misreading it.
>

---

From: Rob Stradling <[email-masked]>
Date: Mon, 29 Dec 2014 21:11:44 +0000

On 29/12/14 20:08, Yoav Nir wrote:
> Me neither, but I would like the CFRG to come up with a signature algorithm and compatible curves for TLS / IKE / SSH. Deployment will be far slower. We need CFRG to recommend before TLS specifies, and TLS will specify before the browsers implement,

+1

> and the CAs won’t sign certificates with such keys before the vast majority of browsers support.

I hope that CAs will be ready and willing to sign such certs sooner than 
that.

There might not be huge demand for such certs until there is widespread 
browser support, but I expect there will be some demand.  And if there 
is some demand then CAs may as well add support for the CFRG-blessed 
curves and signature algorithms ASAP.  We won't even need to wait for 
new HSMs in order to issue such certs from our existing RSA and ECDSA 
issuing CAs.

Some TLS server software (notably Apache httpd) can already use several 
certs for the same hostname, where each cert has a different public key 
algorithm (RSA, DSA, ECC).  This means that certs with P-256 and P-384 
public keys can be used where there is browser support, with fallback to 
certs with RSA public keys for the long tail of non-ECC-capable browsers.
I'd like to think that it wouldn't be too hard to make this sort of 
mechanism also support certs with keys on the new CFRG curve(s).

> This is not like a new ECDHE curve where anyone can add it to their implementation.
>
> Yoav

-- 
Rob Stradling
Senior Research & Development Scientist
COMODO - Creating Trust Online

---

From: "Salz, Rich" <[email-masked]>
Date: Mon, 29 Dec 2014 16:15:58 -0500

> algorithm (RSA, DSA, ECC).  This means that certs with P-256 and P-384 public
> keys can be used where there is browser support, with fallback to certs with
> RSA public keys for the long tail of non-ECC-capable browsers.

Any server that uses OpenSSL can do this, provided they make the calls to register the keypairs.  (And only the NIST curves are currently supported.)  So that probably includes, nginx, Node.js, anything built on Ruby or Python, etc.  Some minor code work (config and making an additional API call) could be required, but that's pretty easy.

---

From: Benjamin Black <[email-masked]>
Date: Mon, 29 Dec 2014 13:47:36 -0800

> more security for very little drop in speed with 2^448-2^224-1.
How far from 2^384 did you look? I think it would be useful to the group to
know which candidates were considered and why they were rejected.

b

---

From: Tony Arcieri <[email-masked]>
Date: Mon, 29 Dec 2014 18:52:15 -0800

> Ed25519 being pulled in is either naive or an attempt to sneak them both in

I think you can avoid this slippery slope by the CFRG recommending
Curve25519 as one of potentially many curves at a 128-bit security level,
for now, as an interim solution, simply to avoid the current situation of
apparent infinite deadlock.

Proposal: If and when rigid curve generation guidelines can be agreed upon,
the CFRG can recommend an "updated" curve at a 128-bit security level.

Everything I've described is little different from exactly what's happening
right now: there's an informal agreement on Curve25519, and you would like
to specify a different curve based on "rigid" guidelines.

I'm afraid if we wait on the bikeshedding debate surrounding what
constitutes "rigidity" to conclude, we're just going to be stuck with the
existing choices forever.

Compromise to avoid the slippery slope: proceed with Curve25519 for D-H
with an option for a new curve in the future after the rigidity
bikeshedding debate is over, and postpone any Ed25519-related discussion
until after that.

Here in the real world we're still using RSA signatures. I don't know how
many years until the stuff being discussed here actually trickles down into
what I can practically use day-to-day.

-- 
Tony Arcieri

---

From: Adam Langley <[email-masked]>
Date: Tue, 30 Dec 2014 11:28:37 +0100

On Mon, Dec 29, 2014 at 6:14 PM, Benjamin Black <[email-masked]> wrote:
> again, "False."). X-only on the wire has clear advantages and I support that
> recommendation, but that does not force use of ladders.

I don't see quite how you're understanding Dan's quoted message to
mean that, but I think that everyone would be happy with any technique
that eliminated possible problems.

But, since a working with a windowed multiplication on the Edwards
curve is faster with Curve41417, that opens the question of whether it
would be better to transmit compressed Edwards points for ECDH at that
size.

Tanja did some calculations and the answer appears to be "no": for
41417, it's better to work with Montgomery-X for ECDH rather than do
the square-root to uncompress the point and then use the (slightly
faster) windowed method. So a general rule of "send Montgomery-X on
the wire" appears to be optimal in the cases under consideration,
which is nice.

(The limiting factor for the windowed method is reading from the L1.
The size of the window, and thus the speedup, is limited by the
requirement to read the whole table each step in order that the code
be constant-time. That means that a windowed method with 41417 is only
very slightly faster and thus the square-root cost is sufficient to
tip the balance. Of course, that also assumes that cache-pressure is
free, which it isn't in reality, so the Montgomery ladder is actually
even better than the estimates would suggest.)

Cheers

AGL

---

From: Rob Stradling <[email-masked]>
Date: Tue, 30 Dec 2014 11:52:20 +0000

On 29/12/14 21:15, Salz, Rich wrote:
> Any server that uses OpenSSL can do this, provided they make the calls to register the keypairs.  (And only the NIST curves are currently supported.)

Indeed.

BTW Rich, are the OpenSSL team planning to add support for whatever new 
curve(s) and associated signature algorithm(s) CFRG blesses?

Assuming yes, please will you aim to make it possible for a server to 
register 4 certs/keypairs - RSA, DSA, NIST ECC and CFRG ECC - for the 
same hostname (rather than only permit RSA + DSA + 1 ECC option)?

> So that probably includes, nginx, Node.js, anything built on Ruby or Python, etc.  Some minor code work (config and making an additional API call) could be required, but that's pretty easy.

Nginx can't do this yet, sadly.  I wrote a patch [1], but it's rather 
bitrotten now [2].  Registering the certs/keypairs with OpenSSL was 
indeed "minor code work", but the required updates to the Nginx OCSP 
Stapling code were rather more extensive.  One day I'll find time to 
address the preliminary review comments and finish the job.  :-)

[1] http://osdir.com/ml/nginx-development/2013-10/msg00159.html
[2] http://forum.nginx.org/read.php?2,253440

---

From: Watson Ladd <[email-masked]>
Date: Tue, 30 Dec 2014 11:06:17 -0500

> cofactor constraint acceptable?

No, for several reasons.

2^389-21 has significant performance benefits on Haswell, 8-9% over
2^384-big, which performs the same way as Ed448. Our early
measurements were on other platforms, with relatively unoptimized
code, and didn't compare to the NUMS code you released, but to your
performance numbers. Because we used different benchmarking setups,
there was a systemic error in our cycle counts vs. yours. Now that we
remeasured your code with our benchmark, we get better numbers. (We is
misleading: Mike Hamburg did a lot more of the work then I did, and
the suggestion was Ilari Liusivaas. My sole contribution was writing a
terrible first cut, which Mike threw out for the second version)

The easiest way to get good numbers across multiple platforms would be
a SUPERCOP run. I've screwed up enough measurements to know that one
needs the same framework for as many numbers as possible, otherwise
you benchmark the testbench. But the NUMS people have made sure that
won't happen.

If you want ECDSA, use Weierstrass form. It's not ECDSA if you don't.
I get the idea of the FrankenECDSA, but I'd like to know that it would
be actually useful and speed adoption in TLS, and it relies on
implementations that have a generic ECDSA that calls curve specific
multiply functions. Maybe FrankenECDSA is useful: my guess is it
isn't, but I could be convinced. But this doesn't affect what curve to
use.

As for customers, if they don't find Curve25519 acceptable, they won't
find a curve that's Curve25519 with a different basepoint acceptable
unless they really have no idea how things work. At this point you've
already agreed to Curve25519, modulo the basepoint, which doesn't
matter for security, but does matter for implementators. Why have this
waste?

Sincerely,
Watson Ladd

---

From: "Salz, Rich" <[email-masked]>
Date: Tue, 30 Dec 2014 12:05:20 -0500

> curve(s) and associated signature algorithm(s) CFRG blesses?

I expect so, as part of TLS 1.3.  Hopefully that won't take too long to happen

> Assuming yes, please will you aim to make it possible for a server to register 4
> certs/keypairs - RSA, DSA, NIST ECC and CFRG ECC - for the same hostname
> (rather than only permit RSA + DSA + 1 ECC option)?

We need to provide a way to let smart applications pick which key/cert to use.

Further discussion on this topic is probably better off at [email-masked]

	/r$

---

From: Paul Hoffman <[email-masked]>
Date: Tue, 30 Dec 2014 09:33:56 -0800

On Dec 29, 2014, at 6:52 PM, Tony Arcieri <[email-masked]> wrote:
> I think you can avoid this slippery slope by the CFRG recommending Curve25519 as one of potentially many curves at a 128-bit security level, for now, as an interim solution, simply to avoid the current situation of apparent infinite deadlock.

No, please no. An "interim solution" signature algorithm is stillborn. Few people would want to take the operational effort to create *and maintain* keys for an interim solution when the current solution (P256) is good enough.

If the CFRG cannot come to an agreement on a curve, a signature algorithm, and the necessary format additions, for 128-strength ECC, it should tell the IETF so as soon as possible. Stretching this out with interim values and half-solutions will be worse than claiming defeat.

--Paul Hoffman

---

From: Nico Williams <[email-masked]>
Date: Tue, 30 Dec 2014 11:41:18 -0600

> No, please no. An "interim solution" signature algorithm is stillborn. Few people would want to take the operational effort to create *and maintain* keys for an interim solution when the current so…

That's not what Tony proposed though.  Tony proposed recommending
Curve25519 for ECDH soone and considering digital signatures later.  I
think that's a fine proposal, but the slippery slope can't be avoided
anyways: many developers are aching to use off-the-shell ECDH and
anything better than RSA, and EdDSA is looking pretty good.  If
developers should be told not to (e.g., because EdDSA might be no
good), then CFRG should say so.  Waiting won't stop the slide, and it
might be a fun slope to sled anyways, not a dangerous one (pardon the
terrible analogy).

Nico
--

---

From: Watson Ladd <[email-masked]>
Date: Tue, 30 Dec 2014 12:45:54 -0500

> If the CFRG cannot come to an agreement on a curve, a signature algorithm, and the necessary format additions, for 128-strength ECC, it should tell the IETF so as soon as possible. Stretching this…

We already have agreement: It's a Montgomery x-coordinate solution
modulo the prime 2^255-19, with the curve equal to that of Curve25519.
Literally the only difference is the basepoint, which is irrelevant to
security. This is hidden behind the dramatically increased stream of
emails, but it's there.

For signatures, NUMS isn't opposed to EdDSA. Rather they would like to
see FrankenECDSA, which may be slightly easier for some to adopt.

I strongly urge that we finish off the 128-bit level ASAP.

---

From: "Salz, Rich" <[email-masked]>
Date: Tue, 30 Dec 2014 12:47:29 -0500

> No, please no. An "interim solution" signature algorithm is stillborn. Few
> people would want to take the operational effort to create *and maintain*
> keys for an interim solution when the current solution (P256) is good enough.

It's important to not mix key exchange and signature.  My interest, and arguably the primary TLS WG interest, is in the former, not the latter.

---

From: Paul Hoffman <[email-masked]>
Date: Tue, 30 Dec 2014 10:01:19 -0800

> It's important to not mix key exchange and signature.  My interest, and arguably the primary TLS WG interest, is in the former, not the latter.

The TLS WG cares about both, but in the WG meetings so far, it has only asked about the former because they assumed the latter would come for free. This discussion has made it clearer that the assumption is wrong, but no one has brought that back to the TLS WG yet. Once that is done, particularly if the CFRG says "here is the curve and base point, but we think we're going to have a different signature mechanism later", I believe the TLS WG will be just as borked as they are now. I know that will certainly be the case for the DNS community looking at EC for DNSSEC.

--Paul Hoffman

---

From: Alyssa Rowan <[email-masked]>
Date: Tue, 30 Dec 2014 18:39:48 +0000

> modulo the prime 2^255-19, with the curve equal to that of

I think we are at, or very near, agreement on Curve25519 (although of
course we would need to confirm that with everyone).

> Literally the only difference is the basepoint, which is irrelevant
> to security.

Yes; that is one of the only remaining sticking points with Ben's
draft, other than the changes he's already agreed to make.

If the draft can be changed to match Curve25519's x=9 basepoint, then
yes, I think that we would have agreement to recommend Curve25519 and
the associated X25519 Montgomery-x key agreement (and people could
more or less go ahead and start rolling that out!).

It's a gratuitous incompatibility with no security justification
otherwise, which makes no sense to me.

> I strongly urge that we finish off the 128-bit level ASAP.

That I definitely agree with.

Would it be beneficial to take the 384-bit curve out of the draft for
now? Or can we relatively quickly reach agreement on something like
2^389-21? If we run with just the WF128 curve for now, we could always
follow it up later.

I'm a little concerned that the twisted-Edwards form proposed by Ben
is not Ed25519's, as that may unnecessarily complicate the discussion
about signatures - but that discussion is (despite having raised it
months ago) in any case in a much earlier phase and I'm unsure where
it'll actually end up.

- -- 
/akr