Computational Puzzle: SHA-1 Collision

To follow along this tutorial

Clone the Github repository
cd code
npm install or yarn install
Execute the transaction code by typing node tx_filename.js
Alternatively you can enter the commands step-by-step by cd into ./code then type node in a terminal to open the Node.js REPL
Open the Bitcoin Core GUI console or use bitcoin-cli for the Bitcoin Core commands
Use bx aka Libbitcoin-explorer as a handy complement

On September 13, 2013, Peter Todd, a renowned Bitcoin Core developer, announced a bounty on BitcoinTalk forum. As he explain himself, "rewards at P2SH addresses are available for anyone able to demonstrate collision attacks against a variety of cryptographic algorithms. You collect your bounty by demonstrating two messages that are not equal in value, yet result in the same digest when hashed. These messages are used in a scriptSig, which satisfies the scriptPubKey storing the bountied funds, allowing you to move them to a scriptPubKey (Bitcoin address) of your choice".

On the February 23, 2017, someone successfully claimed the SHA-1 hash collision bounty of 2.48 BTC, with this transaction 8d31992805518fd62daa3bdd2a5c4fd2cd3054c9b3dca1d78055e9528cff6adc

To read more about Bitcoin computational puzzles and Peter Todd bounties

Let’s recreate the Peter Todd bounty for SHA-1 hash collision.

Creating and Funding the P2SH

Import libraries, test wallets and set the network

const bitcoin = require('bitcoinjs-lib')
const { alice } = require('./wallets.json')
const network = bitcoin.networks.regtest

Create the script.

const redeemScript = bitcoin.script.compile([
  bitcoin.opcodes.OP_2DUP,
  bitcoin.opcodes.OP_EQUAL,
  bitcoin.opcodes.OP_NOT,
  bitcoin.opcodes.OP_VERIFY,
  bitcoin.opcodes.OP_SHA1,
  bitcoin.opcodes.OP_SWAP,
  bitcoin.opcodes.OP_SHA1,
  bitcoin.opcodes.OP_EQUAL])

console.log('Redeem script:')
console.log(redeemScript.toString('hex'))

You can decode the redeem script in Bitcoin Core CLI.

decodescript 6e879169a77ca787

The p2sh method will generate an object that contains the P2SH address.

Get the P2SH address

const p2sh = bitcoin.payments.p2sh({redeem: {output: redeemScript, network}, network})
console.log('P2SH address')
console.log(p2sh.address)

Let’s fund this address with 1 BTC. This is the reward for whoever as the solution to the locking script.

sendtoaddress 2MyJKxYR2zNZZsZ39SgkCXWCfQtXKhnWSWq 1

Get the output index so that we have the outpoint (txid / vout).

gettransaction TX_ID

Find the output index (or vout) under vout.

Preparing the spending transaction

Now let’s prepare the spending transaction by setting input and output.

Alice_1 wants to send the funds to her P2WPKH address.

Create the PSBT by filling TX_ID, TX_OUT and TX_HEX.

const psbt = new bitcoin.Psbt({network})
  .addInput({
    hash: 'TX_ID',
    index: TX_VOUT,
    nonWitnessUtxo: Buffer.from('TX_HEX', 'hex'),
    redeemScript: Buffer.from(redeemScript, 'hex')
  }) (1)
  .addOutput({
    address: alice[1].p2wpkh,
    value: 999e5,
  }) (2)

1	Input referencing the outpoint of our P2SH funding transaction, the previous tx, and the redeem script
2	Output, leaving 100 000 satoshis as mining fees

Creating the unlocking script

Now we can update the transaction with the unlocking script, providing a solution to the SHA-1 bounty.

Here are the two values that have been used to claim the Peter Todd bounty.

const value_1 = '255044462d312e330a25e2e3cfd30a0a0a312030206f626a0a3c3c2f57696474682032203020522f4865696768742033203020522f547970652034203020522f537562747970652035203020522f46696c7465722036203020522f436f6c6f7253706163652037203020522f4c656e6774682038203020522f42697473506572436f6d706f6e656e7420383e3e0a73747265616d0affd8fffe00245348412d3120697320646561642121212121852fec092339759c39b1a1c63c4c97e1fffe017f46dc93a6b67e013b029aaa1db2560b45ca67d688c7f84b8c4c791fe02b3df614f86db1690901c56b45c1530afedfb76038e972722fe7ad728f0e4904e046c230570fe9d41398abe12ef5bc942be33542a4802d98b5d70f2a332ec37fac3514e74ddc0f2cc1a874cd0c78305a21566461309789606bd0bf3f98cda8044629a1'
const value_2 = '255044462d312e330a25e2e3cfd30a0a0a312030206f626a0a3c3c2f57696474682032203020522f4865696768742033203020522f547970652034203020522f537562747970652035203020522f46696c7465722036203020522f436f6c6f7253706163652037203020522f4c656e6774682038203020522f42697473506572436f6d706f6e656e7420383e3e0a73747265616d0affd8fffe00245348412d3120697320646561642121212121852fec092339759c39b1a1c63c4c97e1fffe017346dc9166b67e118f029ab621b2560ff9ca67cca8c7f85ba84c79030c2b3de218f86db3a90901d5df45c14f26fedfb3dc38e96ac22fe7bd728f0e45bce046d23c570feb141398bb552ef5a0a82be331fea48037b8b5d71f0e332edf93ac3500eb4ddc0decc1a864790c782c76215660dd309791d06bd0af3f98cda4bc4629b1'

Finalize the PSBT.

const getFinalScripts = (inputIndex, input, script) => {
  // Step 1: Check to make sure the meaningful locking script matches what you expect.
  const decompiled = bitcoin.script.decompile(script)
  if (!decompiled || decompiled[0] !== bitcoin.opcodes.OP_2DUP) {
    throw new Error(`Can not finalize input #${inputIndex}`)
  }

  // Step 2: Create final scripts
  const payment = bitcoin.payments.p2sh({
    redeem: {
      output: script,
      input: bitcoin.script.compile([
        Buffer.from(value_1, 'hex'),
        Buffer.from(value_2, 'hex'),
      ]), (1)
    },
  })

  return {
    finalScriptSig: payment.input
  }
}

psbt.finalizeInput(0, getFinalScripts)

1	The two pre-images values preceded by `4d4001`. `4d` is the OP_PUSHDATA2 opcode, which states that the next two bytes contain the number of bytes to be pushed onto the stack in little endian order. `0140` is 320 in decimal, which is the length of the values.

We don’t need to sign this transaction since the redeem script doesn’t ask for a signature.

Extract the transaction and get the raw hex serialization.

console.log('Transaction hexadecimal:')
console.log(psbt.extractTransaction().toHex())

Inspect the raw transaction with Bitcoin Core CLI, check that everything is correct.

decoderawtransaction TX_HEX

Broadcasting the transaction

It’s time to broadcast the transaction via Bitcoin Core CLI.

sendrawtransaction TX_HEX

Inspect the transaction.

getrawtransaction TX_ID true

Observations

Check the hash collision

bitcoin.crypto.sha1(Buffer.from(value_1, 'hex')).toString('hex')
bitcoin.crypto.sha1(Buffer.from(value_2, 'hex')).toString('hex')

Both returns the same hash, f92d74e3874587aaf443d1db961d4e26dde13e9c.

Peter Todd’s other bounties (SHA256, RIPEMD160, RIPEMD160-SHA256, SHA256-SHA256) remain unclaimed at the time of this writing. They’re all written in the same manner as this SHA-1 tutorial.

« Algebra Puzzle - Nested Segwit P2SH-P2WSH Multi-signatures »