Re: [Cfrg] Mishandling twist attacks

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

I think it's important for the public record to be clear on the security
advantages of Curve25519 over PinkBikeShed.

I realize that most people don't see this as important---"Microsoft has
abandoned the PinkBikeShed proposal now; you're beating a dead horse"---
but I have serious concerns about the procedures that have brought CFRG
to this point. This message first discusses the procedures, and then
discusses the technology issues. Some of these issues are also of
interest beyond PinkBikeShed.

Timeline review:

   * 19 May 2005: http://cr.yp.to/talks/2005.05.19/slides.pdf was the
     original presentation of what I now call PinkBikeShed. At the time
     I didn't give it a name (the talk said "Curve"), and the curve
     didn't last long---very soon afterwards I had thought through the
     security issues carefully enough to see that Curve25519 was better.

   * 16 October 2014: One of the CFRG chairs proposed taking two weeks
     to finalize requirements and agree on "whatever benchmarking system
     we're going to use for performance measurements", and then a month
     to measure and settle on the final "recommendations to the TLS WG".

   * 2 November 2014: Benjamin Black wrote "I don't understand the
     insistence on rushing a decision. We're talking about choices we
     will have to live with for 20 years. An extra month or two won't
     kill us."

     Notice the calm long-term perspective here, quite consistent with
     the idea that CFRG wanted to take time to think carefully through
     curve-selection issues---a process I respect and have been happy to
     contribute to.

   * 3 November 2014: The chair wrote "We are in fairly regular contact
     with the W3C folks, and while it's true that they are waiting with
     bated breath for our recommendations, we are not about to miss any
     trains. ... I agree with the sentiment that we have excellent
     choices already before us. However, if there's a reasonably simple
     way to ensure the highest possible levels of trustworthiness in our
     recommendations with[out] unduly compromising efficiency and
     security, then I am prepared to sacrifice some extra time to
     achieve it. ... And the longer we take, the better answers we can
     hope to get on the things that really matter."

   * 26 November 2014: The chair foreshadowed "significant developments
     ... that will help us move forward with that main work of selecting
     curves to recommend to the TLS WG." What would these developments
     be? Finally the requirements list? The details of the publicly
     verifiable benchmarking process?

   * 26 November 2014, after sundown: Night of the Living PinkBikeShed.

   * Subsequent days: Various followup discussion, both inside and
     outside CFRG. For example, Felix von Leitner characterized
     Microsoft's approach as "embrace+extend", and Trevor Perrin
     characterized Microsoft's approach as a "meaningless tweak" and a
     "terrible idea" given its impact on the existing and future code
     base. (Microsoft can afford this sort of fragmentation, but most
     ECC implementors can't.)
   
   * 28 November 2014: I sent my first "Mishandling twist attacks"
     message, carefully explaining one of the security reasons to reject
     PinkBikeShed. (In my messages to the CFRG mailing list, I've been
     careful to focus on intrinsic long-term merits of curve choices,
     rather than on how well established Curve25519 already is.)

   * 1 December 2014: Black claimed that twist attacks don't apply to
     PinkBikeShed if the curve-specifying document presents the Edwards
     view of PinkBikeShed rather than the Montgomery view.

   * 2 December 2014: I asked how Black could justify _any_ form of
     twist security in his Edwards proposals if he believes his claim;
     this question is still unanswered weeks later. I also explained why
     his claim was wrong.

   * 8 December 2014: Black, in the guise of responding to my message,
     made many erroneous comments about related issues. I was extremely
     busy and didn't have a chance to respond to this before now.

   * 12 December 2014: The chair characterized Black's comments as
     "quite powerful arguments" but said that Black should abandon those
     arguments for the sake of "unblocking our current logjam" and
     "making progress".

     There was no explanation of why CFRG was suddenly in a rush, or why
     CFRG was suddenly in a "logjam", or why CFRG should abandon its
     ongoing process of settling requirements and evaluating curves
     according to those requirements.

   * 12 December 2014: Black wrote "we will acquiesce to the will of the
     co-chairs in the interest of seeing this move forward."

Some of Black's errors related to PinkBikeShed were already pointed out
in the brief period between 8 December and 12 December, but certainly
not all, and after 12 December people seem to have decided that no
further comment was required on his message.

It's easy to imagine how someone looking back at this record could
imagine that Black had raised real technical objections that at this
point are still unaddressed---and that the result was dictated by
non-transparent politics rather than by technology. Look at the
situation from the future reader's perspective:

   * If Black's arguments were plainly bogus, or were considered and
     rejected, or were considered and judged to be outweighed by more
     important factors, then why did the chair four days later declare
     the objections to be "quite powerful arguments"?
     
   * Black's recent behavior is quite explicitly the type of
     "compromise" blasted in RFC 7282---and behind the scenes there's
     even worse "horse-trading" going on. The people who sent me private
     email along the lines of "we'll convince them to stop complaining
     about Curve25519 if you give them their pet 384-bit prime" ought to
     be ashamed of themselves. If a company can so easily push its pet
     cryptography into standards, what stops an attacker from doing the
     same with secretly weak cryptography?

   * Last month Black and the chair were saying how important it was to
     obtain "the highest possible levels of trustworthiness" in "choices
     we will have to live with for 20 years"---and suddenly this month
     they're rushing towards a call for "consensus" on a highly
     questionable new Black document.

The reader should also be faced with the technical evaluation: no, Black
never had good arguments for regressing from Curve25519 to PinkBikeShed;
no, his arguments aren't "powerful"; no, PinkBikeShed isn't some sort of
superior Microsoft technology being repressed by politics.

Enough about procedures; let me now focus on the technology.

In my first "Mishandling twist attacks" message I wrote "every major ECC
standard already multiplies scalars by the curve's cofactor" and then
analyzed the worrisome impact on PinkBikeShed if a "protocol multiplies
the secret scalar s by the cofactor 4 exactly as the standards say".
This security issue for PinkBikeShed is eliminated by Curve25519.

Here's the centerpiece of Black's response: "A sloppy implementor could
just as easily misread guidance and clear cofactor 4 on Curve25519."

Let's think this through, starting from the facts.

The DH factor used in IEEE P1363-2000 Section 7.2.2 is "k", which by
definition is the "cofactor k = #E/r"; of course, "r" is a big "prime
integer" and is the order of the specified generator. The MQV cofactor
in Section 7.2.4 is also k. The DH factor in ANSI X9.63 Section 5.4 is
"h", the same cofactor under a different name. The MQV factor in ANSI
X9.63 Section 5.5 is the same cofactor. I could keep going like this for
a while. There are explanations all over the place, in these standards
and elsewhere, of why you should multiply by the curve's cofactor.

In the case of Curve25519, the curve's cofactor is amply documented as
being 8, and the consistent message of these standards is to multiply by
8. There's no ambiguity here, and Black gives no indication of how a
"sloppy implementor" (or protocol designer) could "misread" any of this.

It's true that, in the types of protocols I've been talking about,
taking cofactor 4 on Curve25519 would cause very similar damage to
taking cofactor 4 on PinkBikeShed. However, to judge the impact of
conceivable failures, one has to rationally evaluate the probability of
the failures. For PinkBikeShed, multiplying by 4 is _exactly_ what all
of these standards recommend, and it's easy to see how the failures
would happen. For Curve25519, Black's imaginary multiplication by 4 is
_contrary_ to what all of these standards recommend. Black's claim of
equal probability ("just as easily") isn't even marginally plausible.

Benjamin Black writes:
> I am objecting to the notion that cofactors (8,4) are in any way more
> secure than (4,8).

See my first "Mishandling twist attacks" message, and see above.

> I am not objecting to twist security and the curves in the draft are
> twist secure.

This doesn't answer the question that I asked on 2 December. Let me try
phrasing it differently.

You claim that, because of your choice to specify curves in Edwards form
rather than Montgomery form, the advanced twist attacks that I'm talking
about "do not apply" to your draft. You therefore claim that "rigidity"
requires taking a smaller coefficient (PinkBikeShed) rather than a
coefficient protected against these attacks (Curve25519).

Obvious analogy: You claim that, because of exactly the same choice,
_no_ twist attacks apply to your draft. You therefore claim that
"rigidity" requires taking a smaller (in fact, _much_ smaller)
coefficient, ignoring _all_ twist attacks.

But wait a minute: you _don't_ seem to be making these last two claims;
these claims aren't consistent with any of the curves you've proposed.
You must therefore have some reason for believing that Edwards curves
_are_ subject to twist attacks. What exactly is this reason, and why do
you think that it _doesn't_ apply to more advanced twist attacks?

> I do not agree with your assertion that "adding twist security" _and_
> "switching to single-coordinate ladders" is the solution against
> security failures when it comes to invalid-curve attacks. Windowing
> implementations on complete Edwards curves can be implemented securely
> and eliminate any risks against those attacks.

Yes, the implementor _can_ check whether the incoming point is on the
curve. However, it's very easy to see how an implementor could end up
using a scalarmult routine that doesn't include this check---see

   https://duckduckgo.com/?q=elliptic+curve+scalar+multiplication

for many, many, many examples---and then the attacker wins. As I wrote
before: "Rather than blaming the implementor, we eliminate these
security failures by adding twist security, for both Montgomery and
Edwards, and switching to single-coordinate ladders."

You say that you don't agree that this is "the solution". You instead
advocate ignoring the problem on the protocol level, and relying on the
implementor to be careful to do this right. The simple fact is that your
"solution" is fragile (even Hugo Krawczyk was bitten by these attacks!)
while mine is not.

More examples of the same general phenomenon, and a more detailed
discussion of this example, appear in the "General context" section of
my first "Mishandling twist attacks" message.

> In fact, looking at the Curve41417 paper, you eschew the
> Montgomery (or Edwards) ladder in favor of windowing.

No, the paper does not "eschew" the Montgomery ladder. It says that (for
this number of bits on this platform, and of course disregarding the
differences in inputs) Montgomery-ladder scalarmult is "not quite as
fast" as windowed-Edwards scalarmult, but it also says that the
Montgomery ladder "has the advantage of fitting the computation into
less SRAM", says that "each curve in Edwards form is birationally
equivalent to one in Montgomery form, so there is no need to choose one
over the other", and mentions the importance of twist-security when
"only the [Montgomery] x-coordinate is transmitted and used".

Furthermore, you're once again confusing the choice of _computation_
with the choice of _coordinates_. I feel like a broken record here---
starting in my first message to CFRG in July, I've pointed out a number
of errors from your team stemming from this rather basic confusion, and
your team has consistently dodged rather than responding.

> In this case, the performance advantages of Edwards trump the
> irrefutable and essential requirement for eliminating "security
> failures" above via use of single-coordinate ladders.

No, the paper says nothing of the sort; it simply evaluates the speed of
scalar multiplication. Furthermore, you're _again_ confusing the choice
of computation with the choice of coordinates.

> I am also objecting to your repeated claims, contradicted by your own
> work, that single-coordinate ladders are required.

Precisely what do you think you mean by "single-coordinate ladders are
required", and precisely which claims do you think you're objecting to?
Exact quotes in context, please, not careless paraphrases.

Here's a sampling of what I've actually written. The Montgomery ladder
is a remarkably simple, fast, constant-time algorithm for single-scalar
multiplication on (e.g.) Curve25519:

   x2,z2,x3,z3 = 1,0,x1,1
   for i in reversed(range(255)):
     bit = 1 & (n >> i)
     x2,x3 = cswap(x2,x3,bit)
     z2,z3 = cswap(z2,z3,bit)
     x3,z3 = ((x2*x3-z2*z3)^2,x1*(x2*z3-z2*x3)^2)
     x2,z2 = ((x2^2-z2^2)^2,4*x2*z2*(x2^2+A*x2*z2+z2^2))
     x2,x3 = cswap(x2,x3,bit)
     z2,z3 = cswap(z2,z3,bit)
   return x2*z2^(p-2)

For DH I've repeatedly said that the Montgomery ladder minimizes
tensions between speed, simplicity, and security; I've seen no arguments
to the contrary. My primary reason for objecting to cofactor-1 curves is
that those curves fail to provide this important option to DH protocol
designers and DH implementors.

There are many situations---most obviously, signatures---where most
implementors will want to do something different from the Montgomery
ladder. If you think that I've told them "No, you have to use the
Montgomery ladder!" then you're mistaken. If you think that specifying a
Montgomery curve forces people to use the Montgomery ladder then you're
again mistaken.

> Suggesting that (4,8) vs (8,4) introduces security risk is not a
> technical argument about the strength of the curve.

Are you trying to say that twist security isn't a technical issue, or
that leaks of scalar bits inside existing and future protocols aren't a
technical issue, or that you have some more limited notion of curve
"strength" that doesn't cover these security issues?

> The additional criterion you are describing is difficult to see as
> "twist security".

That depends on how broad your protocol view is. As I said before,
unless the RNG is backdoored, standard DH is _not_ noticeably damaged by
this particular type of leak of scalar bits; but there are other
protocols that _are_ seriously damaged.

> The curves in the draft are twist secure by any reasonable definition,
> including your own SafeCurves twist security requirements.

There's one attack paper after another showing how to break
implementations of standard ECC (and of semi-standard ECC making similar
mistakes, such as Bitcoin). I'm talking about major failures in major
protocols such as DH and signatures.

The traditional response to these problems is to blame the implementor.
SafeCurves blames the curve choices, declaring the underlying curves to
be "unsafe", since we know exactly how the underlying implementation
pitfalls are eliminated by better choices of curves. SafeCurves is
completely explicit about what it means by "safe", and about why it is
drawing that line.

If some particular curve is labeled as "safe" by SafeCurves, can you
conclude that it has identical security to all of the other curves
labeled "safe" by SafeCurves? Of course not: this conclusion is silly,
and certainly isn't justified by anything SafeCurves says.

It should also be obvious, as a procedural matter, that CFRG needs more
stringent requirements than SafeCurves. The BADA55 paper shows that
there are more than a million "safe" curves (including Brainpool-level
rigidity) even without exploiting variations in primes; something is
seriously wrong if CFRG is actively recommending all of those curves for
deployment.

> A sloppy implementor could even more easily skip checks for weak keys
> when using Montgomery Curve25519 outside of DH. All Curve25519
> documentation makes clear all 32-byte strings are valid keys. That
> this is so only for DH is easily forgotten and I've not found a
> Curve25519 implementation that performs the required check.

Let me get this straight. You think that the amazing simplicity and
robustness of Montgomery coordinates for DH are _bad_ things since

   (1) you think they might encourage implementors to oversimplify some
       unusual protocol that relies on "contributory" behavior and

   (2) you think this oversimplification would be less likely if
       implementors were forced to use other coordinates for DH?

Even if the (many) unclear details in this argument were filled in, the
argument would be completely missing the incredible importance of DH.
DH obviously outweighs all of the "contributory" protocols that have
ever been invented.

The analogy to the PinkBikeShed/Curve25519 comparison also doesn't work.
For PinkBikeShed/Curve25519, the DH situation is the same and the
lesser-known protocols are the tiebreaker.

> using p = 1 mod 4 primes introduces the concern you are raising

First, this isn't an argument for PinkBikeShed over Curve25519; they
both use the same prime.

Second, this argument is incorrect. I'm talking about curves where
multiplying by the curve cofactor doesn't clear the twist cofactor.
Curve25519 is _not_ one of these curves, but the prime _is_ 1 mod 4.

> Rather than blaming the implementor for clearing the "wrong" cofactor,
> we can eliminate this "security failure" by using p = 3 mod 4 to
> ensure the cofactors are equal, which is the choice you made for both
> Curve1174 and Curve41417.

First, this isn't an argument for PinkBikeShed over Curve25519.

Second, this argument gets the technical facts all wrong. Taking primes
that are 3 mod 4 _allows_ equal cofactors but doesn't "ensure" them.
More importantly, having the twist cofactor _divide_ the curve cofactor
fully solves the problem I'm talking about; there is no reason to have
the cofactors equal.

Third, this argument gets the historical facts all wrong. The prime for
Curve41417 was the output of a performance-focused search, and it
happened to be 3 mod 4. Curve1174 _did_ require 3 mod 4---but the reason
for this requirement had nothing to do with cofactors; the reason was to
give an example of a curve supporting the Elligator 1 function. The
introduction of the Elligator paper is completely explicit in saying "we
introduce a high-security high-speed elliptic curve that supports the
[Elligator 1] function".

> Looking at your Curve25519 paper there is a single mention of
> requirements on cofactors: "Multiply the secret key by a small power
> of 2 to account for cofactors in the curve group and the twist group".

Actually, the paper contains a considerably more detailed discussion of
cofactor requirements, although to see this you have to read the paper
and understand what some formulas are saying---a naive word search isn't
adequate.

In particular, in the "Security" section, the "Small-subgroup attacks"
subsection gives a unified description of small-subgroup attacks and
twist attacks, describes the information leaked considering the curve
cofactor 8 and the twist cofactor 4, and observes that the
multiplication of scalars by 8 eliminates the leak.

For the security analysis in the paper, it's irrelevant whether this
multiplication is

   * by the curve cofactor (as all the standards say) or
   * by the lcm of curve and twist cofactors (as the paper introduction
     says).
   
The reason it's irrelevant is that for Curve25519 these two options are
identical. This is exactly where PinkBikeShed would have created an
unnecessary conflict, begging implementations to do the wrong thing.

> Curve1174: "Edwards curve shape x^2+y^2=1+dx^2y^2 chosen for efficiency."
> Curve25519: "Montgomery curve shape y^2=x^3+Ax^2+x chosen for efficiency"
> Curve41417: "Edwards curve shape x^2+y^2=1+dx^2y^2 chosen for efficiency"
> Curve1174: "Complete Edwards curve chosen for security."
> Curve25519: No such statement.
> Curve41417: "Complete Edwards curve chosen for security."
> It is difficult to see this as rigidity.

All of these curves can be viewed as Montgomery curves _and_ as complete
Edwards curves. The Edwards view is better for signatures and similar
speed for DH (depending on exact sizes, compression, etc.), although
Montgomery is by far the simplest DH option.

The reason that Curve25519 didn't require completeness in Edwards form
is obvious from the following timeline:

   * ECC 2005: I introduced Curve25519.

   * 2007: Tanja Lange and I went to a surprising talk by Edwards
     presenting what are now called "original Edwards curves". We then
     introduced "Edwards curves", in particular introduced "complete
     Edwards curves" (none of which are original Edwards curves), and
     introduced fast algorithms for arithmetic on Edwards curves.

Surely you understand that it would have been rather difficult to make
efficiency choices and security choices on the basis of tools that
nobody knew about until two years later. You can think of Curve25519 as
being lucky for also meeting the newer requirements, and then the fact
that it was introduced so early makes it arguably _more_ rigid---curve
manipulation would have had to be based on secret attacks known in 2005.

Of course, any manipulation of, e.g., NIST P-224 would have had to be
based on attacks known in the 1990s. The critical difference is that
P-224 _doesn't_ meet newer public requirements. For example, P-224
doesn't meet the SafeCurves twist-security requirements. P-224 turns out
to be at the attacker's perfect level of twist-insecurity, similar to
DES, breakable at moderate cost while still being plausibly deniable.

> In the recent Curve41417 paper I similarly find a single mention of
> cofactor requirements: "For security we ... insist on the same level
> of twist-security as Curve25519 — the cofactors of the curve and its
> twist are in {4, 8}." No mention of either requiring the cofactors be
> equal or that they be minimal (which they aren't).

Obviously very large cofactors aren't compatible with security, but very
specific rules such as cofactor _minimality_ and cofactor _equality_
aren't required. Even NIST managed to get this right in the original
NIST-curve specification: it advocated minimal cofactors for
"efficiency", not for security.

What ultimately matters is the tradeoff between the security level and
performance. This is influenced in a complicated, but measurable, way by
choices of primes, cofactors, etc. In the case of Curve41417, we
obtained a surprisingly small d by allowing (8,8), although of course
this also reduced the rho security from 2^205.8 to 2^205.3.

---Dan