On the security of 2-key triple DES

该论文通过提出自 1990 年以来首个针对 2 密钥三重 DES 的泛化攻击及其增强方案，证明其 80 位安全性的传统估计已不再保守且定期更换密钥的假设受到挑战，从而指出该算法的安全余量极小，亟需加速向 3 密钥变体迁移。

要点

这篇论文主要讨论了一个老牌的加密技术——2 密钥三重 DES（2-key triple DES）的安全性。虽然它现在已经被美国国家标准与技术研究院（NIST）“降级”甚至建议停用，但在全球支付系统（如信用卡）中依然被广泛使用。

作者 Chris J. Mitchell 在文中提出了一个令人担忧的结论：这种加密方式的安全余量比我们想象的要薄得多，甚至可以说“千钧一发”。

为了让你更容易理解，我们可以把这篇论文的核心内容想象成破解一个复杂的保险箱的故事。

1. 背景：那个“老式保险箱”

想象一下，银行和支付系统里有一个用了很久的老式保险箱（这就是 2-key triple DES）。

• 它的构造：它有三道锁，但只有两把钥匙（钥匙 A 和钥匙 B）。开锁的顺序是：用 A 锁上 -> 用 B 打开 -> 再用 A 锁上。
• 它的地位：虽然密码学界早就觉得它不够安全，但因为它是旧系统的标准，而且更换成本太高，所以它依然在世界各地（特别是刷卡支付）被大量使用。
• 过去的共识：大家一直认为，只要定期更换钥匙（比如每天换一次），这个保险箱就是安全的。大家估算它的安全性相当于80 位（80 bits），这被认为是一个比较保守、安全的数字。

2. 新的发现：黑客的“新招数”

这篇论文就像是一个顶级锁匠（密码学家）发表的新报告，他发现了三种让破解这个保险箱变得更容易、更快速的方法。

第一招：把“单挑”变成“群殴”（泛化攻击）

• 旧方法：以前的黑客（van Oorschot-Wiener 攻击）认为，要破解保险箱，必须收集同一把钥匙锁住的成千上万个包裹（明文/密文对）。如果钥匙换得太勤，收集不到这么多数据，就破不了。
• 新发现：作者发现，黑客根本不需要盯着同一把钥匙！他们可以把不同钥匙锁住的包裹混在一起。
  • 比喻：以前黑客想开锁，必须偷到同一个管家（钥匙）保管的所有信件。现在，黑客发现，只要把所有管家保管的信件都收集起来，混在一个大袋子里，依然能算出其中某一把钥匙的密码。
  • 后果：这意味着“定期换钥匙”这个防御手段失效了。即使你每天换钥匙，只要黑客收集了足够多的、由不同钥匙加密的数据，依然能算出其中某一把钥匙。

第二招：利用“镜像”特性（互补性）

• 原理：DES 加密算法有一个奇怪的数学特性（互补性）：如果你把输入的数据和钥匙都“反过来”（0 变 1，1 变 0），输出的结果也会完全反过来。
• 新发现：作者利用这个特性，相当于让黑客同时尝试两把钥匙。
  • 比喻：以前黑客试一次钥匙，只能开一次门。现在利用这个“镜像”特性，他试一次，相当于同时试了正着和反着，效率直接翻倍。
  • 后果：破解速度又提高了一倍。

第三招：利用“模糊”的线索（部分已知明文）

• 场景：在现实生活中，黑客往往拿不到完整的包裹内容。比如，他们知道包裹里有一串账号（已知），但不知道具体的 PIN 码（未知，只有 4 位数字）。
• 新发现：以前的攻击方法要求必须知道完整的包裹内容。但作者发现，即使只知道一部分，黑客也可以把剩下的可能性全部列出来（4 位 PIN 码只有 1 万种可能，很快就能试完），把它们都当成“已知”数据扔进攻击程序里。
  • 比喻：以前黑客必须拿到完整的快递单才能破解。现在，只要知道快递单上写了“寄给张三”，哪怕不知道里面装了什么，黑客也可以把“张三收到苹果、香蕉、橘子……"等一万种可能性都列出来，假装自己全都知道，然后继续破解。
  • 后果：这让攻击变得在更多实际场景下可行（比如破解 PIN 码）。

3. 结论：安全余量“薄如蝉翼”

综合以上三点，作者得出了几个震撼的结论：

1. 80 位安全并不安全：以前大家觉得 80 位安全很稳，现在发现，考虑到上述的优化，这个安全余量其实非常小，甚至可以说几乎没有安全余量。
2. “定期换钥匙”没用：这是最危险的误区。以前人们以为只要勤换钥匙就能防住，现在证明，只要数据量够大（哪怕是用不同钥匙加密的），定期换钥匙并不能阻止被破解，只能限制被破解后能恢复多少数据。
3. 紧急呼吁：虽然这个保险箱还没被彻底“炸开”（完全破解），但它已经摇摇欲坠。作者强烈建议，必须尽快停止使用 2 密钥三重 DES，要么升级到 3 密钥版本（更安全），要么直接换成更现代、更强大的算法（如 AES）。

总结

这就好比我们一直以为家里的老式防盗门（2-key triple DES）只要勤换锁芯（定期换钥匙）就没事。但这篇论文告诉我们：

• 小偷现在有一种新工具，不需要盯着同一个锁芯，把全小区的锁芯数据混在一起就能猜出密码。
• 小偷还能利用锁的镜像原理，一次试两把锁。
• 小偷甚至不需要知道门里有什么，只要猜几个可能性就能继续破解。

所以，这扇门已经不安全了。不要等到被偷了才后悔，赶紧换把新锁（AES）吧！

技术摘要

这篇论文《On the security of 2-key triple DES》（2 密钥三重 DES 的安全性）由伦敦大学皇家霍洛威学院信息安全组的 Chris J. Mitchell 撰写。文章重新评估了尽管已被 NIST 取消标准化支持但仍被广泛使用的 2 密钥三重 DES（2-key Triple DES）的安全性。

以下是该论文的详细技术总结：

1. 研究背景与问题 (Problem)

• 现状：2 密钥三重 DES（即 $E_{K1}(D_{K2}(E_{K1}(P)))$，其中 $K_1=K_3$）在支付行业（如 EMV 标准）中仍被广泛使用。尽管 NIST 在 2015 年底撤回了对其的支持，且 ISO/IEC 标准对其安全性提出了警告，但业界普遍认为其提供约 80 比特的安全强度，且只要定期更换密钥即可保持安全。
• 核心问题：现有的安全评估是否过于乐观？定期更换密钥是否足以防御已知的密码分析攻击？作者旨在证明 2 密钥三重 DES 的安全边际比之前认为的要小得多，且“定期换钥”的建议在防御此类攻击方面有效性有限。

2. 方法论与攻击改进 (Methodology & Key Contributions)

作者对 1990 年 van Oorschot 和 Wiener 提出的经典攻击进行了三项主要改进，使其更加通用和高效：

A. 攻击的通用化 (Generalisation)

• 原攻击局限：van Oorschot-Wiener 攻击原本要求所有明文/密文对（$P, C$）必须使用同一对密钥生成。如果密钥频繁更换，攻击者无法积累足够的数据。
• 改进：作者指出，攻击算法可以修改为处理多组不同密钥生成的数据。
  • 将明文/密文对按密钥标签（Key Label）分组。
  • 在构建查找表时，不仅存储 $(P, C)$，还存储密钥标签 $s$。
  • 结果：攻击者无需等待单一密钥下积累大量数据。只要收集到足够数量的（可能来自不同密钥的）明文/密文对，攻击依然有效。这意味着“定期更换密钥”只能限制单次攻击成功后的解密范围，而不能阻止攻击本身的成功。

B. 利用 DES 互补性质 (Exploiting Complementation Property)

• 原理：DES 具有互补性质：$E_K(P) = \overline{E_{\bar{K}}(\bar{P})}$。即如果明文和密钥取反，密文也会取反。
• 改进：利用这一性质，攻击者可以同时对 $A$ 和 $\bar{A}$（$A$ 的按位取反）进行测试。
• 结果：这使得攻击效率提高了一倍（即减少 1 比特的计算复杂度）。原本需要 $2^{121-t}$次 DES 运算，现在降至$2^{120-t}$。

C. 利用部分已知明文 (Using Partially Known Plaintext)

• 场景：在实际应用中（如支付行业的 PIN 块），攻击者可能知道明文的大部分比特，但不知道其中一小部分（例如 PIN 码只有 4 位，即 13 比特未知）。
• 改进：对于每个已知密文块，攻击者可以生成所有可能的明文组合（$2^w$个，其中$w$ 是未知比特数），并将它们作为“伪”明文/密文对加入攻击数据集。
• 结果：虽然这会略微增加存储需求（$O(2^{t+w})$），但只要 $t+w \ll 56$，计算复杂度不会显著增加。这使得攻击在部分明文泄露的场景下依然可行，大大扩展了攻击的适用范围。

3. 攻击复杂度与结果 (Results)

作者推导了改进后攻击的复杂度公式：

• 假设：拥有 $n = 2^t$ 个明文/密文对（可以是完全已知或部分已知，且可来自不同密钥）。
• 计算复杂度：$2^{120-t}$ 次 DES 运算（结合了互补性质优化后）。
• 存储复杂度：$O(2^{t+w})$，其中 $w$ 是部分已知明文中的未知比特数。

具体案例：
如果攻击者拥有 $2^{32}$（约 40 亿）个明文/密文对（即使是部分已知或来自不同密钥）：

• 攻击所需的 DES 运算次数约为 $2^{88}$。
• 这远低于之前认为的 80 比特安全强度（即 $2^{80}$ 次运算）。
• 对于 ANSI 零售 MAC（基于 2 密钥三重 DES），同样的攻击逻辑也适用，且由于 MAC 生成通常涉及多密钥，通用化攻击使其更容易被破解。

4. 结论与意义 (Significance)

• 安全评估修正：2 密钥三重 DES 提供的 80 比特安全强度并非保守估计，实际上其安全边际非常薄弱。
• 挑战现有建议：业界广泛接受的“只要定期更换密钥就是安全的”这一建议被证明是无效的。因为改进后的攻击可以利用多密钥下的数据积累，换钥无法阻止攻击成功，只能限制攻击成功后的解密范围。
• 紧迫性：2 密钥三重 DES 不应再被视为安全。
  • 应立即停止使用，并迁移到 3 密钥三重 DES（3-key Triple DES）或更现代的算法（如 AES）。
  • 使用 AES 还可以引入 256 位密钥，以应对未来量子计算的潜在威胁。
• 对 ANSI 零售 MAC 的影响：该攻击方法同样适用于基于 2 密钥三重 DES 的 ANSI 零售 MAC，表明该 MAC 方案在 DES 环境下已不再安全。

总结：
这篇论文通过理论推导和算法优化，证明了 2 密钥三重 DES 在拥有大量（即使是部分已知或来自多密钥的）数据时，其安全性远低于预期。它推翻了“定期换钥即可防御”的旧有认知，呼吁业界以紧迫感加速淘汰 2 密钥三重 DES，转向更安全的加密标准。