两条消息具有相同的MD5摘要和SHA1摘要的概率有多大？

Question

两条消息具有相同的MD5摘要和SHA1摘要的概率有多大？

50

假设有两个不同的消息A和B（如果大小重要，可能是20-80个字符的文本），那么A的MD5摘要与B的MD5摘要相同且A的SHA1摘要与B的SHA1摘要相同的概率是多少？

(MD5(A) == MD5(B)) && (SHA1(A) == SHA1(B))

假设没有恶意意图，即这些消息的选择并非出于寻找冲突的目的。我只是想知道这种情况自然发生的可能性有多大。

我认为机会是“天文数字级别的低”，但我不确定如何验证这一点。

更多信息：可能消息的池子大小受限，但很大（几亿）。我担心的正是生日悖论的情况。

- John Siracusa

6

@Mitch 两者在给定消息冲突的概率小于任一方发生冲突的概率。 - Sinan Ünür

5

我认为他的观点是，OP使用两种算法的原因是为了进一步减少碰撞的可能性——如果在MD5中发生碰撞，希望在SHA-1的不同算法中不会发生碰撞。没必要挖苦别人。 - ceejayoz

7

如果目标是减少碰撞的可能性，只需使用生成更大摘要的哈希系统，例如SHA-256、SHA-384或SHA-512。 - Fantius

4

根据应用程序的不同，问题可能是SHA-256、SHA-384和SHA-512 计算时间较长，生成的哈希值比MD5和SHA-1的串联更占空间，或者已部署的系统只支持使用MD5和SHA-1的硬件。这是一个非常合理的问题。 - H. Green

进一步改进摘要的好方法是考虑使用一个比较昂贵的校验和（例如SHA！）和文件大小。相同大小但内容不同的2个文件发生SHA哈希冲突的可能性微乎其微。 - erik258

显示剩余4条评论

5个回答

7

Welbog的帖子的补充说明：

可以使用Stirling's approximation计算大阶乘数的比值，而无需使用任意精度算法：

n! ≈ sqrt(2πn) * (n/e)ⁿ

因此，(S!)/(S^N * (S - N)!) ≈ sqrt(2πS)/sqrt(2π(S-N))*(S/e)^S/((S-N)/e)^S-N/S^N

= sqrt(S/(S-N)) * (S/(S-N))^S-N * e^-N

= sqrt(1 + α) * (1 + α)^S-N * e^-N，其中α = N/(S-N)很小。

当n → ∞（或至少变得非常大）时，近似式(1+a/n)^nx ≈ e^ax成立。

因此，这意味着(1+(N/(S-N)))^S-N ≈ e^N，当S-N >> N时。

所以我期望

(S!)/(S^N * (S - N)!) ≈ sqrt(1 + N/(S-N)) * e^N * e^-N = sqrt(1 + N/(S-N))，当S-N >> N时....

除了这个结果大于1...所以其中一个近似不够好。 :p

(**注意：N/S必须很小：对于N=22，S=365，这个值偏差大约为2)

- Jason S

该死，每当我打错字时，你们就给我投票！ - Jason S

4

如果不限制消息大小，由于有无限数量的可能消息和有限数量的可能散列，机会渐近地趋近于100％。

- ceejayoz

不管消息有多大，它仍会哈希为单个MD5+SHA1哈希值。 - Captain Segfault

你没有理解重点。哈希值的可能性是有限的，因为它们具有固定的长度。而消息的数量是无限的。无限的消息加上有限的哈希值意味着会产生无限的碰撞。 - ceejayoz

1

@fantius问题已经被编辑了。我甚至在你评论之前19分钟就在这个答案中加了一个注释指出了这一点。 - ceejayoz

1

ceejaoyz，我认为这种混淆是因为你说“消息大小”时实际上指的是“消息数量”。 - Beta

2

如果消息大小没有限制，那么消息的数量也就没有限制了，因为我可以发送"message"、"messagemessage"、"messagemessagemessage"等等。无限的消息大小逻辑上会导致无限数量的消息。 - ceejayoz

显示剩余2条评论

1

选定的答案是不正确的，因为它使用了错误的概率。我今天花了很多时间研究这个问题（你可以在那个答案的评论中看到我的思考过程），并且相信实际答案如下（对于稍大于你所讨论的消息的生日攻击）：
2^-61 * 2^-18 = 一次在2^79中发生碰撞。
如果只是简单地将这些概率相乘的话，这是可行的（我不确定）。
现代超级计算机可以在几个月内完成这项任务，并且每年都在缩短时间。
请注意，这是基于足够大的消息池（使生日悖论有意义）的情况。这也是您所担心的场景。

现在，另一种情况是找到一对哈希值（SHA1和MD5）的碰撞，针对一个特定的消息。这使您摆脱了生日悖论的领域，并且难度更大。我不确定那是2^(-61*2)*2^(-18*2)还是其他什么。如果有人知道，请在此答案下发表评论（将不胜感激！）。

现在你问：

给定两个不同的消息A和B（如果大小有关系，则可能包含20-80个字符的文本）

是的，大小很重要。单击2^-18图中的链接，您会看到该值用于两个输入块。在MD5中，输入块为512字节。20-80个字符的文本对于它来说太小了，而单个块的值为2^41。

因此，对于该数据量，您将获得2^-61（我想）* 2^-41 = 2^-102。

对于这个规模来说，它看起来是安全的（链接包含SHA256两倍当前比特币哈希率的数字：46626.93 TH/sec）。

- Greg Slepak

1

通常，当随机选择N个元素时，计算预期的碰撞次数比计算碰撞概率更容易。由于预期碰撞次数不可能小于碰撞概率，因此通常可作为适当的上限。

假设p是两个随机选择的元素发生碰撞的概率。如果我们选择了N个随机元素，则有N*(N-1)/2对元素，因此预期的碰撞次数为 p * N * (N-1)/2.

例如，假设MD5和SHA1的碰撞概率都为p=2^-288，则即使随机选择了2^100个元素，我们仍然只能预期大约2^-89次碰撞。

另一个例子：如果我们选择了2^30个随机元素，并仅计算MD5。假设两个MD5哈希之间的碰撞概率为p=2^-128，则预期的碰撞次数为2^-59。因此，即使对于两个输入，MD5哈希碰撞的概率已经非常小。

- Accipitridae

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Welbog · Accepted Answer

假设随机字符串的MD5和SHA-1哈希值在范围内均匀分布（实际情况并非如此），并且我们只讨论两个字符串而不是一组字符串（因此避免了生日悖论类型的复杂性）：

MD5哈希值宽度为128位，SHA-1的哈希值宽度为160位。根据上述假设，如果两个字符串A和B的哈希值相同，则它们发生碰撞的概率为P。

P(both collide) = P(MD5 collides) * P(SHA-1 collides)

并且

P(MD5 collides) = 1/(2^128)
P(SHA-1 collides) = 1/(2^160)

所以

P(both) = 2^-128 * 2^-160 = 2^-288 ~= 2.01 x 10^-87

如果您有一组字符串，并且正在尝试确定与该组的碰撞概率，则处于生日悖论的领域，我在此计算的概率不适用。此外，哈希值并不像它们应该那样均匀。实际上，您将拥有更高的碰撞率，但仍将非常小。

编辑

由于您正在处理生日悖论的情况，因此应用与解决生日悖论的解决方案相同的逻辑。让我们从一个哈希函数的角度来看待它：

N := the number of hashes in your pool (several hundred million)
S := the size of your hash space (2^288)
Therefore,
P(There are no collisions) = (S!)/(S^N * (S - N)!)

假设我们有一个漂亮的偶数哈希值，例如2^29（大约5.3亿）。

P = (2^288!)/(2^288^(2^29) * (2^288 - 2^29)!)

简而言之，我甚至不想考虑计算这个数字。我甚至不确定如何估计它。你至少需要一个可以处理巨大阶乘的任意精度计算器。

请注意，当N = 1或2时，概率将呈近乎0的曲线开始，并且当N >= 2^288时，它将达到1，形状类似于维基百科生日悖论页面上的曲线。

生日悖论在N = 23时达到P = .5。换句话说，当N是S的6％时，碰撞的概率为50％。如果可以按比例缩放（我不确定是否可以），这意味着当你有2^288个哈希的6％时，会有50％的碰撞几率。你的N值（几亿）远远不及此。与S相比，它几乎微不足道，因此我认为你没有什么可担心的。碰撞的可能性不太高。