Re: [Cfrg] A few good primes

I think this can be distilled down to a simpler point.

In this project, we are not required to choose a curve which matches the AES (single-target) work factors.  We were given this instruction explicitly.  Joe Salowey told us, "We leave it up to the CFRG to determine what ECC key strengths are appropriate above 128-bit symmetric key strength”.  Benjamin Black asked Joe Salowey explicitly whether pairings such as 384-bit ECC with 256-bit AES should be allowed, and Joe responded that "The CFRG has the cryptographic expertise to determine what pairings are appropriate.”  (Jul 18).  Yet, some members of this group have fixated on those AES security levels.

Each proposed set of curves has its own strengths and weaknesses.  Some match the AES work factors more exactly, some less, some not at all.  The different curves reflect different trade-offs between performance, work factor, ridigity, simplicity, compatibility, aesthetics, etc.  None of the curves were chosen with any of these goals exclusive to all the others.  In particular, the Microsoft Ed-512-mers curve was heavily skewed toward an aesthetic “round” modulus.  But it also required a 2-mod-4 d, for Montgomery compatibility.  It is in twisted Edwards form instead of untwisted for performance reasons, despite the incomplete addition formula.  It was not chosen purely for rigidity — in fact, it’s only one of the 10 ~512-bit curves in that paper.

I submit that we should not add “must exactly match an AES work factor” as a requirement for this process, though it should count for something since some members of this forum value it highly.  Furthermore, performance and simplicity of implementation should be considered as well as rigidity and work factor.  In particular, Curve41417, Ed448-Goldilocks, Ed480-Ridinghood and E-521 should be considered as options in addition to the NUMS curves.

None of these curves should be considered insufficiently rigid.  If rigidity were our only concern, I believe that E-521 would be the default choice, not the Microsoft NUMS curves, since this curve was found independently by 3 groups.

Finally, note that it is entirely possible to quantify the performance vs security tradeoff even if not every curve is designed for the same strength, either by using the n ^ (1 + log 3 / log 2) heuristic, or just by making a graph and looking for outliers.

Cheers,
— Mike

> On Aug 2, 2014, at 10:09 AM, D. J. Bernstein <djb@cr.yp.to> wrote:
> 
> 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
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg