Trevor Perrin

2017-05-19 01:31:49 UTC

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

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