O(2^80) theoretical attack on P2SH

[adam3us]

Unless I am misunderstanding something about the seralization, with pay to script hash, you create an address which is the hash of the script, and to claim you have to provide the script and the inputs to make it execute to true.

A recurring pattern in cross-chain atomic swaps (litecoin for bitcoin) and atomic colored coin swaps, or fair-coin-toss / fair-roulette, CoinSwap etc like is use of "SIG(A) and SIG(B) and y=H(x)" where one party with-holds x and the other party builds a related transaction that he can see will become payable as a consequence of the counter-party spending the first transaction because both transactions rely on knowing x.

One example is (to see what I mean about the two stage, this protocol was by iddo and optimized by myself, I think the y=H(x) idiom is used in multiple earlier protocols also):

https://bitcointalk.org/index.php?topic=277048.msg3220019#msg3220019

The problem is hash output approach is only secure up to the birthday attack which is a generic brute-force O(2^80) attack, not bitcoins O(2^128) design target.

Lets call the bitcoin address-hash AH(z) = RIPEMD160(SHA256(Q)) where Q is a public key or more generally a bitcoin script.

This is because I can use the birthday attack to search for strings s="SIG(A) and y=H(x)" and s'="SIG(B)" such that AH(s)==AH(s').  That can be done in work O(2^80) (and massive storage), or various time memory tradeoffs with lower storage and more work.

Sounds expensive but bitcoin right now is doing O(2^62) every 10 minutes or about O(2^78) per year.  Maybe in a few years bitcoin will be doing O(2^80) every 10 minutes and 14nm ultra-dense energy efficient ASIC miners will fill racks of data-centers.

Also worth thinking about that there are O(2^64) birthday attacks on SHA1, and no one has probably tried to find analogous attacks on RIPEMD160 but that is not proof that RIPEMD160 is immune.   But note the SHA1 birthday attacks need multi-hash-block inputs, and the inner SHA256 output fits in one SHA1 input block; and SHA1 birthday attacks work by choosing and steering bits; SHA256 output is one-block and random and frustrates that.   Realistically given the constraints therefore even SHA1(SHA256(z)) for this purpose probably retains O(2^80) birthday strength.  Designing hashes immune to that class of multi-block steering attacks is what the SHA3 NIST competition is about...

Adam

[grau]

  That can be done in work O(2^80) (and massive storage), or various time memory tradeoffs with lower storage and more work.

While work might become feasible, a successful attack on P2SH needs more than a collision: an alternate script valid and redeemable by the attacker.

[Undecidable]

 That can be done in work O(2^80) (and massive storage), or various time memory tradeoffs with lower storage and more work.

While work might become feasible, a successful attack on P2SH needs more than a collision: an alternate script valid and redeemable by the attacker.

The attacker uses a 1-of-N multisig redeemScript where the first public key is legitimately his and the other keys (up to 130 bytes) are what he keeps twiddling until he finds a collision.

[grau]

 That can be done in work O(2^80) (and massive storage), or various time memory tradeoffs with lower storage and more work.

While work might become feasible, a successful attack on P2SH needs more than a collision: an alternate script valid and redeemable by the attacker.

The attacker uses a 1-of-N multisig redeemScript where the first public key is legitimately his and the other keys (up to 130 bytes) are what he keeps twiddling until he finds a collision.

How is this easier than mining private keys that lead to public key hash (aka. an address) of pay to address transaction?

[gmaxwell]

How is this easier than mining private keys that lead to public key hash (aka. an address) of pay to address transaction?

Because it's a collision not a second-preimage.  You don't need to find some H(Y_2) = X for some specified X.  You need to find Y_1, Y_2 such that H(Y_1) == H(Y_2) and thats fundamentally easier. E.g. 2^80 work instead of 2^160 work, if you have unlimited memory with zero access cost (otherwise you end up with some small constant more work than 2^80 in order to make your memory use more efficient).

I think Adam overstates this a bit, as you note the collision is constrained. In most protocols you can avoid this being an issue by not letting the other party (e.g. the one you'd count on revealing the preimage to your hashlock) pick the P2SH address. E.g. have them specify their inputs, and then you specify some inputs into that script. For the coinswap stuff you probably wouldn't use P2SH for the actual hashlocked parts (which normally should never get transmitted).

It was also discussed on IRC that you could make your p2sh addresses expensive to generate, e.g. using a vanity P2SH, to make collision searches more costly.

[grau]

I see, I missed that this works if the attacker can choose the original script.

[adam3us]

The problem is hash output approach is only secure up to the birthday attack which is a generic brute-force O(2^80) attack, not bitcoins O(2^128) design target.

Lets call the bitcoin address-hash AH(z) = RIPEMD160(SHA256(Q)) where Q is a public key or more generally a bitcoin script.

This is because I can use the birthday attack to search for strings s="SIG(A) and y=H(x)" and s'="SIG(B)" such that AH(s)==AH(s').  That can be done in work O(2^80) (and massive storage), or various time memory tradeoffs with lower storage and more work.

One work-around is to use scripts directly serialised into the transaction rather than script hash, however that impacts UTXO size, P2SH is good because only the script hash goes on the blockchain which is typically smaller than the script itself.  Note script addresses are intentionally incompatible (different version) with regular addresses, so its not possible to find AH(Q)==AH(script) where Q is a public key and script is a script.

Probably the most generic approach is to increase the script hash address to 256-bit hash eg define new AH'(z) = SHA256( SHA256( z ) ).

Alternatively work-arounds or security can be achieved by considering the size of the attack O(2^80) + TMTO is large even relating to a bitcoin hashrate.  Users of hashlock as a protocol sub-step should avoid creating pre-computation attacks.  Eg accept hashlocks only on strings they had input in shortly-before (few hours/days which might be needed for confirmation) or during the protocol.

Adam

ps thanks to sipa and gmaxwell for discussion on IRC about this topic, clarifying assumptions for me.