Why does this document seem to imply that the birthday attack only works for multisig P2SH and then only for one of the signers?
The birthday attack (to the best of my knowledge) requires that the P2SH address is constructed from a script which involves both a key of the victim and the attacker. That is typically only the case for multisig, but is not technically restricted to it. It does not apply to single-key scenarios.
If an attacker can generate an alternative redemption script that happens to hash to the value given in a P2SH output
That is called a preimage search, not a collision search.
- Preimage search: given a hash H, find X such that Hash(X) = H.
- Collision search: find an X and a Y, such that X != Y and Hash(X) = Hash(Y).
A preimage search for a 160-bit hash function needs 2160 steps. A collision search however only needs 280 steps.
Am I misreading the document or misunderstanding the nature of the birthday attack?
I believe you are. I'll start with explaining a simplified (infeasible) attack in a 2-of-2 multisig situation, and then optimize it and generalize.
Example
Say you (A) and me (B) are engaging in a 2-of-2 escrow. This means that someone (possibly one of us) is going to send money to a 2-of-2 multisig script, requiring that both of us agree before it can be spent.
In order to do so, we must first agree on what that script is going to be. You have revealed your public key A to me, and are waiting for me to respond with mine.
Instead of just giving you the key B, I generate a huge list of 280 public keys, all of which I know the private key for.
For each of those keys K, I compute:
- Hash160(A-and-K)
- Hash160(B-and-K)
I put all the A-and-K hashes in one list L1, and all of the B-and-K hashes in a list L2. I sort both lists. Then I go through both lists, and find a hash that exists in both in a single iteration. This is the critical point. It is likely that such a collision exists, because even though there are only 280 entries in each list, there are 2160 combinations of entries. Each of those has a 2-160 chance to be a collision. This is also the explanation of the Birthday Paradox, and such an attack is therefore called a birthday attack.
So, say I have found a hash that occurs in both lists. Say that K1 is the key that generated the hash in L1, and K2 is the key that generated the hash in L2. In other words, Hash160(A-and-K1) = Hash160(B-and-K2).
Now I just tell you that my key is K1. You cannot disprove that, as in fact, K1 is a completely valid key of mine. You happily accept that, and we both agree on using the script A-and-K1. We construct the address Hash160(A-and-K1), which I already know is identical to Hash160(B-and-K2).
We hand out that P2SH address, and the payer sends money to that hash's address.
Once funds have been sent there, I can spend them without your cooperation.
The requirements for spending a P2SH outputs are:
- (1) a redeemscript whose hash equals the Hash160 in the P2SH address
- (2) inputs to that redeemscript that make it evaluate to true.
For (1) I can use the B-and-K2 script, and for (2) I can simply sign with both B and K2, both of which I have the private keys for.
Making it practical
In practice, the above attack is not feasible, because the lists L1 and L2 are too large to store (much less sort them) for current day hardware. However, cycle-detection algorithms can be used to find a K1 and K2 such that Hash160(A-and-K1) = Hash160(B-and-K2) in 280 steps without ever fully storing or sorting the lists L1 and L2.
Generalizing
The attack can also be generalized for other scripts where multiple people are involved, as long as the attacker has an influence over the chosen script.
Mitigation
SegWit does no longer have a 160-bit script hash system. It still uses 160-bit hashes for the single key case (for efficiency reasons), as the birthday attack does not apply to them. Instead it introduces P2WSH, which uses 256-bit script hashes. The birthday attack still applies there, but requires 2128 steps rather than 280. 2128 is considered infeasible to attack in the short to medium term. Furthermore, it is the security target for Bitcoin in general (including forging signatures), doing more is not very valuable.
Why is this not an issue for single-key addresses?
In the case where no input from the attacker goes into the creation of the address being stolen from, this attack doesn't work.
All the attacker has in this case is an address. He can't insert variance into it to produce 2160 combinations out of 280 attempts. The only thing that works here is a preimage attack, which needs 2160 iterations for a 160-bit hash.