On Fri, 19 May 2017 01:31:49 +0000 Trevor Perrin <tr...@trevp.net> 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 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. > 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. 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 ? > (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 _______________________________________________ Curves mailing list Curves@moderncrypto.org https://moderncrypto.org/mailman/listinfo/curves