Skip to main content
  1. Posts/

短兵相接: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 碰撞攻击 #

攻击分为三步:

  1. 构造一对差分 M 与 M'
  2. 由此生成充分条件
  3. 对随机消息 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 $$

  1. F 函数引理 1,为了让 $b_2$ 第 13 位和 15 位上的变化不影响 $a_3$,我们可以令 $c_2$ 和 $d_2$ 在第 13 和 15 位上相等。

  2. F 函数引理 2,为了让 $c_3$ 第 19-22 位上的变化不影响 $a_3$,我们可以令 $b_2$ 第 19-22 位全部为 0。

  3. 由 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}$。

  4. 我们最后令 $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);

这里仅给出了核心代码,不过理解了核心代码,其余细节也迎刃而解了。总的来说,理解这篇论文还是颇有难度的,从理解原理到代码实现也仍有很长一段距离。