对MD5攻击的研究:思考和改进

| categories notes 
tags cryptography 

原文:https://www.iacr.org/archive/fse2006/40470265/40470265.pdf

2. 符号说明

所有的索引都从0开始。这和王的原始论文不同。

在这种表示下,4-byte无符号整数 $x$ 从0到32标记,0表示最低符号位。

${0, 1}^n$ 表示n位二进制串的集合。令 $\sum^\ast$ 表示所有 $\sum$ 中元素组成的串的集合, $\sum^+ = \sum^\ast - {\epsilon}$ ,其中 $\epsilon$ 表示空串。

对于串 $s, t$ ,令 $s||t$ 表示 $s, t$ 的连接。

令 $|s|$ 表示 $s$ 的长度。如果 $|s|$ 是 $n$ 的倍数,令 $|s|_n$ 表示 $|s|/n$ 。

给定串 $s, t$ 有 $|s| = |t|$ ,则令 $s \oplus t$ 表示 $s$ 和 $t$ 按位异或。

对于串 $M$ 有 $|M|_n = k$ ,我们将使用这种表示方法: $M = (M_0, M_1, M_2, … , M_{k-1})$ ,其中 $|M_0| = |M_1| = |M_2| = … = |M_{k-1}| = n$ 。 $n = |m_i| = 32$ 时,我们使用小写符号表示: $M = (m_0, m_1, m_2, … , m_{k-1})$ 进行表示。 $n = |M_i| = 512$ 时我们使用大写符号表示。

方便起见,我们认为 $M$ 是一个k-元组。

一般符号 $M$ 表示 $({0, 1}^{512})^+$ 中的元素。

对于集合 $S = {A_i\ : a \le i \le b}$ 我们通常用 $A_{a:b}$ 表示。

异或差分 VS. 减法差分 。破解方法使用了这两种差分的结合。但是主要使用的是减法差分。

简单来说,对于两个整数 $x, x^\prime \in [0, 2^{31} - 1]$ ,考虑函数 $\Delta_X(x, x^\prime) = x \oplus x^\prime$ , $\Delta_S(x, x^\prime) = x - x^\prime \mod 2^{32}$ 。

作者在表中用两列分别展示了每一步的异或差分和减法差分,但是比特差分还表达了额外的信息。

例如 $\Delta_S(x, x^\prime) = 2^2$,符合条件的异或差分有很多种可能,例如下面的三种:

  • $\Delta_X(x, x^\prime) = \mathrm{0x00000004}$ (只在 bit 2 有一个比特的差异)
  • $\Delta_X(x, x^\prime) = \mathrm{0x0000000c}$ ( bit 3 在 $x^\prime$ 中置位但没在 $x$ 置位,bit 2 在 $x$ 中置位而没在 $x^\prime$ 中置位)
  • $\Delta_X(x, x^\prime) = \mathrm{0x0000fffc}$ ( bit 15 在 $x^\prime$ 中置位但没在 $x$ 置位,bit 2-14 在 $x$ 中置位而没在 $x^\prime$ 中置位)

令 $x \in [0, 2^{31} - 1]$ ,则 $x^\prime = x[a_1, a_2, …, a_n, -b_1, -b_2, …, -b_m]$ ,即 $x^\prime = x + 2^{a_1} + 2^{a_2} + … + 2^{a_n} - 2^{b_1} - 2^{b_2} … - 2^{b_m} \mod 2^{32}$ 。从中我们可以完全确定 $\Delta_X(x, x^\prime)$ 和 $\Delta_S(x, x^\prime)$ 。只有当 $x$ 和 $x^\prime$ 的第 $i$ 位不同时,我们才把 $i$ 写出来。

3. MD5 算法

如下简要的介绍了本文中将用于攻击的MD5算法。我们忽略算法中的消息拓展,因为它对我们的攻击没有影响。

MD5是一种使用Merkle–Damgård范式的哈希函数,而哈希函数的安全性取决于他的压缩函数。我们用 $MD5_c$ 表示MD5的哈希函数。$MD5_c$ 接收一个128-bit长的链值 $CV$ 和一个512-bit的消息块 $M$ ,输出一个128-bit长的链值 $CV^\prime$ 。我们将 $CV$ 其分为四个32-bit的值 $cv_0, cv_1, cv_2, cv_3$ 。

有 $MD5_c : {0, 1}^{128} \times {0, 1}^{512} \to {0, 1}^{128}$ 。令 $H_0 \in {0, 1}^{128}$ ,$M = (M_0, M_1, … , M_k)$ ,其中 $k \ge 0$ 。 $|M_i| \in {0, 1}^{512}$ ,其中 $0 \le i \le k$ 。令 $H^{i+1} = MD5_c(H_i, M_i)$ 其中 $0 \le i \le k$ 。 $ MD5(M) $ 即为 $H_{k+1}$ 。

3.1 压缩函数

压缩函数中有64个中间值,我们称之为单步值,用 $Q_i$ 表示,其中 $0 \le i \lt 64$ 。单步值用如下公式得出:

其中 $s_i, y_i$ 为每步特定的常量,$w_i$ 为输入值中的第 $i$ 块,$w_i = m_j(0 \le i \lt 64, 0 \le j \lt 16)$ 。

我们用 ‘$x + y$’ 表示 $x + y \mod 2^{32}$ , 用 ‘$x \lll y$’ 表示 $x$ 向左循环移 $y$ 位。

$\Phi$ 函数定义如下:

$Q_{-1}, .. Q_{-4}$ 分别为

初始链值为

所有64步运行完毕,$MD5_c$ 的计算出

最后输出 $CV^\prime \gets cv^\prime_0||cv^\prime_1||cv^\prime_2||cv^\prime_3$ 。

对于每个消息块,$MD5_c$ 有4轮(round),每轮计算16个单步值(step value)。

4. 高度概括

定义 $\delta_0$ 为 $(0, 0, 0, 0, 2^{31}, 0, 0, 0, 0, 0, 0, 2^{15}, 0, 0, 2^{31}, 0)$ ,$\delta_1$ 为 $(0, 0, 0, 0, 2^{31}, 0, 0, 0, 0, 0, 0, -2^{15}, 0, 0, 2^{31}, 0)$ 。令 $M = (M_0, M_1)$ 为1024-bit的串,$|M_0| = |M_1| = 512$ ,对于所有的 $M$ ,令 $M_0^\prime = M_0 + \delta_0, M_1^\prime = M_1 + \delta_1, M^\prime = (M_0^\prime, M_1^\prime)$ ,其中加法运算mod $2^{32}$ 。

王的攻击阐述了一种通过跟踪单步值的差分的方式,找到一个1024-bit的串,使得 $MD5(M) = MD5(M^\prime)$ 。

令 $Q_i$ 表示输入 $M$ 的第 $i$ 个周的输出值,$Q_i^\prime$ 表示输入 $M^\prime$ 的第 $i$ 个周的输出值。王的论文提供了128个中间值(第一个块的64个值和第二个块的64个值) $a_i(0 \le i \le 128)$ 。如果他们的方法找到了一个 $M$ 令 $MD5(M) = MD5(M^\prime)$ ,那么所有计算 $MD5_c(M_0)$ 和 $MD5_c(M_0^\prime)$过程中的 $Q_i$ 满足 $Q_i^\prime - Q_i = a_i$ ,所有计算 $MD5_c(M_1)$ 和 $MD5_c(M_1^\prime)$过程中的 $Q_i$ 满足 $Q_i^\prime - Q_i = a_{i+64}$ 。我们称这个值为 $Q_i^\prime - Q_i$ 差分。$a_i$ 称为正确差分或预定义差分。

进一步的,王的论文给出了4组额外的值表示中间链值的差分。

没有任何文献说明了王是如何选择这些 $a_i$ 的值的。下一章我们将阐述一些关于这点的猜测。王的方法通过使得 $Q_i$ 满足特定条件来保证有较大的概率碰撞,但是没有给出多少关于如何获取这些条件的方法。不过 Hawkes, Paddon, and Rose 的论文给出一个令人惊喜的分析。

王的搜寻 $M$ 方法可以通过如下伪代码表示:

如果没有发现碰撞:

  1. 用一个随机的种子和特定的一组方法来找到一个 $M$ 来使得 $Q_i$ 满足尽可能多的条件。
  2. 计算所有的 $Q_i$ 和 $Q_i^\prime$ 来检查差分是否满足
  3. 如果所有差分都正确,那么就找到一个碰撞了,结束。
  4. 否则继续。

如上步骤对 $M$ 中的每个块重复进行。先找满足条件的 $M_0$ ,然后找满足条件的 $M_1$ 。

4.1 寻找差分和条件

生成消息差分。消息的划分和单步差分的选择,目前还没有解释。我们这里尝试进行猜测。

我们开始注意到如下三件事:

  • 第二轮末尾和第三轮开头的一些单步值的差分为0
  • 第三轮的$\Phi$函数简单的对输入异或,因此是线性的。输入的每一位的改变,都将导致输出的对应位的改变。相关联的,如图一所示,$\Phi_i(0 \le i \lt 32)$ 有一些有趣的属性,即输入改变某些位并不会导致输出改变。
  • 第三和第四轮汇总,几乎所有单步值的差分都为 $2^{31}$

在继续分析之前,我们稍作离题,来回答这样一个问题:bit 31的差分在第三轮是如何传播的?第二轮的最后几步保持了0差分,随后的第一个出现的差分出现在第三轮的34步中:

(省略原文的公式。简单而已,作者通过对每一步计算的布尔表达式的求解,证明了在上述前提下,后续的差分只会表现在bit 31,不会引入其它位的差分。也就是说,通过精心构造的条件,如果能够保证在第三轮之前差分为0,后面的步骤较为容易保持较小的差分)

If you liked this post, you can share it with your followers !