DES 是如何被破解的

DES 有 2^56 个可能的密钥，约等于 7.2 京（72,057,594,037,927,936）个密钥。虽然这个数字听起来极其庞大，但它仍是一个有限的空间，只要计算能力足够，就可以进行系统搜索。

密钥穷举（暴力破解）平均需要测试一半的密钥空间，才能找到正确密钥。对于 DES，这意味着大约需要进行 2^55 次尝试解密，而现代硬件执行每次解密只需几步运算。

1997 年，RSA 数据安全公司悬赏 10,000 美元，征集破解 DES 加密消息的方法。罗克·维瑟尔协调了一个分布式计算项目，动员了数万台连接互联网的计算机。

经过 96 天的搜索，最终找到了密钥。明文为“强大的密码技术让世界更安全。”这次行动证明了 DES 可以被破解，尽管破解过程需要数月时间和大规模协作。

电子前沿基金会于 1998 年耗资 250,000 美元建造了深度破解系统。该系统包含 1,856 个定制 ASIC，每个每秒能够测试 250 万个 DES 密钥，使深度破解系统达到每秒超过 900 亿个密钥的综合测试速率。

深度破解系统平均约 9 天即可遍历整个 DES 密钥空间。这证明了攻击者只需投资 250,000 美元，就能在两周以内破解 DES。

在 DES 挑战赛 II-1（1998 年 2 月）中，深度破解系统与 distributed.net 志愿者计算网络协作，仅用 39 天就破解了 DES。挑战赛 II-2（1998 年 7 月）则在 56 小时内告破。

仅一年时间，破解时间就从 96 天大幅缩短到 56 小时，这表明硬件改进和更好的协作能够多么迅速地加快暴力破解攻击。

1999 年 1 月，EFF 的深度破解系统与 distributed.net 协作，仅用 22 小时 15 分钟就破解了 DES 挑战赛 III，并赢得了 RSA Security 提供的 10,000 美元奖金。

这次决定性的演示表明 DES 可以在 24 小时内被破解，从而有效终结了任何认为 DES 仍然安全的观点。不久之后，NIST 开始着手选择 DES 的替代方案，最终选出了 AES。

Distributed.net 组织了志愿者计算项目，普通互联网用户可以将自己的 CPU 计算周期捐献给 DES 挑战赛。参与计算的计算机数量在高峰期达到数十万台。

每台计算机测试密钥空间中的不同部分，并由中央服务器进行协调。这开创了将分布式计算用于密码分析的模式，如今这种模式仍用于破解旧密码等挑战。

密钥穷举之所以可行，是因为每次 DES 解密都很快（硬件上只需几微秒），而且彼此独立。测试密钥 N 与测试密钥 N+1 之间不存在依赖关系，因此搜索可以在任意数量的计算机之间完美并行。

这种天然高度并行的特性意味着，硬件数量翻倍，所需时间就会恰好减半。增加更多计算机可以带来线性加速，因此对攻击者而言具有良好的经济效益。

Eli Biham 和 Adi Shamir 于 1990 年发表了差分密码分析。这是一种利用输入对中的差异如何在密码轮次中传播的技术。对于 DES，理论上需要 2^47 个选择明文。

后来披露的信息显示，DES 的 S 盒设计时就考虑了抵抗差分密码分析的能力，这表明 NSA 在 20 世纪 70 年代已经了解这项技术。这种攻击在理论上令人印象深刻，但在实际中已被硬件暴力破解的能力远远超过。

Mitsuru Matsui 于 1993 年发表了线性密码分析，攻击 DES 需要 2^43 个已知明文。他实现了这种攻击，并于 1994 年通过实验破解了 DES，证实了理论分析。

线性密码分析会寻找 S 盒行为的线性近似，并利用这些近似中的统计偏差恢复密钥位。从理论上说，它所需的数据远少于暴力破解，但在硬件攻击出现之前，这种方法并不实用。

差分密码分析发表于 1990 年，但需要选择明文，而这在大多数现实场景中并不实用。线性密码分析发表于 1993 年，可以使用已知明文，但需要 2^43 个已知明文。

硬件暴力破解（深度破解系统）于 1999 年在 22 小时内破解了 DES。实际上，硬件攻击比理论密码分析方面的进展更加具有破坏性，因为它完全不需要特殊的明文-密文对。

公开且有文档记录的 DES 破解事件立即产生了政策影响。NIST 于 1997 年开始 AES 竞赛流程，而这一年 DES 挑战赛 I 也取得了成功。这场竞赛的设计明确旨在避免 DES 标准化流程中的弱点。

在 AES 开发期间，银行和政府机构开始过渡到 3DES，作为临时措施。DES 破解的时间线直接决定了采用 AES 的紧迫性和实施时间表。

测试您对 DES 破解历史的理解。

DES 被破解的速度不断加快：1997 年需要 96 天，1998 年需要 56 小时，1999 年只需 22 小时。EFF 耗资 250,000 美元建造的深度破解系统使用定制 ASIC，每秒能够测试 900 亿个密钥。

差分密码分析（2^47 个选择明文）和线性密码分析（2^43 个已知明文）在理论上也能破解 DES，但硬件暴力破解才是实际上的致命打击。22 小时破解事件终结了 DES 作为可行密码的生命。