[Cfrg] Handling invalid points

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

My goal for curve selection, as I explained in Toronto, is to minimize
tensions between speed, simplicity, and security. My impression is that
there's consensus on at least one part of this: choosing a curve that
can be expressed in Edwards form, i.e., a curve that has a point of
order 4.

Microsoft has made a broader spectrum of proposals, apparently to be
prepared in case CFRG instead wants a curve of cofactor 1, but hasn't
actually been arguing that cofactor 1 is preferable. Nigel Smart claimed
at one point that cofactor 1 is "vital to avoid mistakes" but has never
given details. Meanwhile many people have pointed to the undisputed
benefits of Edwards curves, such as a very fast complete addition law.
I think CFRG could reasonably declare that a point of order 4 is a
requirement, simplifying subsequent discussion.

However, http://eprint.iacr.org/2014/832.pdf claims that cofactor 1 is
desirable because cofactors larger than 1 create "an additional
overhead" and "a source for implementation weaknesses" if a certain
"check is omitted or just forgotten". Similarly, a recent Oberthur
message claims that cofactor 1 should be "mandatory" to avoid "small
subgroup attacks" in careless implementations.

I find these claims quite puzzling, for several reasons:

   * Cofactors are already allowed by all of the usual ECC standards
     from IEEE, ANSI, and NIST. FIPS 186-4 sets the cofactor limit at
     2^14 for 255-bit primes. Certicom's pet SEC 1 standard has always
     allowed cofactor 4, and in 2009 started allowing even more.

   * Small-subgroup attacks were a big issue for pre-ECC discrete-log
     systems because those systems typically have huge cofactors---but
     for ECC everybody uses curves with vastly smaller cofactors, so the
     small-subgroup attacks learn almost nothing, even if nobody bothers
     defending against them. Invalid-curve attacks are a different
     story, but they have nothing to do with the minor difference
     between, e.g., cofactor 1 and cofactor 8 for the original curve.

   * The major ECC standards already eliminate _all_ of the information
     leakage from small-subgroup attacks. For example, ECDH in ANSI
     X9.63 computes a shared secret as "P=hdQ", where h is the cofactor
     and d is the secret key.

Notice that the cofactor multiplication in ANSI X9.63 etc. isn't a
"check" that can be "forgotten" by a careless implementation: such an
implementation would flunk every normal test vector for shared-secret
generation.

For comparison, a static-ECDH (or reused-ephemeral-ECDH) implementation
that doesn't check an incoming (x,y) against the curve equation will
leak its _entire_ secret key to a very fast attack. This huge security
problem _won't_ be caught by typical test vectors. This is vastly more
important than small-subgroup attacks.

Oberthur claims that checking the curve equation to stop these attacks
is "insignificant" compared to cofactor multiplication, but this is
exaggerating a tiny performance issue while ignoring the likelihood of
an omitted test and the security damage caused by the omission. We have
enough trouble getting crypto right without adding unnecessary traps!

The right way to eliminate the invalid-curve problem has two steps:

   (1) Require compressed points in protocols. This syntactically limits
       the input point to two curves: the original curve and its twist.

   (2) Choose twist-secure curves.

This also has many further benefits. Compressed points on curves with
points of order 4 also allow unmatched ECDH simplicity, at an excellent
performance level, via the Montgomery ladder. Serious hardware analyses
such as

   http://mhutter.org/papers/Wenger2011HardwareProcessorSupporting.pdf

consistently praise the Montgomery ladder---using compressed inputs and
outputs---for its simplicity, speed, and small resource consumption in
hardware. Of course, compressed points also reduce network traffic.

Why would anyone talk about small-subgroup attacks as being stopped by a
"check" that might be "forgotten", the same way that a curve-equation
check can stop invalid-curve attacks but might be forgotten? Answer:
What I've described so far is

   * a computational (robust) defense against small-subgroup attacks,
   * a verifying (not robust) defense against invalid-curve attacks, and
   * a computational (robust) defense against invalid-curve attacks,

but there's also

   * a verifying (not robust) defense against small-subgroup attacks.

Specifically, instead of multiplying the incoming point Q by h, one can
check whether hQ = 0. This check runs a serious risk of being omitted,
the same way that a curve-equation check runs a serious risk of being
omitted, although the resulting damage is much less severe.

Note that Certicom's dwindling patent portfolio has a not-quite-dead-yet
patent 6563928 on this inferior method ("determining whether said public
information ... lies within a subgroup ... having less than a
predetermined number of elements and rejecting messages utilizing said
public information if said public information lies within such a
subgroup"), which makes it particularly strange that anyone would talk
about this as the normal thing to do. Does Oberthur have a license for
this patent?

Anyway, if there really are reasons that CFRG should seriously consider
curve proposals with cofactor 1 then I think it's important for those
reasons to be made clear.

---Dan