比特币史话·91 | 随机(5): 生日攻击

(生日攻击。图片来源于网络)

前情回顾：

正文：

对比特币地址的攻击就是剑指其背后的资产控制权——私钥。在2010年7月25日中本聪在论坛中参与主题为“盗币”的讨论[1]时指出，比特币地址所采用的是160比特的哈希：

“比特币地址是唯一使用160位哈希的地方。其他一切都是SHA-256。计算公式为：”

“比特币地址 = RIPEMD-160(SHA-256(公钥))”

中本聪剖析了两种攻击方法。一种是碰撞攻击，另一种是分析攻击。前者是暴力破解，后者则是尝试找到哈希算法的弱点予以击破。

对于哈希函数的碰撞攻击，有一种称之为“生日攻击”(birthday attack)[2]的方法可以惊人地提高效率。能提高多少呢？对160比特的哈希进行生日攻击所需尝试的次数不是2的160次方(记为2^160)，而是2的80次方(记为2^80)，效率足足提高了2的80次方倍之多(2^80 * 2^80 = 2^160)。也因此哈希函数最低的安全位数不能低于160位，比特币所采用的RIPEMD-160是已知安全的哈希函数中最短的，也是最短的哈希函数里已知最安全的。在确保安全的前提下，长度短可以方便记录和沟通。

生日攻击所产生的与直觉有一点点相悖的原因在于组合爆炸。我们每个人的生日随机地分布在一年365天的某一天。请问一个有23位同学的班级里，有至少两人生日相同的概率是多少？答案是令人略感吃惊的50%概率，也就是有超过一半的可能性会有同学在同一天过生日。如果班级人数增加到50人，这个概率会上升到97%。

把生日看作是把每个人作为输入的、有365个输出值的哈希函数。发现哈希碰撞所需的计算次数并非正比于值空间大小，而是值空间大小的平方根。据说，量子计算机可以把这个效率进一步提高到值空间大小的立方根。只是由于实用化量子计算机迟迟没有问世，所以关于这一点，学界也有争议。

但是在攻击比特币地址背后的私钥这件事上，生日攻击的方法是不可用的，因为私钥是用户随机选取的，攻击者并不能自由选择私钥。正如中本聪在上述论坛帖子中所指出的那样，“如果可以使用生日攻击，则为2^80。你不能为此使用生日攻击，因此难度是完整的2^160比特。虽然，如果你尝试破解100万(2^20)个交易中的任何一个，则可以进行部分生日攻击 2^160/2^20 = 2^140。”

关于分析攻击，中本聪又写道，“如果我说错了，请纠正我(我会很高兴收回我说过的话)，但在这种情况下，我认为很难对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仅用作一轮密钥加固。”

【未完待续】(公众号：刘教链)