MD5产生碰撞之前有多少随机元素？

我在Amazon S3上有一个图像库.对于每个图像,我md5我的服务器上的源URL加上一个时间戳来获取唯一的文件名.由于S3不能有子目录,我需要将所有这些图像存储在一个平面文件夹中.

我是否需要担心产生的MD5哈希值中的冲突？

额外奖励:在我开始看到MD5产生的哈希值发生冲突之前,我可以拥有多少个文件？

1> Kornel..：

---

只有两个哈希意外碰撞的可能性是1/2 ¹²⁸ ,其中 1 340分之十亿分之282十亿分之366千分之一920 octillion 938 septillion 463 sextillion 463 quintillion 374 quadrillion 607万亿431亿768百万211千456.

但是如果保留所有哈希值,那么由于生日悖论,概率会略高一些.要有任何哈希与任何其他哈希冲突的几率为50%,您需要2 ^64个哈希值.这意味着平均而言,要获得冲突,您需要在100年内每秒哈希60 亿个文件.

---

JørgenFogh:所有物理定律都"不正确".这种迂腐程度是不必要的,因为它不会以任何有意义的方式改变答案.

---

*"碰撞概率是1/2 ^ 64"* - 什么？碰撞的概率取决于已经散列的物品数量,它不是固定数量.事实上,它完全等于`1 - sPn/s ^ n`,其中`s`是搜索空间的大小(在这种情况下为`2 ^ 128`),`n`是散列的项目数.您可能想到的是"2 ^ 64",这是您需要MD5哈希才有50%碰撞几率的项目的近似数量.

---

+1因为我一直想知道如何计算超过999万亿lol(哦,是的,你的回答是提供信息的)

---

所以你说有机会!

---

不幸的是,你仍然不正确.您假设散列函数是真正随机的.它不是.这意味着碰撞概率更高.

---

不完全正确.碰撞的概率远高于此,因为新URL可能会与表中的任何现有项冲突.请参阅[此帖子](http://stackoverflow.com/questions/2145510/python-random-is-barely-random-at-all)(免责声明,我写了这篇文章),了解数学的失败,以及小python脚本,可以适应计算特定数量的URL的概率.

---

@vargonian我明白了:)

2> davr..：

---

S3可以有子目录.只需在密钥名称中加上"/",即可访问这些文件,就好像它们位于不同的目录中一样.我使用它来根据用户在S3中的用户ID将用户文件存储在不同的文件夹中.

例如:"mybucket/users/1234/somefile.jpg".它与文件系统中的目录不完全相同,但S3 API具有一些功能,可以使它几乎完全相同.我可以要求它列出所有以"users/1234 /"开头的文件,它会显示该"目录"中的所有文件.

---

这应该是我认为的内容,因为它实际上并没有回答有关碰撞可能性的问题

3> Ryan..：

---

等等,是吗:

md5(filename) + timestamp

要么:

md5(filename + timestamp)

如果是前者,那么你大部分都是通往GUID的,我不会担心它.如果是后者,那么请参阅Karg的帖子,了解你最终会如何碰撞.

---

@BradThomas:事实并非如此.无论是文件名还是文件名+时间戳的组合,MD5的冲突风险都是相同的.但在第一种情况下,您需要同时进行MD5冲突和时间戳冲突.

---

这仍然留下每分钟两个用户的2 ^(128 ^ 60)次碰撞的机会.字面上无法使用.

---

@BradThomas要更清楚：`md5（filename）+ timestamp`大大降低了碰撞风险，因为对于完全相同的时间戳，您需要具有md5碰撞，才能整体上具有碰撞。md5（filename + timestamp）与md5（filename）相同，假设文件名开头是随机的（因为为随机数添加更多随机性只会更改单个md5结果，并且生日问题仍然存在于所有md5哈希）。

4> Will Dean..：

---

碰撞的粗略经验法则是值范围的平方根.您的MD5 sig大概是128位长,因​​此您可能会看到超过2 ^ 64个图像的碰撞.

---

http://en.wikipedia.org/wiki/Birthday_Problem有关该问题的更多信息.

5> bdonlan..：

---

虽然随机MD5冲突极为罕见,但如果您的用户可以提供文件(将逐字存储),那么他们可以设计冲突.也就是说,他们可以故意创建两个具有相同MD5sum但数据不同的文件.确保您的应用程序能够以合理的方式处理这种情况,或者使用像SHA-256这样的更强大的哈希.

6> acrosman..：

---

尽管由于冲突而引起了人们对MD5的广泛关注，但随机数据之间的无意识冲突却极为罕见。另一方面，如果您要在文件名上进行哈希处理，则该数据不是随机数据，我希望很快会发生冲突。