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

以前 123.4 第2页 下一个

单向功能也比较容易计算，但显著更难扭转。[...]在此背景下，“硬”的定义是这样的：这将需要数百万年，从F（X）计算x，即使在世界上所有的计算机被分配到这个问题。[...]这听起来不错，但它的很多雾里看花。如果我们是严格的数学，我们没有证据证明单向函数的存在，也没有任何真正的证据，他们可以构造。

这并不意味着加密散列函数或加密算法是没有用或不工作，它只是意味着他们的“一wayness”不是功能的成熟，不变的数学特性。

警惕加密散列函数作为一个神奇的盒子，你可以东西的投入，一定可以得到一个完全独特的固定大小的输出回报的思维，即使你读它描述这样一个数学冠冕堂皇的定义。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个比特。这种错误是不知道。几年前，在一个著名的网络公司程序员骄傲地向我解释他们的网页缓存是如何工作的。每个页面由它的内容，截断为64位的MD5散列（对于64位的数据类型方便地使用）来寻址。由于有2⁶⁴可能的散列值和许多少于2⁶⁴网页，他认为，哈希将永远不会在实践中发生碰撞。我做了一个粗略的想法如何存在，当时很多网页，但可以肯定，我问他有多少页是在数据库中。答案是：约4十亿（2³²)页，或者可能的散列值的平方根。当程序员认为它可以忽略的时候，碰撞的几率实际上是50%左右。自那以后，网络发展壮大;如果缓存还没有发生过碰撞，那么几乎可以肯定的是，从那以后就发生了碰撞。

这来自于（天文大量可能的散列值）的碰撞为1的概率的思维另一个直观的错误是假设碰撞的几率是完全随机的，独立的。我们正在训练，这样的想法在入门概率类 - 只是因为在过去五年掷骰想出了乱七八糟不改变下一卷的未来六个概率。但是，加密散列函数是确定的 - 如果输入散列六的第一次，它会散到六下一次了。想象如果你有一个碰撞时会发生什么错误毛骨悚然 - 好吧，有碰撞，但它是在第一时间令人难以置信的可能性不大，而且发生两次的机会更不可能。这是不正确的;一旦发生碰撞，总是该数据集的碰撞（除非你可以改变你的哈希函数）。

密码散列函数的生命周期

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

更详细地说，加密散列函数开始寿命作为初始建议。在这一点上，一些密码学家已经研究它，它被认为是不可靠的;许多建议加密散列函数都处于起步阶段削减，提出后，他们通过另一个密码专家很快被打破。作为一个加密散列函数进行审查，没有弱点被越来越密码学家正在测试发现，早期采用者开始使用它在实践中更加注重于它。如果散列生存与日益普及走来增加的推敲，它享有一些年，成熟期和信赖。然而，在创建密码散列的信心一样普及也促使打破功能研究人员的工作。几年后，一个弱点被发现允许幅度更低的复杂性比蛮力攻击的几个订单的攻击。在这一点上，没有实际的攻击存在，但专家认为这是一个警告信号，一个更强大的攻击是迫在眉睫，并开始建议从之前的原始哈希函数搬走。一个的这个更非凡实例发生在1995年，当NSA推荐从SHA-0（当时称为只是普通SHA），并稍加修改SHA-1移开，而无需准确知道为什么说明。（SHA-0完全打破2004年），在这期间，非专业人士嗤之以鼻，并比较了攻击在宇宙或其他一些令人印象深刻的物理量原子数的复杂性。

在几年之内第一个理论的弱点，更强的弱点被发现，其结果是哈希函数的略微简化的版本是容易使用的几个月的时间就相当于一个大的超级计算机的攻击。在这一点上，专家们建议丢弃立即使用该哈希的，虽然没有实际的攻击还不存在。非专家指出，超级计算机的时间几个月是很难得到和正常人没有什么后顾之忧。在短短几个月内或几年强烈的弱点的发现，一些雄心勃勃的研究人员发现，以产生相当无意义的随机前瞻性输入之间冲突的可行之路。有关专家宣告散列的确很破，香槟开瓶，拍拍肩膀上的研究员。非专家指出，冲突只能在随机前瞻性数据，而不是数据看起来像合同或证书，所以还是有什么可操心产生。此后不久，在进攻的改进让一些无聊的程序员写程序到家庭计算机上生成有意义的输入之间的碰撞和释放它作为开源。专家们没有任何正式的反应，因为他们忙于复习新的加密散列函数。

流行密码散列的生命周期

这个图表显示较知名的哈希值的不同生命阶段。你可能注意到了很大的变化，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功能完全在美国境外设计，既有优点也有缺点管理国家安全局。

业余密码

警惕发明一种新的散列函数的 - 那就是，加入盐，双散列，串联散列，异或结果，隐写它们嵌入到大笑猫图片等设计密码散列是极硬，通过名称MD5（MD上之后1〜4）所证明的，RIPEMD-160（RIPEMD和RIPEMD-128），和SHA-2家族（SHA和SHA-1）。添加一些操作来散列函数或组合现有的功能是一个诱人的做自己动手修复，但通常仅增加了极少量的复杂性的攻击，并可以很容易地减少受攻击的复杂性。从抽象的CRYPTO 2004年纸在迭代散列函数Multicollisions作者Joux(打破SHA-0的主要贡献者之一):

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