[curves] CryptoNote and equivalent points
Rene Struik
rstruik.ext at gmail.com
Fri May 19 06:29:52 PDT 2017
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 at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves
--
email: rstruik.ext at gmail.com | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363
More information about the Curves
mailing list