关于基于内容寻址的加密哈希的代码猴子指南

以前的 123.4 第二页 下一个

单向函数计算起来相对容易，但是反转函数要困难得多。[…在这种情况下，“困难”的定义是这样的:从f(x)计算出x要花费数百万年的时间，即使世界上所有的计算机都被分配到这个问题上。[…这听起来不错，但其实是一派胡言。如果我们是严格的数学，我们没有证据证明单向函数存在，也没有任何真实的证据可以构造它们。

这并不意味着加密哈希函数或加密算法没有用处或不起作用，只是意味着它们的“单向性”不是函数的已证明的、不变的数学性质。

请注意，不要将加密哈希函数看作一个魔术盒，您可以将输入塞入其中，并始终得到完全惟一的固定大小的输出，即使您读到的是一种数学上听起来像这样描述它的定义。MD5不再具有这种特性，大多数专家预计SHA-1将在几年内失去这种特性。

哈希冲突

在最基本的级别上，加密哈希函数接受几乎任何大小的输入，并将其折叠为n位输出。输入远多于输出，所以输出相同的输入，哈希碰撞，是有保证的。使哈希函数成为加密哈希函数的原因是，以现有的知识和技术，人类很难发现碰撞。

“难”到底有多难?蛮力是一个很好的起点"生日攻击“ - 简单地选择输入随机，哈希他们，看他们是否发生碰撞这一速度比似乎直觉发现冲突如果有2个。^N可能的哈希值，直观的猜测是哈希值是输入的一半- 2^{N - 1}-会导致50%的几率发生碰撞。实际上，只有大约平方根需要的散列总数为- 2^{N / 2}-有50%的几率发生碰撞。举个具体的例子，SHA-1的输出有160位，对于2来说¹⁶⁰可能的散列值。生日袭击大约需要2分钟⁸⁰哈希计算有50%的机会发现碰撞。生日攻击是在密码学哈希函数中发现冲突的“难”程度的上限。对于一个好的加密哈希函数，没有比birthday攻击快得多的攻击。

对程序员来说，一个实际的影响是，被比较的输入数量应该比可能哈希值的平方根小得多。如果目标是哈希2^N如果输入的任意两个输出之间发生意外碰撞的概率可以忽略不计，那么哈希函数的输出至少需要有N*2位。这种错误并不是未知的。几年前，一个著名的网络公司的程序员自豪地向我解释他们的网页缓存是如何工作的。每个页面通过其内容的MD5散列进行寻址，该散列被截断为64位(为了方便地使用64位数据类型)。因为有两个⁶⁴可能的散列值和很多小于2的值⁶⁴他认为，在实际操作中，哈希不会发生冲突。我大概知道当时有多少网页，但为了确定，我问他数据库中有多少网页。答案是:大约40亿³²)页，或者可能的散列值的平方根。当程序员认为它可以忽略的时候，碰撞的几率实际上是50%左右。自那以后，网络发展壮大;如果缓存还没有发生过碰撞，那么几乎可以肯定的是，从那以后就发生了碰撞。

另一个直观的错误来自于认为碰撞的概率是1 in(天文数字的可能哈希值)，这是假设碰撞的机会是完全随机和独立的。我们在概率论课程中被训练成这样思考——仅仅因为最后5次掷出6并不会改变下一次掷出6的概率。但是加密哈希函数是确定性的——如果一个输入第一次哈希为6，那么下一次它也会哈希为6。当你想象发生了碰撞会发生什么的时候，这个错误就出现了——好吧，确实发生了碰撞，但它一开始就不太可能发生，而且它发生两次的几率更不可能。这不是真的;一旦发生冲突，总是该数据集的冲突(除非你能改变你的哈希函数)。

密码散列函数的生命周期

密码学哈希函数已经从最先进的发展到完全崩溃，因此密码学哈希函数生命周期中的一些一般趋势已经很清楚了，如下表所示。每个阶段需要几个月到几年的时间，绿色和黄色的阶段表示哈希函数可靠地抗碰撞(只要国安局不参与);在所有其他阶段，哈希函数很可能会发生碰撞。

更详细地说，加密哈希函数是作为初始提议开始的。在这一点上，几乎没有密码学家检查过它，它被认为是不可靠的;许多加密哈希函数在初期就被砍掉了，在它们被提出后不久就被另一个密码学家破解。随着越来越多的密码学家对密码学哈希函数进行审查和测试，发现其不足之处，早期采纳者开始在实践中使用它，并对其给予了更多的关注。如果hash能经受住随着越来越受欢迎而来的越来越严格的审查，它将会有一段成熟期和几年的信任期。然而，为加密哈希带来信心的流行程度，也促使研究人员致力于破解该函数。几年后，一个弱点被发现，使得攻击的复杂性比蛮力攻击低几个数量级。此时，没有实际的攻击存在，但专家们将其视为一个警告信号，表明更强的攻击即将来临，并开始建议远离以前原始的哈希函数。其中一个非同寻常的例子发生在1995年，当时美国国家安全局建议将SHA-0(当时称为plain SHA)改为稍加修改的SHA-1，但没有确切解释原因。(SHA-0在2004年被完全打破。) Around this time, non-experts scoff and compare the complexity of the attack to the number of atoms in the universe or some other impressive physical quantity.

在第一个理论上的弱点几年内，更强的弱点就会被发现，结果是稍微简化的哈希函数很容易受到攻击，攻击时间相当于在一台大型超级计算机上花费几个月的时间。在这一点上，专家建议立即停止使用这个散列，尽管还没有实际的攻击存在。非专家指出，用超级计算机工作几个月的时间是很难获得的，普通人没有什么可担心的。在发现一个强弱点的几个月或几年之内，一些雄心勃勃的研究人员发现了一种实际的方法，可以在相当无意义的随机输入之间产生碰撞。专家们宣布大杂烩真的碎了，开了几瓶香槟，拍了拍研究人员的肩膀。非专家指出，碰撞只能在随机数据中产生，而不是像契约或证书那样的数据，因此仍然没有什么可担心的。此后不久，攻击方面的改进允许一些无聊的程序员编写一个程序，在家用计算机上有意义的输入之间产生冲突，并将其作为开放源代码发布。专家们没有任何官方反应，因为他们忙于审查新的加密哈希函数。

流行密码散列的生命周期

这张图表显示了那些更为人熟知的哈希表的不同生命阶段。你可能会注意到2004年发生了很多变化;就在这一年，王晓云等发表了一篇论文，简单地说，哈希函数MD4、MD5、HAVAL-128和RIPEMD的冲突。(我听说MD5被破解了，一边吃着爆米花一边观看网络直播。)这篇论文中我最喜欢的一句话是:“我们的攻击(在MD4中)可以通过手工计算找到冲突。”这在加密哈希函数的生命周期中引入了另一个阶段:查找冲突甚至不需要袖珍计算器的阶段。

完整的加密哈希函数

目前，唯一被广泛推荐用于安全使用的散列是SHA-2家族，其中包括SHA-256和其他变体。其他大多数流行的密码散列都已被破坏或削弱。

一些不太受欢迎的算法还没有被打破，但通常这些算法不太受欢迎是有充分理由的。例如，有几种方法可以安全地将块密码转换为加密的哈希函数，例如Davies-Meyer技术。不幸的是，输出是块密码输出的大小，通常为64位，尽管存在将长度加倍到128位的修改。160位被认为是当前安全哈希输出长度的最低值，有些人建议为256位。将块密码转换为加密哈希函数和增加其输出长度的大多数方案都已被打破。基于块密码学的散列的性能往往比专门构建的密码散列要慢得多;第456页的表18.2应用密码学比较戴维斯 - 迈耶（使用DES），戴维斯 - 迈耶（使用IDEA），命名为GOST另一个基于密码块散列的一个128位的变体，和12个的散列函数的性能。基于块的密码哈希值都在本次评测中最低的三个进行散列。

回到专门构建加密哈希函数的领域，许多专家认为RIPEMD-128太短了。RIPEMD-160是SHA-2家族的有力竞争者，但相对而言，它受到的关注较少，也不太可信。RIPEMD功能的优点和缺点是完全在美国控制的国家安全局之外设计的。

业余密码学

发明新的哈希函数时要小心——也就是说，添加盐、重复哈希、连接哈希、XORing results、用隐写法将它们嵌入其中大笑猫图片等。设计密码散列非常困难，从名称MD5 (MDs 1到4之后)、RIPEMD-160 (RIPEMD和RIPEMD-128)和SHA-2家族(SHA和SHA-1)可以看出。在散列函数中添加一些操作或组合现有函数是一种诱人的自助修复方法，但通常只会给攻击增加微不足道的复杂性，而且可以轻松降低攻击的复杂性。摘自CRYPTO 2004论文摘要迭代哈希函数中的多集合作者Joux(打破SHA-0的主要贡献者之一):

[...]我们解决了长期存在的公开问题，证明了串联的几个迭代散列函数的结果，以建立一个更大的一个不产生安全建设。