<p>First note that, since Mastering Bitcoin was first published, Bitcoin has activated SegWit (<a href="https://en.bitcoin.it/wiki/BIP_0141" rel="nofollow noreferrer">BIP-141</a>) and multi-party users now have the possibility of using P2WSH to lock up their funds, which is secure against collision search because it uses a 256-bit hash (sha256) which has 128-bits of security against birthday attack.
Even the forked version (Bitcoin Cash) eventually ('23) solved the problem by extending the P2SH feature (<a href="https://en.bitcoin.it/wiki/BIP_0016" rel="nofollow noreferrer">BIP-16</a>) with P2SH32 (using sha256d, <a href="https://upgradespecs.bitcoincashnode.org/2023-05-15-upgrade/" rel="nofollow noreferrer">source</a>).
Newer blockchains mostly had 256-bit addresses from the get-go, and now this collision problem only persists in some old forks of Bitcoin's codebase (e.g. Dogecoin).</p>
<p>Why was it a problem that needed solving? Here's a brief explanation / example (<a href="https://gitlab.com/bitcoin-cash-node/announcements/-/blob/master/2022-06-09_bitcoin_cash_pay_to_script_hash_p2sh_past_present_and_future_EN.md#322-plausibility-of-a-collision-attack" rel="nofollow noreferrer">source</a>):</p>
<blockquote>
<p>The problem arises when users are asked to pay into an address where
someone else had control over address generation, such as P2SH
multi-party multisig addresses and public-facing covenants.
Feasibility of a collision attack makes it usable as part of a con
executed in 3 stages:</p>
<ol>
<li>Collision attack: generate a colliding contract (redeem script) pair;</li>
<li>Social hacking set-up: release the address and only one of the two colliding contracts to some other party or parties and convince them
to pay funds into the contract address;</li>
<li>Rug-pull: when the address has accumulated enough funds to pay for step 1 and have some profit, steal the funds from the address by using
the other, secret, contract.</li>
</ol>
<p>For the con to work, the contract revealed to other parties must look
innocent while also having a variable part suitable for manipulation
by the attacker, one that can encode a whole 160-bit hash in order to
make use of the constant-memory method by finding cycles. This does
not just mean a continuous 160-bit block, it is much more broad - it
means any degree of freedom which would let the attacker feed 160 bits
of entropy of his choice into the final address. The other message can
be anything that will allow only the attacker to spend from it.</p>
</blockquote>
<p>Note that, while it is feasible to birthday attack a 160-bit hash collision, it is still not cheap to do it. Ripemd160 ASICs don't exist yet (P2SH <code>hash160</code> is <code>ripemd160(sha256(x))</code>), however the Ripemd hash function has similar construction (<a href="https://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_construction" rel="nofollow noreferrer">Merkle-Damgard</a>) as sha256 so R&amp;D may not need to have large capex cost. If we assume efficiency to match sha256d we could estimate cost of individual collision search based on Bitcoin's hashrate and value of block reward.</p>
<p>Collision search would need 2^80 attempts (about 1M exahashes). Bitcoin network as a whole now (November 2024) does 790 exahashes/s meaning it now does 2^80 hashes every 21 minutes!
Assuming hash160 ASICs of equal efficiency, the cost of a single collision search would be about 2 block rewards, or about 470,000 USD per collision search.</p>
<p>The attacker would need a target of high enough value for the attack to be worth it. How could he set it up? Here's a hypothetical long con (<a href="https://gitlab.com/bitcoin-cash-node/announcements/-/blob/master/2022-06-09_bitcoin_cash_pay_to_script_hash_p2sh_past_present_and_future_EN.md#example-attack" rel="nofollow noreferrer">source</a>):</p>
<blockquote>
<h5>Example Attack</h5>
<p>To better illustrate the attack, consider an adversary that creates a
custody service which sets up 2-of-3 P2SH multisig addresses for their
users. Any user of such service would control two keys, and the
custodian (attacker) would control one. Note that there exist
legitimate services that work just as described, enabling users to
hold one of their two keys in cold storage and rely on the service to
produce 2-of-3 signatures.</p>
<p>For the attack to be possible, user interface of the rogue service
would have to first ask the user for their 2 public keys, and the
adversary would add its key last to generate the multisig address, and
then reveal their 3rd key to the user so the user could verify
correctness of the contract. The user would likely think it is safe,
because it would be the familiar multisig contract (redeem script)
template which, if evaluated on its own, indeed works as advertised:</p>
<ul>
<li>Redeem script: <code>OP_2 &lt;attacker's 33-byte pubkey&gt; &lt;user's 33-byte pubkey 1&gt; &lt;user's 33-byte pubkey 0&gt; OP_3 OP_CHECKMULTISIG</code>;</li>
<li>Locking script: <code>OP_HASH160 &lt;hash160(redeem_script)&gt; OP_EQUAL</code>.</li>
</ul>
<p>Such an output could then be spent from using an input of the
following form:</p>
<ul>
<li>Unlocking script: <code>OP_0 &lt;user's signature&gt; &lt;user's other signature or attacker's signature&gt; &lt;redeem_script&gt;</code></li>
</ul>
<p>In our con scenario, when setting up the multisig address the attacker
would have generated a <code>redeem_script_steal</code>, one that would hash to
the exact same address and allow him to spend from the address by
executing an entirely different script like:</p>
<ul>
<li>Redeem script: <code>&lt;20-bytes&gt; OP_DROP OP_DUP OP_HASH160 OP_EQUALVERIFY OP_CHECKSIG</code>.</li>
</ul>
<p>The script would be kept secret until stage 3. of the attack, the
rug-pull. In the innocent-looking multisig script, his key would not
really be a key, he would be using it as a variable part in his
collision search. If the attacker expects users to call on the service
to actually use the key from the innocent-looking script, then it
would make stage 1. somewhat more expensive but still feasible.</p>
<p>The service could be operating legitimately for a long time, waiting
for the right target or a set of targets. The attacker would not need
to perform step 1. for all users, that would have an uncertain
return-on-investment. He would first need to attract enough users and
identify high-value targets, ones where they have enough funds to make
a collision search worthwhile. The attacker could then ask his targets
to move their funds into a new contract that would have the same 2
user keys, and the attacker could plausibly say he has to update his
key for some internal security upgrade.</p>
<p>He would wait for his targets to move the funds, and then steal them
all in one go and disappear.</p>
<p>There is a simple way users could protect themselves in this scenario:
insist on having the last say in address generation. The service would
have to provide their public key first, and the user would then
generate two brand new keys for himself and use those to finalize the
P2SH multisig address. The user would then be the one with the freedom
to generate a collision, but in this scenario he is already the owner
of the address so neither himself nor the service would be exposed.</p>
</blockquote>

CC BY-SA 4.0
2024-11-08T11:23:44.913Z
2024-11-08T11:23:44.913Z
bca-0353f40e
<p>Book &quot;mastering bitcoin&quot; 3rd edition, on page 73, there is a statement as following:
&quot;but there are organizations that expect to receive billions of dollars in bitcoins to
addresses generated by processes involving multiple parties, which could make the
attack profitable.&quot;</p>
<p>anybody can take an example to explain it? thanks.</p>

CC BY-SA 4.0
2024-03-14T04:11:37.503Z
Does this answer your question? [Birthday attack on P2SH](https://bitcoin.stackexchange.com/questions/54841/birthday-attack-on-p2sh)
Vojtěch Strnad
<p2sh><attack>
collision attack on bitcoin p2sh
fa william
# collision attack on bitcoin p2sh

(Asked by: username_0 on 2024-03-14)

Book "mastering bitcoin" 3rd edition, on page 73, there is a statement as following:
"but there are organizations that expect to receive billions of dollars in bitcoins to
addresses generated by processes involving multiple parties, which could make the
attack profitable."

anybody can take an example to explain it? thanks.

**Tags:** p2sh, attack

> **Comments:**
> **username_1**: Does this answer your question? [Birthday attack on P2SH](https://bitcoin.stackexchange.com/questions/54841/birthday-attack-on-p2sh)  

---

## 1 answers

### Answer by username_2 on 2024-11-08. Score: 0

First note that, since Mastering Bitcoin was first published, Bitcoin has activated SegWit ([BIP-141](https://en.bitcoin.it/wiki/BIP_0141)) and multi-party users now have the possibility of using P2WSH to lock up their funds, which is secure against collision search because it uses a 256-bit hash (sha256) which has 128-bits of security against birthday attack.
Even the forked version (Bitcoin Cash) eventually ('23) solved the problem by extending the P2SH feature ([BIP-16](https://en.bitcoin.it/wiki/BIP_0016)) with P2SH32 (using sha256d, [source](https://upgradespecs.bitcoincashnode.org/2023-05-15-upgrade/)).
Newer blockchains mostly had 256-bit addresses from the get-go, and now this collision problem only persists in some old forks of Bitcoin's codebase (e.g. Dogecoin).

Why was it a problem that needed solving? Here's a brief explanation / example ([source](https://gitlab.com/bitcoin-cash-node/announcements/-/blob/master/2022-06-09_bitcoin_cash_pay_to_script_hash_p2sh_past_present_and_future_EN.md#322-plausibility-of-a-collision-attack)):

> The problem arises when users are asked to pay into an address where
> someone else had control over address generation, such as P2SH
> multi-party multisig addresses and public-facing covenants.
> Feasibility of a collision attack makes it usable as part of a con
> executed in 3 stages:
>
> 1. Collision attack: generate a colliding contract (redeem script) pair;
> 2. Social hacking set-up: release the address and only one of the two colliding contracts to some other party or parties and convince them
>    to pay funds into the contract address;
> 3. Rug-pull: when the address has accumulated enough funds to pay for step 1 and have some profit, steal the funds from the address by using
>    the other, secret, contract.
>
> For the con to work, the contract revealed to other parties must look
> innocent while also having a variable part suitable for manipulation
> by the attacker, one that can encode a whole 160-bit hash in order to
> make use of the constant-memory method by finding cycles. This does
> not just mean a continuous 160-bit block, it is much more broad - it
> means any degree of freedom which would let the attacker feed 160 bits
> of entropy of his choice into the final address. The other message can
> be anything that will allow only the attacker to spend from it.

Note that, while it is feasible to birthday attack a 160-bit hash collision, it is still not cheap to do it. Ripemd160 ASICs don't exist yet (P2SH `hash160` is `ripemd160(sha256(x))`), however the Ripemd hash function has similar construction ([Merkle-Damgard](https://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_construction)) as sha256 so R&D may not need to have large capex cost. If we assume efficiency to match sha256d we could estimate cost of individual collision search based on Bitcoin's hashrate and value of block reward.

Collision search would need 2^80 attempts (about 1M exahashes). Bitcoin network as a whole now (November 2024) does 790 exahashes/s meaning it now does 2^80 hashes every 21 minutes!
Assuming hash160 ASICs of equal efficiency, the cost of a single collision search would be about 2 block rewards, or about 470,000 USD per collision search.

The attacker would need a target of high enough value for the attack to be worth it. How could he set it up? Here's a hypothetical long con ([source](https://gitlab.com/bitcoin-cash-node/announcements/-/blob/master/2022-06-09_bitcoin_cash_pay_to_script_hash_p2sh_past_present_and_future_EN.md#example-attack)):

> ##### Example Attack
>
> To better illustrate the attack, consider an adversary that creates a
> custody service which sets up 2-of-3 P2SH multisig addresses for their
> users. Any user of such service would control two keys, and the
> custodian (attacker) would control one. Note that there exist
> legitimate services that work just as described, enabling users to
> hold one of their two keys in cold storage and rely on the service to
> produce 2-of-3 signatures.
>
> For the attack to be possible, user interface of the rogue service
> would have to first ask the user for their 2 public keys, and the
> adversary would add its key last to generate the multisig address, and
> then reveal their 3rd key to the user so the user could verify
> correctness of the contract. The user would likely think it is safe,
> because it would be the familiar multisig contract (redeem script)
> template which, if evaluated on its own, indeed works as advertised:
>
> * Redeem script: `OP_2 <attacker's 33-byte pubkey> <user's 33-byte pubkey 1> <user's 33-byte pubkey 0> OP_3 OP_CHECKMULTISIG`;
> * Locking script: `OP_HASH160 <hash160(redeem_script)> OP_EQUAL`.
>
> Such an output could then be spent from using an input of the
> following form:
>
> * Unlocking script: `OP_0 <user's signature> <user's other signature or attacker's signature> <redeem_script>`
>
> In our con scenario, when setting up the multisig address the attacker
> would have generated a `redeem_script_steal`, one that would hash to
> the exact same address and allow him to spend from the address by
> executing an entirely different script like:
>
> * Redeem script: `<20-bytes> OP_DROP OP_DUP OP_HASH160 OP_EQUALVERIFY OP_CHECKSIG`.
>
> The script would be kept secret until stage 3. of the attack, the
> rug-pull. In the innocent-looking multisig script, his key would not
> really be a key, he would be using it as a variable part in his
> collision search. If the attacker expects users to call on the service
> to actually use the key from the innocent-looking script, then it
> would make stage 1. somewhat more expensive but still feasible.
>
> The service could be operating legitimately for a long time, waiting
> for the right target or a set of targets. The attacker would not need
> to perform step 1. for all users, that would have an uncertain
> return-on-investment. He would first need to attract enough users and
> identify high-value targets, ones where they have enough funds to make
> a collision search worthwhile. The attacker could then ask his targets
> to move their funds into a new contract that would have the same 2
> user keys, and the attacker could plausibly say he has to update his
> key for some internal security upgrade.
>
> He would wait for his targets to move the funds, and then steal them
> all in one go and disappear.
>
> There is a simple way users could protect themselves in this scenario:
> insist on having the last say in address generation. The service would
> have to provide their public key first, and the user would then
> generate two brand new keys for himself and use those to finalize the
> P2SH multisig address. The user would then be the one with the freedom
> to generate a collision, but in this scenario he is already the owner
> of the address so neither himself nor the service would be exposed.


---

