Topic: Attack against some P2P coin mixing schemes (Read 948 times)

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

Thanks

+1

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

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:


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.

(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://bitcointalksearch.org/topic/p2p-coin-mixing-93390) 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.