保持使用哈希值的内容大块的轨迹只能是一种方法来节省带宽和构建新的应用领域。遵循一些重要的规则正确，安全地使用哈希值。
序幕
那是1996年，澳大利亚和世界其他地区之间的带宽非常痛苦，和Andrew Tridgell的出现了问题。他想给位于澳大利亚与世界各地的计算机源代码同步的源代码，但发送补丁是烦人，而且容易出错，只是将所有的文件是痛苦的缓慢。大多数人会刚等了几年了跨太平洋的带宽以提高;代替Tridgell的写道：rsync它是第一个已知的基于内容寻址的实例(也称为内容寻址存储，或按哈希比较)，这一创新最终传播到了像BitTorrent这样的软件上，混帐，以及市场上许多文档存储产品。
如果使用得当，基于内容的寻址显着降低带宽使用，简化了代码，并提高了安全性。但是，使用时没有意义，它可以降低性能，提高带宽利用率，并创建新的安全风险。当基于内容的寻址是搞清楚好，当它是非常非常糟糕既需要系统编程和数学的理解。什么是程序员做？在这篇文章中，我们将在语言，任何程序员（甚至一些管理者）能够理解布局的考虑。
基于内容的寻址：基础知识
让我们用一个例子问题开始。假设你有一个MP3音乐收藏，和你的朋友向您发送一个链接到一个新的MP3，但不给你的称号。如果它已经在您的收藏，你不想打扰下载并存储第二个副本，所以要尽快查出是否是相同的其他的MP3之一。如果只有少数的MP3，你只直接比较新的MP3到每个现有的MP3。这需要时间成正比的量来你已经有MP3歌曲的数量，如果你有很多的MP3（我们知道你做的），它会运行得太慢，你会寻找一个更聪明的算法。一种用于快速发现，是老几乎与计算机科学被称为哈希表的特定项目方法。有在哈希表千个变化，但是我们将介绍一个非常简单的例子，然后用它来了解的内容为基础的解决权衡。
而不是与其他所有MP3整个MP3直接比较，我们可以运行一个函数，它的MP3数据作为其输入，输出基于输入一个固定大小的签名。我们的目标是产生类似的数字照片的缩略图 - 签名没有在原来的所有信息，但它是一个有用的提示，以什么整个文件中包含。例如，我们可以只XOR在一起，每4字节加在一起 - CRC32的哈希函数的核心。Hash函数的设计生成这些签名或哈希值。相同的输入将始终具有相同的哈希值，反之，不同的散列值将总是具有不同的输入。所以，与其比较所有文件的数据，你会保护你已经拥有了MP3音乐的哈希值的表。然后，你可以问你的朋友给你新的MP3的CRC32并在哈希表中查找。如果没有与该散列值的一个MP3，那么你知道你没有朋友的MP3，这是值得的下载。
哈希冲突
如果新的MP3的散列值与数据库中已经存在的散列值相匹配，会发生什么?虽然相同的输入总是具有相同的哈希值，但不同的输入可能具有相同的哈希值——这就是哈希冲突。例如，由两个32位数字0x12340000和0x00005678组成的输入的4字节XOR就是0x12345678, 0x12345678和0x00000000的4字节XOR也是0x12345678。因为输入的数目是无限的，而哈希值的数目是有限的，碰撞是不可避免的。实际上，您自己的一些mp3可能已经具有冲突的散列值。处理这个问题的最简单的方法是使哈希表中的每个条目都成为具有相同哈希值的mp3列表，以及指向它们整个数据的指针。当您发现具有相同哈希值的两个mp3时，您可以比较整个文件，看看它们是否真的相同，或者只是具有相同的哈希值。现在，您只比较MP3与少数具有相同哈希值的文件，而不是与每个文件进行比较，这比直接与每个单独的文件进行比较快得多。
现在到了有趣的部分。有时，文件对另一个文件比较甚至一度是贵得离谱，因为当这些文件位于不同的机器上分离的低带宽网络 - 说你在一个南极科考站而你朋友的MP3则是通过卫星链路共享以每秒几千位的速度。(或者你还在拨号上网。)如果你让她把MP3的哈希值发给你，而你没有任何具有相同哈希值的文件，你就会知道下载MP3是值得的。问题是，当散列与数据库中现有的MP3匹配时，如何知道它们是否是相同的MP3，而不需要缓慢而痛苦地下载新的MP3并进行比较?哈希函数有碰撞，这是事实。但是如果你能找到一个几乎不存在冲突的哈希函数，那么你就可以，以非常高的概率，确保如果哈希是相同的，那么它们所代表的文件也是相同的。如果这个概率足够高，你就会觉得在实践中永远不会发生碰撞是安全的(勇敢地接受从来没有听到过艾尔·扬科维奇那首非常怪异的歌的风险)。
输入加密散列函数
幸运的是，散列函数是抗碰撞（简单地说，很难找到相同的输出输入）已经被用于其他用途开发的 - 他们被称为加密散列函数和用于消息认证，数字签名，混淆密码，更多。作为程序员，我们可以“借用”这些功能，并将其用于其他用途。所以，现在你检测两个MP3歌曲是否是相同的算法非常简单：计算和存储所有的MP3的加密哈希。当你想知道你的朋友的MP3是新的，你问它的密码散列，然后把它比作所有其他的MP3的哈希值。如果是与任何现有的MP3，你认为这是相同的MP3也懒得下载或存储它。否则，你开始下载并击杀时拍摄的研究站外的企鹅。
简而言之，这就是所谓的基于内容的寻址(CBA)、按散列比较(CBH)或内容寻址存储(CAS)。只需计算数据段的加密哈希值(粒度通常小于整个文件)，并使用所得到的哈希值作为数据的地址。除了节省网络带宽，CBA消除了自上而下地址分配框架的需要——每个人都计算相同的地址，而不必与任何人交谈——这对于点对点网络，如BitTorrent和分布式哈希表是有用的。它还简化了实现——保存状态是可选的，因为所有地址都可以从内容本身重新生成。
基于内容也解决可能产生严重的缺点，根据不同的应用和密码学研究的状态。首先，加密散列计算价格昂贵，因此在许多应用中，成本转移或数据比较低，CBA只会拖慢应用。如果您想您的本地硬盘上的MP3相比，更普通的技术，如传统的哈希表，会比CBA要快得多在大多数情况下。其次，随着时间的推移加密散列函数降解的碰撞性 - 这是耐碰撞，当程序第一次写将不再是防冲突的几年密码散列函数，之后其他密码学家弄清楚如何找到哈希冲突迅速（因此，术语“抗碰撞”而不是“无碰撞”）。
在本文的其余部分，我们先回顾一下，因为他们从过渡新提出可靠耐碰撞破碎加密散列函数，检查其来源，计算成本，数学性质，以及“生命周期”。然后，我们将详细介绍如何判断何时内容为基础的解决将提高应用程序，以及什么样的影响所选择的加密散列函数的断裂将对应用探索。随着在你的腰带这些信息，您可以放心地判断何时使用基于内容的寻址。
用于程序员的加密哈希函数
在本节中，我们将使用基于内容的解决提供一个快速“N”脏的最相关的程序员加密散列函数方面的概述。对于那些有兴趣在更深的潜水，看到延伸阅读部分。细节的财富可在以下网站上的这些天，包括大多数出版物及预印本，当然，总是有应用密码学（虽然它的严重过期。当涉及到加密散列函数和许多松树为第三版）。
大多数程序员都熟悉的加密签名的文件的想法 - 您使用的加密算法生成使用文档作为输入签名。其他人可以验证你的签名给予适当的键。的问题是，签名是常非常慢的和昂贵的计算，正比于输入的长度。相反签署整个文件的，这将是更好签署该文件的一个短，定长特征码。这个签名必须是每个人都能轻松给出的原始文件计算，但在同一时间是非常困难的人找到具有相同签名（在技术的说法，第二预图像电阻）另一个文档。这也应该是很难找到具有给定签名（预形象电阻），或任何一对具有相同签名，永远（碰撞阻力）文档的文档。
加密哈希函数的设计就是为了满足这一需求和类似的需求。在他们的设计中主要的权衡，作为一个程序员可见的，是:
- 计算的复杂性：太简单了，和哈希容易断裂。太复杂了，哈希时间过长计算。
- 输出的大小：太小，暴力攻击太容易。太大，存储和发送散列值的代价太大。
通常，更好的cryptograhic散列函数，较大的哈希值，并且时间越长来计算。设计成检测随机损坏哈希函数通常更快，具有更短的输出。
计算成本
为了得到一个粗略的想法的CPU时间计算密码散列如何要求，让我们MD5高水平之旅。（MD5已经相当彻底打破，但使一个很好的例子。）卡明斯基描述了一个高层次的MD5算法MD5被认为是有害的某天：
在什么被称为梅克尔-Damgard结构，MD5开始与在长度的任意的初始状态128位。输入数据的512个比特“搅拌”到该128位的状态下，用新的，大规模改组128位的值作为结果。512个更多的比特都在不断搅拌中，遍地，直到没有进一步的数据。64位的更多附加到数据流，以明确地反映被散列的数据的量与另一轮MD5的正在做如果需要的话（如果有没有足够的空间在一个前一轮到散列在于64位），并且最终的128位值后所有的搅拌完成时命名为MD5哈希值。
搅拌操作涉及对消息（在技术上，4轮每16个操作的）的每个512位64操作轮。每一轮Feed的输出进入下一轮 - 也就是发不容易被并行化。更新，更现代的哈希函数通常使用80或更多轮混合。整体信息是密码散列函数涉及一种用于处理数据的每个块中的显著计算成本和多个操作。
数学与加密散列函数
质数永远是质数，数学知识的进步不会改变这一点。但是哈希函数的抗碰撞性会随着密码学的改进而改变。密码哈希函数本质上是人类技术，是人类发明的，用来迷惑受现有技术和数学知识限制的其他人。(如果你怀疑这一点，问问你自己，世界密码学界什么时候不再认为SHA-0是单向函数了——美国国家安全局什么时候才这么认为。)
虽然加密散列函数的数学函数，它们的碰撞性属性不会数学证明 - 而且往往是由例如证伪，当哈希被打破。以下是布鲁斯不得不说的单向函数，其中包括加密散列函数，第29页应用密码学：