短兵相接：MD4 碰撞攻击
目录
重复了王小云教授 14 年前的工作，RIPEMD/MD5/SHA 家族碰撞原理类似。
课程《Hash 函数安全性分析》要求我们基于王小云教授在 2005 年欧密会上发表的 Cryptanalysis of the Hash Functions MD4 and RIPEMD，实现对 MD4 函数的碰撞攻击。所谓 MD4 函数，就是大名鼎鼎的 MD5 函数的前身，后者相较于前者更为安全（尽管也同样被王小云教授找到了碰撞攻击的方法）。值得一提的是，MD4 和 MD5 的发明者是 Ronald Rivest，也就是 RSA 中的‘R’。
本文可以看作是对这篇著名论文的中文概述，其中混杂了一些个人在构筑代码时的简略思路。
MD4 算法介绍 #
MD4 是将任意长度的消息压缩为 128bit 的一种单向散列函数。MD4 先将消息填充至其长度为 512bit 的整数倍（即使消息原长已经是 512bit 的整数倍），随后将填充后的消息压缩至 128bit。由于填充消息的方法与 MD4 碰撞无关，这里不再赘述，我们只关注压缩消息的方法。
为了阐释 MD4 压缩函数的步骤，首先定义三个函数：
$$ F(X,Y,Z) = (X\land Y)\lor (\lnot X\land Z)\\ G(X,Y,Z) = (X\land Y)\lor (X\land Z)\lor (Y\land Z)\\ H(X,Y,Z) = X\oplus Y\oplus Z $$
其中 X,Y,Z 都是 32bit 的字（注意到在 C++ 中，unsigned int 可以很好地表示它们）。压缩函数共 3 轮，每轮有 16 步操作，每次操作都会更新链接变量 a,b,c,d 之一。更新时需要用到这三个函数：
$$ \phi_0(a,b,c,d,m_k,s) = ((a + F(b,c,d) + m_k)\ mod\ 2^{32})\lll s\\ \phi_1(a,b,c,d,m_k,s) = ((a + G(b,c,d) + m_k + 0x5a827999)\ mod\ 2^{32})\lll s\\ \phi_2(a,b,c,d,m_k,s) = ((a + H(b,c,d) + m_k + 0x6ed9eba1)\ mod\ 2^{32})\lll s $$
而 a,b,c,d 的初始值定义为：
$$ (a,b,c,d) = (0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476) $$
这里的 4 个 16 进制数，以及上面 $\phi_1$ 和 $\phi_2$ 式中的 2 个 16 进制数，都是可以任意选取的。
MD4 压缩函数 #
记填充后的消息为 $\bar{M}$，对 $\bar{M}$ 中的任一 512bit 块 $M$，将其划分为 16 个 32bit 字 $(m_0, m_1, …, m_{15})$。同时，定义 $(aa,bb,cc,dd)$ 为链接变量，也就是上一消息块经过压缩后的输出，或者说压缩本消息块所用到的输入。在第一轮，链接变量的值就是上述 a,b,c,d 的初始值。
压缩函数的主体是三轮，或者说 48 步运算：
$$ \text{For\ j = 0,1,2\ and\ i = 0,1,2,3}\\ a = \phi_j(a,b,c,d,w_{j,4i},s_{j,4i})\\ d = \phi_j(d,a,b,c,w_{j,4i+1},s_{j,4i+1})\\ c = \phi_j(c,d,a,b,w_{j,4i+2},s_{j,4i+2})\\ b = \phi_j(b,c,d,a,w_{j,4i+3},s_{j,4i+3}) $$
这里的 w 是消息字，s 是循环左移的位数。压缩函数的最后一步意外简单，将计算得到的链接变量 a,b,c,d 加到输入的链接变量 aa,bb,cc,dd 上：
$$ 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$ 是最后一个消息块，那么 $H(\bar{M}) = aa|bb|cc|dd$，否则用 $(aa,bb,cc,dd)$ 作为下一个消息块的输入链接变量。
注意到这里的四个表达式和上面的三个 $\phi$ 系列表达式都含有 $mod\ 2^{32}$ 这个特殊的模运算。从 01 串的角度看，这个运算相当于截取该串的低 32 位。而由上述分析我们已知，参与运算的 a,b,c,d、F/G/H 函数的输出、以及 $m_k$ 都是 32bit 的 01 串，或者说 unsigned int。这构成了一个美妙的巧合，那就是：在利用 unsigned int 进行四则运算时默认自动丢弃溢出的位，而这与 $mod\ 2^{32}$ 的效果完全一致！
当然，实际上这并不是巧合。
引理与记号 #
下面给出的定理都只涉及位运算，逻辑十分简单，却是后面推导充分条件的关键所在。
F 函数引理 #
$$ F(x,y,z) = F(\lnot x,y,z)\ \text{iff}\ y=z\\ F(x,y,z) = F(x,\lnot y,z)\ \text{iff}\ x=0\\ F(x,y,z) = F(x,y,\lnot z)\ \text{iff}\ x=1 $$
G 函数引理 #
$$ G(x,y,z) = G(\lnot x,y,z)\ \text{iff}\ y=z\\ G(x,y,z) = G(x,\lnot y,z)\ \text{iff}\ x=z\\ G(x,y,z) = G(x,y,\lnot z)\ \text{iff}\ x=y $$
H 函数引理 #
$$ H(x,y,z) = \lnot H(\lnot x,y,z) = \lnot H(x,\lnot y,z) = \lnot H(x,y,\lnot z)\\ H(x,y,z) = H(\lnot x,\lnot y,z) = H(x,\lnot y,\lnot z) = H(\lnot x,y,\lnot z) $$
记号 #
下文中只有一个记号是不怎么常见的，那就是 $x_i[\pm j_1,\pm j_2,…,\pm j_l]$，它表示改变 $x_i$ 的第 $j_1,j_2,…,j_l$ 位后得到的 01 串。正号表示将该位从 0 变成 1，负号相反。
等价转换方法 #
在原文中，为了说明这种方法作者举了一个简单的例子，对于：
$$ \Delta c_2 = c_2’- c_2 = -2^{18} + 2^{21} $$
用刚才的记号表示，就是 $c_2’= c_2[-19,22]$。在一些特定的差分路径上需要将其中的单 bit 差分扩展成多 bit 差分，这就需要一种等价转换方法。显然这里 $-2^{18}=2^{18}+2^{19}-2^{20}$，也就是说 $c_2[-19] = c_2[19,20,-21]$。综上：
$$ c_2’= c_2[19,20,-21,22] $$
MD4 碰撞攻击 #
攻击分为三步：
- 构造一对差分 M 与 M'
- 由此生成充分条件
- 对随机消息 M 进行修改来尽可能满足之前的充分条件
差分构造与充分条件推导 #
构造 M 与 M’，使得：
$$ \Delta M = M’- M = (\Delta m_0, \Delta m_1, …, \Delta m_{15})\\ \Delta m_1 = 2^{31},\ \ \Delta m_2 = 2^{31}-2^{28},\ \ \Delta m_{12} = -2^{16}\\ \Delta m_i = 0,\ \ 0\le i\le 15,\ \ i\ne 1,2,12 $$
接下来就是寻找碰撞差分，并根据 F/G/H 函数的上述引理，生成使得差分性质能够被满足的一系列充分条件。只需要尽可能保证这些充分条件成立，即可大幅提高产生碰撞的概率。在论文中，作者在表 5 中给出了碰撞差分的特征，在表 6 中给出了所有充分条件，由于表格较长这里不再搬运。
作者举了一个详细的例子来说明，我们如何生成这样的充分条件。
对于如下变换（表 5 中的第 9 步）：
$$ (b_2[-13,-14,15], c_2[19,20,-21,-22], d_2[14], a_2)\\ \to (a_3[17], b_2[-13,-14,15], c_2[19,20,-21,22], d_2[14]) $$
我们已经知道：
$$ a_3 = ((a_2 + F(b_2, c_2, d_2) + m_8)\ mod\ 2^{32}) \lll 3 $$
由F 函数引理 1，为了让 $b_2$ 第 13 位和 15 位上的变化不影响 $a_3$，我们可以令 $c_2$ 和 $d_2$ 在第 13 和 15 位上相等。
由F 函数引理 2，为了让 $c_3$ 第 19-22 位上的变化不影响 $a_3$，我们可以令 $b_2$ 第 19-22 位全部为 0。
由 F 函数性质，构造 $b_{2,14}=1, d_{2,14}=0, c_{2,14}=0$，这样当 $b_2$ 和 $d_2$ 的第 14 位分别由 1 变 0 和由 0 变 1 时（ $c_2$ 不变），F 函数返回值就会由 0 变 1。也就是说，$F(b_{2,14}, c_{2,14}, d_{2,14}) = 0, F(\lnot b_{2,14}, c_{2,14}, \lnot d_{2,14}) = 1$，再把相应的 i、j 和移位（根据表 5，第 9 步的移位为 3）代入压缩函数的第一个表达式中，就可以得到 $\Delta a_3 = 2^{16}$。
我们最后令 $a_3$ 第 17 位为 0，就可以得到 $a_3’= a_3[17]$。
于是上述 10 个条件足够保证第 9 步的差分性质成立，也就是说这 10 个条件是第 9 步的充分条件。其余每步的充分条件的推导都类似。
消息修改 #
如果没有消息修改，要让 M 与 M’ 碰撞只有 $2^{-122}$ 的概率，还远远不如生日攻击的 $2^{64}$，因此作者提出通过消息修改来尽可能多满足一些充分条件，提升碰撞概率。
多步消息修改的本质在于利用单步消息修改，满足尽可能多的充分条件而不破坏已满足的那些条件。因此其原理与单步消息修改相同，这里不作过多赘述。值得一提的是，多步消息修改可以将碰撞概率提升到 $2^{-6}$ ~ $2^{-2}$，只需要至多 $2^8$ 次 MD4 运算，考虑到 MD4 运算中，填充耗时可忽略，计算时一共只有 48 轮 $\phi$ 函数运算，且 $\phi$ 函数中只用到了位运算与加法运算，该算法找到一对 MD4 碰撞的消息所需要的时间只需用秒来计算。
而单步消息修改的原理是十分简单的：对于任意一个变量 $x$，如果我们希望令 $x$ 的第 $i$ 位为 0，只需要将 $x$ 与 $y$ 异或一下，其中 $y$ 的第 $i$ 位与 $x$ 的第 $i$ 位相同，其余位都为 0。这是由非常简单又非常经典的异或的性质告诉我们的。如果我们希望令 $x$ 的第 $i$ 位为 1，或者希望令 $x$ 和 $z$ 的第 $i$ 位相等，那么原理是相同的。
作者给的例子是关于 $m_1$ 的修改：
$$ d_1\gets d_1\oplus (d_{1,7} \lll 6)\oplus ((d_{1,8}\oplus a_{1,8})\lll 7)\oplus ((d_{1,11}\oplus a_{1,11})\lll 10)\\ m_1\gets (d_1\ggg 7) - d_0 - F(a_1, b_0, c_0) $$
注意此处的 $d_{1,7}$ 指的是：最低位为 $d_1$ 的第 7 位，前 31 位全为 0 的串，也因此需要左移 6 位（似乎不需要循环左移？）。
经过单步消息修改后，碰撞概率提升到了约 $2^{-25}$，这个概率看起来很小，但是经过测试，我发现只需要 $2^{24}$ ~ $2^{27}$ 次 MD4 运算，也就是 4-8 分钟左右就可以找到 MD4 碰撞，不算太慢？尽管如此，多步消息修改在 RIPEMD 和 MD5 的碰撞攻击中的作用，就举足轻重了。
代码实现 #
我觉得 C++ 应该会快一点于是用了 C++ 实现。首先是要定义好数据结构。
其余数据结构，比如存储移位量的数组、存储消息 M 与 M’ 的数组都很容易定义，然而表 6 中的充分条件存储起来却让人很头疼。几经修改后，我采用了如下方式：
...
// Following: {x=0, x=1, x==y}
{{}, {}, {7}}, // a1
{{7}, {}, {8, 11}}, // d1
{{11}, {7, 8}, {26}}, // c1
{{8, 11, 26}, {7}, {}}, // b1
...
对照表 6 应该很好理解。
利用 unsigned 类型存所有链变量和消息块（原因上面已经写了），定义好 FGH 函数，以及循环移位、取特定位等辅助函数，接下来就是实现核心功能了：
class Msg {
public:
Msg() {data = vec_u(16);}
explicit Msg(const vec_u &_data) {data = _data;}
vec_u data;
static unsigned modify(const int &i);
vec_u md4();
void print_val(const char name[], int length);
private:
void round1();
void round2();
void round3();
};
三轮压缩函数很简单，比较难的是消息修改：
unsigned Msg::modify(const int &i) {
unsigned m = e();
chain_var[i] = l_rotate(chain_var[i-4] + F(chain_var[i-1], chain_var[i-2], chain_var[i-3]) + m, shift[i%4]);
for (int j = 0; suf_cond[i][0][j]; ++j)
chain_var[i] ^= bit(chain_var[i], suf_cond[i][0][j]);
for (int j = 0; suf_cond[i][1][j]; ++j)
chain_var[i] ^= bit(~chain_var[i], suf_cond[i][1][j]);
for (int j = 0; suf_cond[i][2][j]; ++j)
chain_var[i] ^= bit(chain_var[i], suf_cond[i][2][j]) ^ bit(chain_var[i-1], suf_cond[i][2][j]);
m = r_rotate(chain_var[i], shift[i%4]) - chain_var[i-4] - F(chain_var[i-1], chain_var[i-2], chain_var[i-3]);
return m;
}
最后在主函数中调用修改：
for (int i = 4; i < 20; ++i)
m.data[i-4] = m_.data[i-4] = Msg::modify(i);
// Construct differential
m_.data[1] += (1<<31);
m_.data[2] += (1<<31);
m_.data[2] -= (1<<28);
m_.data[12] -= (1<<16);
这里仅给出了核心代码，不过理解了核心代码，其余细节也迎刃而解了。总的来说，理解这篇论文还是颇有难度的，从理解原理到代码实现也仍有很长一段距离。