### [Cfrg] A few good primes

"D. J. Bernstein" <djb@cr.yp.to> Sat, 02 August 2014 17:10 UTC

Return-Path: <djb-dsn2-1406711340.7506@cr.yp.to>

X-Original-To: cfrg@ietfa.amsl.com

Delivered-To: cfrg@ietfa.amsl.com

Received: from localhost (ietfa.amsl.com [127.0.0.1])
by ietfa.amsl.com (Postfix) with ESMTP id 688F21B27A6
for <cfrg@ietfa.amsl.com>; Sat, 2 Aug 2014 10:10:09 -0700 (PDT)

X-Virus-Scanned: amavisd-new at amsl.com

X-Spam-Flag: NO

X-Spam-Score: 0.101

X-Spam-Level:

X-Spam-Status: No, score=0.101 tagged_above=-999 required=5
tests=[BAYES_50=0.8, RCVD_IN_DNSWL_LOW=-0.7, UNPARSEABLE_RELAY=0.001]
autolearn=ham

Received: from mail.ietf.org ([4.31.198.44])
by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id LmuEXeBiYDnn for <cfrg@ietfa.amsl.com>;
Sat, 2 Aug 2014 10:10:05 -0700 (PDT)

Received: from mace.cs.uic.edu (mace.cs.uic.edu [131.193.32.224])
by ietfa.amsl.com (Postfix) with SMTP id DFD7D1A02FB
for <cfrg@irtf.org>; Sat, 2 Aug 2014 10:10:03 -0700 (PDT)

Received: (qmail 11089 invoked by uid 1011); 2 Aug 2014 17:10:04 -0000

Received: from unknown (unknown)
by unknown with QMTP; 2 Aug 2014 17:10:04 -0000

Received: (qmail 8052 invoked by uid 1001); 2 Aug 2014 17:09:52 -0000

Date: 2 Aug 2014 17:09:52 -0000

Message-ID: <20140802170952.8050.qmail@cr.yp.to>

From: "D. J. Bernstein" <djb@cr.yp.to>

To: cfrg@irtf.org

Mail-Followup-To: cfrg@irtf.org

In-Reply-To: <CAMm+LwgZp4sgLaFZeWV05UDvN=x7FUNbM5Gi32fJRRrKmais+A@mail.gmail.com>

Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/Do1NkGC_v4oaJ9DoZycrARzJa74

Subject: [Cfrg] A few good primes

X-BeenThere: cfrg@irtf.org

X-Mailman-Version: 2.1.15

Precedence: list

List-Id: Crypto Forum Research Group <cfrg.irtf.org>

List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>,
<mailto:cfrg-request@irtf.org?subject=unsubscribe>

List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>

List-Post: <mailto:cfrg@irtf.org>

List-Help: <mailto:cfrg-request@irtf.org?subject=help>

List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>,
<mailto:cfrg-request@irtf.org?subject=subscribe>

X-List-Received-Date: Sat, 02 Aug 2014 17:10:09 -0000

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] Another perspective on the Curve256/255 pr… Phillip Hallam-Baker
- Re: [Cfrg] Another perspective on the Curve256/25… Salz, Rich
- Re: [Cfrg] Another perspective on the Curve256/25… Phillip Hallam-Baker
- Re: [Cfrg] Another perspective on the Curve256/25… Salz, Rich
- [Cfrg] A few good primes D. J. Bernstein
- Re: [Cfrg] A few good primes Michael Hamburg