递归MD5和碰撞概率

Question

我想知道将一堆MD5散列值哈希在一起创建一个新的哈希值是否“安全”，或者这样做是否会增加发生冲突的可能性。

背景：我有一些具有依赖关系的文件。每个文件都有一个相关联的哈希值，该哈希值是基于其内容计算的。我们称之为“单文件”哈希值。除此之外，文件还应该有一个包括所有依赖文件的哈希值，即“多文件”哈希值。

因此，问题是：我可以只取所有依赖文件的单文件MD5哈希值，将它们连接起来，然后计算连结值的MD5以获得多文件哈希值，还是这将导致比连接所有依赖文件的内容更易发生冲突的MD5哈希值。

另外，我能否将单文件哈希值异或在一起生成多文件哈希值，还是这样做可能会导致更多的冲突？

- Janick Bernet

Answer 1

听起来你需要一个 默克尔树

- James

---

谢谢，那个看起来很有趣 :) - Janick Bernet

尽管它并没有特别回答我的MD5问题，但这确实解决了我的问题，因为我现在要使用Tiger哈希，这似乎非常适合我的目的 :) - Janick Bernet

Answer 2

MD5存在许多碰撞问题，请参见维基百科上的MD5条目。

然而，如果您将MD5用作检查依赖项的唯一标识符而不是安全性，则即使对连接的哈希进行哈希处理，也应该是相当安全的。

或者，如果还没有太晚，可以切换到SHA-1。

- squadette

---

据我理解，碰撞问题主要与主动攻击者有关，其唯一目的是引发碰撞，但随机碰撞比使用SHA-1更有可能发生。由于它仅用于生成唯一ID而非安全目的，因此主动攻击者不是问题，性能才是主要关注点。 - Janick Bernet

对于校验和（从问题中很明显可以看出这就是 OP 所做的），伪造的碰撞并不重要。第二句话的最后一部分才涉及到问题，而且绝对需要详细说明——你是如何得出这个结论的？ - user395760

我相信你应该是相当安全的。你正在将文件映射到2^128空间中的点。然后，你又将另一个小文件（串联）映射到2^128空间中的另一个点。如果你相信MD5可以均匀地哈希文件，那么你也应该相信它可以同样均匀地哈希串联。 - squadette

@squadette：这可能是因为MD5哈希本身具有一些使它们成为使用MD5再次进行哈希的基础的不良属性，尤其是因为人工构造碰撞很容易。例如，理论上可能是无限应用MD5哈希会收敛到特定的哈希值。 - Janick Bernet

Answer 3

我认为将连接的文件进行哈希处理和将连接的文件哈希值进行哈希处理，发生碰撞的风险大致相同。

- Gerben

---

我也这么认为 :) 但是，我宁愿保险一些，避免一直出现大量的冲突。 - Janick Bernet

哈希算法是关于概率的。如果你想要百分之百的确定性，就不应该使用哈希算法。只需要知道哈希算法被设计成尽可能随机分布，因此碰撞的几率非常接近1/哈希表大小（例如md5的1/2^128）。虽然你不会遇到大量的碰撞，但你的代码在发生碰撞时也不应该出现问题。 - Gerben

我并不害怕1:1^128的碰撞几率，但是正如我写给squadette的那样，理论上递归应用MD5可能会收敛到特定的哈希值，我又怎么知道呢。因此，我想向了解该算法的人获取一些信息，看看它是否存在这样的问题。 - Janick Bernet

首先，您不是在哈希一个哈希，而是在哈希一串连接的哈希字符串。其次，您只深入了2个级别，而不像重新哈希1000次那样。在仅进行2轮后，不会发生收敛。 - Gerben

是的，我的示例只涉及一层深度，也许我应该更加概括问题。但是如果它会收敛，那么深入一层肯定会增加碰撞的概率，这只是一个问题，取决于增加了多少。正如我所说，我不认为这是一个问题，但我仍然希望得到一些数学事实，或者至少得到一些了解MD5内部工作的人的内部知识，以便安全地使用它。 - Janick Bernet