如何评估哈希碰撞概率？

Question

我正在开发一个搜索系统的后端应用程序。搜索系统将文件复制到临时目录并随机命名，然后将临时文件名传递给我的应用程序。我的应用程序必须在有限的时间内处理每个文件，否则它会被关闭 - 这是一种类似看门狗的安全措施。处理文件可能需要很长时间，因此我需要设计能够处理这种情况的应用程序。如果我的应用程序下次被关闭，搜索系统想要索引相同的文件，它可能会给它一个不同的临时名称。

显而易见的解决方案是在搜索系统和后端之间提供一个中间层。它将对请求进行排队，并等待结果到达。如果中间层中的请求超时 - 没问题，后端将继续工作，只有中间层被重新启动，并且当搜索系统稍后重复请求时，它可以从后端检索结果。

问题在于如何识别文件。它们的名称随机更改。我打算使用哈希函数（如MD5）对文件内容进行哈希。我很清楚生日悖论并使用链接文章中的估计来计算概率。如果我假设我没有超过100,000个文件，则两个文件具有相同MD5（128位）的概率约为1.47x10^-29。

我应该关注这种碰撞概率，还是只假设相等的哈希值意味着相等的文件内容？

- sharptooth

---

这是对文件名内容的哈希吗？ - Sam Saffron

内容已经被哈希处理了。对文件名进行哈希处理没有意义——它们会随机更改。 - sharptooth

如果您担心碰撞问题，请考虑文件大小和哈希值。 - Marcus Adams

Answer 1

相等的哈希值意味着文件相等，除非有人恶意干扰你的文件并注入冲突。（如果他们正在从互联网下载内容，则可能是这种情况）如果是这种情况，请选择基于SHA2的函数。

没有意外的MD5冲突，1.47x10 ^-29是一个非常非常小的数字。

为了解决重新哈希大型文件的问题，我将采用三阶段身份验证方案。

1. 仅文件大小
2. 文件大小+文件中不同位置的64k * 4散列值
3. 完整哈希值

因此，如果您看到一个具有新大小的文件，则可以确定您没有重复。以此类推。

- Sam Saffron

---

@sharptooth 看看这个问题，里面有一些你可以使用的技巧：https://dev59.com/TkfRa4cB1Zd3GeqP8Vgg - Sam Saffron

我已经在数据库中存储了2.5万张图片，在其中发现了第一个MD5碰撞。 - Valentin H

“没有偶然的MD5碰撞” - 这个声明是错误的。 - ColinM

喜欢在对整个文件进行哈希之前先对一些小部分进行哈希的想法。这可以大大加快重复文件检查的速度。 - Toni Homedes i Saun

Answer 2

仅因概率是1/X，并不意味着在您拥有X个记录之前它不会发生在您身上。这就像彩票，你不太可能赢，但总有人会赢。

随着计算机的速度和容量（甚至不谈安全性，仅讨论可靠性），对于任何关键事项，真的没有理由不使用更大/更好的哈希函数而不是MD5。升级到SHA-1应该会让您晚上睡得更好，但如果您想要更加谨慎，则请升级到SHA-265，并永远不再考虑它。

如果性能真的是一个问题，那么使用BLAKE2可能比MD5更快，但支持256位及以上，以使冲突变得不太可能，同时具有相同或更好的性能。然而，尽管BLAKE2已被广泛采用，但它可能需要向您的项目添加新的依赖项。

- ColinM

---

然而，对于彩票来说，你有一个保证获胜者。虽然目前没有已知的SHA256碰撞，从技术上讲，在完全耗尽之前可能永远不会出现碰撞，对吧？ - JamesTheAwesomeDude

总的来说，对于一个文件哈希应用程序来说，你可以相当安全地假设SHA-256永远不会产生碰撞（不像Git使用的SHA1，在大型实际项目中已经发生了碰撞）。然而，如果使用SHA-256来哈希随机输入位（例如生成会话ID），你仍然应该考虑到RNG碰撞的机会是相同的，无论使用什么哈希方法。也就是说，使用SHA-256哈希随机的32位整数仍然只有32位数据，因此碰撞很可能发生。 - ColinM

Answer 3

我认为你不应该这样做。

但是，如果你有两个名称不同（不是基于md5的）但内容相同的文件的概念，那么你应该这样做。例如，在搜索系统中，两篇文档可能具有完全相同的内容，但因为它们位于不同的位置而被视为不同。

- alamar

---

这是搜索系统的问题，而不是我的应用程序的问题。我的应用程序只需要从传递的文件中提取文本。 - sharptooth

Answer 4

我提出了一种蒙特卡洛方法，以便在使用UUID进行序列化时能够安全地睡眠，而不会发生冲突的分布式系统。

from random import randint
from math import log
from collections import Counter

def colltest(exp):
    uniques = []
    while True:
        r = randint(0,2**exp)
        if r in uniques:
            return log(len(uniques) + 1, 2)
        uniques.append(r)

for k,v in Counter([colltest(20) for i in xrange(1000)]):
    print k, "hash orders of magnitude events before collission:",v

会打印出类似于以下内容:

5 hash orders of magnitude events before collission: 1
6 hash orders of magnitude events before collission: 5
7 hash orders of magnitude events before collission: 21
8 hash orders of magnitude events before collission: 91
9 hash orders of magnitude events before collission: 274
10 hash orders of magnitude events before collission: 469
11 hash orders of magnitude events before collission: 138
12 hash orders of magnitude events before collission: 1

我之前听过这个公式：如果你需要存储log(x/2)个键，使用至少有keyspace e**(x)的哈希函数。

重复实验表明，在1000个log-20空间的人口中，有时会在log(x/4)早期发生冲突。

对于uuid4，它有122位，这意味着我可以安心睡觉，而几台计算机随机选择uuid，直到我拥有大约2**31个项目。我正在考虑的系统中，峰值交易大约是每秒10-20个事件，我假设平均为7个。在极端的偏执情况下，这给我大约10年的运行时间。

- Árni St. Steinunnarson

Answer 5

这里有一个交互式计算器，可以估算任何哈希大小和对象数量的碰撞概率 - http://everydayinternetstuff.com/2015/04/hash-collision-probability-calculator/。

- Ghostrider

---

问题不在于估计概率，我知道概率。问题是接下来我该怎么做。 - sharptooth

接下来要做的很简单：选择一个比原来更多位数且分布更好的哈希函数，例如sha1，并描述碰撞发生的概率、发生时会发生什么以及后果是什么。 - Ellert van Koperen

Answer 6

对于临时文件名，请使用操作系统功能。它可能会使用一个中间子目录，Unix-纪元等。

- druid62