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

<p>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.</p>

<blockquote>
  <p>If an attacker can generate an alternative redemption script that happens to hash to the value given in a P2SH output</p>
</blockquote>

<p>That is called a preimage search, not a collision search.</p>

<ul>
<li>Preimage search: given a hash H, find X such that Hash(X) = H.</li>
<li>Collision search: find an X and a Y, such that X != Y and Hash(X) = Hash(Y).</li>
</ul>

<p>A preimage search for a 160-bit hash function needs 2<sup>160</sup> steps. A collision search however only needs 2<sup>80</sup> steps.</p>

<blockquote>
  <p>Am I misreading the document or misunderstanding the nature of the birthday attack?</p>
</blockquote>

<p>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.</p>

<p><strong>Example</strong></p>

<p>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.</p>

<p>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.</p>

<p>Instead of just giving you the key B, I generate a huge list of 2<sup>80</sup> public keys, all of which I know the private key for.</p>

<p>For each of those keys K, I compute:</p>

<ul>
<li><em>Hash160(A-and-K)</em></li>
<li><em>Hash160(B-and-K)</em></li>
</ul>

<p>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<sup>80</sup> entries in each list, there are 2<sup>160</sup> combinations of entries. Each of those has a 2<sup>-160</sup> chance to be a collision. This is also the explanation of the <a href="https://en.wikipedia.org/wiki/Birthday_problem" rel="noreferrer">Birthday Paradox</a>, and such an attack is therefore called a birthday attack.</p>

<p>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, <em>Hash160(A-and-K1) = Hash160(B-and-K2)</em>.</p>

<p>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 <em>A-and-K1</em>. We construct the address <em>Hash160(A-and-K1)</em>, which I already know is identical to <em>Hash160(B-and-K2)</em>.</p>

<p>We hand out that P2SH address, and the payer sends money to that hash's address.</p>

<p>Once funds have been sent there, I can spend them without your cooperation.</p>

<p>The requirements for spending a P2SH outputs are:</p>

<ul>
<li>(1) a redeemscript whose hash equals the Hash160 in the P2SH address</li>
<li>(2) inputs to that redeemscript that make it evaluate to true.</li>
</ul>

<p>For (1) I can use the <em>B-and-K2</em> script, and for (2) I can simply sign with both B and K2, both of which I have the private keys for.</p>

<p><strong>Making it practical</strong></p>

<p>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, <a href="https://en.wikipedia.org/wiki/Cycle_detection" rel="noreferrer">cycle-detection algorithms</a> can be used to find a K1 and K2 such that <em>Hash160(A-and-K1) = Hash160(B-and-K2)</em> in 2<sup>80</sup> steps without ever fully storing or sorting the lists L1 and L2.</p>

<p><strong>Generalizing</strong></p>

<p>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.</p>

<p><strong>Mitigation</strong></p>

<p>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<sup>128</sup> steps rather than 2<sup>80</sup>. 2<sup>128</sup> 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.</p>

<p><strong>Why is this not an issue for single-key addresses?</strong></p>

<p>In the case where no input from the attacker goes into the creation of the address being stolen from, this attack doesn't work.</p>

<p>All the attacker has in this case is an address. He can't insert variance into it to produce 2<sup>160</sup> combinations out of 2<sup>80</sup> attempts. The only thing that works here is a preimage attack, which needs 2<sup>160</sup> iterations for a 160-bit hash.</p>

CC BY-SA 3.0
2017-06-23T18:39:35.753Z
2018-02-05T01:18:06.750Z
2018-02-05T01:18:06.750Z
Pieter Wuille
<blockquote>
  <p>Why does this document seem to imply that the birthday attack only works for multisig P2SH</p>
</blockquote>

<p>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.</p>

<blockquote>
  <p>and then only for one of the signers?</p>
</blockquote>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2017-06-23T17:45:55.860Z
The birthday attack requires that the attacker and the victim are both involved in the construction of the script. So while it does not only apply to multisig, but it does require multiple parties to be involved in the construction of a single script (which in practice means multisig). It does not apply to single-key P2SH.
Pieter Wuille
CC BY-SA 3.0
2017-06-23T17:50:49.493Z
How so? Couldn't one party create a script which collides with any hash160 for a P2SH output?
Ava Chow
CC BY-SA 3.0
2017-06-23T17:52:32.233Z
That's a preimage search, not a collision search, and needs 2^160 of work. The 2^80 birthday attack only applies to collision search (find two scripts that hash to the same thing), not to a preimage search (find a script that hashes to a given hash).
Pieter Wuille
CC BY-SA 3.0
2017-06-23T18:01:36.280Z
Ah, yes. I always seem to get those two confused :)
Ava Chow
CC BY-SA 3.0
2017-06-23T17:41:59.567Z
2017-06-23T18:03:18.567Z
2017-06-23T18:03:18.567Z
Ava Chow
<p>The <a href="https://bitcoincore.org/en/2016/01/26/segwit-benefits/#increased-security-for-multisig-via-pay-to-script-hash-p2sh" rel="noreferrer">Segwit Benefits</a> document has this to say about P2SH security for base transactions:</p>

<blockquote>
  <p>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)</p>
</blockquote>

<p>It then goes on to state:</p>

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

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

<p>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.</p>

<p>Am I misreading the document or misunderstanding the nature of the birthday attack?</p>

<segregated-witness><p2sh><attack>
Birthday attack on P2SH
Rich Apodaca
# Birthday attack on P2SH

(Asked by: username_0 on 2017-06-23)

The [Segwit Benefits](https://bitcoincore.org/en/2016/01/26/segwit-benefits/#increased-security-for-multisig-via-pay-to-script-hash-p2sh) 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?

**Tags:** segregated-witness, p2sh, attack


---

## 2 answers

### Answer by username_1 on 2017-06-23. Score: 13

> 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](https://en.wikipedia.org/wiki/Birthday_problem), 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](https://en.wikipedia.org/wiki/Cycle_detection) 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.


---

### Answer by username_2 on 2017-06-23. Score: 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 username_1 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.

> **Comments:**
> **username_1**: The birthday attack requires that the attacker and the victim are both involved in the construction of the script. So while it does not only apply to multisig, but it does require multiple parties to be involved in the construction of a single script (which in practice means multisig). It does not apply to single-key P2SH.  
> **username_2**: How so? Couldn't one party create a script which collides with any hash160 for a P2SH output?  
> **username_1**: That's a preimage search, not a collision search, and needs 2^160 of work. The 2^80 birthday attack only applies to collision search (find two scripts that hash to the same thing), not to a preimage search (find a script that hashes to a given hash).  
> **username_2**: Ah, yes. I always seem to get those two confused :)  

---

