[curves] CryptoNote and equivalent points

[Mike Hamburg]

> On May 19, 2017, at 6:29 AM, Rene Struik <rstruik.ext at gmail.com> wrote:
> 
> 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]).

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

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.

>> 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
> 
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 3571 bytes
Desc: not available
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20170519/14b97514/attachment.bin>