[curves] CryptoNote and equivalent points

[Lee Clagett]

On Fri, 19 May 2017 01:31:49 +0000 Trevor Perrin <trevp at trevp.net>
wrote:
> Interesting bug:
> 
> https://getmonero.org/2017/05/17/disclosure-of-a-major-bug-in-cryptonote-based-currencies.html
> 
> I don't know much about CryptoNote, but I think this is the story:
> 
> They sign transactions with a ring signature scheme so the signature
> can be verified without knowing which of several private keys produced
> it.  Private keys are intended to be used once.  To prevent
> double-spending, the signature contains a "tag" or "key image" which
> will be the same if the same private key is used.
> 
> However, the tag is just a point on the 25519 curve encoded in Ed25519
> format, and verification performs scalar-multiplication with some
> scalar and this point.  I guess the signer can control this scalar to
> be a multiple of the cofactor, in which case it's possible to find
> "equivalent" tags by adding small-order points to the tag, defeating
> the double-spending protection.

This is correct.

The scalar is not necessarily chosen by the attacker ("random oracle
value"), but with such a small group finding an appropriate scalar
should not be difficult.

An alternate attack is to send coins to a small order public key.
_Anyone_ can then use _any_ small order tag to spend the coins. This is
the attack that was done on Bytecoin recently. If you look at the
equations below this attack becomes more obvious.

> This is the most dramatic case I've seen of an "equivalent" EC point
> affecting a protocol, so it's an interesting data point.  It's worth
> pondering what this means for protocol design and safe use of EC.
> 
> The obvious fixes are:
> 
>  (A) Since the signature is intended to bind a unique tag value, the
> tag should have been hashed as a signature input.

I'm not sure how this would be done without altering the construction
significantly:

    L[i] = r[i]*G       + c[i]*P[i]
    R[i] = r[i]*H(P[i]) + c[i]*I

    SUM c[i] 0...n = H(m, L[0],...,L[n], R[0],...,R[n])

Ideally the signer is providing `I = x*H(p)` where `P = x*G`. Adding `I`
to the signature hash input does not prevent the attack, and if the
verifier hashed `I` to retrieve a point it will remove the distance
equivalence between hashed public key and tag. Is there some other
technique / idea ?

>  (B) Doing a "full validation" scalar-multiplication to reject points
> outside the main subgroup also prevents this, though with a
> computation cost (note that a check that only rejects small-order
> points, such as the "all-zeros" check, doesn't help here).
> 
> (B) is what's being deployed, for compatibility, but I assume (A) is
> what they wished they had done.
> 
> Perhaps this also argues that future complex protocols should consider
> something like Mike Hamburg's Decaf (but does this work with 25519?),
> or the "torsion-safe representatives" Henry de Valence was recently
> proposing?  Or just prime-order curves?
> 
> Other thoughts?
> 
> 
> Trevor

Lee