减少哈希冲突的最佳方法:多散列，还是更大的哈希？

Question

我想要维护一个唯一的数据块列表(大小最多为1MiB )，使用该块的SHA-256散列作为索引中的键。显然，存在哈希冲突的可能性，那么降低这种风险的最佳方法是什么？如果我也计算(例如)MD-5块的散列，并使用组合(SHA-256，MD-5)作为关键，是否有可能发生类似于384-bit哈希函数的碰撞，还是因为我使用不同的哈希函数而稍微好一些？

谢谢为我提供信息!

编辑:我的数据块来自硬盘上的普通用户数据，但总共会有很多字节。

Edit2:作为后续(只需告诉我是否应该将其移到另一个问题)：由于块的大小可能不同，但可以达到某些预先配置的限制(例如，1MiB)，如果我将键块的(64位)大小作为键块的一部分，那么碰撞抗力将如何受到影响？那样的话你只能有相同大小的块碰撞..。

Answer 1

碰撞风险只是理论上的，在实践中是不会发生的。浪费时间花在担心这种碰撞风险的时间里。考虑一下，即使您有2^{90} 1MB块(即10亿个十亿个块--存储在1TB硬盘上，这些磁盘会使堆在美国一样大，高几公里)，发生碰撞的风险也比2^{-76}低。另一方面，被从动物园逃出的大猩猩伤害的风险至少是每天2^{-60}的风险，也就是说比SHA-256在更多的街区上碰撞的可能性要高出65000倍。另一种说法是，在撞上一次碰撞之前，你可以预料到65000只连续的凶残大猩猩的来访。所以，如果你知道什么对你有好处，放下MD5，去买一把猎枪。

现在，对于连接两个不同散列函数的输出的建议，比如SHA-256和MD5。事实证明，这并没有像人们所相信的那样加强安全。384位的总大小当然不会像384位哈希函数所提供的那样提供更多的抗碰撞安全性；但它实际上要弱得多:它并不比单用SHA-256强多少。有关血淋淋的细节，请参阅前一个问题和本研究文章。这可以概括为:当并行使用几个散列函数并将输出连接起来时，对于冲突，总数并不比单个函数中最强的函数强。

当然，MD5本身就是弱碰撞，因此不应该为较新的设计设想。

Answer 2

碰撞风险只是理论上的，在实践中是不会发生的。

除了一个特殊的例子。所给出的描述意味着该系统将是某种形式的去复制文件系统或备份系统。对大多数用户来说，碰撞风险很小。

但是，对于一个特定类别的用户来说，风险要大得多。这些用户是密码哈希研究人员，人们可以认为，他们的HD数据内容中的哈希冲突比普通的joe更有可能发生，仅仅是因为他们试图制造这样的碰撞。

因此，如果这是一个去复制的文件系统或备份系统，并且密码哈希研究人员使用它，那么两个不同的数据块具有碰撞哈希的风险要比普通joe大。

Answer 3

几乎不存在碰撞的风险，但是作为一个优秀的软件开发人员，编写代码来处理它：

如果散列等于，那么比较块的长度，如果它们相等，然后逐字节比较块，如果它们不同，或者如果长度不同，那么1)增加在散列ID末尾连接的整数计数器(在其他地方应该是0)，2)大声记录碰撞，3)利润。

CPU密集型部分是比较，但不要担心，它应该只发生在重复的情况下，即使是比较字节应该是轻量级的。通过选择CRC32作为哈希函数来测试代码。

编辑:不要低估密码学的研究，没有人能保证在5年内发现碰撞是不可行的，所以保护自己免受恶意用户和大猩猩的攻击。