How to Break MD5 and Other Hash Functions

阅读说明

个人论文阅读报告留档：总结发表于 EUROCRYPT 2005 的论文 How to Break MD5 and Other Hash Functions，介绍基于模差的 MD5 碰撞攻击、充分条件与信息修改技术，并简述对 MD4 等函数的适用性。

论文信息

Title: How to Break MD5 and Other Hash Functions
Venue: EUROCRYPT 2005
Author(s): Xiaoyun Wang, Hongbo Yu
Institution(s): Shandong University
Link: Springer PDF

引言#

MD5（Message Digest 5）由 Ron Rivest 于 1992 年提出，是对 MD4 的加强。作为长期广泛使用的密码哈希函数之一，其安全性一直受到关注。此前较著名的结果多为伪碰撞或 semi-free-start collision（将标准初值换成非标准初值）。Wang & Yu¹ 提出一种真正的两块消息碰撞攻击：以模整数减法（而非异或）度量差分，称为模差（modular differential）。在 IBM P690 上，找第一块消息对大约需 15 分钟到 1 小时；第二块约 15 秒到 5 分钟。同一思路也可用于 MD4、RIPEMD、HAVAL 等。

数字签名、完整性校验、群签名、电子现金等应用都依赖底层哈希的抗碰撞能力。当时国际通用哈希以 MD5 与 SHA-1 为代表。1993 年，Den Boer 与 Bosselaers 给出伪碰撞（相同消息、不同初值），暴露了链接变量最高位的弱雪崩。Eurocrypt’96 Rump Session 上，Dobbertin 给出 semi-free-start collision，所用非标准初值为：

a_0=\texttt{0x12ac2375},\quad b_0=\texttt{0x3b341042},\quad c_0=\texttt{0x5f62b97c},\quad d_0=\texttt{0x4ba763ed}

虽未得到标准初值下的真碰撞，但说明在一次压缩中构造特殊差分是可能的。受此启发，本文关心：能否找到由两块组成的消息对 $(M_0,M_1)$ 与 $(M_0',M_1')$ ，使第二块之后发生 MD5 碰撞，即

\begin{aligned} (a,b,c,d)&=\mathrm{MD5}(a_0,b_0,c_0,d_0,M_0), \\ (a',b',c',d')&=\mathrm{MD5}(a_0,b_0,c_0,d_0,M_0'), \\ \mathrm{MD5}(a,b,c,d,M_1)&=\mathrm{MD5}(a',b',c',d',M_1'), \end{aligned}

其中 $a_0,b_0,c_0,d_0$ 为 MD5 标准初值。相对此前方法，找 $(M_0,M_0')$ 约需 $2^{29}$ 次 MD5 运算，找 $(M_1,M_1')$ 约需 $2^{32}$ 次（后文在计入信息修改开销时，也将第一块搜索复杂度表述为不超过 $2^{39}$ ）。所得碰撞实例（见表 2）曾在 Crypto’04 Rump Session 公布。同届会议上还有 Biham–Chen 对 SHA-0 的近碰撞、Joux 对 SHA-0 的四块完全碰撞等工作。

全文组织如下：MD5 算法简述 → 差分攻击思想 → MD5 上的差分攻击 → 总结，附录为原文表 1–6 截图。

MD5 算法简述#

哈希通常由压缩函数 $X=f(Z)$ 迭代得到（Merkle–Damgård 结构）。压缩函数把长度为 $l$ 的消息块映射到长度为 $s$ 的摘要（ $l>s$ ）。对 MD5， $l=512$ ， $s=128$ 。填充后长度为 512 比特倍数的消息 $M=(M_0,\ldots,M_{t-1})$ 满足

H_{i+1}=f(H_i,M_i),\qquad 0\leq i\leq t-1,

初值 $H_0=IV_0$ 。本文攻击所用消息恰为两块（长度已是 512 的倍数），填充与否不影响结论。

每个 $M_i$ 拆成 16 个 32 比特字 $M_i=(m_0,\ldots,m_{15})$ 。压缩函数分 4 个阶段（round），每阶段 16 步；连续四步形如

\begin{aligned} a&=b+\bigl((a+\phi_i(b,c,d)+w_i+t_i)\lll s_i\bigr), \\ d&=a+\bigl((d+\phi_{i+1}(a,b,c)+w_{i+1}+t_{i+1})\lll s_{i+1}\bigr), \\ c&=d+\bigl((c+\phi_{i+2}(d,a,b)+w_{i+2}+t_{i+2})\lll s_{i+2}\bigr), \\ b&=c+\bigl((b+\phi_{i+3}(c,d,a)+w_{i+3}+t_{i+3})\lll s_{i+3}\bigr), \end{aligned}

其中 $+$ 为模 $2^{32}$ 加法， $t_{i+j}$ 、 $s_{i+j}$ 为与步数相关的常数， $w_{i+j}$ 为消息字， $\lll$ 表示循环左移。四阶段非线性函数分别为

\begin{aligned} \phi_i(X,Y,Z)&=(X\land Y)\lor(\lnot X\land Z), & 0&\leq i\leq 15, \\ \phi_i(X,Y,Z)&=(X\land Z)\lor(Y\land\lnot Z), & 16&\leq i\leq 31, \\ \phi_i(X,Y,Z)&=X\oplus Y\oplus Z, & 32&\leq i\leq 47, \\ \phi_i(X,Y,Z)&=Y\oplus(X\lor\lnot Z), & 48&\leq i\leq 63. \end{aligned}

链接变量初值为

a=\texttt{0x67452301},\quad b=\texttt{0xefcdab89},\quad c=\texttt{0x98badcfe},\quad d=\texttt{0x10325476}.

记上一块输出为 $H_{i-1}=(aa,bb,cc,dd)$ ，经四阶段后再与 $H_{i-1}$ 逐字相加，得到本块压缩输出 $H_i$ 。

差分攻击思想#

模差与异或差#

差分攻击是分析哈希与分组密码的重要手段；分组密码中常见以异或为差分。Biham 与 Shamir 对 DES 类算法的差分密码分析，考察明文对特定差分如何影响密文对差分。

本文采用基于整数模减法的精确差分，并结合模特征同时描述异或差与模差，以获得比单独使用任一度量更丰富的信息。

例如未知量 $X$ 满足 $X'-X=2^6$ 时，异或差可有多种情形：

仅第 7 位不同：异或为 $\texttt{0x00000040}$ ， $X'$ 与 $X$ 该位为 $1$ 与 $0$ ；
第 7 位向第 8 位借位：异或为 $\texttt{0x000000c0}$ ，两比特模式分别为 $10$ 与 $01$ ；
继续向第 9 位借位：异或为 $\texttt{0x000001c0}$ ，模式为 $100$ 与 $011$ ；
更长连续借位时， $X'$ 与 $X$ 分别呈 $1000\ldots$ 与 $0111\ldots$ ；
若模差为负，异或绝对值可相同，但 $X'$ 与 $X$ 的比特模式对调。

表示上，常同时给出模 $2^{32}$ 的整数差，以及带符号的比特位置序列：某位在 $X$ 上为 $0$ 则无符号，为 $1$ 则标负号。例如模差 $-2^6$ 可记为 $[7,8,\ldots,22,-23]$ ，表示从第 7 位借到第 23 位： $X$ 的第 7–22 位为 $0$ 、第 23 位为 $1$ ，而 $X'$ 相反。更复杂的例子如 $-1-2^6+2^{23}-2^{27}$ 对应一长串带符号位置。最高位（第 32 位）也可参与借位；借位后该位本身不再标负号。

相对此前对 SHA-0、MD4、RIPEMD 等的模差分析，本文攻击有以下特点：

消息仅两块（各 512 比特），两次迭代即可碰撞；
差分特征更精确，除差分外还约束具体比特取值；
给出保证差分成立的充分条件；
使用信息修改技术（message modification），显著提高碰撞概率。

哈希上的差分形式#

定义 $\Delta X=X'-X$ 。对长度同为 512 倍数的 $M=(M_0,\ldots,M_{k-1})$ 与 $M'=(M_0',\ldots,M_{k-1}')$ ，完全差分写作

\Delta H_0 \xrightarrow{(M_0,M_0')} \Delta H_1 \xrightarrow{(M_1,M_1')} \cdots \xrightarrow{(M_{k-1},M_{k-1}')} \Delta H,

其中 $\Delta H_0=0$ ， $\Delta H$ 为输出差， $\Delta H_i$ 既是第 $i$ 次迭代输出差，也是下一次迭代初值差。若 $\Delta H=0$ ，则发生碰撞，相应差分称为碰撞差分。

MD5 每次迭代含 4 阶段、每阶段 16 步。第 $i$ 次迭代差分可展开为

\Delta H_i \xrightarrow{P_1} \Delta R_{i+1,1} \xrightarrow{P_2} \Delta R_{i+1,2} \xrightarrow{P_3} \Delta R_{i+1,3} \xrightarrow{P_4} \Delta R_{i+1,4}=\Delta H_{i+1}.

各阶段再拆成 16 步差分特征，概率满足

P\geq\prod_{j=1}^{4}P_j,\qquad P_j\geq\prod_{t=1}^{16}P_{jt}.

更优碰撞差分的选取思路#

借助信息修改，可粗略指导如何寻找更好的（碰撞）差分：

对任意块对 $(M_i,M_i')$ 与第一阶段非零差分 $\Delta H_i\to\Delta R_{i+1,1}$ ，可修改 $M_i$ 使 $P_1=1$ ；
多重信息修改还能在保持 $P_1=1$ 的同时显著提高第二阶段概率。

因此宜选取能使后两阶段仍以较高概率成立的消息差分。

MD5 上的差分攻击#

记号#

$M=(m_0,\ldots,m_{15})$ 、 $M'=(m_0',\ldots,m_{15}')$ 为两块 512 比特消息； $\Delta m_i=m_i'-m_i$ 。
$a_i,b_i,c_i,d_i$ 分别表示第 $4i-3,4i-2,4i-1,4i$ 步的输出（ $1\leq i\leq 16$ ）；带撇号者为对应 $M'$ 的量。
$a_{i,j}$ 等表示字的第 $j$ 位（第 1 位为最低位，第 32 位为最高位）。
$\phi_{i,j}$ 为第 $i$ 步非线性函数输出的第 $j$ 位。
$x_i[j]$ （ $x_i[-j]$ ）表示仅将 $x_i$ 第 $j$ 位由 $0\to 1$ （或 $1\to 0$ ）后的取值； $x$ 可为 $a,b,c,d,\phi$ 。
$x_i[\pm j_1,\ldots,\pm j_l]$ 表示若干指定位同时翻转； $+$ 可省略，表示 $0\to 1$ ， $-$ 表示 $1\to 0$ 。

MD5 的碰撞差分#

在标准初值 $IV_0$ 下，寻找两段各 1024 比特的消息对，使

\Delta H_0 \xrightarrow{(M_0,M_0')} \Delta H_1 \xrightarrow{(M_1,M_1')} \Delta H=0,

其中

\begin{aligned} \Delta M_0&=(0,0,0,0,2^{31},0,0,0,0,0,0,2^{15},0,0,2^{31},0), \\ \Delta M_1&=(0,0,0,0,2^{31},0,0,0,0,0,0,-2^{15},0,0,2^{31},0), \\ \Delta H_1&=(2^{31},\,2^{31}+2^{25},\,2^{31}+2^{25},\,2^{31}+2^{25}). \end{aligned}

非零差分落在下标为 $4$ 、 $11$ 、 $14$ 的字上（即第 5、12、15 个字，从 0 计数）。 $\Delta H_1=(\Delta a,\Delta b,\Delta c,\Delta d)$ 为第一块压缩后链接变量之差。 $\Delta M_0$ 需使第 3、4 阶段差分以较高概率成立； $\Delta M_1$ 还须使输出差被 $\Delta H_1$ 抵消。

完整差分特征见表 3 与表 5（列含义相同）。表 3 各列依次为：步数； $M_0$ 上该步链接变量；该步消息字；循环左移位数； $M_0$ 与 $M_0'$ 的消息字 / 链接变量差分； $M_0'$ 的链接变量。空白表示无差分；完全无差分的步省略。

充分条件（以第 8 步为例）#

下面以表 3 中第 8 步为例，说明如何导出保证差分特征成立的充分条件。该步差分形为

(\Delta c_2,\Delta d_2,\Delta a_2,\Delta b_1)\longrightarrow\Delta b_2,

且

\begin{aligned} b_1'&=b_1, \\ a_2'&=a_2[7,\ldots,22,-23], \\ d_2'&=d_2[-7,24,32], \\ c_2'&=c_2[7,8,9,10,11,-12,-24,-25,-26,27,28,29,30,31,32,1,2,3,4,5,-6], \\ b_2'&=b_2[1,16,-17,18,19,20,-21,-24]. \end{aligned}

由压缩函数，

\begin{aligned} b_2&=c_2+\bigl((b_1+F(c_2,d_2,a_2)+m_7+t_7)\lll 22\bigr), \\ b_2'&=c_2'+\bigl((b_1+F(c_2',d_2',a_2')+m_7'+t_7)\lll 22\bigr), \\ \phi_7&=F(c_2,d_2,a_2)=(c_2\land d_2)\lor(\lnot c_2\land a_2). \end{aligned}

为区分右端两次出现的 $c_2$ ，记 $c_2^F$ 为 $F$ 内的 $c_2$ ， $c_2^{NF}$ 为 $F$ 外的 $c_2$ 。推导基于：

$\Delta b_1=0$ 且 $\Delta m_7=0$ 时， $\Delta b_2=\Delta c_2^{NF}+(\Delta\phi_7\lll 22)$ ；
固定 $F$ 的一个或两个自变量后， $F$ 可退化为单变量函数。

据此可列出使差分保持的充分条件。对 $\Delta b_2$ 的非零位：

(a) $d_{2,11}=1$ 、 $b_{2,1}=0$ 时，可保证 $b_2$ 第 1 位翻转。若再有 $d_{2,11}=\overline{a_{2,11}}=1$ ，则 $\Delta\phi_{7,11}=1$ ；左移 22 位后该差落在第 1 位；又 $\Delta c_{2,1}^{NF}=0$ ，故 $\Delta b_{2,1}=1$ 。
(b) $d_{2,26}=\overline{a_{2,26}}=1$ 、 $b_{2,16}=0$ 且 $b_{2,17}=1$ 时，可保证第 16、17 位翻转。
(c) $d_{2,28}=\overline{a_{2,28}}=0$ ， $b_{2,i}=0$ （ $i=18,19,20$ ）且 $b_{2,21}=1$ 时，可保证第 18–21 位翻转。
(d) $d_{2,3}=\overline{a_{2,3}}=0$ 、 $b_{2,24}=1$ 时，可保证第 24 位翻转，并有

\Delta c_2^{NF}[-24,-25,-26,27]+(\Delta\phi_7[3]\lll 22)=2^{23}-2^{24}=-2^{23}.

对 $\Delta b_2$ 的零位：

(a) $c_{2,17}=0$ 时，可允许 $(c_2')^{NF}$ 第 7、12 位与 $a_2'$ 第 17 位变化而 $b_2$ 不变：

\Delta c_2^{NF}[7,\ldots,11,-12]+(\Delta\phi_7[17]\lll 22)=-2^6+2^6=0.

(b) $d_{2,i}=a_{2,i}$ （ $i\in\{1,2,4,5,25,27,29,30,31\}$ ）时， $c_2^F$ 第 $i$ 位可变而 $b_2$ 不变。
(c) $c_{2,i}=1$ （ $i\in\{13,\ldots,16,18,\ldots,23\}$ ）时， $a_2$ 第 $i$ 位可变而 $b_2$ 不变。
(d) $d_{2,6}=\overline{a_{2,6}}=0$ 时， $c_2^F$ 第 6 位可变而 $b_2$ 不变。
(e) $a_{2,32}=1$ 时， $c_2^F$ 与 $d_2$ 第 32 位可变而 $b_2$ 不变。
(f) $d_{2,i}=0$ （ $i\in\{8,9,10\}$ ）时， $a_2$ 与 $c_2^F$ 第 $i$ 位可变而 $b_2$ 不变。
(g) $d_{2,12}=1$ 时， $a_2$ 与 $c_2^F$ 第 12 位可变而 $b_2$ 不变。
(h) $a_{2,24}=0$ 时， $c_2^F$ 与 $d_2$ 第 24 位可变而 $b_2$ 不变。
(i) $c_2^F$ 、 $d_2$ 、 $a_2$ 第 7 位同时变化时， $b_2$ 仍可不变。

其余步的充分条件可用同样方式推出。

信息修改#

单一信息修改。通过改消息字可提前满足部分充分条件。对 $M_0$ （或 $M_1$ ）及相应中间链接值，可修改消息使表 4、表 6 中第一阶段（前 16 步）条件几乎必然成立。例如为满足表 4 中 $c_1$ 的三个条件，可令

\begin{aligned} c_1^{\mathrm{new}}&\leftarrow c_1^{\mathrm{old}}-c_{1,7}^{\mathrm{old}}\cdot 2^6-c_{1,12}^{\mathrm{old}}\cdot 2^{11}-c_{1,20}^{\mathrm{old}}\cdot 2^{19}, \\ m_2^{\mathrm{new}}&\leftarrow\bigl((c_1^{\mathrm{new}}-c_1^{\mathrm{old}})\ggg 17\bigr)+m_2^{\mathrm{old}}. \end{aligned}

对 $M_0$ 各字做完修改后，第一阶段条件成立，第一块差分概率约为 $2^{-43}$ ；对 $M_1$ 类似修改后，第二块约为 $2^{-37}$ 。

多重信息修改。还可满足部分前 32 步条件。例如若 $a_{5,32}=1$ ，可改 $m_1,\ldots,m_5$ 使其变为 $0$ ，从而在第 2–6 步形成局部碰撞且不破坏第一阶段条件（见表 1）。之后表 4 第 2–4 阶段约剩 37 个未定条件，表 6 约剩 30 个，故两块差分概率分别约为 $2^{-37}$ 与 $2^{-30}$ 。

攻击流程#

目标是实现

\Delta H_0 \xrightarrow{(M_0,M_0'),\,2^{-37}} \Delta H_1 \xrightarrow{(M_1,M_1'),\,2^{-30}} \Delta H=0.

重复直至找到 $M_0$ ：随机取 $M_0$ → 信息修改 → 令 $M_0'=M_0+\Delta M_0$ 检验第一块差分（概率约 $2^{-37}$ ）→ 用压缩函数核对特征。
重复直至碰撞：随机取 $M_1$ → 信息修改 → 用 $M_1$ 与 $M_1+\Delta M_1$ 检验第二块差分（概率约 $2^{-30}$ ）→ 检查是否碰撞。

实现上， $M_0'$ 只需改 $M_0$ 最后两字；前 14 字的单一修改开销可忽略。对每个候选 $M_0$ ，约需对最后两字各做一次单一修改，并在第二阶段做约 7 次多重修改，总时间不超过约两次 MD5。计入这些后，搜索 $(M_0,M_0')$ 的复杂度不超过约 $2^{39}$ 次 MD5。

表 2 给出两个碰撞实例：二者第一块完全相同；一旦第一块满足条件，第二块通常很容易找到。

总结#

上述模差方法使寻找 MD5 碰撞变得现实可行，并可用于其它哈希。论文给出的粗略复杂度如下（不含 / 含多重信息修改）：

MD4：约 $2^{23}$ / $2^{8}$ 次 MD4；
HAVAL-128：约 $2^{13}$ / $2^{7}$ 次；
RIPEMD：约 $2^{30}$ / $2^{18}$ 次；
SHA-0：约 $2^{61}$ / $2^{45}$ 次。

附录：原文表格截图#

图表说明

下列截图依次对应正文中的表 1–6（信息修改示例、碰撞实例、差分特征与充分条件等）。

参考文献#

Xiaoyun Wang, Hongbo Yu. How to Break MD5 and Other Hash Functions. EUROCRYPT 2005. ↩

音乐

音乐

引言#

MD5 算法简述#