### [Cfrg] Mishandling twist attacks

"D. J. Bernstein" <djb@cr.yp.to> Fri, 28 November 2014 01:41 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 ED5A81A038C for <cfrg@ietfa.amsl.com>; Thu, 27 Nov 2014 17:41:11 -0800 (PST)

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

X-Spam-Flag: NO

X-Spam-Score: 2.896

X-Spam-Level: **

X-Spam-Status: No, score=2.896 tagged_above=-999 required=5 tests=[BAYES_50=0.8, HELO_EQ_NL=0.55, HOST_EQ_NL=1.545, UNPARSEABLE_RELAY=0.001] autolearn=no

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 dP-ik878B492 for <cfrg@ietfa.amsl.com>; Thu, 27 Nov 2014 17:41:08 -0800 (PST)

Received: from calvin.win.tue.nl (calvin.win.tue.nl [131.155.70.11]) by ietfa.amsl.com (Postfix) with SMTP id 4A9421A0387 for <cfrg@irtf.org>; Thu, 27 Nov 2014 17:41:08 -0800 (PST)

Received: (qmail 6729 invoked by uid 1017); 28 Nov 2014 01:41:27 -0000

Received: from unknown (unknown) by unknown with QMTP; 28 Nov 2014 01:41:27 -0000

Received: (qmail 26624 invoked by uid 1001); 28 Nov 2014 01:40:59 -0000

Date: Fri, 28 Nov 2014 01:40:59 -0000

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

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

To: cfrg@irtf.org

Mail-Followup-To: cfrg@irtf.org

MIME-Version: 1.0

Content-Type: text/plain; charset="utf-8"

Content-Disposition: inline

Content-Transfer-Encoding: 8bit

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

Subject: [Cfrg] Mishandling twist attacks

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: Fri, 28 Nov 2014 01:41:12 -0000

Two slight variants of Curve25519 were considered and rejected in the Curve25519 paper. Apparently there's now a proposal to revive one of those variants. Here are all three curves for comparison, including names for the two variants so that I can refer to them: Curve25519: y^2 = x^3 + 486662x^2 + x mod 2^255-19 FuschiaBikeShed: y^2 = x^3 + 464586x^2 + x mod 2^255-19 PinkBikeShed: y^2 = x^3 + 358990x^2 + x mod 2^255-19 The proposal, specifically, is to use PinkBikeShed. The core argument for this is that 358990 is smaller than 464586 and 486662. Perhaps I should emphasize that---when security is equal---the ultimate arbiter is performance, not any preconceived notion of smallness. My impression is that the ASIC costs of Curve25519 are marginally smaller than the ASIC costs of PinkBikeShed and FuschiaBikeShed, after careful optimization, because of the nicer bit pattern in 486662. Larger gaps in sizes of constants often produce more noticeable slowdowns in software, but I haven't found any platforms where 358990 is faster than 486662. But performance isn't the main topic of this message. There are much more important reasons---security reasons---to reject PinkBikeShed. The purpose of this message is to carefully explain one of those reasons. General context first: We've had many years of serious vulnerabilities in deployed crypto, and we know what makes these vulnerabilities stick around. The protocol designer (or promoter) takes every possible opportunity to blame the implementor for security failures---e.g., "This IS an attack against a particular implementation of ECDSA. This is NOT an attack against all implementations of ECDSA." ---rather than admitting that the protocol could have and should have been fixed. The protocol designer evades responsibility by saying that it's _possible_ to fix every implementation, even though in most cases it's crystal clear that this is much harder and much more fragile than fixing the protocol. Similarly, the designer of the underlying crypto primitive takes every possible opportunity to blame the protocol designers and implementors for security failures---e.g., "The initial key scheduling component of RC4 should for now be routinely amended for new applications to include hashing and/or discarding the first 256 bytes of pseudo-random output. (This has in any case been RSA's routine recommendation.)" ---rather than admitting that the primitive could have and should have been fixed. As an ECC example, consider uncompressed static ECDH using the NIST curves. The simplest scalarmult procedures that seem to work turn out to have huge problems: for example, * they leak secret keys through timing, * they produce dangerously wrong results for some inputs, and * they leak secret keys to invalid-curve attacks. There's a long tradition of blaming the implementor for the resulting security failures: it's the implementor's fault for not writing constant-time code, for not checking for exceptional cases, etc. However, we've known for many years how to _change the crypto_ to avoid all of these implementation pitfalls. Specifically, we * compress points to just one coordinate (as suggested in Miller's original ECC paper), forcing attacker-supplied points to be on the curve or on the twist; * take twist-secure curves to eliminate the damage from attackers taking points on the twist; * choose curves for which the main theorem of the Curve25519 paper applies, showing that the remarkably simple, fast, constant-time Montgomery ladder works for all inputs; and * always set the top bit of scalars so that an input-length-agnostic variant of the Montgomery ladder doesn't create a timing leak. It's of course still _possible_ for security to be compromised by a sufficiently determined implementor, but this failure is no longer the _default_. Similar steps also protect signatures. But, wait, what about small-subgroup attacks? This has been the main theme in the occasional objections to choosing a curve that allows Montgomery coordinates (or Edwards coordinates): these coordinates require a cofactor of at least 4, and then an attacker can send a point of order 4 on the curve, easily learning the secret mod 4. One can say that the _implementor_ should check for points of order 4. But it's much better to solve this problem in the _protocol_. This is why every major ECC standard already multiplies scalars by the curve's cofactor. Should we have tried to address this problem even earlier, namely in the choice of _curve_? Unfortunately, we don't know how to achieve the huge benefits mentioned earlier while taking cofactor 1---there's nothing for cofactor 1 matching the amazing simplicity of the Montgomery ladder for DH (or the simplicity of complete Edwards coordinates for signatures). Fortunately, the attacks prevented by cofactor 1 cause security failures in far fewer situations than the attacks prevented by taking a larger cofactor, so the correct choice for the curve designer is clear. By far the simplest, most robust ECC systems that we know how to build are systems following the strategy explained above. So far I haven't said anything that distinguishes Curve25519 from PinkBikeShed---both of the curves solve the critical problems for the most important protocols in exactly the same way. However, a closer look shows that PinkBikeShed has smaller problems that are eliminated by Curve25519. (FuschiaBikeShed has the same problems.) I'm not saying that PinkBikeShed is anywhere near as bad as the NIST curves. For example, unless the RNG is backdoored, standard DH is _not_ noticeably damaged by the particular type of security failure that I'll focus on for the rest of this message, whereas standard DH with the NIST curves (or the Brainpool curves) is an implementation nightmare. What I'm saying is merely that Curve25519 is better---it eliminates the failures for DH _and_ eliminates further failures for other protocols. Specifically, consider a protocol that uses PinkBikeShed to multiply its secret scalar by an attacker-specified point, with all the protections listed above. PinkBikeShed has cofactor 4, so the protocol multiplies the secret scalar s by the cofactor 4 exactly as the standards say, and then uses the Montgomery ladder to multiply 4s by the Montgomery x-coordinate received from the attacker. Does this protocol leak information about the secret scalar s? One might think that the answer is no. Small-subgroup attacks don't learn anything. Invalid-curve attacks are syntactically prohibited, except of course for the twist, and PinkBikeShed is twist-secure. But it's not that simple! Twist-security doesn't mean that the twist cofactor is 4. (As the Curve25519 paper mentions, for this prime it's obviously not possible to have curve cofactor 4 and twist cofactor 4 simultaneously.) The twist of PinkBikeShed has points of order 8. If the attacker sends one of those points Q, then 4sQ will be either 0 or a particular nonzero point depending on whether s is even or odd. Unless the protocol takes some unusual step to squash this distinction, the bottom bit of s will end up directly controlling subsequent outputs that the attacker can see. How much damage is caused by having the bottom bit of secret scalars leaked to the attacker? As I said, there's no problem for the most important protocols. For example, in pure DH (again, with a non-malicious RNG), the bottom bit of s is independent of everything else, and the other bits provide ample protection. In pure signatures (at least the state-of-the-art systems), secret scalars are never applied to an attacker-controlled point. However, there are quite a few protocols that use scalars in more complicated ways. For example, there are more and more proposals to share public keys between DH and signatures, and of course those are reusing scalars. There are more and more proposals to derive DH scalars from other DH scalars: consider Zooko's "semi-private" keys, for example, or Tor's proposed replacement for the .onion design. It seems to me that this bottom-bit leak is enough to completely break, e.g., HMQV-PinkBikeShed by an adaptation of the Menezes HMQV attack in http://anotherlook.ca/hmqv.shtml. I haven't worked through the details, but if you _have_ to work through the details of how a completely unnecessary ECC information leak affects a higher-level protocol then you know you've done a bad system design. One can of course blame the implementors for not checking whether the input point has order 8. One can blame the standards for not warning people about twist attacks. One can blame the protocols for multiplying by 4 for this particular curve rather than 8. But a competent curve designer, instead of blaming everybody else for a predictable problem, will simply eliminate the problem by choosing a better curve. For Curve25519, the twist cofactor divides the curve cofactor, and this problem disappears. What the standards say to do, namely multiply by the curve cofactor, is wrong for PinkBikeShed but correct for Curve25519. The numerical details are spelled out in the "Small-subgroup attacks" section of the Curve25519 paper. This wasn't my only reason for rejecting PinkBikeShed. The Curve25519 paper mentions a less important reason that allowed a much shorter summary and that, as a historical matter, came first. I didn't bother writing down a comprehensive critique of PinkBikeShed, and didn't imagine that anyone would ever try to revive that curve. ---Dan P.S. Apparently Microsoft claims that each of its proposals, now including PinkBikeShed, is "the most trustworthy curve". But we've now all seen Microsoft changing from one curve mod 2^521-1 to another curve mod 2^521-1 by manipulating their generation procedure. Which one of those curves mod 2^521-1 is "the most trustworthy curve"? Given the fact that Microsoft's curve-generation procedure is clearly subject to change, let me suggest a possible way forward. Microsoft adds further security criteria to its generation procedure, such as requiring the twist cofactor to divide the curve cofactor. For 2^255-19 it ends up with Curve25519---what a surprise! Microsoft then switches to proposing the latest edition of its "most trustworthy curve", namely Curve25519. This wouldn't resolve everything---I'd have to ask Microsoft to stop saying "new" for curves that really aren't new, and presumably there would still be discussion of larger primes---but surely it would help. P.P.S. Apparently there's also a claim that ECDSA-PinkBikeShed would be simpler than ECDSA-Curve25519. This claim starts from the Curve25519 paper's observation that _one_ of the primes for PinkBikeShed is slightly below 2^252; concludes that the _curve order_ is slightly below 2^255; and tries to argue that a curve order slightly below 2^255 has advantages outweighing the advantages of a curve order slightly above 2^255. However, the curve order for PinkBikeShed is in fact _above_ 2^255, just like the curve order for Curve25519; so the intermediate conclusion is wrong, the subsequent argument is irrelevant, and the claim crumples. The _twist_ order is below 2^255 (divide by the twist cofactor 8 to obtain a prime slightly below 2^252, the prime that the paper is describing) but the twist isn't the curve that's being proposed. I'll find it richly entertaining if Microsoft now proposes the twist.

- [Cfrg] Mishandling twist attacks D. J. Bernstein
- Re: [Cfrg] Mishandling twist attacks Michael Hamburg
- Re: [Cfrg] Mishandling twist attacks Alyssa Rowan
- Re: [Cfrg] Mishandling twist attacks Watson Ladd
- Re: [Cfrg] Mishandling twist attacks Samuel Neves
- Re: [Cfrg] Mishandling twist attacks David Leon Gil
- Re: [Cfrg] Mishandling twist attacks D. J. Bernstein
- Re: [Cfrg] Mishandling twist attacks Ilari Liusvaara
- Re: [Cfrg] Mishandling twist attacks Lochter, Manfred
- Re: [Cfrg] Mishandling twist attacks D. J. Bernstein
- Re: [Cfrg] Mishandling twist attacks Lochter, Manfred
- Re: [Cfrg] Mishandling twist attacks Watson Ladd
- Re: [Cfrg] Mishandling twist attacks Lochter, Manfred
- Re: [Cfrg] Mishandling twist attacks Watson Ladd