密码分析学 Part 6 of 16

第 6 章：中间相遇攻击

中间相遇攻击 (meet-in-the-middle attack) 最早由 Diffie 和 Hellman 在 1977 年提出，用于分析二重 DES 和三重 DES。通过猜测明文加密到中间状态 \(x\) 的密钥、密文解密到 \(x\) 的密钥，分别求得 \(x\) 的值，若相等就是正确密钥的候选。为降低猜测的密钥量，可以只在 \(x\) 的部分比特上相遇，即部分匹配技术 (partial matching)。现在相遇函数已经从一个固定中间状态的取值，发展为跨越多轮区分器头尾的集合映射关系等多种形式，攻击轮数进一步提高；还可以结合拼切技术 (splice-and-cut) 优化时间复杂度。中间相遇攻击在 AES 等多个对称加密算法和杂凑函数上都取得了很好的结果。

发布于 2026-07-24 7,370 字 · 约 21 分钟

§ 01中间相遇攻击原理

顾名思义，中间相遇就是在算法的“中间”相遇，所以关键问题是相遇位置的选取和“相遇”函数的定义。把分组加密算法分为三部分

\[ C=E(P)=E_2(E_1(E_0(P))), \]

\(P\) 经 \(E_0\) 得中间状态 \(x\)，\(x\) 经 \(E_1\) 得 \(y\)，\(y\) 经 \(E_2\) 得密文 \(C\)：

\[ P\xrightarrow{E_0,\ \mathcal K_0}x\xrightarrow{E_1,\ \mathcal K_1}y\xrightarrow{E_2,\ \mathcal K_2}C. \]

\(E_1\) 对应中间相遇的区分器，相遇函数是与 \((x,y)\) 有关的信息的函数，记为 \(\mathbb G(\mathrm{info}(x),\mathrm{info}(y))\)。（这些信息只要能确定 \(\mathbb G\) 即可，不一定是 \(x\) 或 \(y\) 的全部比特。）

\(E_1\) 可以省略，此时 \(E=E_2\circ E_0\)，\(x=y\)，相遇位置是中间状态 \(x\)，相遇函数往往是 \(x\) 的全部或部分比特的值；
\(E_1\) 也可以是多轮加密，此时相遇位置分别在 \(x\) 和 \(y\)，相遇函数是 \((\mathrm{info}(x),\mathrm{info}(y))\) 之间的某种对应关系。

一般的攻击原理是：猜测相关密钥，对明文加密得到与 \(x\) 有关的信息 \(\mathrm{info}(x)\)（称为向前计算），对密文解密得到与 \(y\) 有关的信息 \(\mathrm{info}(y)\)（称为向后计算），代入 \(\mathbb G\) 看是否匹配。匹配则所猜密钥为正确密钥的候选，否则为错误密钥。

注

这里的“向前”指在加密算法图中计算的方向，与“前向安全”中的“前向”不同。

§ 02相遇函数为值的攻击

这一节讨论 \(E=E_0\circ E_1\)（即省略了中间的区分器），相遇函数为 \(x\) 的全部或部分比特的取值：

\[ P\xrightarrow{E_0,\ \mathcal K_0}x\xleftarrow{E_1^{-1},\ \mathcal K_1}C. \]

2.1 全状态值相遇

先讨论相遇函数为 \(x\) 的取值，即 \(\mathrm{info}(x)=x\)。结合密钥编排，令 \(K_f\)、\(K_b\) 分别为向前计算和向后计算中相互独立的密钥，\(K_j\) 为两者共同使用的密钥。（\(K_f\cup K_j\) 可以不包含 \(\mathcal K_0\) 的全部比特，\(K_b\cup K_j\) 同理。）

设分组长度为 \(n\)，\(|K|\) 为密钥 \(K\) 的比特长度，\(|K_f|+|K_b|+|K_j|=k\)。

定理 2.1算法（相遇函数为 \(x\) 的取值的中间相遇攻击）

输入：\(t\) 个明密文对 \((P_i,C_i)\)，\(i=0,\cdots,t-1\)。输出：正确密钥。

初筛阶段：

对 \(K_j\) 的每个可能取值：
1. 猜测 \(K_f\) 的每个可能取值，由明文 \(P_0\) 根据 \(K_f\cup K_j\) 向前计算 \(x\)，把所有 \(K_f\) 存入以 \(x\) 为索引的表 \(L\)；
2. 对 \(K_b\) 的每个可能取值，由密文 \(C_0\) 根据 \(K_b\cup K_j\) 向后计算 \(x'\)，以 \(x'\) 访问表 \(L\)；
3. 若表 \(L\) 中有 \(x=x'\)，取出相应的 \(K_f\)，把 \((K_f,K_b,K_j)\) 作为正确密钥的候选存入表 \(T\)。

复筛阶段：

对表 \(T\) 中所有 \((K_f,K_b,K_j)\)，分别用 \((P_i,C_i)\)，\(i=1,\cdots,t-1\) 计算 \(x\) 和 \(x'\)，若都相等，则输出为正确密钥。

任一错误密钥满足 \(x=x'\) 的概率为 \(2^{-n}\)，所以初筛后表 \(T\) 中期望有 \(2^{|K_j|}\cdot2^{|K_f|+|K_b|}/2^n=2^{k-n}\) 个候选。复筛阶段先用一个明密文对验证，约剩 \(2^{k-2n}\) 个，再换一个继续筛……整个攻击的时间复杂度为

\[ \underbrace{2^{|K_j|}\cdot\left(2^{|K_f|}+2^{|K_b|}\right)}_{\text{初筛阶段}}+\underbrace{\left(2^{k-n}+2^{k-2n}+\cdots+2^{k-tn}\right)}_{\text{复筛阶段}}.\tag{1} \]

为保证只有正确密钥留下，数据复杂度为 \(t=\lceil k/n\rceil\) 个已知明密文对。（具体分析时，为了平衡复杂度，也可以保留多个候选。）

为降低存储，可以不存入表 \(T\)，每得到一个候选就立即复筛。复筛的过滤概率很高，需要的明密文对很少，于是存储复杂度由表 \(L\) 占主项，为 \(\min(2^{|K_f|},2^{|K_b|})\)（把较小的一边存表即可）。

下面以二重 DES 为例。\(t\) 重加密指同一个分组密码 \(E\) 用多个独立选取的密钥 \(K_0,\cdots,K_{t-1}\) 依次加密。引入这种模式是为了解决 DES 密钥过短、不能满足 20 世纪 90 年代以后安全需求的问题：把 DES 的一次加密变为多次，既节省升级成本，又期望提高安全性。但分析表明并非如此。

定义 2.2二重 DES

明文 \(P\in\{0,1\}^{64}\)，两个相互独立的密钥 \(K_0,K_1\in\{0,1\}^{56}\)，密文为

\[ C=\mathrm{Enc}_{K_1}(\mathrm{Enc}_{K_0}(P)), \]

\(\mathrm{Enc}\) 为 DES 的加密算法。

例 2.3二重 DES 的中间相遇攻击

此时 \(k=56+56=112\)，\(n=64\)，需要 \(\lceil112/64\rceil=2\) 个已知明密文对 \((P_0,C_0)\)、\((P_1,C_1)\)。

对 \(K_0\in\{0,1\}^{56}\) 的每个可能取值，计算 \(x=\mathrm{Enc}_{K_0}(P_0)\)，把 \(K_0\) 存入以 \(x\) 为索引的表 \(L\)；
对 \(K_1\in\{0,1\}^{56}\) 的每个可能取值，计算 \(x'=\mathrm{Enc}^{-1}_{K_1}(C_0)\)，以 \(x'\) 访问表 \(L\)。

若表中存在 \(x=x'\)，得到相应的 \((K_0,K_1)\)，再计算 \(\mathrm{Enc}_{K_0}(P_1)\) 与 \(\mathrm{Enc}^{-1}_{K_1}(C_1)\)，仍相等则输出为正确密钥。

时间复杂度约 \(2^{56}+2^{56}=2^{57}\) 次 DES 加密，即 \(2^{56}\) 次二重 DES 加密；存储复杂度 \(2^{56}\)。

可见二重 DES 的密钥长度增加到 112 比特，安全性却仍与 DES 相当，所以没有被推广。实际中，若算法向前、向后计算的密钥（在一定条件下）存在独立性，就可以分而治之，受到中间相遇攻击的威胁。

习题 2.4

给出三个密钥的三重 DES（\(C=\mathrm{Enc}_{K_2}(\mathrm{Enc}_{K_1}(\mathrm{Enc}_{K_0}(P)))\)）的中间相遇攻击，并分析复杂度。

解

在第一次加密之后相遇：向前只用 \(K_0\)，向后用 \((K_1,K_2)\)。

\[ P\xrightarrow{K_0}x\xleftarrow{K_1}y\xleftarrow{K_2}C. \]

\(k=168\)，\(n=64\)，需要 \(t=\lceil168/64\rceil=3\) 个明密文对。

对 \(2^{56}\) 个 \(K_0\) 计算 \(x=\mathrm{Enc}_{K_0}(P_0)\) 存表；
对 \(2^{112}\) 个 \((K_1,K_2)\) 计算 \(x'=\mathrm{Enc}^{-1}_{K_1}(\mathrm{Enc}^{-1}_{K_2}(C_0))\) 查表；
初筛约剩 \(2^{168-64}=2^{104}\) 个候选，用 \((P_1,C_1)\)、\((P_2,C_2)\) 复筛。

时间复杂度约 \(2^{56}+2\cdot2^{112}\approx2^{113}\) 次 DES 运算，复筛 \(2^{104}\) 量级可忽略；存储 \(2^{56}\)。所以三重 DES 的有效安全强度约为 112 比特，而不是 168 比特。

习题 2.5

设 \(E\) 为密钥长度和分组长度均为 128 比特的分组密码，考虑二重加密 \(\mathrm{Enc}_k(m)=E_{k_2}(E_{k_1}(m))\)，\(k_1,k_2\) 相互独立。假设对大表排序、存储、访问的时间忽略不计。在已知明文攻击下：

给出一种存储复杂度不超过 \(2^{128}\) 字节的密钥恢复攻击，并分析复杂度；（提示：只对 128 比特密钥的部分比特建表。）
给出一种时间复杂度不超过 \(2^{128}\) 次 \(E\) 或 \(E^{-1}\) 运算的密钥恢复攻击，并分析复杂度；（提示：同时利用多个明密文对，增加第一次比较时的限制条件，降低满足条件的候选密钥个数。）
若借助 8000 台计算机同时工作，每台每秒约执行 \(2^{27}\) 次 \(E\) 或 \(E^{-1}\)，可以访问共享存储，估计以上两种攻击所需的时间（以年为单位）。

解

\(k=256\)，\(n=128\)，至少需要 \(t=2\) 个明密文对。

完整的表 \(L\) 有 \(2^{128}\) 项，每项存 16 字节的 \(k_1\)，共 \(2^{132}\) 字节，超了。改为分批：把 \(k_1\) 的前 \(4\) 比特固定为 \(j=0,\cdots,15\)，每批只对剩余 \(124\) 比特建表，每批 \(2^{124}\times16=2^{128}\) 字节。每批都要对所有 \(2^{128}\) 个 \(k_2\) 做向后计算查表。时间 \(16\times(2^{124}+2^{128})\approx2^{132}\) 次运算，存储 \(2^{128}\) 字节，数据 2 个明密文对。
只用一个明密文对时，初筛会留下 \(2^{256-128}=2^{128}\) 个候选，复筛又要约 \(2^{129}\) 次运算，总时间约 \(2^{130}\)。按提示，建表时对 \(k_1\) 同时存 \(E_{k_1}(P_0)\) 和 \(E_{k_1}(P_1)\)，向后计算时只在 \(E^{-1}_{k_2}(C_0)\) 命中后才计算 \(E^{-1}_{k_2}(C_1)\) 并比较。\(2^{128}\) 次命中中的绝大多数在第二个值上被淘汰，留下的错误候选约 \(2^{256-256}=1\) 个，复筛代价可以忽略。总时间为向前 \(2\cdot2^{128}\) 次 \(E\) 加向后约 \(2^{128}+2^{128}\) 次 \(E^{-1}\)。若只要求期望时间，并在建表时按 \(E_{k_1}(P_0)\) 的 128 比特索引，则主项是 \(2^{128}\) 次向前计算加平均 \(2^{127}\) 次向后计算（期望在一半处遇到正确的 \(k_2\)），与提示要求的量级 \(2^{128}\) 相当。代价是存储 \(2^{128}\times(16+16+16)\approx2^{133.6}\) 字节，所以两种攻击是在时间和存储之间折中。
总速率 \(8000\times2^{27}\approx2^{12.97}\times2^{27}=2^{39.97}\) 次/秒，一年约 \(2^{24.9}\) 秒，即每年约 \(2^{64.9}\) 次运算。\(2^{128}\) 次需要约 \(2^{63.1}\approx10^{19}\) 年，\(2^{132}\) 次约 \(2^{67.1}\) 年。两种攻击在现实中都不可行，这也是二重加密在理论上弱于预期、但实际仍不可破的原因。

2.2 部分状态值相遇

由 (1) 可见，攻击复杂度与向前、向后计算涉及的密钥长度正相关。若能降低涉及的密钥长度，就有望降低复杂度。这就是部分匹配技术：相遇函数为 \(x\) 的 \(l\) 比特（\(l<n\)）。下面以 5 轮 Mini-AES 为例。

例 2.6轮 Mini-AES 的中间相遇攻击

Mini-AES 的算法见算法附录。把它的密钥编排换成交替使用两个相互独立的 16 比特轮密钥，即主密钥为 32 比特 \(K=K_0\Vert K_1\)，\(K_0,K_1\in\mathbb F_2^{16}\)。第 1 轮前的白化密钥为 \(K_0\)，第 \(i\) 轮的子密钥为 \(K_{i-1\bmod2}\)。把 16 比特状态按半字节划分，位置编号为

\[ \begin{pmatrix}0&2\\1&3\end{pmatrix}. \]

为平衡复杂度，选第 3 轮输出状态的一个半字节 \(x[0]\) 作为“中间”。按密钥编排，要计算 \(x[0]\)：

向前与向后共用的密钥有 3 个半字节，\(K_j=\{K_0[0,3],K_1[0]\}\)；
只在向前计算中涉及的密钥 \(K_f=\{K_0[1,2],K_1[3]\}\)；
只在向后计算中涉及的密钥 \(K_b=\{K_1[1]\}\)。

相遇只有 \(l=4\) 比特，每个明密文对只能过滤掉 \(2^{-4}\)，所以要 \(t=\lceil28/4\rceil=7\) 个已知明密文对。由 (1)（\(n\) 换成 \(l\)），时间复杂度为

\[ 2^{3\times4}\times\left(2^{3\times4}+2^4\right)+\left(2^{7\times4-4}+2^{28-2\times4}+\cdots+2^{28-7\times4}\right) \]

次 5 轮 Mini-AES 加密，存储复杂度为 \(2^{12}\)（以 \(K_f\) 建表）或 \(2^4\)（以 \(K_b\) 建表）。

注

我按上式算出来，初筛 \(2^{12}\times(2^{12}+2^4)\approx2^{24.006}\)，复筛 \(2^{24}+2^{20}+\cdots\)，加起来约 \(2^{25}\)，与教材的 \(2^{25}\) 一致；教材写存储为 \(2^4\)，即把向后计算的 \(K_b\) 存表。

2.3 拼切技术

前面的分析都在已知明文环境下，相当于从中间把算法分割为两部分，由明密文分别向中间计算。若敌手可以选择明文（或密文），Merkle 和 Hellman 在 1981 年提出了一种新的分割方式，进一步利用密钥编排降低复杂度。基于类似的思路，Aoki 和 Sasaki 在 2008 年提出拼切技术 (splice-and-cut)，用于杂凑函数的原像攻击，后来也用于下一节相遇函数为集合关系的中间相遇攻击，在杂凑函数、认证加密等的分析中取得了很好的效果。

以两个密钥的三重 DES（2K3DES）为例。二重 DES 不能有效提高安全性，所以 NIST 推荐至少加密三重。三重 DES 要 168 比特密钥，为便于管理，美国国家标准 ANS X9.17-1998 和国际标准 ISO 8732 采用了 2K3DES：

定义 2.7两个密钥的三重 DES, 2K3DES

明文 \(P\in\{0,1\}^{64}\)，两个相互独立的密钥 \(K_0,K_1\in\{0,1\}^{56}\)，

\[ x=\mathrm{Enc}_{K_0}(P),\qquad y=\mathrm{Dec}_{K_1}(x),\qquad C=\mathrm{Enc}_{K_0}(y), \]

\(\mathrm{Enc}\)、\(\mathrm{Dec}\) 为 DES 的加密和解密算法。

注

2K3DES 的好处是与 DES 兼容：\(K_0=K_1\) 时，它就等价于 DES。

若按 §2.1 在 \(x\) 或 \(y\) 处直接分割，计算取值必须同时猜测 \(K_0\) 和 \(K_1\)，复杂度约 \(2^{112}\)，与强力攻击相当。要降低复杂度，必须把与 \(K_0\) 相关的运算和与 \(K_1\) 相关的运算独立分割开。观察关于 \(y\) 的方程组

\[ \begin{cases}y=\mathrm{Dec}_{K_1}(x),\\y=\mathrm{Dec}_{K_0}(C)=\mathrm{Dec}_{K_0}(E(P))=\mathrm{Dec}_{K_0}(E(\mathrm{Dec}_{K_0}(x))).\end{cases}\tag{2} \]

若控制 \(x=0\)（也可以是任意 \(n\) 比特常数），(2) 中两个关于 \(y\) 的等式就分别只与 \(K_1\) 或 \(K_0\) 有关！

例 2.8K3DES 的中间相遇攻击

预计算：对 \(K_1\in\{0,1\}^{56}\) 的每个可能取值，计算 \(y=\mathrm{Dec}_{K_1}(0)\)，把 \(K_1\) 存入以 \(y\) 为索引的表 \(L\)；
对 \(K_0\in\{0,1\}^{56}\) 的每个可能取值：
1. 计算 \(P=\mathrm{Dec}_{K_0}(0)\)，以 \(P\) 为选择明文，获得对应的密文 \(C\)；
2. 计算 \(y'=\mathrm{Dec}_{K_0}(C)\)，以 \(y'\) 访问表 \(L\)。

若表中存在 \(y=y'\)，得到 \((K_0,K_1)\)。换一对明密文 \((P_1,C_1)\) 验证，若 \(E_{K_0,K_1}(P_1)=C_1\)，输出为正确密钥。

\[ P\xleftarrow{\mathrm{Dec},\ K_0}0\ \Big|\ 0\xrightarrow{\mathrm{Dec},\ K_1}y\ \Big|\ y\xleftarrow{\mathrm{Dec},\ K_0}C,\qquad P\xrightarrow{\text{选择明文}}C. \]

任一错误密钥满足 \(y=y'\) 的概率为 \(2^{-64}\)，所以两对明密文足以以很大的概率筛出正确密钥。时间复杂度约 \(2^{57}\) 次加密，存储 \(2^{56}\)。代价是需要 \(2^{56}\) 个选择明文。

攻击成功的关键在于：通过给 \(x\) 取定值，“切断”加密中把 \(K_0\)、\(K_1\) 绑在一起的运算，再通过明密文之间的对应关系，“拼出”与正常加密一致的中间结果。相遇点仍在中间状态，但“向前”“向后”计算的起点不是明文或密文，而是中间状态，从而可以更灵活地利用密钥关系，降低复杂度。van Oorschot 和 Wiener 在 1990 年把这个攻击转为了已知明文攻击。

§ 03相遇函数为集合映射关系的攻击

这一节讨论 \(E=E_0\circ E_1\circ E_2\) 的情况，相遇函数为 \(E_1\) 头部状态 \(x\) 的部分比特构成的多重集与尾部状态 \(y\) 的部分比特构成的多重集之间的对应关系。这一思想在 Square 攻击和碰撞攻击的影响下，由 Demirci 和 Selçuk 在 FSE 2008 提出，后来经过一系列发展，给出了单密钥场景下 7 轮 AES-128、9 轮 AES-256 和 10 轮 AES-256 的最优攻击。我们把这种基于集合映射关系的中间相遇攻击称为 \(\mathcal{DS}\) 中间相遇攻击。

下面以 7 轮 Mini-AES 为例。假设密钥编排为各轮密钥相互独立，即主密钥 \(K=K_{-1}\Vert K_0\Vert\cdots\Vert K_6\)，\(K_{-1},K_0,\cdots,K_6\in\mathbb F_2^{16}\) 相互独立。（为了与区分器的编号统一，这里从 \(-1\) 开始编号。）

3.1 \(\mathcal{DS}\) 中间相遇区分器

先不考虑白化密钥，每轮由 S 盒 (NS)、行移位 (SR)、列混合 (MC) 和轮密钥加 (AK) 组成。与积分分析类似，区分器的输入是满足某种活跃特性的集合，研究对象是头部输入集与尾部输出集之间的映射关系。

设初始状态为 \(X_0\)，第 \(i\) 轮经过 NS、SR、MC、AK 后的输出分别记为 \(X_{i-1}^S\)、\(X_{i-1}^R\)、\(X_{i-1}^M\) 和 \(X_i\)。考虑 \(2^4\) 个 \(X_0\) 构成的集合

\[ \mathcal X=\{X_0^i\mid X_0^i[0]\ \text{取遍所有可能},\ X_0^i[1],X_0^i[2],X_0^i[3]\ \text{为常数},\ i=0,\cdots,15\}.\tag{3} \]

逐轮分析：输入的活跃半字节构成的集合 \(\{X_0^0[0],\cdots,X_0^{15}[0]\}\)，与 \(i\) 轮加密后输出的一个半字节构成的集合 \(\{X_i^0[0],\cdots,X_i^{15}[0]\}\) 之间的映射，记为 \(\mathcal X_0[0]\to\mathcal X_i[0]\)。

映射 \(\mathcal X_0[0]\to\mathcal X_1[0]\)。 设 \(S(X_0[0])=t_0\)，则

\[ X_1[0]=X_0^M[0]\oplus K_1[0]=3t_0\oplus2S(X_0[3])\oplus K_1[0].\tag{4} \]

\(X_0[3]\) 是定值，\(K_1[0]\) 对加密双方也是定值，所以 \(2S(X_0[3])\oplus K_1[0]\) 可以看作 4 比特常数 \(c_0\)，(4) 等价于

\[ X_1[0]=3S(X_0[0])\oplus c_0.\tag{5} \]

可见映射 \(\mathcal X_0[0]\to\mathcal X_1[0]\) 由 4 比特的 \(c_0\) 决定：对 \(c_0\) 的每个可能值，把 \(2^4\) 个 \(X_0[0]\) 依次代入 (5)，得到 \(2^4\) 个 \(X_1[0]\)，记为一个对应表。所以 \(\mathcal X_0[0]\to\mathcal X_1[0]\) 至多有 \(2^4\) 个对应表：

\(c_0=0\)		\(c_0=1\)		\(c_0=15\)
\(X_0[0]\)	\(X_1[0]\)	\(X_0[0]\)	\(X_1[0]\)	\(X_0[0]\)	\(X_1[0]\)
\(0\)	\(3S(0)\)	\(0\)	\(3S(0)\oplus1\)	\(0\)	\(3S(0)\oplus15\)
\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)
\(15\)	\(3S(15)\)	\(15\)	\(3S(15)\oplus1\)	\(15\)	\(3S(15)\oplus15\)

类似地，存在 4 比特常数 \(c_1\) 使

\[ X_1[1]=2S(X_0[0])\oplus c_1.\tag{6} \]

映射 \(\mathcal X_0[0]\to\mathcal X_2[0]\)。 继续按加密写表达式：

\[ X_2[0]=X_1^M[0]\oplus K_2[0]=3S(X_1[0])\oplus2S(X_1[3])\oplus K_2[0]=3S(3S(X_0[0])\oplus c_0)\oplus c_2, \]

其中 \(c_2=2S(X_1[3])\oplus K_2[0]\) 是 4 比特常数（\(X_1[3]\) 在这 16 个状态中不变）。可见 \(\mathcal X_0[0]\to\mathcal X_2[0]\) 由 8 比特的 \(c_0\Vert c_2\) 决定，至多 \(2^8\) 种可能。类似地，存在 4 比特常数 \(c_3,c_4,c_5\) 使

\[ \begin{aligned} X_2[1]&=2S(3S(X_0[0])\oplus c_0)\oplus c_3,\\ X_2[2]&=2S(2S(X_0[0])\oplus c_1)\oplus c_4,\\ X_2[3]&=3S(2S(X_0[0])\oplus c_1)\oplus c_5. \end{aligned} \]

映射 \(\mathcal X_0[0]\to\mathcal X_3[0]\)。

\[ \begin{aligned} X_3[0]&=X_2^M[0]\oplus K_3[0]=3S(X_2[0])\oplus2S(X_2[3])\oplus K_3[0]\\ &=3S\big(3S(3S(X_0[0])\oplus c_0)\oplus c_2\big)\oplus2S\big(3S(2S(X_0[0])\oplus c_1)\oplus c_5\big)\oplus K_3[0], \end{aligned} \]

由 20 比特的 \(c_0\Vert c_1\Vert c_2\Vert c_5\Vert K_3[0]\) 决定，至多 \(2^{20}\) 种可能。同理

\[ X_3[3]=2S(X_2[2])\oplus3S(X_2[1])\oplus K_3[3]=2S\big(2S(2S(X_0[0])\oplus c_1)\oplus c_4\big)\oplus3S\big(2S(3S(X_0[0])\oplus c_0)\oplus c_3\big)\oplus K_3[3]. \]

映射 \(\mathcal X_0[0]\to\mathcal X_4[0]\)。

\[ X_4[0]=X_3^M[0]\oplus K_4[0]=3S(X_3[0])\oplus2S(X_3[3])\oplus K_4[0],\tag{7} \]

由上面两式，(7) 的取值由

\[ \mathcal V=c_0\Vert c_1\Vert c_2\Vert c_3\Vert c_4\Vert c_5\Vert K_3[0]\Vert K_3[3]\Vert K_4[0] \]

决定，共 36 比特，即 \(\mathcal X_0[0]\to\mathcal X_4[0]\) 至多有 \(2^{36}\) 种可能。

而 4 比特到 4 比特的随机映射共有 \(16^{16}=2^{64}\) 种。\(2^{36}\ll2^{64}\)，按 4 轮 Mini-AES 构造的映射表的个数远小于随机映射的个数。这种差异性就是相遇函数为集合映射关系的区分器：

定理 3.1算法（4 轮 Mini-AES 的 \(\mathcal{DS}\) 区分攻击）

预计算：遍历 \(\mathcal V\) 的所有可能，构造 \(\mathcal X_0[0]\to\mathcal X_4[0]\) 的 \(2^{36}\) 种可能的对应表并存储；
选择满足 (3) 的 \(2^4\) 个输入，获得相应的输出；
根据输入集合和输出集合，得到一个 \(\mathcal X_0[0]\to\mathcal X_4[0]\) 的对应表 \(T\)；
若 \(T\) 属于预计算出的 \(2^{36}\) 种之一，判断为 4 轮 Mini-AES，否则判断为随机置换。

习题 3.2

分析上面区分攻击的复杂度。

解

数据：\(2^4\) 个选择明文。
预计算时间：对 \(2^{36}\) 个 \(\mathcal V\)，各算 16 个输入的 \(X_4[0]\)，每个约需 \(X_1[0],X_1[1]\)（2 次 S 盒）、\(X_2\) 的 4 个半字节（4 次）、\(X_3[0],X_3[3]\)（4 次）、\(X_4[0]\)（2 次）共约 12 次 S 盒，总计 \(2^{36}\times16\times12\approx2^{43.6}\) 次查表。
存储：每个表存 16 个 4 比特值，共 64 比特，\(2^{36}\times64=2^{42}\) 比特。（实际存一个排序的 64 比特指纹即可。）
在线时间：\(2^4\) 次加密加一次查表，可忽略。
成功率：真实算法一定判对；随机置换判错（落在预计算集合里）的概率为 \(2^{36}/2^{64}=2^{-28}\)。

可见区分攻击的复杂度由预计算表的计算和存储占主项，而这主要由 \(X_4[0]\) 涉及的变量个数决定。

注意到 (7) 最后是 \(\oplus K_4[0]\)，可以通过差分消去。Demirci 和 Selçuk 提出了一种改进：考虑差分值之间的对应，而不是取值的对应。按活跃半字节的值由小到大给输入集合排序（固定任意顺序遍历即可），设 \(X_0^0\) 为 \(X_0^0[0]=0\) 时对应的值，构造差分形式的映射

\[ X_4^i[0]\oplus X_4^0[0]=3\big(S(X_3^i[0])\oplus S(X_3^0[0])\big)\oplus2\big(S(X_3^i[3])\oplus S(X_3^0[3])\big),\qquad i=1,\cdots,15. \]

此时变量为

\[ \mathcal V'=c_0\Vert c_1\Vert c_2\Vert c_3\Vert c_4\Vert c_5\Vert K_3[0]\Vert K_3[3], \]

从 36 比特降为 32 比特，只需存储 \(2^{32}\) 种对应表，降低了存储：

\(X_0^i[0]\)	\(\Delta X_4^i[0]\)
\(1\)	\(X_4^1[0]\oplus X_4^0[0]\)
\(2\)	\(X_4^2[0]\oplus X_4^0[0]\)
\(\vdots\)	\(\vdots\)
\(15\)	\(X_4^{15}[0]\oplus X_4^0[0]\)

注

这个区分器是头部取值与尾部差分的对应表。从 36 比特降为 32 比特的本质在于：尾部固定位置半字节的表达式都含 \(\oplus K\) 这一项，利用差分这种线性关系可以消去它，少猜 1 个半字节的密钥。推而广之，若不同位置的多个字的表达式中也有共项（例如 MC 后同一列每个字的表达式都由 MC 之前同一列的字表示），就可以考虑多个字的异或和或更广义的线性关系，减少变量个数，降低复杂度。Derbez 等就利用这一思路，把 AES 中间相遇区分器的变量个数从 24 降到 14，大大降低了预计算表的存储。此外，还可以把映射表中的有序对应转为无序对应来降低存储量，或选择满足截断差分的区分器头尾，降低中间变量个数，以数据换存储。

3.2 密钥恢复攻击

把 4 轮区分器 \(\mathcal X_0[0]\to\Delta\mathcal X_4[0]\) 放在 \(E_1\) 的位置，前面加 1 轮，后面加 2 轮，进行 7 轮 Mini-AES 的密钥恢复攻击：

\[ P\xrightarrow{K_{-1},\ \mathrm{NS,SR,MC},\ K_0}X_0\xrightarrow{4\text{ 轮区分器}}X_4\xrightarrow{\mathrm{NS,SR},\ WK_5,\ \mathrm{MC},\ \mathrm{NS,SR},\ K_6}C. \]

这里 \(WK_5\) 是 \(K_5\) 经 \(\mathrm{MC}^{-1}\) 得到的等价密钥，把密钥加与 MC 交换顺序后，向后计算只需猜一个半字节。

1. 预计算。 令有序集 \(\mathcal X_0[0]=\{X_0^0[0],\cdots,X_0^{15}[0]\}=\{0,\cdots,15\}\)，遍历 \(\mathcal V'\) 的所有可能，构造 \(\mathcal X_0[0]\to\Delta\mathcal X_4[0]\) 的 \(2^{32}\) 种可能的对应表并存储。这一步需要

\[ 2^{32}\times15\times4\times7\approx2^{40.7} \]

次查表运算，\(2^{32}\times15\times4\div8=2^{34.9}\) 字节的存储。

2. 连接明文与区分器头部。 要保证 \(\mathcal X_0[0]\) 活跃，考虑直接猜测密钥，算出满足要求的明文集合 \(\mathcal P=\{P^0,\cdots,P^{15}\}\)，并找到它与有序集合 \(\mathcal X_0[0]\) 的对应。

记第一轮 MC 的输出为 \(X_{-1}^M\)。选择有序集合 \(\mathcal X_{-1}^M[0]=\{0,1,\cdots,15\}\)，\(X_{-1}^{iM}[1]=c_6\)（任意常数）。对 \(i=0,\cdots,15\)，由 \(X_{-1}^{iM}[0]\Vert X_{-1}^{iM}[1]\) 沿解密方向算出 \(X_{-1}^i[0]\Vert X_{-1}^i[3]\)；
猜测 \(K_{-1}[0]\) 和 \(K_{-1}[3]\)，求得 \(P^i[0]\Vert P^i[3]\)。令 \(P^i[1]\Vert P^i[2]\) 为任意固定常数；
猜测 \(K_0[0]\)，计算 \(X_0^i[0]=X_{-1}^{iM}[0]\oplus K_0[0]\)；
为与预计算表对应，识别 \(X_0^0[0]\)，把算出的 \(X_0^i[0]\) 由小到大排序，相应地把明文集合排序，得到有序集合 \(\mathcal P\)，获得密文集合 \(\mathcal C\)。

3. 连接密文与区分器尾部。 找到密文集合 \(\mathcal C\) 与有序集合 \(\{X_4^1[0]\oplus X_4^0[0],\cdots,X_4^{15}[0]\oplus X_4^0[0]\}\) 之间的对应。

猜测 \(K_6[0]\)、\(K_6[3]\) 和等价密钥 \(WK_5[0]\)，计算 \(X_4^i[0]\) 及 \(X_4^i[0]\oplus X_4^0[0]\)，\(i=1,\cdots,15\)；
得到一个对应表 \(\mathcal X_0[0]\to\Delta\mathcal X_4[0]\)。若它在预计算表中，则输出此时的 24 比特

\[ K_{-1}[0]\Vert K_{-1}[3]\Vert K_0[0]\Vert WK_5[0]\Vert K_6[0]\Vert K_6[3] \]

为正确密钥；否则回到 2 中的第 2 步重新猜测。

这一步要选 \(2^4\) 个明文，进行约 \(2^{24}\times16=2^{28}\) 次查表运算。

注

若轮密钥之间不独立，还可以结合密钥编排，进一步平衡复杂度。

可见密钥恢复攻击的复杂度由预计算阶段和在线阶段需要猜测的密钥量决定。一般地，设 \(c\) 为相遇集合中每个元素的比特长度，\(s\) 为头部集合中涉及的元素位置个数（本节只考虑 \(X_0[0]\) 一个位置，\(s=1\)），\(t\) 为尾部集合中涉及的元素位置个数，\(d\) 为预计算阶段要遍历的 \(c\) 比特变量的个数，\(|K_{E_0}\cup K_{E_2}|\) 为在线阶段猜测的密钥比特数，\(\rho_{E_i}\) 为 \(E_i\) 中的运算占一次完整加密的比重（往往只考虑 S 盒运算）。则：

预计算阶段：\(2^{cd}\cdot2^{cs}\cdot\rho_{E_1}\) 次加密，\(2^{cd}\cdot(2^{cs}-1)\cdot ct\) 比特的存储；
在线阶段：\(2^{cs}\) 个明文，\(2^{|K_{E_0}\cup K_{E_2}|}\cdot2^{cs}\cdot\rho_{E_0\cup E_2}\) 次加密。一次筛选后，\(2^{|K_{E_0}\cup K_{E_2}|}\) 个密钥还剩 \(\lambda\cdot2^{|K_{E_0}\cup K_{E_2}|}\) 个，其中 \(\lambda=2^{c(d-t\cdot(2^{cs}-1))}\)。

习题 3.3

用上面的一般公式核对 7 轮 Mini-AES 攻击的数字：\(c=4\)，\(s=t=1\)，\(d=8\)。

解

预计算存储：\(2^{32}\cdot15\cdot4\) 比特 \(=2^{32}\times60\) 比特 \(\approx2^{37.9}\) 比特 \(=2^{34.9}\) 字节，与上面一致。
在线：\(2^4\) 个明文；猜测 \(24\) 比特密钥，每个猜测处理 \(16\) 个明文，\(2^{24}\times16=2^{28}\) 次查表，与上面一致。
筛选：\(\lambda=2^{4(8-15)}=2^{-28}\)，\(2^{24}\) 个猜测中错误候选的期望留下 \(2^{24-28}=2^{-4}\) 个，所以一次筛选基本只剩正确密钥。

习题 3.4

若 Mini-AES 的密钥编排为交替使用两个相互独立的 16 比特轮密钥，能否进行中间相遇攻击？

解

能，而且更容易。轮密钥只有 \(K_0,K_1\) 两个，向前、向后计算猜过的半字节会重复出现在后面的轮中：在线阶段猜测的 \(K_{-1}[0,3]\)、\(K_0[0]\)、\(K_6[0,3]\)、\(WK_5[0]\) 都是 \(K_0\) 或 \(K_1\)（或其线性变换）的半字节，而预计算中的 \(K_3[0]\)、\(K_3[3]\) 也来自同一组密钥。所以 \(\mathcal V'\) 中的部分变量可以由在线阶段的猜测直接算出，预计算表可以按这些比特分块，只与对应块比较，降低存储和匹配代价；猜出的 24 比特与区分器中的 8 比特密钥有重叠，相当于额外的校验条件。这就是上面注中所说的“结合密钥编排进一步平衡复杂度”。当然，同时也要注意 §2.2 的分析已经表明，这种密钥编排下 5 轮版本用值相遇就能以 \(2^{25}\) 攻破。

参考：王美琴主编，《密码分析学》，科学出版社，2024，第 6 章。

完