[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

[Rene Struik]

Hi Trevor:

This simply illustrates that one should not mindlessly copy co-factor
scalar multiplication code, without understanding that the map [k]: k
--> kQ for a point Q of order d is only 1-1 if gcd(k,d)=1.

The [k] map is 1-1 for any point Q on the curve if one picks k co-prime
to the curve's order (since Q's order d divides |E|=h*n). For
Curve25519, one can pick k odd and co-prime to n, e.g., k=2*k0+1, where
k0 in [1, (n-1)/2] (or simply pick k to be a 252-bit integer, where one
simply sets the lowest-order bit to 1 [note that n> 2^{252}, so k<n then
(I think this was Dan Bernstein's original argument in the Curve25519
paper to pick an order slightly above the 252-bit mark]).

Disclaimer: I do not know any CryptoNote details, so picking k as above
may not work in their case. Nevertheless, this seems to be a bug.

Rene

Post by Trevor Perrin
https://getmonero.org/2017/05/17/disclosure-of-a-major-bug-in-cryptonote-based-currencies.html
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.
(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
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves

[Mike Hamburg]

This simply illustrates that one should not mindlessly copy co-factor scalar multiplication code, without understanding that the map [k]: k --> kQ for a point Q of order d is only 1-1 if gcd(k,d)=1.
The [k] map is 1-1 for any point Q on the curve if one picks k co-prime to the curve's order (since Q's order d divides |E|=h*n). For Curve25519, one can pick k odd and co-prime to n, e.g., k=2*k0+1, where k0 in [1, (n-1)/2] (or simply pick k to be a 252-bit integer, where one simply sets the lowest-order bit to 1 [note that n> 2^{252}, so k<n then (I think this was Dan Bernstein's original argument in the Curve25519 paper to pick an order slightly above the 252-bit mark]).

Right. This is a signature verification, probably Schnorr, so hashing to an odd number might have fixed it.

Disclaimer: I do not know any CryptoNote details, so picking k as above may not work in their case.

Like Rene, I’m speculating.

Nevertheless, this seems to be a bug.
Rene

Post by Trevor Perrin
https://getmonero.org/2017/05/17/disclosure-of-a-major-bug-in-cryptonote-based-currencies.html
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.
(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?

Decaf does work for Curve25519. It’s in the paper, and Henry+Isis and I have independently implemented it.

In fact, it turns out there are multiple ways to do it for Curve25519 based on the paper, and Henry+Isis and I probably picked different ones (but we haven’t cross-tested yet, so we aren’t sure). So the curve25519 encode and decode functions in libdecaf should probably be considered unstable for now, as should the ones in Henry+Isis’ golang library.

Post by Trevor Perrin
Other thoughts?
Trevor
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves

--
cell: [phone] | US: [phone]
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves

[Trevor Perrin]

Post by Mike Hamburg
Right. This is a signature verification, probably Schnorr, so hashing to an odd number might have fixed it.

Maybe. I think I was wrong that hashing the "key image" into the
Schnorr challenge is a fix.

Multiplying the "key image" by cofactor before checking for
double-spending might work (similar to VXEdDSA producing its "VRF"
output).

If anyone understands this algorithm in depth feel free to explain more.

Post by Mike Hamburg
Decaf does work for Curve25519. It’s in the paper, and Henry+Isis and I have independently implemented it.
In fact, it turns out there are multiple ways to do it for Curve25519 based on the paper, and Henry+Isis and I probably picked different ones (but we haven’t cross-tested yet, so we aren’t sure).

It would be great to see a writeup + performance analysis of the exact
Curve25519 formulas, including conversions from X25519 and Ed25519
public keys into Decaf.

People with complex protocols designed for prime-order groups will
have to weigh Decaf against just tweaking things for the cofactor, or
choosing a different curve, and the relative costs aren't that easy to
figure out.

Trevor

[CryptoNote] https://cryptonote.org/whitepaper.pdf
[Decaf] https://eprint.iacr.org/2015/673.pdf

[Tim Ruffing]

Post by Trevor Perrin
If anyone understands this algorithm in depth feel free to explain more.

As this came up in the other thread as well:
What they need is that the attacker cannot find two "spends" created
using the same secret key but with different key images. [1]

Then the verifiers can reject double-spends by just keeping a set of
already used key images.

If I'm not entirely mistaken, this should be possible if the verifier
just multiplies the key image by the cofactor and stores the result in
the set.

However, as nicely explained in the other thread, this "clears" the 8-
torsion component but modifies the l-torsion component. So if Monero
had implemented that fix, verifiers would have had to upgrade their
databases before they can continue (by going through the set of key
images and multiplying each key image by the cofactor).

So in an existing system, the simpler fix is to just reject points that
are not in the right subgroup. This is particularly true as they wanted
to deploy a fix without anybody noticing...

(Without warranty, I thought no more than a few minutes about it.)

Tim


[1] You can use proofs of knowledge to make that formal.

[Lee Clagett]

Post by Trevor Perrin
https://getmonero.org/2017/05/17/disclosure-of-a-major-bug-in-cryptonote-based-currencies.html
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.

Post by Trevor Perrin
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.
(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 ?

Post by Trevor Perrin
(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

[Trevor Perrin]

Post by Lee Clagett

Post by Trevor Perrin
(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

Yeah, I was wrong (I was thinking about 3rd-party tampering, instead
of double-spending, for some reason).

Trevor