logo标签列表

不同文件大小的哈希碰撞和相同文件大小的概率一样吗？

hashhash-collisionhash-code-uniqueness
13
我正在对大量文件进行哈希处理，为了避免哈希冲突，我还会存储文件的原始大小——这样，即使出现哈希冲突，文件大小也极不可能相同。这种做法可行吗（哈希冲突的大小是等可能的），还是需要其他信息（如果冲突时相同长度更有可能）？
更一般地说，无论原始文件大小如何，每个文件生成特定哈希的概率是否都相同？
@bmargulies：我想我是在一般情况下提问，但我目前正在使用SHA1，并考虑切换到类似SHA256的算法。我只是想知道，如果我还要按文件大小进行密钥生成，那么哈希长度需要多长。 - SqlRyan
我有完全相同的想法。我们需要对文件进行哈希处理，但需要最大速度（即MD5），而且文件大小差异很大。如果可能在两个不同大小的文件上获得相同的MD5哈希，则可能值得存储MD5 +大小以提供额外的安全层。在我们的情况下，我们正在对数百万（甚至十亿）个文件进行哈希处理，因此可能值得包括文件大小。 - Brain2000
如果您要比较大量文件的相同匹配项，则仅计算具有相同大小的文件的哈希值才值得（因为计算哈希值需要很长时间）。例如，如果您的大多数文件大小不超过100MB，但只有一个文件大小为800TB，则没有必要计算该单个800TB文件的哈希值，因为显然没有其他文件会匹配。 - intrepidis
5个回答
12

哈希函数通常编写为能够将数据均匀地分布到所有结果桶中。

如果您假设您的文件在可用大小的固定范围内均匀分布，假设只有1024（2^10）个不同大小的文件均匀分布，则最好仅存储文件大小，只能将碰撞的几率减少不同文件大小的数量。

注意：我们可以假设它是2 ^ 32个均匀分布和不同的大小，但这并不会改变其余部分的计算。

一般认为MD5（例如）发生冲突的概率是1/（2 ^ 128）。

除非哈希函数中有特别构建的内容表明另外的情况。给定任何有效的X，使得P（MD5（X）== MD5（X + 1））的概率与任意两个随机值{ Y ，Z } 的概率相同。也就是说， P（MD5（Y）== MD5（Z）） = P（MD5（X）== MD5（X + 1）） = 1/（2 ^ 128）对于任何值的X ，Y 和Z 。

将这与2 ^ 10个不同文件的情况结合起来，意味着通过存储文件大小，您最多只能获得10位表示项目是否不同的附加位数（再次假设您的文件对于所有值都是均匀分布的）。

因此，最好的方法是增加哈希函数返回的字节数，例如使用SHA-1 / 2，因为这将更有可能给您一个均匀分布的哈希值数据，而不是存储文件大小。

简而言之，如果MD5对于碰撞不够安全，则使用更强的哈希算法；如果更强的哈希算法速度太慢，则使用具有较低碰撞几率但速度较快的哈希算法，例如MD5，并使用较慢的哈希算法（如SHA-1或SHA256）来降低碰撞几率。但如果SHA256足够快且双倍空间不是问题，则应该使用SHA256。

6

根据您的哈希函数，但通常来说，相同大小但内容不同的文件产生的哈希值与大小不同的文件产生的哈希值相同的可能性较小。尽管如此，最好还是使用一个经过时间考验、空间更大的哈希函数（例如MD5而不是CRC32，或SHA1而不是MD5），而不是依赖自己的解决方案，比如存储文件大小。

我正在考虑使用哈希值和文件大小相结合的方式 - 这样，即使发生碰撞的可能性很小，我也会检查文件大小作为一个额外的键来判断它是否真的是相同的文件。 - SqlRyan
3
我理解你的目标，但我的观点是，与其使用额外的N位来存储文件大小，不如采用一个哈希函数，其哈希值比当前的哈希函数多N位。这样做更有可能产生更少的冲突，因为文件大小是任意的，而哈希函数是专门设计用于避免冲突的，因此这些额外的位将更好地利用。 - Max Shawabkeh
啊，这很有道理。我觉得选择一个“更大”的哈希函数可能会更好，所以也许那就是我最终要做的事情。 - SqlRyan
3
@MaxShawabkeh，你有关于“相同大小但内容不同的文件比不同大小的文件更不可能产生相同的哈希值”的说法的来源吗？我很好奇哈希是否会按此加权。 - Seph
2

哈希函数的设计是为了使得碰撞变得非常困难，否则它们就不会有效。
如果您遇到哈希冲突，那么这种情况的概率是1：可能哈希数量，这与文件大小无关。

如果您真的想要对哈希碰撞进行双重确认，可以为同一文件计算两个不同的哈希值 - 这比保存哈希值+文件大小更少出错。

我实际上正在考虑这个问题 - 请参见我的另一个问题，https://dev59.com/MkzSa4cB1Zd3GeqPnYvn。我想保存两个哈希值（如SHA1和MD5），以及文件大小，这样碰撞的可能性就非常小，以至于我永远不必担心它。 - SqlRyan
假设您使用sha256，它提供了2^256个可能的哈希值，并且您有数十亿个文件，每个文件有数百万个版本，大约为1 000 000 000 * 1 000 000，接近2^50，因此每个文件平均有2^200个可能的哈希值，没有任何碰撞威胁。这不是非常巨大吗？更精确地说，您可以尝试通过计算1 - ((2^256)! / ((2^256) - 10^15)! ) / ((2^256)^(10^15))来评估哈希冲突的概率，或者如果不太准确，则为1 - (1 - (10^15)/(2*2^256))^(10^15)，这将给出4e-48的碰撞机会。 - Li0liQ
2

哈希值的大小与原始数据的大小无关。由于可能的哈希值数量是有限的，理论上两个不同大小的文件可能具有相同的哈希值。然而，这也意味着两个相同大小的文件可能具有相同的哈希值。

0
整个密码哈希族（如MD5、SHA-x等）的目的是使碰撞的可能性极小化。 这个概念是，官方的法律程序准备依赖于无法有意制造碰撞的实际情况。 因此，真正的问题是，在这些哈希函数中加入一条背带会浪费空间和CPU时间。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接