[curves] CryptoNote and equivalent points

[Trevor Perrin]

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 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.

 (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