Coinspect, a new Bitcoin focused security company, recently disclosed technical details of an attack against Copay’s multisignature wallets. At the same time they issued a challenge to recover the Bitcoins that had been used to test the Copay exploit. This post will go over the details of this challenge and how to solve it.

When the challenge started there were two unspent transaction outputs associated with the target Bitcoin address. It appeared that the challenge would be to find some way to spend these outputs without knowledge of the private keys that are normally required to sign a transaction.

Throughout this post I am going to make use of pybitcointools to perform Bitcoin related operations from the command line.

Redeeming a Bitcoin transaction

A Bitcoin transaction moves coins between one or more inputs and outputs. Each input spends the coins paid to a previous output, and each output waits as an unspent transaction output until it is spent as an input to a later transaction.

An output contains the amount that has been transferred and a script that describes the conditions that must be met in order for the output to be spent. An input references an output in a previous transaction — a transaction ID (the hash of the transaction data) and output index — and provides a script, known as the scriptSig, that satifies the output script conditions.

In the simplest case, a Bitcoin address is the hash of a user’s public key. In order to send some Bitcoin to this user a pay-to-public-key-hash (P2PKH) transaction output is created. The P2PKH output script contains instructions that allow the owner of the private key that corresponds to the hashed public key to spend the output. Such a script looks like this:

OP_DUP OP_HASH160 <PublicKeyHash> OP_EQUALVERIFY OP_CHECKSIG

The corresponding scriptSig that redeems this output is simply two pieces of data: the receivers public key, and a signature of the transaction data with the private key. (Note that the signature is of the new transaction that is spending the previous output). Not only does the signature prove ownership of the expected private key, but it also protects the new transaction against modification.

In order to verify a transaction the output script is appended to the scriptSig:

<Sig> <PublicKey> OP_DUP OP_HASH160 <PublicKeyHash> OP_EQUALVERIFY OP_CHECKSIG

This entire script is then evaluated. If the resulting stack has the value true at the top then the transaction is valid.

In this example of the most common form of transaction the OP_EQUALVERIFY and OP_CHECKSIG instructions must both complete successfully. OP_EQUALVERIFY will check that the public key provided in the scriptSig matches the expected hash in the output script, and OP_CHECKSIG will verify the signature of the transaction against the public key. For a full run through of the script execution see the Bitcoin developer guide on P2PKH Script Validation.

P2SH Addresses

With a basic understanding of Bitcoin transactions it is now time to take a look at the two unspent transactions associated with the target wallet:

>>> target = '32GkPB9XjMAELR4Q2Hr31Jdz2tntY18zCe'
>>> unspent(target)
[{'output': '8602122a7044b8795b5829b6b48fb1960a124f42ab1c003e769bbaad31cb2afd:0', 'value': 677200}, {'output': 'bd992789fd8cff1a2e515ce2c3473f510df933e1f44b3da6a8737630b82d0786:0', 'value': 5000000}]
# Get the outputs of each transaction
>>> deserialize(fetchtx('8602122a7044b8795b5829b6b48fb1960a124f42ab1c003e769bbaad31cb2afd'))['outs'][0]
{'value': 677200, 'script': 'a91406612b7cb2027e80ec340f9e02ffe4a9a59ba76287'}
>>> deserialize(fetchtx('bd992789fd8cff1a2e515ce2c3473f510df933e1f44b3da6a8737630b82d0786'))['outs'][0]
{'value': 5000000, 'script': 'a91406612b7cb2027e80ec340f9e02ffe4a9a59ba76287'}

Decoding the output script produces the following opcodes:

OP_HASH160 06612b7cb2027e80ec340f9e02ffe4a9a59ba762 OP_EQUAL

which looks nothing like the common P2PKH output script described above. It looks like that ‘all’ that’s necessary to spend these outputs is to find a value that when hashed (with SHA-256 and then RIPEMD-160) matches 06612b7cb2027e80ec340f9e02ffe4a9a59ba762. However, it turns out that this is actually another type of transaction known as pay-to-script-hash (P2SH).

In order to spend a P2SH output the scriptSig must push a serialized script, known as the redeemScript, onto the stack which has a hash that matches the one in the output script. If the hashes match, i.e. the OP_EQUAL instruction in the output script has returned true, then the redeemScript is deserialized and evaluated. The transaction is valid if the redeemScript matches the expected hash and it returns true.

Let’s look at some previous transactions from the target address and see what the redeemScript does:

# Get an existing scriptSig
>>> deserialize(fetchtx('6102bfd4bad33443bcb99765c0751b6b8e4e65f4db4e3b65324c5e9e3dac8132'))['ins'][0]
{'script': '00483045022100e5d7c59ea1fb5d0285e755dfc09634e1e3af36d12950b9b5d5f92b136021b3d202202c181129443b08dcfb8d9ced30187186c57c96f9cdb3f3914e0798682ea35d2b03493046022100e1f8dbad16926cfa3bf61b66e23b3846323dcabf6c75748bcfad762fc50bfaf402210081d955160b5f8d2b9d09d8838a2cf61f5055009d9031e0e106e19ebab234d949034c695221023927b5cd7facefa7b85d02f73d1e1632b3aaf8dd15d4f9f359e37e39f05611962103d2c0e82979b8aba4591fe39cffbf255b3b9c67b3d24f94de79c5013420c67b802103ec010970aae2e3d75eef0b44eaa31d7a0d13392513cd0614ff1c136b3b1020df53ae', 'outpoint': {'index': 1, 'hash': 'ec2a40cac3ac5dadf1d31f3cad03bdc8465caab5acbc5407ee7f4a7400aab577'}, 'sequence': 4294967295}
# Confirm that the corresponding output script matches the one discovered above
>>> deserialize(fetchtx('ec2a40cac3ac5dadf1d31f3cad03bdc8465caab5acbc5407ee7f4a7400aab577'))['outs'][1]
{'value': 350000, 'script': 'a91406612b7cb2027e80ec340f9e02ffe4a9a59ba76287'}

Decoding the scriptSig gets:

OP_FALSE 304502... 304602... 5221023927b5cd7facefa7b85d02f73d1e1632b3aaf8dd15d4f9f359e37e39f05611962103d2c0e82979b8aba4591fe39cffbf255b3b9c67b3d24f94de79c5013420c67b802103ec010970aae2e3d75eef0b44eaa31d7a0d13392513cd0614ff1c136b3b1020df53ae

We can manually verify that the final value that’s pushed onto the stack does match the expected hash in the output script:

>>> import hashlib
>>> data = "5221023927b5cd7facefa7b85d02f73d1e1632b3aaf8dd15d4f9f359e37e39f05611962103d2c0e82979b8aba4591fe39cffbf255b3b9c67b3d24f94de79c5013420c67b802103ec010970aae2e3d75eef0b44eaa31d7a0d13392513cd0614ff1c136b3b1020df53ae".decode("hex")
>>> data = hashlib.sha256(data).digest()
>>> hashlib.new('ripemd160', data).hexdigest()
'06612b7cb2027e80ec340f9e02ffe4a9a59ba762'

Therefore this is the redeemScript. Decoding it produces the following instructions:

2 023927... 03d2c0... 03ec01... 3 OP_CHECKMULTISIG

OP_CHECKMULTISIG takes a number of signatures and a number of public keys. Each signature and public key pair is checked with OP_CHECKSIG for validity. In order for OP_CHECKMULTISIG to return true all of the signatures must match one of the public keys. In this case there are two signatures which are provided by the scriptSig and three public keys which are included in the redeemScript. The OP_FALSE instruction in the scriptSig is required due to a bug which means that OP_CHECKMULTISIG removes an extra, unused value from the stack.

Therefore, the target address is a multisignature wallet that has three associated public keys. In order to spend an output two valid signatures are required in the scriptSig (along with the redeemScript).

Signature hash types

Bitcoin supports transaction signatures that only validate portions of the transaction. There are three signature hash types:

• SIGHASH_ALL: All inputs and outputs are signed. This is the default signature hash type.
• SIGHASH_NONE: All of the inputs are signed, but none of the outputs are.
• SIGHASH_SINGLE: Only the corresponding input and output (the output with the same index number as the input) are signed.

The signature hash type is specified by the last byte of a signature in the scriptSig. Transaction 6102bfd4... has three inputs. Here are the ends of the two signatures from each of the scriptSigs:

OP_FALSE ...5d2b03 ...d94903 <redeemScript>
OP_FALSE ...069803 ...182503 <redeemScript>
OP_FALSE ...7c2903 ...10b803 <redeemScript>

All of the signatures end in the value 0x03 which identifies them as SIGHASH_SINGLE signatures: the signature only covers the input itself and the output with the same index number. But there are three inputs and only two outputs; there is no corresponding output for the input with index two. What happens when it comes to creating the signature for this input?

It turns out that, due to a bug, if an output with the same index does not exist then the integer value one will be returned as the hash of the transaction. This appears to have been first described by Peter Todd on the bitcointalk forum. We can verify this behaviour in a Python shell:

>>> pubs = ['023927b5cd7facefa7b85d02f73d1e1632b3aaf8dd15d4f9f359e37e39f0561196', '03d2c0e82979b8aba4591fe39cffbf255b3b9c67b3d24f94de79c5013420c67b80', '03ec010970aae2e3d75eef0b44eaa31d7a0d13392513cd0614ff1c136b3b1020df']
>>> sigs = [der_decode_sig('3045022100dfcfafcea73d83e1c54d444a19fb30d17317f922c19e2ff92dcda65ad09cba24022001e7a805c5672c49b222c5f2f1e67bb01f87215fb69df184e7c16f66c1f87c2903'), der_decode_sig('304402204a657ab8358a2edb8fd5ed8a45f846989a43655d2e8f80566b385b8f5a70dab402207362f870ce40f942437d43b6b99343419b14fb18fa69bee801d696a39b3410b803')]
>>> hash = '\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
>>> ecdsa_raw_verify(hash, sigs[0], pubs[0])
True
>>> ecdsa_raw_verify(hash, sigs[1], pubs[1])
True

This means that it should be possible to forge a valid scriptSig for another transaction by reusing these signatures on inputs that do not have a corresponding output!

Stealing coins in a new transaction

We want to create a transaction with a single output to an address that we control. This requires one input from an address we control to force the input index for the two inputs from the target transactions above zero. Here are the commands that I ran to create such a transaction:

# My address
>>> addr
'1Lyafe8mSqubnynbAWPcXbHE5pnHMzEnT3'
# Unspent transaction outputs (legitimately) under my control
>>> unspent(addr)
[{'output': '23e81960ba8bb95c33c2336c84c126e378e4d1123921f881da9247c25f524161:1', 'value': 300000}]
# Target address and unspent transaction outputs
>>> target = '32GkPB9XjMAELR4Q2Hr31Jdz2tntY18zCe'
>>> unspent(target)
[{'output': '8602122a7044b8795b5829b6b48fb1960a124f42ab1c003e769bbaad31cb2afd:0', 'value': 677200}, {'output': 'bd992789fd8cff1a2e515ce2c3473f510df933e1f44b3da6a8737630b82d0786:0', 'value': 5000000}]
# The unspent outputs are the inputs to the new transaction
>>> ins = unspent(addr) + unspent(target)
# Amount to send in the transaction
# Sum of the three inputs minus a fee for the block miner
>>> amount = 300000 + 5000000 + 677200
>>> amount -= 10000
# Single output to my address
>>> outs = [{'address': addr, 'value': value}]
# Create a new transaction from these inputs and outputs
>>> tx = mktx(ins, outs)
# Sign the first input with my private key
>>> tx = sign(tx, 0, priv)
>>> tx = deserialize(tx)
# Add the scriptSigs containing SIGHASH_SINGLE signatures of 1
>>> tx['ins'][1]['script'] = '00483045022100dfcfafcea73d83e1c54d444a19fb30d17317f922c19e2ff92dcda65ad09cba24022001e7a805c5672c49b222c5f2f1e67bb01f87215fb69df184e7c16f66c1f87c290347304402204a657ab8358a2edb8fd5ed8a45f846989a43655d2e8f80566b385b8f5a70dab402207362f870ce40f942437d43b6b99343419b14fb18fa69bee801d696a39b3410b8034c695221023927b5cd7facefa7b85d02f73d1e1632b3aaf8dd15d4f9f359e37e39f05611962103d2c0e82979b8aba4591fe39cffbf255b3b9c67b3d24f94de79c5013420c67b802103ec010970aae2e3d75eef0b44eaa31d7a0d13392513cd0614ff1c136b3b1020df53ae'
>>> tx['ins'][2]['script'] = '00483045022100dfcfafcea73d83e1c54d444a19fb30d17317f922c19e2ff92dcda65ad09cba24022001e7a805c5672c49b222c5f2f1e67bb01f87215fb69df184e7c16f66c1f87c290347304402204a657ab8358a2edb8fd5ed8a45f846989a43655d2e8f80566b385b8f5a70dab402207362f870ce40f942437d43b6b99343419b14fb18fa69bee801d696a39b3410b8034c695221023927b5cd7facefa7b85d02f73d1e1632b3aaf8dd15d4f9f359e37e39f05611962103d2c0e82979b8aba4591fe39cffbf255b3b9c67b3d24f94de79c5013420c67b802103ec010970aae2e3d75eef0b44eaa31d7a0d13392513cd0614ff1c136b3b1020df53ae'
>>> serialize(tx)
'01000000036141525fc24792da81f8213912d1e478e326c18...'

I sent this pushed this transaction out onto the network: 791fe035d312dcf9196b48649a5c9a027198f623c0a5f5bd4cc311b8864dd0cf. The coins were now mine!