校验和：CRC还是哈希？

Question

校验和：CRC还是哈希？

hashchecksumcrc32error-detection

10

除了性能和安全方面的考虑，假设哈希函数具有完美的雪崩效应，对于数据块的校验和，我应该使用CRC32还是截断为N字节的哈希？也就是说，哪一个会更有可能错过错误？具体如下：

CRC32与4字节哈希
CRC32与8字节哈希
CRC64与8字节哈希

数据块将在网络上传输并重复存储在磁盘上。块的大小可以从1KB到1GB不等。

据我所知，CRC32可以以100％的可靠性检测出高达32位翻转，但在此之后，它的可靠性接近1-2^(-32) ，对于某些模式而言更糟糕。一个完美的4字节哈希的可靠性始终是1-2^(-32)，因此可以自己理解一下。

8字节哈希的整体可靠性应该要比CRC32好得多（2^(-64)的错过错误机会），因此应该优先选用8字节哈希。那么CRC64呢？

我想答案取决于此操作可能出现的错误类型。我们是否可能看到稀疏的1位翻转或大规模块损坏？此外，考虑到大多数存储和网络硬件实现了某种形式的CRC，应该已经处理了意外位翻转吧？

- ayurchen

我觉得我对“通用哈希”这个概念有些困惑。 - lc.

好的，我把“general”去掉了，我的错。 - ayurchen

2个回答

0

暂且不考虑“性能”问题，您可能想要考虑使用SHA-2函数之一（比如SHA-256）。

- jlee88my

6

哇，那真的是完全忽略了性能问题。SHA-256所需的时间是CRC-32的100倍或CityHash的50倍。而且这并没有什么理由，因为这不是需要加密哈希的应用程序。 - Mark Adler

1

其实我可能会考虑使用256位哈希，虽然不需要加密强度，但由于校验和中比特数至关重要，因此研究256位哈希可能是有意义的。只是我不确定除了SHA-256之外还有没有其他好用的256位哈希算法。此外，这不是为了将短字符串进行散列而进行的哈希表操作，而是为了对通常超过1KB的消息进行校验和。我想这是一个基准测试问题，以查看它可能引入多少额外开销。我一定会将其作为一种选择。 - ayurchen

刚刚进行了快速搜索，发现有CityHash 256位版本！一定比SHA快一个数量级。 - ayurchen

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

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

- Mark Adler · Accepted Answer

只有你能决定1-2^-32是否足够适合你的应用程序。CRC-n和从好的哈希函数中获得的n位之间的误差检测性能非常接近，因此选择更快的那个。这很可能是CRC-n。

更新：

上面的“这很可能是CRC-n”只是有些可能。如果使用非常高性能的哈希函数，则不太可能。特别是，CityHash似乎几乎与使用Intel crc32硬件指令计算的CRC-32一样快！我在434 MB文件上测试了三个CityHash例程和Intel crc32指令。 crc32指令版本（计算CRC-32C）花费了24毫秒的CPU时间。 CityHash64花费了55毫秒，CityHash128 60毫秒，而CityHashCrc128则花费了50毫秒。 CityHashCrc128利用相同的硬件指令，但它不计算CRC。

为了快速计算CRC-32C，我需要在三个独立的缓冲区上使用三个crc32指令，以便在单个核心中并行使用三个算术逻辑单元，然后将内部循环编写成汇编语言。CityHash非常快。如果您没有crc32指令，则很难像使用CityHash64或CityHash128那样快速计算32位CRC。

但请注意，为此目的需要修改CityHash函数，或者需要做出任意选择，以定义大量数据流的CityHash值的一致含义。原因是这些函数未设置为接受缓冲数据，即一次只能输入一个块，并期望获得与一次性输入整个数据集相同的结果。 CityHash函数需要修改以更新中间状态。

另一种选择，也是我在进行快速测试时所做的，是使用函数的Seed版本，其中我会将前一个缓冲区的CityHash作为下一个缓冲区的种子。但问题在于结果取决于缓冲区的大小。如果您使用这种方法向CityHash提供不同大小的缓冲区，则会得到不同的哈希值。

四年后的另一个更新:

xxhash family更快。我现在建议使用它作为非加密哈希而不是CRC。