查看原文
其他

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

刘教链 刘教链 2023-01-30

(生日攻击。图片来源于网络)
前情回顾:
比特币史话·86 | 压缩(4): 布隆过滤器
比特币史话·87 | 随机(1): 真伪随机数
比特币史话·88 | 随机(2): 脑钱包
比特币史话·89 | 随机(3): 破解索尼
比特币史话·90 | 随机(4): 香农熵

正文:

对比特币地址的攻击就是剑指其背后的资产控制权——私钥。在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仅用作一轮密钥加固。”

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

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存