Bitcoin Forum
November 19, 2017, 05:01:15 PM *
News: Latest stable version of Bitcoin Core: 0.15.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: Attack against some P2P coin mixing schemes  (Read 834 times)
Sergio_Demian_Lerner
Hero Member
*****
expert
Offline Offline

Activity: 539


View Profile WWW
April 01, 2013, 05:03:01 PM
 #1

(disclaimer: this post has not been verified by exploit code or even test code. I've relied on code inspection only, so I may be wrong)

There was some discussion (e.g. https://bitcointalk.org/index.php?topic=93390.0) regarding possible coin mixing schemes. I don't any of them have been implemented, but many people have risen such proposals.

Straightforward solution is to combine multiple transactions from different owners into a single one, by combining the inputs and the outputs (possibly changing the output amounts, and adding additional outputs). We suppose here that the scheme does not make use of SIGHASH_ANYONECANPAY. The simplified protocol is this: first all parties build a big mixing transaction, then all parties sign their inputs in turns.

There is a subtle "bug" in the Bitcoin protocol that allows two different inputs of the same transaction to be signed by the same signature. If the parent output contains a trailing OP_CODESEPARATOR, then the subscript inserted into the transaction to be hashed will be empty.
(https://en.bitcoin.it/w/images/en/7/70/Bitcoin_OpCheckSig_InDetail.png seems not to agree with it and I think it is mistaken)

Then any transaction input whose parent output scripts ends with OP_CODESEPARATOR will compute the same hash, and so they will require signatures of the same message. Identical signatures will work.

Attack

Suppose Alice always mixes her coins with random people with the p2p protocol described above. Each time she wants to resend some previously received coins X, she mixes X with a random group.

Suppose Mallory has to pay Alice some amounts x and y.  She builds two transactions Tx and Ty, to be sent to an addresses given by Alice. But in each output script, the last opcode is a OP_CODESEPARATOR. I suppose these transactions will be non-standard, but Mallory manages to send them to a miner or mine a block with them herself.

Alice receives these transactions (*) and now she wants to spend Tx. She start building a big mixing transaction with some people that, among other inputs, spends Tx.

Mallory takes also part of the mixing, but instead of providing her own previous outputs, she provides the output of Ty as an input, and an output address that she controls. When all parties sign the mixing Tx, she first listens to Alice signature, and then replicates it.

Now, Alice has stolen the coins in Ty.

Some time ago I posted about possible problems with the complexity of the script signing method, and I suggested just inserting '*' in the script to be signed, instead of the subscript mess.

(*) I wonder if the Satoshi client will recognize them as for herself.


Best regards,
 Sergio.
1511110875
Hero Member
*
Offline Offline

Posts: 1511110875

View Profile Personal Message (Offline)

Ignore
1511110875
Reply with quote  #2

1511110875
Report to moderator
"Governments are good at cutting off the heads of a centrally controlled networks like Napster, but pure P2P networks like Gnutella and Tor seem to be holding their own." -- Satoshi
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1511110875
Hero Member
*
Offline Offline

Posts: 1511110875

View Profile Personal Message (Offline)

Ignore
1511110875
Reply with quote  #2

1511110875
Report to moderator
Peter Todd
Legendary
*
expert
Offline Offline

Activity: 1106


View Profile
July 21, 2013, 12:50:30 PM
 #2

Then any transaction input whose parent output scripts ends with OP_CODESEPARATOR will compute the same hash, and so they will require signatures of the same message. Identical signatures will work.

OP_CODESEPARATOR only comes into affect when it is actually executed: EvalScript() starts off with pbegincodehash = script.begin(); and only updates pbegincodehash when the OP_CODESEPARATOR is executed.

In a scriptPubKey of the following form:


<pubkey> OP_CHECKSIG OP_CODESEPARATOR


The OP_CODESEPARATOR has no effect. Interestingly the signature is the same for a scriptPubKey with no OP_CODESEPARATOR at all, because of the scriptCode.FindAndDelete(CScript(OP_CODESEPARATOR)); line in SignatureHash(), but that doesn't change anything with regard to your proposed attack.

I really should get around to writing some separator related unittests; we don't have any right now.

jgarzik
Legendary
*
qt
Offline Offline

Activity: 1470


View Profile
July 22, 2013, 02:59:23 PM
 #3

I really should get around to writing some separator related unittests; we don't have any right now.

+1

Related note:  JSON test vector data from bitcoin/bitcoin.git is reused in multiple projects: pynode, picocoin and now node-libcoin.


Jeff Garzik, bitcoin core dev team and BitPay engineer; opinions are my own, not my employer.
Donations / tip jar: 1BrufViLKnSWtuWGkryPsKsxonV2NQ7Tcj
Sergio_Demian_Lerner
Hero Member
*****
expert
Offline Offline

Activity: 539


View Profile WWW
July 22, 2013, 03:03:36 PM
 #4

Thanks
Peter Todd
Legendary
*
expert
Offline Offline

Activity: 1106


View Profile
July 22, 2013, 03:19:27 PM
 #5

I really should get around to writing some separator related unittests; we don't have any right now.

+1

Related note:  JSON test vector data from bitcoin/bitcoin.git is reused in multiple projects: pynode, picocoin and now node-libcoin.

pythion-bitcoinlib too if I ever get around to finishing up the unittests I wrote. Smiley

Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!