Re: Stealing Coins


2010-07-25 20:48:01 UTC - Original Post
Here is a paper that claims to find SHA-1 collisions in 2^52 crypto operations. And optimally secure hash would take 2^80 operations. 2^52 time is still large, but it is getting into cluster and botnet range.
2^80 is if you can use a birthday attack.  You can't use a birthday attack for this, so the difficulty is the full 2^160 bits.  Although, if you were trying to crack any one of 1 million (2^20) transactions, you could do a partial birthday attack 2^160/2^20 = 2^140.

Bitcoin Addresses are the only place where 160-bit hash is used.  Everything else is SHA-256.  They're calculated as:

bitcoinaddress = RIPEMD-160(SHA-256(publickey))

Correct me if I'm wrong (please, and I'll gladly eat crow) but I think it would be hard to use an analytical attack on RIPEMD-160 in this case.  An analytical attack prescribes a certain range or pattern of inputs to try that will greatly increase your chance of finding a collision.  Here, you don't have that kind of control over RIPEMD-160's input, because the input is the output of SHA-256.  If an analytical attack helps you find an input to RIPEMD-160 that produces a collision, what are you going to do with it?  You still have to get SHA-256 to output that value, so you would still have to break SHA-256 too.

For brute force, RIPEMD-160(SHA-256(x)) is no stronger than RIPEMD-160 alone.  But for analytical attack, it seems like you must analytical attack both RIPEMD-160 and SHA-256.  If I'm wrong, then the strength is the same as RIPEMD-160 and the SHA-256 only serves as one round of key strengthening.