两个消息具有相同的MD5摘要和相同的SHA1摘要的机会是什么? [英] What are the chances that two messages have the same MD5 digest and the same SHA1 digest?

问题描述

给出两个不同的消息，A和B(如果大小很重要的话，可能是20-80个字符的文本)，那么A的MD5摘要与B 的MD5摘要相同的概率是多少，并且 A的SHA1摘要与B的SHA1摘要相同?那是:

Given two different messages, A and B (maybe 20-80 characters of text, if size matters at all), what is the probability that the MD5 digest of A is the same as the MD5 digest of B and the SHA1 digest of A is the same as the SHA1 digest of B? That is:

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

假定没有恶意意图，即，未选择旨在发现冲突的消息.我只想知道这种情况自然发生的可能性.

Assume no malicious intent, i.e., that the messages are not selected with an aim of finding a clash. I just want to know the odds of this happening naturally.

我认为机会是天文数字低"，但是我不确定如何验证这一点.

I'm thinking the chances are "astronomically low," but I'm not sure how to verify this.

更多信息:可能的消息池的大小受到限制，但是很大(几亿).生日矛盾的情况正是我所担心的.

More information: the size of the pool of possible messages is restricted, but large (several hundred million). Birthday paradox situations are exactly what I'm worried about.

推荐答案

假定随机字符串在MD5和SHA-1散列的范围内均匀散布(不是这种情况)，并假设我们只是在谈论两个字符串，而不是讨论字符串池(因此避免了生日悖论类型的复杂性):

Assuming uniform spread in the range of MD5 and SHA-1 hashes for random strings (which isn't the case), and assuming we're only talking about two strings and not talking about a pool of strings (so we avoid birthday-paradox-type complexities):

MD5哈希为128位宽，SHA-1为160.在上述假设下，如果两个哈希A发生冲突，则两个字符串A和B就有可能发生P冲突.所以

An MD5 hash is 128 bits wide, and SHA-1's is 160. With the above assumptions, two strings A and B have a probability of colliding P if both hashes collide. So

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

同样，如果您有一个字符串池，并且试图确定与该池发生冲突的可能性，那么您就位于

Again, if you have a pool of strings and you're trying to determine the probabilities of collisions with the pool, you're in the domain of the birthday paradox and this probability I've calculated here doesn't apply. That and hashes aren't as uniform as they should be. In reality you're going to have a much higher collision rate, but it will still be tiny.

编辑

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

Since you are dealing with a birthday paradox situation, apply the same logic as the solution to the birthday paradox. Let's look at it from the point of view of just one hash function:

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亿个).

Let's pretend we have a nice even number of hashes like 2^29 (roughly 530 million).

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

简而言之，我什至不想考虑计算这个数字.我什至不知道你怎么去估计它.您至少需要一个可以在不死的情况下处理大量阶乘的任意精度计算器.

In short, I don't even want to think about calculating this number. I'm not even sure how you can go about estimating it. You'll at least need an arbitrary-precision calculator that can handle huge factorials without dying.

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

Note that the probabilities will follow a curve that starts at nearly 0 when N = 1 or 2, and it will reach 1 when N >= 2^288, similar in shape to the one on the Wikipedia page for the birthday paradox.

当N = 23时，生日悖论达到P = .5.换句话说，当N为S的6％时，发生碰撞的可能性为50％.如果缩放(我不确定是否会发生)，这意味着当您拥有2 ^ 288哈希值的6％. 2 ^ 288的6％在2 ^ 284附近.您的N值(几亿美元)远不及此.与您的S相比，这几乎是微不足道的，因此我认为您无需担心.碰撞的可能性很小.

The birthday paradox reaches P = .5 when N = 23. In other words, the probability of a collision is 50% when N is 6% of S. If that scales (I'm not sure if it does), it means that there will be a 50% chance of a collision when you have 6% of 2^288 hashes. 6% of 2^288 is around 2^284. Your value of N (several hundred million) is nowhere near that. It's practically insignificant compared to your S, so I don't think you have anything to worry about. Collisions aren't very likely.

这篇关于两个消息具有相同的MD5摘要和相同的SHA1摘要的机会是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！