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
On 5/18/2017 9:31 PM, Trevor Perrin 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 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
_______________________________________________
Curves mailing list
Curves@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/curves
--
email: rstruik....@gmail.com | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363
_______________________________________________
Curves mailing list
Curves@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/curves
