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

3 回答

• 1

  更新

  具有讽刺意味的是，在我发布前一个答案后的几个星期，两位中国研究人员，陶燮和邓国峰，published a new single-block collision for MD5 . 直到现在我还没有意识到那篇论文 . 单个MD5块意味着输入大小为64字节或512位 . 请注意，输入大多相同， differing only in 2 bits .

  他们的方法将在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'
  

  Update: 该论文发表于2013年3月：Tao Xie and Fanbao Liu and Dengguo Feng - Fast Collision Attack on 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集群上生成这两个特定输入需要2天，by Mark Stevens :)

  回复于 2024-04-27T01:16:03+08:00
• 10

  birthday paradox的数学使得碰撞概率的拐点大致在sqrt（N）附近，其中N是散列函数中不同的bin的数量，因此对于128位散列，当你得到大约64位时，你是适度的可能有1次碰撞 . 所以我的猜测是完整的8字节字符串，它很可能是_1569607 .

  edit: 这假定MD5哈希算法导致从输入字节串到接近"random"的输出哈希的映射 . （与在一组可能的哈希值之间更均匀地分布字符串的那个相比，在这种情况下它将更接近16个字节 . ）

  另外，对于更具体的数字答案，如果你看one of the approximations来计算碰撞概率，你得到

  p（k）≈1-e-k（k-1）/（2 * 2128）其中k =可能输入的空间大小= 2m，其中输入字节串是m位长 .

  8字节字符串的集合：p（264）≈1 - e-0.5≈0.3935

  9字节字符串的集合：p（272）≈1 - e-2144 /（2 * 2128）= 1 - e-215 = 1 - e-32768≈1

  另请注意，这些假定完整的m / 8字节字符串集 . 如果您只使用字母数字字符，则需要更多字节才能获得可能的冲突 .

  回复于 2024-04-27T01:16:03+08:00
• 71

  我怀疑是否有任何有用的长度，你不会有可能的碰撞 . 那些算法并没有真正用于此目的 . 它意味着尝试对数据中的微小变化（如损坏的文件）而言是唯一的，而不是对所有可能的数据集都是唯一的 .

  回复于 2024-04-27T01:16:03+08:00