50

给定两条不同的消息，A 和 B（可能 20-80 个字符的文本，如果大小很重要的话），A 的 MD5 摘要与 B 的 MD5 摘要和 A 的 SHA1 摘要相同的概率是多少与 B 的 SHA1 摘要相同吗？那是：

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

假设没有恶意，即选择消息的目的不是为了发现冲突。我只是想知道这种情况自然发生的几率。

我认为机会“非常低”，但我不确定如何验证这一点。

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

4

5 回答 5

63

假设随机字符串在 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)!)

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

请注意，概率将遵循一条曲线，该曲线从 0 时开始N = 1 or 2，并且在 1 时达到 1 N >= 2^288，其形状类似于 Wikipedia 页面上的生日悖论。

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

于 2009-08-24T15:27:33.263 回答
6

Welbog 帖子的附录：

通过使用斯特林近似，可以在不使用任意精度算术的情况下计算大阶乘的比率：

嗯！≈ sqrt(2πn) * (n/e) n

所以 (S!)/(S^N * (S - N)!) ≈ sqrt(2πS)/sqrt(2π(SN))*(S/e) S /((SN)/e) SN /S N

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

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

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

** 所以这意味着 (1+(N/(SN))) SN ≈ e N对于 SN >> N。

所以我希望

(S!)/(S^N * (S - N)!) ≈ sqrt(1 + N/(SN)) * e N * e -N = sqrt(1 + N/(SN)) 对于 SN >> N....

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

（** 警告：N/S 必须很小：对于 N=22,S=365，这是 2 倍）

于 2009-08-24T19:36:10.687 回答
4

如果消息大小不受限制，则机会渐近接近 100%，因为有无限数量的可能消息和有限数量的可能散列。

（注意：对问题的编辑现在使这不那么相关了）

于 2009-08-24T15:35:29.490 回答
1

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

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

p * N * (N-1)/2。

例如，如果我们假设 MD5 和 SHA1 的碰撞概率是 p=2 -288，那么即使在随机挑选2100个元素之后，我们仍然只期望大约 2 -89次碰撞。

另一个例子：如果我们选择 2 30 个随机元素并且只计算 MD5。假设两个 MD5 散列之间的冲突是 p=2 -128，这给出了冲突次数的预期数字 2 -59。因此，即使是两个输入的 MD5 哈希冲突的概率也已经非常小。

于 2009-08-26T19:15:50.223 回答
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）。

于 2014-04-12T03:54:16.433 回答