非加密哈希与CRC-32等相比在检测数据错误方面表现如何？

Question

非加密哈希与CRC-32等相比在检测数据错误方面表现如何？

hashchecksumcrcdata-integrityerror-detection

8

Non-cryptographic hashes，例如MurmurHash3和xxHash，几乎专门为哈希表设计，但它们似乎与CRC-32、Adler-32和Fletcher-32的功能相当甚至更好。非加密哈希通常比CRC-32更快，并产生类似于慢加密哈希（MD5，SHA）的更多“随机”输出。尽管如此，我只看到CRC-32或MD5被推荐用于数据完整性/校验和目的。

在下表中，我测试了32位校验和/CRC/hash函数，以确定它们检测数据中小差异的效果如何：

每个单元格中的结果表示：A）发现的碰撞数量，以及B）32个输出位中任何一个被设置为1的最小和最大概率。要通过测试B，最大值和最小值应尽可能接近50。任何低于45或高于55的数值均表示偏差。

看着这张表格，MurmurHash3和 Jenkins lookup2与CRC-32（实际上有一个测试失败）相比较，表现得更好。它们也很均匀。DJB2和FNV1a通过碰撞测试，但分布不均匀。Fletcher32和Adler32在NullBytes和8RandBytes测试中表现不佳。

那么我的问题是，与其他校验和相比，'非加密哈希'用于检测文件中的错误或差异有多合适？是否有任何理由认为CRC-32 / Adler-32 / CRC-64可能优于任何良好的32位/ 64位哈希？

- bryc

https://eklitzke.org/crcs-vs-hash-functions - Eugene Sh.

1

为了进行错误检测，您希望在输入中翻转任何位时产生不同输出的可能性很高。理想情况下，您希望两个或更多位翻转的组合具有相当高的可能性。您执行的测试似乎没有解决这个问题。结果中每个位为1的概率忽略了相关性的可能性。 - John Bollinger

1

例如，考虑以下算法：（1）将结果设置为零；（2）对于输入的每个字节，如果最高有效位的奇偶性与字节在输入中的位置的奇偶性相同，则翻转结果的所有位。如果我正确理解测试，那么这将在所有测试中产生接近理想的结果（并且它可以非常快速地完成！），但它对于错误检测来说极其无效。 - John Bollinger

是的。好的哈希函数在您的测试中会表现得很好，但在您的测试中表现良好的哈希函数并不一定是好的。 - John Bollinger

2

您的Bytes1to255测试挑战了一个CRC的特定属性，该CRC的寄存器初始化为全1，并随后输入全1，即您的255序列。您计数的碰撞不代表CRC的平均行为。 254个碰撞仅发生在五个字节后（您无需到72就能看到它们）。所有碰撞的形式都是CRC（3 * 255 + n）== CRC（4 * 255 +〜n），其中“*”表示重复该次数，“+”表示连接。 “〜”表示按位取反。 - Mark Adler

显示剩余5条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mark Adler · Accepted Answer

这个函数相比于CRC-32或Adler-32检测数据错误有劣势，但对于某些错误特征，可以设计出非常有效地检测分组内少量位错误的CRC。这就是它的设计目的。如果有大量错误，任何填充32位并对分组所有位敏感的32位检查将与其他检查一样工作得很好。所以它可以和CRC-32一样好，并且比Adler-32稍微好一点（Adler-32故意不使用所有可能的32位值，因此误报率略高于使用所有可能值的32位检查）。顺便说一下，更深入地看一下您的算法，除非输入了许多字节，否则它不会在所有32位值中分配。因此，在涵盖检查的可能32位值之前，您的检查在大量错误方面不如其他32位检查。