Birthday attack on P2SH

Question

The Segwit Benefits document has this to say about P2SH security for base transactions:

Multisig payments currently use P2SH which is secured by the 160-bit HASH160 algorithm (RIPEMD of SHA256). However, if one of the signers wishes to steal all the funds, they can find a collision between a valid address as part of a multisig script and a script that simply pays them all the funds with only 80-bits (280) worth of work, which is already within the realm of possibility for an extremely well-resourced attacker. (For comparison, at a sustained 1 exahash/second, the Bitcoin mining network does 80-bits worth of work every two weeks)

It then goes on to state:

Segwit resolves this by using HASH160 only for payments direct to a single public key (where this sort of attack is useless) ... [my emphasis]

Why does this document seem to imply that the birthday attack only works for multisig P2SH and then only for one of the signers?

It seems this attack works for anybody who sees the P2SH output on the block chain and decides to start hashing. If an attacker can generate an alternative redemption script that happens to hash to the value given in a P2SH output, s/he can make the redemption script do anything.

Am I misreading the document or misunderstanding the nature of the birthday attack?

Answer 1

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 2¹⁶⁰ steps. A collision search however only needs 2⁸⁰ 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 2⁸⁰ 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 2⁸⁰ entries in each list, there are 2¹⁶⁰ 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 2⁸⁰ 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 2¹²⁸ steps rather than 2⁸⁰. 2¹²⁸ 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 2¹⁶⁰ combinations out of 2⁸⁰ attempts. The only thing that works here is a preimage attack, which needs 2¹⁶⁰ iterations for a 160-bit hash.

Answer 2

Why does this document seem to imply that the birthday attack only works for multisig P2SH

It does not just apply to multisig, but to any P2SH output. The reason the attack does not apply to P2PKH and P2WPKH outputs is that those have a built-in signature checking operation in the output script itself. This means that the data that is hashed to compare to the hash specified in the output will be treated as a public key and the data before it will be treated as a signature. Thus you would need to find a private key which has a public key that hashes to the hash160, and that is far more difficult to do than just generating a colliding hash160.

and then only for one of the signers?

You are misreading this. The page uses that as an example since most people are most familiar with P2SH as being multisig and not just scripts. This attack is a problem for all P2SH outputs.

Edit: As Pieter mentions below, the birthday attack is only applicable when multiple parties are involved. This is because the attacker and his victim(s) must be involved in the creation of one script, the legitimate script.