MD5中的碰撞概率

Question

最糟糕的情况是,我在缓存中有1.8亿个值(15分钟窗口,然后它们变得陈旧),MD5有2 ^ 128个值.碰撞的概率是多少？或者更好的是,是否有一个网页可以回答这个问题或粗略估计？那会摇滚,所以我知道我的机会.

Answer 1

概率为1-m!/(mⁿ(mn)!),其中m = 2 12',n = 180000000.

通过在线Wolfram运行它超过了可用的计算时间!

如果您在本地安装了SmallTalk,则可以运行以下命令:

|m n p|

m := 2 raisedTo:128.
n := 180000000.
p := (1-(m factorial/((m raisedTo:n)*(m-n)factorial)))asFloat.

Transcript show:p printString;cr.

搜索生日问题会显示一个维基百科页面,其中提供了一个显示128位和2.6×10 15哈希的表格,碰撞的概率是10十分之一,所以这是哈希数量的140倍而不是你的考虑.所以你知道你的赔率比这更糟糕.

如果n？m是1-e ^{-n 2/2m},那么这是一个很好的近似值,如果插入上面的m和n,则得到4.76×10 -2或1或2.10×10 2 2作为碰撞的概率.

即使碰撞的可能性非常低,但在这种FOOBAR情况下是谨慎的,比如说存在问题并且散列累积超过15分钟,至少确认在发生碰撞时会发生什么.