> On May 19, 2017, at 6:29 AM, Rene Struik <rstruik....@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@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
smime.p7s
Description: S/MIME cryptographic signature
_______________________________________________ Curves mailing list Curves@moderncrypto.org https://moderncrypto.org/mailman/listinfo/curves
