crc - 两个数据块产生相同 CRC64 值的可能性有多大？

Question

我有一个使用 CRC64 值来确保数据完整性的缓存应用程序。我正在考虑放置一个额外的字段，一个时间戳，用于在各种缓存服务器之间传递数据并进行比较以查看数据是否已更改。

但是，这需要更改协议。虽然这不是什么大不了的事，但我已经有一个 CRC64 可以用作指示某些情况发生变化的指标。

有谁知道产生相同 CRC64 的两个数据块的统计数据？如果不是，我该如何计算或估计它的可能性？

Answer 1

如果您假设 crc64 是“完美的”，那么这些数字非常合理：

对于 1% 的碰撞概率，您需要 6.1 × 10^8 个条目。对于 50% 的碰撞概率，您需要 5.1 × 10^9 个条目。

当然，如果数据可能是由恶意来源提供的，那么像 crc64 这样简单的散列中的冲突很容易产生，并且冲突可能很猖獗。所以你是否走这条路取决于输入数据的来源和碰撞的潜在后果。

Answer 2

任何两个给定块碰撞的概率是 1/2 ⁶⁴，或大约 1.8 × 10 ¹⁹中的 1 。

但是，如果您对大小为 N 的群体中任意两个块的碰撞率感兴趣，则概率很快就会变得更有可能。

有关更多信息，请参阅Wikipedia 上的生日问题，其中包含公式和近似值。

Answer 3

不同随机数据上的两个 CRC64 相同的概率在 2** 64 中接近 1 次。但由于 CRC 对数据模式有些敏感，可能会出现退化的情况，您会失去几个二进制保护顺序。可能无法得出一个硬数字，但假设最坏情况下的碰撞几率在 2** 50 左右时小于 1 次，您可能会很安全。

如果您使用加密散列而不是 CRC64，您肯定会更接近理论极限，但加密散列的计算成本通常要高得多。