Post
Topic
Board Development & Technical Discussion
Re: O(2^80) theoretical attack on P2SH
by
gmaxwell
on 02/11/2013, 16:12:36 UTC
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.