原始文献 / 论坛帖 / Re: Stealing Coins
Re: Stealing Coins
Bitcointalk · 2010-07-25 20:48:01 UTC
引用
有一篇论文声称用 2^52 次密码学运算找到了 SHA-1 碰撞。而最优安全哈希需要 2^80 次运算。2^52 的时间还是很大，但已经进入集群和僵尸网络的范围了。
2^80 是你能用生日攻击的情况。这里不能用生日攻击，所以难度是完整的 2^160 位。不过，如果你要破解 100 万（2^20）笔交易中的任意一笔，可以做部分生日攻击 2^160/2^20 = 2^140。
比特币地址是唯一用 160 位哈希的地方。其他地方都是 SHA-256。它们的计算方式是：
bitcoinaddress = RIPEMD-160(SHA-256(publickey))
如果我说错了请纠正我（我很乐意认错），但我觉得在这种情况下很难对 RIPEMD-160 用解析攻击。解析攻击规定了某一范围或模式的输入去尝试，会大大增加你找到碰撞的几率。但在这里，你对 RIPEMD-160 的输入没有那种控制权，因为它的输入是 SHA-256 的输出。如果解析攻击帮你找到了一个能让 RIPEMD-160 产生碰撞的输入，你打算拿它怎么办？你还是得让 SHA-256 输出那个值，所以你还是得把 SHA-256 也攻破。
对暴力破解来说，RIPEMD-160(SHA-256(x)) 并不比单独的 RIPEMD-160 更强。但对解析攻击来说，似乎你必须同时解析攻击 RIPEMD-160 和 SHA-256。如果我错了，那强度就和 RIPEMD-160 一样，SHA-256 只起到一轮密钥强化的作用。
英文原文
Quote
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.