MD4 Collision

Author Avatar
Tr0y 10月 29, 2017 16:50:16 本文共 3.5k 字
  • 文为知己者书
  • 在其它设备中阅读本文章

利用王小云的论文实现 MD4 碰撞攻击

前言

MD4 是麻省理工学院教授 Ronald Rivest 于 1990 年设计的一种信息摘要算法,能够将任意长度的字符串压缩成 128bits 的 hash 值。但是由于存在碰撞攻击,已经不再使用。本题是对 MD4 碰撞攻击的实现。

论文内容

下面是对论文的大致翻译,最好对着原论文看(LaTeX 啥的麻烦,word 复制粘贴勉强看看吧)
(以下提到的表均为王小云论文中的表)

MD4 算法描述

  1. 对于给定的字符串,首先对字符串进行填充,使得填充后的长度为 512bits 的整数倍
  2. 对每一块长度为 512bits 的字符串,MD4 利用压缩函数将它压缩成 128bits 的 hash 值。这个压缩函数一共有 3 轮,每一轮使用不同的非线性布尔函数,定义如下:
    F(X, Y, Z) = (X∧Y)∨(¬X∧Z)
    G(X, Y, Z) = (X∧Y)∨(X∧Z)∨(Y∧Z)
    H(X, Y, Z) = X⊕Y⊕Z
    注意,这里的 X,Y,Z 均为 32bits,且函数 F,G,H 均进行的是位运算
    ¬为按位取反,∧为与,∨为或,⊕为异或
    压缩函数的每一轮的均使用 16 次对应的非线性布尔函数,在每一步中,链变量 a,b,c,d 的值都会更新。
    φ0(a, b, c, d, mk, s) = ((a + F(b, c, d) + mk) mod 2^32) <<< s
    φ1(a, b, c, d, mk, s) = ((a + G(b, c, d) + mk + 0x5a827999) mod 2^32) >>> s
    φ2(a, b, c, d, mk, s) = ((a + H(b, c, d) + mk + 0x6ed9eba1) mod 2^32) <<< s
    链变量的初始值为
    (a, b, c, d) = (0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476)
  3. MD4 压缩函数
    记填充后的字符串为 M’,M 为 M’中的一块,压缩函数定义如下:
    记 M 的链变量为(aa, bb, cc, dd)。若 M 是第一块要进行 hash 的分块,则(aa, bb, cc, dd)为初始值(即 0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476)。否则,它们来源于压缩前一块 M 时更新的链变量值。
    执行以下 48 个步骤(三轮):
    For j = 0, 1, 2 and i = 0, 1, 2, 3
    a = φj(a, b, c, d, wj,4i, sj,4i)
    d = φj(d, a, b, c, wj,4i+1, sj,4i+1)
    c = φj(c, d, a, b, wj,4i+2, sj,4i+2)
    b = φj(b, c, d, a, wj,4i+3, sj,4i+3)

在这里,wj,4i+k 是 M,<<< sj,4i+k 为循环左移 sj,4i+k 位
M’分组的使用顺序以及移位的数量已在表 5 给出
更新链变量的方法
aa = (a + aa) mod 2^32
bb = (b + bb) mod 2^32
cc = (c + cc) mod 2^32
dd = (d + dd) mod 2^32
若 M 是 M’的最后一块,则 H(M’) = aa+bb+cc+dd 就是 M’的 hash 值
否则对下一个 512bits 块重复上述过程,(aa,bb,cc,dd)就作为下一块 M 的初始链变量值。

攻击前的准备

  1. 符号说明
    1.1 M = (m0, m1, …, m15) 与 M = (m0, m1, …, m15)代表 2 组 512bits 的明文
    1.2 ai, bi, ci, di 代表对 M 压缩时的第 (4i - 3) ,(4i - 2),(4i - 1) 和 4i 步的输出, 1 ≤ i ≤ 16.
    1.3 a’i, b’i, c’i, d’i 代表对 M’压缩时的第 (4i - 3) ,(4i - 2),(4i - 1) 和 4i 步的输出, 1 ≤ i ≤ 16.
    1.4 ∆mi = m i – mi代表m i与m i之间的单字差异
    1.5 ai,j, bi,j, ci,j, di,j 代表 ai, bi, ci, di 的第 j 位 bit,第 1 位为 j=1
    1.6 xi[j], xi[-j] (x 可以是 a, b, c, d) 代表改变 x(x 为单字)的第 j 位比特后的值, j 为 0 变为 1,-j 为 1 变为 0。
    xi[±j1, ±j2, …, ±jl]代表改变x的第j1, j2, …, jn 位bit后的值, j为0变为1,-j为1变为0。
    1.7 为了更好的描述过程,将使用整数模来表示位差异,比如
    ∆c2 = c2 - c2 = -2^18 + 2^21
    即为
    c’2 = c2[-19, 22]

碰撞攻击过程

攻击成功的概率在 2^(-2)- 2^(-6)之间,复杂度小于 2^8 次 MD4 计算。攻击过程分为 3 步:
找出 M 和 M' 产生碰撞的碰撞微分
推导出一组确保碰撞微分保持不变的充分条件
对于任意随机消息 m,对 m 做一些修改,使几乎所有的充分条件保持不变(弱明文)

  1. MD4 的碰撞微分
    我们选择如下碰撞微分:
    ∆M = M’ - M = (∆m0, ∆m1, ……, ∆m15)
    ∆m1 = 2^31, ∆m2 = 2^31 - 2^28, ∆m12 = -2^16
    ∆mi = 0, 0 ≤ i ≤ 15, i != 1, 2, 12.
    很明显,碰撞微分由两个内部碰撞,分别为步骤 2-25 和步骤 36-41 组成。
    由第三节我们可以知道,只要 M 满足表 6 中的所有条件,则 M 和 M’构成一对碰撞。

  2. 明文修改
    依据表 6,我们知道(M, M’)构成一对碰撞的概率是 2^(-122),远低于生日攻击的 2^(-64)
    我们可以通过 2 种明文修改技术将碰撞概率提升至 2^(-16) ~ 2^(-2),方法如下:
    2.1 单步修正
    我们可以很轻易地修改 M 使其满足第 1 轮的条件保持不变。
    经过单步修正后,(M, M’)构成一对碰撞的概率提升至 2^(-25)
    2.2 多步修正
    虽然 2^(-25)的概率对于要找到一对碰撞已经够大了,但是在第二轮中使用多步修正
    还可以进一步提高,而且这种方法在对 MD5, SHA-0, 特别是 SHA-1.的分析中特别重要
    多步修正的原理是对某些明文的修改由第一轮中的部分碰撞组成,它保留第一轮中的所有条件,但只改变第二轮中的 1bit。方法如下:
    (这里按照表 1 给出的方法进行修改即可)

实现过程

按照论文内容,我们要是不想理会繁琐的推导,直接实现就行
首先选定一个 M(随机或者指定),然后对于第一轮的所有条件,修改链变量的值,并更新对应的 M。然后在第二轮里,我只使用了能更大幅度提升碰撞概率的多步修正修改了 a5 与 d5 的值,单步修正没有使用。第二轮修正完成后,M 就已经修改成一个容易找到碰撞的明文。依据碰撞微分的公式,修改第 1,2,12 分组的相关 bit,我们就有大概率能找到 M 的碰撞 M’。论文最后还提到,修改 c5 及以后的链变量能更大程度提升概率(即表 6 后 7 行,与其相关联的是表 2),但是没有详细说,所以我也就没加在代码里了。
概括起来就是:
对于任意一个 m,修改使其满足表 6 所有条件后为 m1,此时 m1 称为弱明文,弱明文的意思就是,m1 的 1,2,12 分组修改后(记为 m2),会与 m1 形成一对碰撞。即 m1 与 m2 形成碰撞

代码

#encoding: utf-8
import winsound, random
import struct, hashlib
import time, re

#4 字节
def Endian(b): return [struct.unpack('<I', ''.join(b[i:i+4]))[0] for i in range(0, len(b), 4)]

#循环左 右移
def LeftRot(n, b): return ((n << b) | ((n & 0xffffffff) >> (32 - b))) & 0xffffffff
def RightRot(n, b): return ((n >> b) | ((n & 0xffffffff) << (32 - b))) & 0xffffffff

#MD4 中的函数
def F(x, y, z): return x & y | ~x & z
def G(x, y, z): return x & y | x & z | y & z
def H(x, y, z): return x ^ y ^ z

def FF(a, b, c, d, k, s, X): return LeftRot(a + F(b, c, d) + X[k], s)
def GG(a, b, c, d, k, s, X): return LeftRot(a + G(b, c, d) + X[k] + 0x5a827999, s)
def HH(a, b, c, d, k, s, X): return LeftRot(a + H(b, c, d) + X[k] + 0x6ed9eba1, s)

#计算 MD4
def MD4(m): 
  md4 = hashlib.new('md4')
  md4.update(m)
  return md4.hexdigest()

#第一轮修改
def FirstRound(abcd, j, i, s, x, constraints):
  v = LeftRot(abcd[j%4] + F(abcd[(j+1)%4], abcd[(j+2)%4], abcd[(j+3)%4]) + x[i], s)
  for constraint in constraints:
    if   constraint[0] == '=': v ^= (v ^ abcd[(j+1)%4]) & (2 ** constraint[1]) #等于下一个链变量
    elif constraint[0] == '0': v &= ~(2 ** constraint[1]) # =0 的位
    elif constraint[0] == '1': v |= 2 ** constraint[1] # =1 的位

  #反推,更新 m
  x[i] = (RightRot(v, s) - abcd[j%4] - F(abcd[(j+1)%4], abcd[(j+2)%4], abcd[(j+3)%4])) % 2**32
  abcd[j%4] = v #更新链变量

def FindCollision(m):
  x = Endian(m) # 小端序
  initial_abcd = [0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476]
  abcd = initial_abcd[:]

  #第一轮的所有条件
  constraints = [
    [['=', 6]],[['0', 6],['=', 7],['=', 10]],
    [['1', 6],['1', 7],['0', 10],['=', 25]],
    [['1', 6],['0', 7],['0', 10],['0', 25]],
    [['1', 7],['1', 10],['0', 25],['=', 13]],
    [['0', 13],['=', 18],['=', 19],['=', 20],['=', 21],['1', 25]],
    [['=', 12],['0', 13],['=', 14],['0', 18],['0', 19],['1', 20],['0', 21]],
    [['1', 12],['1', 13],['0', 14],['=', 16],['0', 18],['0', 19],['0', 20],['0', 21]],
    [['1', 12],['1', 13],['1', 14],['0', 16],['0', 18],['0', 19],['0', 20],['=', 22],['1', 21],['=', 25]],
    [['1', 12],['1', 13],['1', 14],['0', 16],['0', 19],['1', 20],['1', 21],['0', 22],['1', 25],['=', 29]],
    [['1', 16],['0', 19],['0', 20],['0', 21],['0', 22],['0', 25],['1', 29],['=', 31]],
    [['0', 19],['1', 20],['1', 21],['=', 22],['1', 25],['0', 29],['0', 31]],
    [['0', 22],['0', 25],['=', 26],['=', 28],['1', 29],['0', 31]],
    [['0', 22],['0', 25],['1', 26],['1', 28],['0', 29],['1', 31]],
    [['=', 18],['1', 22],['1', 25],['0', 26],['0', 28],['0', 29]],
    [['0', 18],['=', 25], ['1', 26],['1', 28],['0', 29],['=', 31]]
  ]

  shift = [3, 7, 11, 19] * 4
  change = [0, 3, 2, 1] * 4

  #使满足第一轮的所有条件
  for i in range(16):
    FirstRound(abcd, change[i], i, shift[i], x, constraints[i])

  #第二轮的所有条件
  constraints2 = [
    [['=', 18, 2], ['1', 25], ['0', 26], ['1', 28], ['1', 31]],
    [['=', 18, 0], ['=', 25, 1], ['=', 26, 1], ['=', 28, 1], ['=', 31, 1]]
  ]

  #计算 a5
  a5 = GG(abcd[0], abcd[1], abcd[2], abcd[3], 0, 3, x)
  for constraint in constraints2[0]:
    if   constraint[0] == '=': a5 ^= ((a5 ^ abcd[constraint[2]]) & (2 ** constraint[1]))
    elif constraint[0] == '0': a5 &= ~(2 ** constraint[1])
    elif constraint[0] == '1': a5 |= (2 ** constraint[1])

  q = (RightRot(a5, 3) - abcd[0] - G(abcd[1], abcd[2], abcd[3]) - 0x5a827999) % 2**32

  #多步修正
  a0, b0, c0, d0 = initial_abcd[0], initial_abcd[1], initial_abcd[2], initial_abcd[3]
  a_ = FF(a0,b0,c0,d0, 0, 3, [q]) #计算 a'
  a1 = FF(a0,b0,c0,d0, 0, 3, x) #按照原来的方法算
  d1 = FF(d0,a1,b0,c0, 1, 7, x) 
  x[0] = q #更新 m0
  q = x[1]
  x[1] = (RightRot(d1,  7) - d0 - F(a_, b0, c0)) % 2**32

  c1 = FF(c0,d1,a1,b0, 2, 11, x)
  x[2] = (RightRot(c1, 11) - c0 - F(d1, a_, b0)) % 2**32

  b1 = FF(b0,c1,d1,a1, 3, 19, x)
  x[3] = (RightRot(b1, 19) - b0 - F(c1, d1, a_)) % 2**32

  a2 = FF(a1,b1,c1,d1, 4, 3, x)
  x[4] = (RightRot(a2,  3) - a_ - F(b1, c1, d1)) % 2**32

  abcd[0] = a5

  #计算 d5
  d5 = GG(abcd[3], abcd[0], abcd[1], abcd[2], 4, 5, x)

  for constraint in constraints2[1]:
    if   constraint[0] == '=': d5 ^= ((d5 ^ abcd[constraint[2]]) & (2 ** constraint[1]))
    elif constraint[0] == '0': d5 &= ~(2 ** constraint[1])
    elif constraint[0] == '1': d5 |= (2 ** constraint[1])

  q = (RightRot(d5, 5) - abcd[3] - G(abcd[0], abcd[1], abcd[2]) - 0x5a827999) % 2**32

  #多步修正
  a, b, c, d = initial_abcd[0], initial_abcd[1], initial_abcd[2], initial_abcd[3]
  a = FF(a,b,c,d, 0, 3, x)
  d = FF(d,a,b,c, 1, 7, x)
  c = FF(c,d,a,b, 2,11, x)
  b = FF(b,c,d,a, 3,19, x)

  a2_ = FF(a,b,c,d, 4, 3, [q] * 5)
  a2 = FF(a,b,c,d, 4, 3, x)
  d2 = FF(d,a2,b,c, 5, 7, x)

  x[4] = q
  q = x[5]
  x[5] = (RightRot(d2,  7) - d - F(a2_, b, c)) % 2 ** 32

  c2 = FF(c,d2,a2,b, 6, 11, x)
  x[6] = (RightRot(c2, 11) - c - F(d2, a2_, b)) % 2 ** 32

  b2 = FF(b,c2,d2,a2, 7, 19, x)
  x[7] = (RightRot(b2, 19) - b - F(c2, d2, a2_)) % 2 ** 32

  a3 = FF(a2,b2,c2,d2, 8, 3, x)
  x[8] = (RightRot(a3,  3) - a2_ - F(b2, c2, d2)) % 2 ** 32

  m = ''.join([struct.pack('<I', i) for i in x])
  m_ = CreateCollision(m) #碰撞微分

  if MD4(m) == MD4(m_):
    return m, m_

  return None, None

#对于修正后的 M,有一定概率可以通过碰撞微分找到 M'
def CreateCollision(m):
  x = Endian(m)
  x[1] = (x[1] + (2 ** 31)) % 2 ** 32
  x[2] = (x[2] + ((2 ** 31) - (2 ** 28))) % 2 ** 32
  x[12] = (x[12] - (2 ** 16)) % 2 ** 32
  return ''.join([struct.pack('<I', i) for i in x])

def Collision():
  num = 1
  while 1:
    #随机的 M
    m = [chr(i) for i in [random.randint(0, 2 ** 8 - 1) for i in range(64)]]
    #m = list('0000000000Tr0y has $10000000000000 in the BOC.')
    #m = m+mtail+list('Tr0y has $100000000000000000000000 in the BOC. -------- 20171101')
    #print ''.join(m)
    ma, mb = FindCollision(m)
    if ma:
      winsound.Beep(600, 1000)
      break
    num += 1

  h1 = MD4(ma)
  h2 = MD4(mb)
  return ma.encode('hex'), mb.encode('hex'), h1, h2

# main()
time.clock()
print '[+]Finding Collision...'
m1, m2, h1, h2 = Collision()
M1 = re.findall('.{4}', m1)
M2 = re.findall('.{4}', m2)

mm1 = ''
mm2 = ''
for i in range(len(M1)):
  if M1[i] != M2[i]:
    mm1 += '[' + M1[i] + ']'
    mm2 += '[' + M2[i] + ']'
  else:
    mm1 += M1[i]
    mm2 += M1[i]

print "  [-]The M1 is:", m1
print "  [-]The M2 is:", m2
print "  [-]M1 and M2 diff:\n    [*]" + mm1 + "\n    [*]" + mm2
print "  [-]The MD4(M1) is:", h1
print "  [-]The MD4(M2) is:", h2
print "[!]M1 == M2 ?", m1 == m2
print "[!]MD4(M1) == MD4(M2) ?", h1 == h2
print "[!]All done!"
print "[!]Timer:", round(time.clock(), 2), "s"

# The diff in:
# m1[1] m2[1]
# m1[2] m2[2] 
# m1[12] m2[12]

概率性碰撞,快的话,我跑过 1.7s 一个碰撞的,慢的话,有 10min 一个碰撞的

结果

[+]Finding Collision...
  [-]The M1 is: 98d46138c68cc81d7cc12c9a82cf0b577b88416accb0fff4b9aa434e86328aed5ab7b751a65c0c672ec4f0172a4020a8df07cffc728072b81e4cd688e16452fc
  [-]The M2 is: 98d46138c68cc89d7cc12c0a82cf0b577b88416accb0fff4b9aa434e86328aed5ab7b751a65c0c672ec4f0172a4020a8df07cefc728072b81e4cd688e16452fc
  [-]M1 and M2 diff:
    [*]98d46138c68c[c81d]7cc1[2c9a]82cf0b577b88416accb0fff4b9aa434e86328aed5ab7b751a65c0c672ec4f0172a4020a8df07[cffc]728072b81e4cd688e16452fc
    [*]98d46138c68c[c89d]7cc1[2c0a]82cf0b577b88416accb0fff4b9aa434e86328aed5ab7b751a65c0c672ec4f0172a4020a8df07[cefc]728072b81e4cd688e16452fc
  [-]The MD4(M1) is: 8e1a0f4554909e76bf4ef7e940bd6a2e
  [-]The MD4(M2) is: 8e1a0f4554909e76bf4ef7e940bd6a2e
[!]M1 == M2 ? False
[!]MD4(M1) == MD4(M2) ? True
[!]All done!
[!]Timer: 5.25 s

M 均经过 hex

总结

  1. 英文文献,看着比较痛苦
  2. 大牛的论文言简意赅,理解论文花了很多时间
  3. 都说 MD4 不安全,有碰撞,别使用,亲身动手实践一遍才知道是什么情况。在搜论文的过程中发现有基于此论文进行对 MD4 有意义的碰撞攻击,实现 2 个有意义的明文 MD4 却一样,感觉这个更好玩,可惜没太看懂实现

End

What do you think?

本文标题: MD4 Collision
原始链接: http://www.tr0y.wang/2017/10/29/MD4Collision/
发布时间: 2017.10.29-16:50
最后更新: 2018.11.03-20:49
版权声明: 本站文章均采用CC BY-NC-SA 4.0协议进行许可。转载请注明出处!