8

我正在尝试对其中包含二进制数据的大量文件进行哈希处理，以便：（1）将来检查是否损坏，以及（2）消除重复文件（可能具有完全不同的名称和其他元数据）。

我知道 md5 和 sha1 及其亲戚，但我的理解是这些是为安全而设计的，因此故意放慢速度以降低暴力攻击的功效。相反，我希望算法尽可能快地运行，同时尽可能地减少冲突。

有什么建议么？

4

3 回答 3

6

你是最正确的。如果您的系统没有任何对手，考虑到它们的安全属性，使用加密散列函数是过度的。

冲突取决于您的哈希函数的位数b和您估计要计算的哈希值N 的数量。学术文献认为这种冲突概率必须低于硬件错误概率，因此与逐字节比较数据 [ ref1 , ref2 , ref3 , ref4 , ref5 ]相比，与散列函数发生冲突的可能性更小。硬件错误概率在2^-12和2^-15 [ ref6 ] 的范围内。如果您希望生成N=2^q哈希值，那么您的碰撞概率可以由这个方程给出，它已经考虑了生日悖论：
方程

哈希函数的位数与其计算复杂度成正比。 因此，您有兴趣找到一个尽可能少的哈希函数，同时能够将冲突概率保持在可接受的值。

以下是有关如何进行该分析的示例：

  • 假设您有f =2^15 个文件；
  • 每个文件lf的平均大小为2^20 字节；
  • 您假装将每个文件分成平均大小lc等于2^10 字节的块；

  • 每个文件将被分成c =lf/lc=2^10 个块；

  • 然后您将散列q = f*c =2^25 个对象。

根据该等式，几种散列大小的冲突概率如下：

  • P(hash=64 bits) = 2^(2*25-64+1) = 2^-13 (小于2^-12)
  • P(hash=128 bits) = 2^(2*25-128+1) 2^-77 (远小于 2^-12)

现在你只需要决定你将使用哪个 64 位或 128 位的非加密哈希函数，知道 64 位它非常接近硬件错误概率（但会更快），而 128 位是一个更安全的选择（虽然更慢）。

您可以在下面找到一个从非加密哈希函数的维基百科中删除的小列表。我知道 Murmurhash3，它比任何加密哈希函数都快得多：

  1. Fowler–Noll–Vo：32、64、128、256、512 和 1024 位
  2. 詹金斯：64 位和 128 位
  3. MurmurHash：32、64、128 和 160 位
  4. CityHash：64、128 和 256 位
于 2012-10-21T21:22:07.887 回答
1

MD5 和 SHA1 不是为安全而设计的，不，所以它们不是特别安全，因此也不是很慢。我自己（使用 Python）使用 MD5 进行重复数据删除，性能还不错。

这篇文章声称今天的机器可以计算每秒 330 MB 数据的 MD5 哈希。

SHA-1 被开发为 MD5 的更安全替代方案，当时发现您可以制作与 MD5 哈希值相同的输入，但我认为出于您的目的，MD5 可以正常工作。它确实对我有用。

于 2012-09-27T11:43:05.007 回答
-1

如果安全性不是您关心的问题，您可以采用安全散列函数之一并减少轮数。这使得密码学上不健全但仍然非常适合平等测试。

绞肉非常强大。它有80轮。尝试减少到​​10个左右。

或者使用 AES 和 XOR 一起加密输出块。AES 在现代 CPU 上进行了硬件加速，速度非常快。

于 2012-10-21T21:25:25.880 回答