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.
First note that, since Mastering Bitcoin was first published, Bitcoin has activated SegWit (BIP-141) 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) with P2SH32 (using sha256d, source). 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):
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:
- Collision attack: generate a colliding contract (redeem script) pair;
- 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;
- 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) 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):
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.