什么是导致MD5碰撞的最短字符串对？

Question

什么是导致MD5碰撞的最短字符串对？

mathcryptographymd5hash-collision

60

在使用MD5哈希时，要避免碰撞的可能性，字符串长度最长可以达到多少？

这应该通过对特定字符集中所有可能的字符串进行哈希计算，逐渐增加字符串长度，直到出现第二次哈希（冲突）为止。然后，没有发生冲突的最大字符串长度将比冲突对中较长的字符串长度少一个字符。

MD5、SHA1等算法是否已经进行过这样的测试？

- Alf Eaton

3

很不幸，MD5和SHA1都被认为已经被近乎破解，因为对于一个信誉良好的密码哈希函数而言，通常的答案是：“不用担心碰撞，就像它们从未发生过一样。即使有人致力于寻找碰撞，在世界末日之前也不可能通过暴力枚举找到碰撞”。 - Pascal Cuoq

1

你过分强调弱点。对于MD5，已知存在碰撞攻击，但尚未发现任何有用的原像攻击。http://www.cs.cmu.edu/~perspectives/md5.html 任何使用现成工具或算法的人都应该了解它的优缺点。 - Jason S

1

如果你需要哈希函数，SHA-2 系列哈希函数（SHA-224、SHA-256、SHA-384、SHA-512）仍然安全，可以抵御碰撞攻击和预像攻击。SHA-1 和 MD5 只应用于旧的应用程序，而不是新的应用程序。 - intgr

http://www.mscs.dal.ca/~selinger/md5collision/ - Nicolas Thery

3个回答

10

生日悖论的数学使得碰撞概率的拐点大约在sqrt(N)处，其中N是哈希函数中不同bin的数量，因此对于一个128位哈希，当你达到大约64位时，你有相当大的可能性会有1次碰撞。所以我的猜测是对于完整的8字节字符串集合，有一定的碰撞可能性，对于9字节字符串，这种可能性非常高。

编辑：这假设MD5哈希算法导致输入bytestring到输出哈希的映射接近“随机”（与将字符串更均匀地分布在可能哈希集合中的情况相比，其中情况更接近16字节）。

此外，对于更具体的数字答案，如果您查看其中一种近似值来计算碰撞概率，则可以得到

p(k) ≈ 1 - e^{-k(k-1)/(2*2¹²⁸)}，其中k = 可能输入空间的大小= 2^m，其中输入bytestring长度为m位。

8字节字符串集合：p(2⁶⁴) ≈ 1 - e^-0.5 ≈ 0.3935

一组由9个字节字符串组成：p(2⁷²) ≈ 1 - e^{-2¹⁴⁴/(2*2¹²⁸)} = 1 - e^-2¹⁵ = 1 - e^-32768 ≈ 1。

此外，请注意这些假设使用了完整的 m/8 字节字符串集合。如果您只使用字母数字字符，则需要更多字节才能获得可能的碰撞。

- Jason S

5

当你将一个无限集合映射到128位数字集合时，碰撞只是一种数学事实。开发者假设哈希唯一性是引起“WTF”错误的主要原因。CCP博客中记录了一个错误（虽然他们使用的是32位哈希）http://www.eveonline.com/devblog.asp?a=blog&bid=371 - Ken Fox

我喜欢这个解释。看起来第一次碰撞可能会发生在8或9个字节内，正如其他人所评论的，如果字符串比这更短，那么哈希它们可能是不值得的。 - Alf Eaton

假设哈希函数没有碰撞是完全可以的。它们显然存在，但对于良好的密码哈希（比如SHA-256），遇到碰撞的概率要比随机硬件错误的概率小得多。@KenFox - CodesInChaos

在哈希函数中，N是不同桶的数量，大约在sqrt(N)附近，因此对于一个128位的哈希函数，当你达到大约64位时，你有相当大的可能性会出现1个冲突。我有点困惑，64位是从哪里来的？ - Dan Bechard

2

2的64次方是2的128次方的平方根。 - Jason S

1

我怀疑在任何有用的长度范围内，都可能存在冲突。这些算法并不是真正用于此目的。它旨在尝试为数据中的轻微更改（如损坏的文件）提供唯一性，而不是针对所有可能的数据集提供唯一性。

- aDev

9

相当错误，MD5是一种加密哈希函数，而加密哈希函数旨在防止碰撞。MD5曾被认为具有抗碰撞能力，但在2004年发现了其弱点。 - intgr

2

@intgr 说“而不是在所有可能的数据集上唯一”是正确的。SHA-256哈希本质上有2^256个可能的值。它由一个64位十六进制字符串表示。这意味着最多需要65个十六进制数字来查找在所有可能的64位十六进制字符串集中重复的哈希值。它也可以用43个字母数字字符（共有62个）表示(256 / log2(62))，这意味着所有43个字符的字母数字字符串的排列都将散列到所有可能的SHA-256哈希值，包括每个长度更长的字符串的哈希值。 - Nicole

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

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

- intgr · Accepted Answer

更新

具有讽刺意味的是，我在发表上一个答案几周后，两位中国研究人员谢涛和冯登国发布了MD5的新单块碰撞。直到现在，我才知道这篇论文。单个MD5块意味着输入大小为64字节或512位。请注意，这些输入大部分相同，只有2个比特位不同。

他们的方法将于2013年1月发表，但可以使用论文中的数字来验证他们的碰撞:

>>> from array import array
>>> from hashlib import md5
>>> input1 = array('I',  [0x6165300e,0x87a79a55,0xf7c60bd0,0x34febd0b,0x6503cf04,
    0x854f709e,0xfb0fc034,0x874c9c65,0x2f94cc40,0x15a12deb,0x5c15f4a3,0x490786bb,
    0x6d658673,0xa4341f7d,0x8fd75920,0xefd18d5a])
>>> input2 = array('I', [x^y for x,y in zip(input1,
    [0, 0, 0, 0, 0, 1<<10, 0, 0, 0, 0, 1<<31, 0, 0, 0, 0, 0])])
>>> input1 == input2
False
>>> md5(input1).hexdigest()
'cee9a457e790cf20d4bdaa6d69f01e41'
>>> md5(input2).hexdigest()
'cee9a457e790cf20d4bdaa6d69f01e41'

更新：该论文已于2013年3月发表：Tao Xie和Fanbao Liu和Dengguo Feng - MD5上快速碰撞攻击

然而，如果您有更多的空间来玩耍，几千字节大小的碰撞计算速度会更快--它们可以在任何普通计算机上在几小时内计算出来。

旧答案

以前至少使用了两个MD5块长度的输入来生成最短碰撞（128字节，1024位）。攻击者可以任意选择第一个块中的前缀，其余部分将被计算并显示为无意义的字符。

以下是两个不同碰撞输入的示例，您可以尝试在Python中运行:

>>> from binascii import unhexlify
>>> from hashlib import md5
>>> input1 = 'Oded Goldreich\nOded Goldreich\nOded Goldreich\nOded Go' + unhexlify(
... 'd8050d0019bb9318924caa96dce35cb835b349e144e98c50c22cf461244a4064bf1afaecc582'
... '0d428ad38d6bec89a5ad51e29063dd79b16cf67c12978647f5af123de3acf844085cd025b956')
>>> len(input1)
128
>>> md5(input1).hexdigest()
'd320b6433d8ebc1ac65711705721c2e1'
>>> input2 = 'Neal Koblitz\nNeal Koblitz\nNeal Koblitz\nNeal Koblitz\n' + unhexlify(
... '75b80e0035f3d2c909af1baddce35cb835b349e144e88c50c22cf461244a40e4bf1afaecc582'
... '0d428ad38d6bec89a5ad51e29063dd79b16cf6fc11978647f5af123de3acf84408dcd025b956')
>>> md5(input2).hexdigest()
'd320b6433d8ebc1ac65711705721c2e1'

在215个Playstation 3节点群集上，Mark Stevens用了2天时间生成这两个特定的输入:)