MD4 Collision

利用王小云的论文实现 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 形成碰撞

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
#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 一个碰撞的

结果

1
2
3
4
5
6
7
8
9
10
11
12
[+]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 却一样，感觉这个更好玩，可惜没太看懂实现

    来呀快活呀

过程记录
#Python #密码学
MD4 Collision
https://www.tr0y.wang/2017/10/29/MD4Collision/
作者
Tr0y
发布于
2017年10月29日
更新于
2024年6月3日
许可协议