Phillip Hallam-Baker writes:
> 2^512 is a round number in crypto, 2^521 is a very odd one.

2^521-1 is a Mersenne prime. This has undisputed benefits for speed and
simplicity of modular reduction. That's why three research teams
independently searched for safe curves mod 2^521-1, all coming up with
the same curve E-521. (The whole story is that Lange and I were the
first to start the computation; Hamburg used more computers and was the
first to find the curve coefficient 376014; the curve name comes from
Aranha, Barreto, Pereira, and Ricardini, who were the second to find
376014 but were the first to announce it.)

The next smaller Mersenne prime is 2^127-1. Primes so close to a power
of 2 are really quite rare! Unfortunately, 127-bit ECC is too small to
be secure. (You _can_ get reasonable security out of ECC over a field of
size (2^127-1)^2, or genus-2 HECC over a field of size 2^127-1, which is
exactly why 2^127-1 appears in papers at Eurocrypt 2013, Eurocrypt 2014,
etc. Because of various complications I doubt that anybody will make
serious proposals of these options to CFRG---but the point I'm making is
that the benefits of Mersenne primes are firmly established.)

What about primes big enough for an acceptable security level but
smaller than 2^521-1? Properly optimized implementations (see

   https://moderncrypto.org/mail-archive/curves/2014/000237.html

for a summary of the techniques) can still take advantage of exactly how
close the prime is to a power of 2. The top tier---since there aren't
any Mersenne primes in this range---is

   2^452-3, 2^336-3, 2^266-3.

There also aren't any 2^n-5 or 2^n-7. The next tiers are

   2^321-9, 2^285-9, 2^251-9;
   2^322-11;
   2^338-15;
   2^488-17, 2^468-17, 2^444-17, 2^414-17, 2^336-17;
   2^379-19, 2^291-19, 2^255-19.

If you continue this analysis then you start seeing more and more
examples of primes that flunk what economists call "Pareto-optimality".
For example, 2^336-17 is in the above list but is obviously a bad choice
because it isn't Pareto-optimal: you can switch to 2^336-3 for better
speed and no loss in security. As a fancier example, 2^254-245 is the
largest prime below 2^254, but it still isn't Pareto-optimal: you can
switch to 2^255-19 for better speed (assuming proper optimization on
typical platforms) and no loss in security. 

I'm not saying that 2^254-245 is terribly slow. I'm also not saying that
most users would notice this cost issue. I'm just saying that 2^255-19
is faster, and of course doesn't lose any security. Insisting on the
_best_ cross-platform performance therefore ends up excluding 2^254-245.
Merely insisting on something _close_ would give more flexibility to the
person choosing primes, in particular allowing 2^254-245---measurably
worse performance, less rigidity, no benefit.

The set of primes becomes even more limited if you start going beyond
Pareto-optimality and acknowledging that very small differences in
quantitative security levels aren't meaningful to anybody. If someone
has enough computer power to break a prime p, does it make any sense to
respond by switching to another prime q with an extra bit---just 1.4x
the attack cost---or two extra bits---just 2x the attack cost?

Specifically, suppose we say that a prime, even if Pareto-optimal, isn't
good if we can gain cross-platform performance by switching to another
prime that's within 1 bit of the same size (or larger). The dependence
of speed upon c is strong enough that this rule still leaves some good
primes, such as 2^255-19 and 2^266-3 and 2^414-17 and 2^521-1. It
_doesn't_ allow 2^254-245 or 2^256-189 or 2^384-317 or 2^512-569. This
rule limits the prime choice in a much more fundamental way than having
to make up marketing arguments for particular primes---the prime choice
is being driven by performance. If you read the Curve25519 paper then
you can see that this is how 2^255-19 was chosen.

Surely we can all agree that security, speed, and simplicity are the top
desiderata to be considered by CFRG. If it's really necessary to include
marketing requirements such as "make sure to use multiples of 128 in the
name" then these requirements should be handled by renaming rather than
by compromising the top desiderata. We can have an adult discussion here
of what the best crypto actually is, and a separate discussion of how to
present the best crypto to the children---or simply skip the paternalism
and treat the users as adults, which is what I recommend.

> All of the curve choices on offer are significantly faster than
> RSA2048

That depends on the application. For example, DNSSEC people say that
signature-verification speed is critical, and if you look at (e.g.) the
Haswell benchmarks near the top of

   http://bench.cr.yp.to/results-sign.html

then you'll see just 60533 cycles (using OpenSSL) for verification in
"ronald2048" (a typical 2048-bit RSA signature system). That's faster
than the 165939 cycles for Ed25519, and it's 50 times faster than the
3027399 cycles for "ecdonaldp521" (P-521 ECDSA, again with OpenSSL). An
E-521 version of Ed25519 would be much faster than ecdonaldp521 (and,
like Ed25519, would allow faster verification through batching, not
included in these benchmarks), but would be much slower than RSA-2048.

Furthermore, most web pages and other Internet services are _not_
cryptographically protected. Obviously the hassle of setting up SSL is a
major factor, but there are many cases where SSL is _already_ set up
and where speed is the only excuse for not running it (or for running
it at a security level that's feasible to break today). For example,

   * https://sourceforge.net/account is fully functional, while
   * https://sourceforge.net/develop redirects to HTTP.

This has no explanation other than SSL being too slow. Slow public-key
crypto isn't the only contributor to slow SSL, but the other problems
are being fixed too, and I see ample room for optimism that this will
drastically increase the deployment of crypto across the Internet.

It's of course nice to hear that _you_ don't have cost problems for
crypto, but my understanding is that CFRG is looking at a much wider
range of use cases, including cases where crypto speed is important.

  [ RSA-2048 ]
> is what every major application doing public key is
> using today.

Let me make sure I understand what you're saying.

Most DNSSEC signatures use RSA-1024 (for performance reasons) rather
than RSA-2048, so DNSSEC is not a "major application doing public key"?
Tor, which recently upgraded from RSA-1024 to Curve25519, is not a
"major application doing public key"? DNSCrypt, which compared to DNSSEC
is actually doing far more to protect DNS integrity and infinitely more
to protect DNS privacy, is not a "major application doing public key"?
Out of all of the Curve25519 applications listed in

   http://www.apple.com/ipad/business/docs/iOS_Security_Feb14.pdf
   http://en.wikipedia.org/wiki/Curve25519#Notable_uses
   http://ianix.com/pub/curve25519-deployment.html

the only ones that can qualify as "major applications doing public key"
are the ones that are also using RSA-2048?

Perhaps you meant to comment only on IETF protocols, but maybe one of
the reasons that Curve25519 is being deployed in so many non-IETF
applications is that IETF protocols don't do what those applications
want, and maybe CFRG can help IETF do a better job there. Furthermore,
DNSSEC is an IETF protocol, and surely you can't be suggesting that CFRG
should ignore DNSSEC.

> WF256 - High security delivering a confidence factor of 50+ years.
> 2^256 work factor

Nobody can plausibly claim "a confidence factor of 50+ years" for ECC
given the serious risk posed by quantum computers. AES-256 isn't so
seriously affected but is still broken in 2^128 simple operations by
Grover's algorithm. My impression is that CFRG's current agenda does not
include 512-bit ciphers, the McEliece system, NTRU, etc.; it does
include hash-based signatures, but this is only one part of post-quantum
security.

Even in these pre-quantum times, AES-256 fails to provide a 2^256 "work
factor"; see the separate "matching AES security" thread. This means
that a curve that achieves "WF256" against pre-quantum attacks would
still fail to achieve "WF256" for applications such as TLS.

> Yesterday someone claimed in another forum that 'performance' was an
> objective factor, as if every algorithm executed as fast (or at least
> relatively) on each architecture.

Fortunately, experience shows that any plausible averaging of
state-of-the-art ECC speeds across architectures leads to the same basic
conclusions regarding the importance of taking primes very close to a
power of 2, the importance of taking curves with points of order 4, etc.

It's of course possible that CFRG will end up facing some sort of tricky
decision---for example, I've seen speculation that software people might
prefer one curve while hardware people prefer another (this would be the
case if CFRG were considering binary curves, but evidently it isn't),
and speculation that signature people might prefer one curve while DH
people prefer another. So far there's no evidence of such complications.

> DJB: Speed! Speed! Speed!

I'm not sure which talk you're referring to. Here are the slides that I
presented at the CFRG meeting in Toronto:

   http://cr.yp.to/talks.html#2014.07.23

I started by saying that I was going to talk not about speed but rather
about simplicity and security. What I spent most of my time explaining
was how implementors are pressured to screw up security---but also how
careful cryptographic choices can eliminate many of these pressures. I
did spend a few seconds on slide 13 mentioning that the 2012 NEON
implementation of Curve25519 is 8 times faster than the 2014 OpenSSL
NIST P-256 on ARM Cortex-A8 (a typical smartphone/tablet CPU), but in
general I said very little about Curve25519's performance.

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

I don't recall Microsoft claiming to "eliminate subjective choices
completely." Unless they speak up to make this claim, I would suggest
that you retract this statement and refrain from overstating their
position in the future.

> Explaining the choice.

Every proposal on the table has an explanation. Having an explanation
from first principles (speed, simplicity, and security) leaves far less
wiggle room than having an explanation from the marketing department
("Wow, 256!").

> Compatibility with legacy crypto HSMs

Obviously one can manufacture platforms that reward some curves. But do
you seriously think that someone saying "I have an HSM that supports
only ECDSA NIST P-256!" should count as an objection to settling on
better curves for everybody else? There doesn't seem to be a current
proposal to _eliminate_ P-256, so why can't that HSM just stick to P-256
while a better curve helps enable crypto for the mass market?

As a more subtle example, do you think that someone saying "I have an
HSM that supports arbitrary curves but only for the NIST P-256 prime!
Please stick to the NIST P-256 prime!" should be able to outweigh

   https://www.imperialviolet.org/2010/12/21/eccspeed.html

illustrating the huge speed advantages of 2^255-19 on widespread CPUs?
This is all speculative---as I said, so far there's no evidence of any
such conflicts---but surely you'll agree that requiring top performance
on each platform separately would be unreasonable in case there _are_
conflicts between platforms. Someone arguing for curve choice on the
basis of one unusual platform is going to, and should, have a tough job.

As a side note, even within the HSM market, it's not at all clear that
_legacy_ HSM support for ECC is anywhere near as important as _future_
HSM support for ECC. If you care about ECC in this market then you
shouldn't be asking merely what the legacy hardware supports, but also
what would help enable future hardware.

> Compatibility with standard data paths

So, after the study

   https://www.hgi.rub.de/hgi/publikationen/curve25519/

showed that the standard 18-bit data path for FPGA multipliers works
very well with splitting 255-bit integers into 17-bit pieces (note that
255 = 17*15), you're saying that the poor alignment of 256 with this
standard rules out 256? Similarly, since standard "lazy reduction" fits
into standard 256-bit data paths for addition of 255-bit integers but
not for addition of 256-bit integers, CFRG must exclude 256-bit primes?

There's an extensive literature quantifying the performance of ECC on
various platforms. You seem to think that this literature misrepresents
some important platform with a 512-bit data path. If you can defend this
by naming the platform, pointing to the documentation, saying where the
platform is used, saying what the users' performance requirements are,
and explaining why you don't think E-521 could meet those requirements
(while you seem to think that 512-bit ECC is obviously fast enough),
then maybe this will influence the E-521 evaluation---but stating this
"compatibility" as a yes/no requirement is clearly wrong.

---Dan