[Cfrg] Mishandling twist attacks

["D. J. Bernstein" <[e-mail]>]

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.