什么是导致MD5碰撞的最短的一对弦？
直到string长度为止，可以使用MD5作为哈希，而不必担心碰撞的可能性？
这大概可以通过为特定字符集中的每个可能的string生成一个MD5哈希来计算，直到哈希第二次出现（碰撞）为止。 没有碰撞的string的最大可能长度将比碰撞对中最长的字符小一个字符。
这已经testing了MD5，SHA1等？
更新
具有讽刺意味的是，在我发表前一个答案的几个星期后，两位中国研究人员谢涛和邓国锋发表了一个新的MD5单块碰撞 。 直到现在，我还没有意识到那篇文章。 单个MD5块意味着input大小是64字节或512位。 请注意，input大部分是相同的， 只有2位不同 。
他们的方法直到2013年1月才会发布，但是他们的碰撞现在可以用纸上的数字来validation：
>>> 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月发表文章： 谢涛，范保宝，冯国国 – MD5快速碰撞攻击
但是，如果你有更多的空间可以玩，几千字节的冲突要快得多 – 它们可以在任何普通的计算机上在几个小时内计算出来。
老答案
以前最短的碰撞使用了至less两个MD5块的input – 这是128字节，1024位。 第一个块中的前缀可以由攻击者任意select，其余的将被计算并显示为乱码。
下面是两个不同碰撞input的例子，你可以在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'
生成这两个特定的input在215节点的PlayStation 3群集上花费了2天， 由Mark Stevens 🙂
生日悖论的math使得碰撞概率的拐点大致在sqrt（N）附近，其中N是散列函数中不同仓的数量，所以对于128位散列，当你获得大约64位时，中等可能有1次碰撞。 所以我的猜测是整个8字节的string有可能会发生冲突，而对于9字节的string来说，这是很有可能的。
编辑：这假定MD5哈希algorithm导致从inputstring到接近“随机”的输出散列的映射。 （而不是在一组可能的哈希中更均匀地分配string，在这种情况下，它将更接近于16字节）。
对于一个更具体的数字答案，如果你看一个计算碰撞概率的近似值 ，你会得到
其中k =可能input的空间的大小= 2m ，其中input字节串是m比特长。其中k = 1 -k
一组8字节的string：p（2 64 ）≈1 – e -0.5≈0.3935
一组9个字节的string：p（2 72 ）≈1 -e -2 144 /（2 * 2 128 ） = 1 – e -2 15 = 1 – e -32768≈1
还要注意，这些假设是完整的一组m / 8字节的string。 如果只使用字母数字字符，则需要更多的字节才能发生可能的冲突。
我怀疑是否有任何有用的长度，你不会有可能的碰撞。 这些algorithm并不是真的用于这个目的。 它旨在尝试对数据进行轻微更改（如损坏的文件），而不是在所有可能的数据集中进行唯一更改。
