中间相遇攻击与时间—内存权衡

MITM 攻击将密码算法拆分为两半，分别进行攻击。攻击者从一端建立表，然后从另一端搜索匹配项。这样会将攻击复杂度从 O(2^{2n}) 降低到 O(2^n)，代价是需要 O(2^n) 的内存。

双重 DES 会应用两次 DES：C = DES_{K2}(DES_{K1}(P))。密钥空间为 2^{112}。MITM 攻击如下：对于所有 2^{56} 个 K1 值，计算 DES_{K1}(P) 并存储结果。对于所有 2^{56} 个 K2 值，计算 DES_{K2}^{-1}(C)，并在表中查找。匹配后得到 (K1, K2) 候选值。总工作量只有 2^{57}。

步骤 1：使用所有可能的 K1 加密明文 P，建立表 T[DES_{K1}(P)] = K1。步骤 2：对于每个 K2，解密密文 C：v = DES^{-1}_{K2}(C)。检查 v ∈ T 是否成立。如果存在 T[v] = K1，则在第二组明文—密文对上验证 (K1, K2)。预计会有 1–2 个误匹配；将它们丢弃。

三重 DES（3DES）使用三个密钥 K1、K2、K3：C = DES_{K3}(DES^{-1}_{K2}(DES_{K1}(P)))。MITM 仍然适用，但效果较弱：双密钥 3DES（K3=K1）将攻击工作量降为 2^{112}。对于三密钥 3DES，存在工作量为 2^{112} 的 MITM 攻击，这解释了为什么尽管密钥长度为 168 位，3DES 提供的有效安全强度却只有约 112 位。

Hellman（1980）提出预先计算由 (start_point, end_point) 组成的链表，以加快离线密钥搜索。给定目标哈希值或密文后，在 Hellman 表中搜索包含该目标的链。其权衡关系为：P = N（时间 × 内存 = 空间常数）。这是彩虹表的基础。

彩虹表（Oechslin，2003）通过在链的每个位置使用不同的归约函数改进了 Hellman 表，从而消除误报（合并的链）。彩虹表适合破解未加盐的密码哈希。一次查找需要 O(table_size/chain_length) 的时间。

盐值是在哈希前添加到密码前面的随机值：H(salt||password)。不同的盐值会使同一个密码产生不同的哈希值——如果使用了不同的盐值，针对“密码”建立的彩虹表就毫无用处。盐值必须与哈希值一起存储。

针对 AES-128（10 轮）的 MITM 攻击会在第 5 轮分割：从前向后加密 5 轮，再从后向前解密 5 轮，在中间相遇。已知的最佳攻击是双团攻击，将 2^{128} 降低到 2^{126.1}。这并不实用，但表明 AES 针对 MITM 类方法没有安全余量。

对于 Merkle-Damgard 哈希，MITM 在某些构造上可以比穷举更快地找到原像。攻击方法是：从 IV 开始，根据消息分组建立表；然后从目标哈希值开始向后搜索。针对完整轮数的 SHA-256，仍然需要约 2^{255} 的工作量，相比穷举没有改进。

分割攻击将 MITM 推广到 r 路拆分。对于密码算法的三路拆分：从前向后加密三分之一的轮，在链的中间相遇，然后从后向前解密三分之一的轮。它需要 O(2^{n*2/3}) 的时间和 O(2^{n/3}) 的内存，是一种更加均衡的权衡。

在协议中，可以通过以下方式防止 MITM 攻击：使用由高熵密码通过 KDF 派生出的长密钥（减少可枚举的密钥空间）；使用硬件令牌（FIDO2），让密钥始终不离开设备；或者使用公钥认证（不存在可供枚举的共享密钥）。

双重 DES（两次 DES，合计 112 位密钥）针对 MITM 攻击的有效安全强度是多少？

MITM 攻击将密码算法拆成两半，使用 2^n 的内存将时间复杂度从 2^{2n} 降低到 2^n。它可以攻破双重 DES；3DES 虽能缓解这一问题，但有效安全强度只有 112 位。彩虹表利用了 MITM 的思路来破解密码，而加盐可以抵御这种攻击。下一节：时序攻击和侧信道攻击。