Re: [Cfrg] Handling invalid points

[Michael Hamburg <[e-mail]>]

Hi DJB,

To play devil’s advocate here, there are other sorts of “attacks" against
curves with cofactors.  They’re fairly narrow, but they should be noted.

In general, these attacks do not exist against properly defined protocols,
but the protocol may have suboptimal properties when used with a
cofactor, or it may require checks that are tempting to skip, or it may
require jumping through some hoops.  Three issues come to mind.

1)

With a prime-order short Weierstrass curve, (x,y) points transmitted on
the wire (compressed or otherwise) cannot be the identity, nor can they
have small order.  As a result, if the secret key is valid (and nonzero, and
not equal to the group order), then the output of ECDH cannot be the
identity.  Furthermore, the output is a 1:1 function of the input, at least if
the input is checked for reduction.

But with an Edwards curve, (x,y) points transmitted on the wire can be the
identity, and can have small order.  Likewise, if a curve with a cofactor
is used in short Weierstrass form, (x,y) cannot be the identity, but can
have small order.  Therefore, ECDH can output the identity, and a malicious
actor can cause ECDH to output the identity with non-negligible probability
(if your ECDH protocol clears the cofactor, then with probability 1.)  This
could cause an exception or error, or it might cause the system to output
a predictable value.

You documented this family of attacks on Curve25519 at cr.yp.to/ecdh.html:

“””
There are some unusual non-Diffie-Hellman elliptic-curve protocols that need
to ensure ``contributory'' behavior. In those protocols, you should reject the
32-byte strings that, in little-endian form, represent 0, 1, [several large
numbers].
“””

As this quote says, most protocols don’t need to worry about this because
they do not need to ensure “contributory” behavior.

The Goldilocks encoding reduces the complexity of dealing with this sort of
attack: the identity is encoded as 0, and no other low-order points can be
encoded.



2)

For curves with a cofactor, ECDH is not 1:1.  This affects Trevor Perrin’s
TripleDH protocol, which attempts to work around concerns about patents on
session-hashing (don’t ask me what those are, I haven’t studied them).  As
a result, TripleDH implementations are forbidden to clear the cofactor, and
secret keys must be invertible mod the cofactor (i.e. odd).  If this requirement
were violated, it probably wouldn’t lead to an attack, but it wouldn’t guarantee
that the sessions seen by both sides were exactly the same.



3)

Another form of “attack” would be to cause two implementations to produce
different results for a supposedly deterministic computation, eg a signature
check.  For example, in the Ed25519 paper, you specify:
""
The verifier is /permitted/ to check this stronger equation and to reject signatures
where the stronger equation does not hold.  However, this is not /required/;
checking that 8SB = 8R + 8H(_R_, _A_, M)A is enough for security.
“””

A similar warning is given in goldilocks.h for goldilocks_verify:
“””
/**
 * @brief Verify a signature.
 *...
 * Currently this function does not detect when the public key is weird,
 * eg 0, has cofactor, etc.  As a result, a party with a bogus public
 * key could create signatures that succeed on some systems and fail on
 * others.
 * ...
 */
“””
The implemented behavior will accept public keys with 2-torsion components or
which are the identity, but not ones which are incorrectly encoded or are on the
twist. It does not permit any laxity in the signature itself.  But there would be some
incentive to be lax about cofactor in the signature during a batch verify.

In both these systems, implementations are allowed to differ when given inputs
that are wrong by a small-order amount.  There are more ways to specify this
sort of laxness with cofactored curves, though behavior should be testable by
vectors if the specification goes one way or the other.

Again, it’s not clear that this constitutes an attack, but it is something to
consider when deploying such a system.

Cheers,
— Mike

> On Nov 21, 2014, at 3:12 PM, D. J. Bernstein <[e-mail]> wrote:
> 
> 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
> 
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg