中间相遇攻击

一、背景与动机

• 问题起源 ：DES 密钥长度仅 56 位，易受暴力破解。
• 改进方案：提出 2-DES（使用两个独立密钥 $K_1,K_2$，加密两次）和 3-DES。
• 关键发现（Diffie & Hellman, 1977）：
  2-DES 的安全性并未提升到 $2^{112}$，而是可被 MitM 攻击在约 $2^{56}$ 时间内破解。

---

二、基本中间相遇攻击（Basic MitM）

1. 攻击模型

• 密码结构：$ C = E_{K_2}(E_{K_1}(P)) $
• 假设：$K_1$ 和 $K_2$ 独立，各为 56 位（如 2-DES）
• 已知一对明密文 $(P,C)$

2. 攻击步骤

1. 前向计算：对所有可能的 $K_1$，计算中间值 $u=E_{K_1}(P)$，存入哈希表（按 $u$ 索引 $K_1$）。
2. 后向计算：对所有可能的 $K_2$，计算 $v=D_{K_2}(C)$（即解密），查表看是否存在 $u=v$。
3. 候选密钥：若匹配，则 $(K_1,K_2)$ 是候选密钥。
4. 验证：用另一对 $(P^{\prime },C^{\prime })$ 验证候选密钥是否正确。

3. 复杂度分析（以 2-DES 为例）

• 时间复杂度：$T\approx 2^{56}+2^{56}=2^{57}$ 次加密/解密操作 → ≈ $2^{56}$
• 空间复杂度：需存储 $2^{56}$ 个中间值 → $M=2^{56}$
• 数据复杂度：通常只需 1~2 对明密文

✅ 结论：2-DES 安全性 ≈ $2^{56}$，不是 $2^{112}$！

---

三、MitM 的变种与扩展

1. 3-DES 的安全性

• 常见形式：$E_{K_1}\circ D_{K_2}\circ E_{K_1}$（两密钥 3-DES）
• 若尝试 MitM，因 $K_1$ 重复使用，无法直接划分为两个独立密钥集。
• 但若采用 splice-and-cut 技术（Aoki & Sasaki, 2008），可将已知明文攻击转为选择明文/密文攻击，仍可在 $2^{56}$ 时间和空间下攻击。

2. 3-Subset MitM（部分密钥相关）

• 当 $K_1$ 和 $K_2$ 不完全独立时（如共享部分比特）：
  • 将密钥划分为三部分：$A_0$（公共部分）、$A_1$、$A_2$
  • 先猜测 $A_0$，再对每个 $A_0$ 执行标准 MitM
• 时间复杂度：$max(2^{|A_1|},2^{|A_2|})\times 2^{|A_0|}$
• 空间复杂度：$min(2^{|A_1|},2^{|A_2|})$

3. All SubKeys Recovery (ASR) 攻击

• 思想：不恢复主密钥，而是直接恢复所有轮密钥（子密钥）
• 优点：绕过复杂的密钥扩展算法
• 适用对象：Feistel 结构、SPN 结构等
• 核心：在中间某状态进行“匹配”，利用多个明密文对缩小子密钥空间

---

四、MitM 在 Feistel 密码中的应用

• Feistel-1[n]：分组长 $n$，密钥长 $n$
• Feistel-1[2n]：密钥长 $2n$，可前后各加 2 轮
• 攻击能力：
  • Feistel-1[2n]：可达 7~8 轮
  • Feistel-2[2n]：可达 9 轮
  • Feistel-3[2n]：可达 11 轮
• 技巧：
  • 固定部分输入（如 $L_1=\text{const}$）
  • 使用 splice-and-cut 增加可攻击轮数

💡 设计启示：Feistel 密码轮数应显著高于当前 MitM 可攻破的轮数。

---

五、MitM 在 AES 上的应用（Demirci-Selçuk 攻击）

1. 核心观察

• 利用 AES 轮函数（SubBytes, ShiftRows, MixColumns）的代数结构
• 构造“区分器”：特定输入模式下，输出由远少于随机情况的参数决定

2. 四轮 AES 区分器

• 输入：256 个明文，仅第一个字节变化，其余固定
• 输出：经 4 轮 AES 后，某个字节序列（或多重集）仅由 24 个字节参数决定
• 随机置换下输出可能性：$2^{2048}$；AES 下仅 $2^{192}$ 或 $2^{184}$ → 可区分

3. 密钥恢复（以 AES-256 为例）

• 攻击 1+4+2 = 7 轮
• 猜测少量轮密钥（如 $k_0,k_1,k_6,k_7$ 的部分字节）
• 利用区分器筛选正确密钥
• 复杂度：$D=2^{32}$, $T=2^{80}$, $M=2^{200}$ 字节

4. 优化技术

• 序列 → 多重集（ASIACTYPT 2010）：忽略输入顺序，减少在线密钥猜测量
• 差分枚举：结合差分特征进一步压缩搜索空间

---

六、MitM 的局限性

• 依赖密钥独立性：若密钥扩展复杂（如 AES、SHA-3），难以划分独立子密钥集
• 高存储需求：标准 MitM 需 $2^{k/2}$ 存储，对大密钥不现实
• 应对策略：
  • 使用 时间-内存权衡（如彩虹表）
  • 采用 局部匹配（partial matching）+ 多对明密文

---

复习题与答案

题目 1：为什么 2-DES 的安全性不是 $2^{112}$？

答：
因为可以使用中间相遇攻击（MitM）。攻击者对所有 $2^{56}$ 个 $K_1$ 计算 $E_{K_1}(P)$ 并存储，再对所有 $K_2$ 计算 $D_{K_2}(C)$ 并查表匹配。总时间约为 $2^{56}+2^{56}\approx 2^{57}$，空间 $2^{56}$，远低于 $2^{112}$。

---

题目 2：简述 ASR（All SubKeys Recovery）攻击的基本思想及其优势。

答：
ASR 攻击不试图恢复主密钥，而是直接恢复所有轮密钥（子密钥）。其优势在于绕过了复杂的密钥扩展算法，使得 MitM 可应用于密钥扩展较复杂的密码（如 LED、GOST）。攻击通过在中间状态匹配，并利用多对明密文逐步筛减子密钥空间。

---

题目 3：在 Demirci-Selçuk 对 AES 的 MitM 攻击中，为何四轮 AES 的输出可被区分？

答：
当输入为 256 个仅首字节变化的明文时，四轮 AES 的某个输出字节序列（或多重集）仅由 24 个内部参数决定（如某些轮密钥字节和中间状态），因此仅有约 $2^{192}$ 种可能输出。而随机置换下有 $2^{2048}$ 种可能，两者差异巨大，故可构造有效区分器。

---

题目 4（计算题）：

假设某密码 $Enc=E_{K_1}\circ E_{K_0}$，其中 $K_0,K_1$ 各为 128 位且独立。
(a) 给出一种时间复杂度 $\le 2^{128}$ 的 MitM 攻击；
(b) 若只有 $2^{128}$ 字节存储，如何调整攻击？
(c) 若有 8000 台计算机，每台每秒执行 $2^{27}$ 次运算，估算攻击所需时间（年）。

答：

(a) 标准 MitM：

• 前向：计算所有 $2^{128}$ 个 $E_{K_0}(P)$，存表 → 时间 $2^{128}$，空间 $2^{128}$
• 后向：对每个 $K_1$，计算 $D_{K_1}(C)$ 查表 → 时间 $2^{128}$
• 总时间 ≈ $2^{129}\approx 2^{128}$（数量级满足）

(b) 若存储限制为 $2^{128}$ 字节（刚好够存 $2^{128}$ 个 128 位中间值），则可直接使用标准 MitM，无需调整。

(c) 总操作数 ≈ $2^{129}$ 次加密/解密

• 总算力：8000 × $2^{27}$ = $2^{13}\times 2^{27}=2^{40}$ 次/秒
• 所需秒数：$2^{129}/2^{40}=2^{89}$ 秒
• 换算：
  • 1 年 ≈ $3.15\times {10}^7\approx 2^{25}$ 秒
  • 时间 ≈ $2^{89}/2^{25}=2^{64}$ 年
  • $2^{64}\approx 1.8\times {10}^{19}$ 年（远超宇宙年龄）

✅ 结论：即使大规模并行，128 位密钥的 MitM 仍不可行，说明 128 位是安全的。

---

希望这份提纲和习题能帮助你系统掌握中间相遇攻击的核心内容！如需进一步深入某一部分，欢迎继续提问。