✨ 要点🔬 技术摘要
想象一个数字锁与钥匙的世界，在那里，秘密信息被加密，只有预定的接收者才能阅读。几十年来，一种被称为数据加密标准（DES）的特定锁一直是守护秘密的金科玉律。把 DES 想象成一个拥有 56 个数字转盘的大型密码锁。为了破解它，窃贼必须尝试每一个可能的组合，直到锁扣弹开。因为数字的数量非常庞大，人们曾认为只有超级计算机或大规模定制的机器才能足够快地尝试完所有组合。但世界已经改变了。今天，我们有了“云”，它就像是按分钟租用一支巨大的、隐形的计算机军队，而不是购买属于你自己的电脑。研究人员一直在问一个大问题：如果你只想破解这把旧锁，租用那支军队需要多少钱，以及你需要等待多久？这个问题至关重要，因为如果成本很低且时间很短，那么这把旧锁就不再安全了，我们需要准确知道我们的旧秘密究竟有多脆弱。
这篇论文就像是一场大胆的实验，两位研究人员 Gonzalo 和 Rodrigo 决定通过实际租用一支云端军队来破解这个 DES 锁，从而寻找答案。他们没有制造专门的机器；他们只是使用了任何持有信用卡的人都能在亚马逊 AWS 云端获取的标准计算机。他们组建了一个由 37 台这类计算机组成的团队共同工作，每台机器检查庞大数字组合中的不同部分。他们把这项工作处理得像一场巨大的寻宝游戏：他们将“宝藏”（秘密密钥）藏在距离起点不同的距离处，并记录下计算机军队找到它所花费的时间。
结果显示，对于较短的距离，速度快得惊人且成本极低。当宝藏藏得很近时（在前 1 亿个组合之内），计算机大部分时间都花在了“苏醒”和准备工作的过程中。在这种情况下，整个任务大约耗时两分钟，成本不到 50 美分。这就像付给出租车司机几美元让他把你送到街角商店一样；路程本身是瞬间完成的，但时间主要花在等待司机到达上。
然而，随着他们将宝藏藏得更远，情况发生了变化。当他们将搜索范围推向 150 亿个组合时，实际寻找密钥所花费的时间成为了主要因素。计算机稳定地工作着，在约 87 分钟内找到了密钥，成本约为 18 美元。研究人员发现，这些计算机效率极高，单台机器每秒能检查近 300 万个组合。当你把所有 37 台机器加在一起时，它们每秒钟能检查超过 1 亿个密钥。
他们发现中最令人兴奋的部分是，如果你真的想破解“整个”锁，而不仅仅是其中的一小部分，会发生什么。整把锁大约有 72 亿亿（72 quadrillion）种可能的组合。使用他们目前的 37 台计算机设置，检查每一个组合需要大约 21 年。这听起来是不可能的，但研究人员展示了由于这项工作非常容易拆分，你可以用金钱换取时间。如果你口袋很深，租用一支约 14 万台计算机的庞大舰队，你可以在短短一天内破解整把锁。进行这项巨大努力的总成本约为 120 万美元。
那么，这意味着什么？这篇论文证明了旧的 DES 锁实际上已经被破解了。如果坏人只有少量的钱，他们可以用一杯咖啡的价格破解一段特定的、有限的代码。如果他们有很多钱，他们可以在一天之内破解整个代码。研究人员还指出，虽然他们基于计算机的方法很快，但使用现代显卡（就是那些用于玩游戏的显卡）可以让这件事情变得更便宜、更快，可能会将时间和成本再降低一百倍。结论很明确：56 位的锁不再是障碍；它仅仅取决于你愿意花多少现金去破解它。
技术摘要：租用破解机器——关于在云端进行穷举 DES-56 密钥搜索的成本与时间分析
问题陈述 2 56 ≈ 7.2 × 10 16 2^{56} \approx 7.2 \times 10^{16} 2 56 ≈ 7.2 × 1 0 16
方法论
系统架构： 该系统利用一个协调器（Python）和 37 个工作节点（AWS EC2 c6i.2xlarge 实例，每个实例包含 8 个 vCPU）。56 位密钥空间被划分为 37 个不相交的范围。协调器通过用户数据（user-data）脚本启动实例，分发搜索范围，并通过 Amazon SQS（简单队列服务）管理结果报告，利用 Amazon S3 广播停止信号。工作节点实现： 工作节点使用 C 语言编写，并结合 OpenMP 在 8 个 vCPU 上进行并行化搜索。为了最大化吞吐量，实现中包含了四项特定优化：
SP 表： 预计算结合了 S-box 置换和 P-置换的表，该表完全适配于 L1 缓存。字节索引查找表（LUTs）： 用于位置换（IP, IP⁻¹, PC-1, PC-2）的查找表，以消除位级循环。直接位移扩展： 将扩展函数与子密钥 XOR 及表索引融合，以避免生成中间的 48 位值。早期拒绝（COA 模式）： 在仅密文攻击（COA）模式下，一旦遇到非打印字节，解密立即停止。这在单个数据块后即可拒绝约 99.96% 的随机密钥，从而大幅降低了每个密钥的有效成本。
评分机制： 系统运行在仅密文攻击（COA）模式下，使用基于西班牙语一元字母频率的对数频率得分来识别有意义的明文。阈值设为 − 4.0 × nbytes -4.0 \times \text{nbytes} − 4.0 × nbytes 实验设计： 作者进行了 15 组独立的试验，分为两组：
A 组（启动主导型）： 10 组试验采用较小的偏移量（10 6 10^6 1 0 6 10 8 10^8 1 0 8 B 组（搜索主导型）： 5 组试验采用较大的偏移量（10 9 10^9 1 0 9 1.5 × 10 10 1.5 \times 10^{10} 1.5 × 1 0 10
关键结果
吞吐量： 系统实现的测量聚合吞吐量约为每秒 1.08 亿个密钥 （每个实例 291 万个密钥/秒），分布在 37 个实例上。搜索时间与偏移量的线性拟合得出 R 2 R^2 R 2 时间与成本区间：
小偏移量 (≤ 10 8 \le 10^8 ≤ 1 0 8 总时间由 AWS 启动延迟（约 90 秒）主导。这些试验的平均时间为 116.8 ± 20.1 116.8 \pm 20.1 116.8 ± 20.1 $0.41 。大偏移量： 搜索时间成为主导因素。位于 1.5 × 10 10 1.5 \times 10^{10} 1.5 × 1 0 10 87 分钟 ，成本为 $18 。
全密钥空间外推：
在测得的吞吐量下，单个 37 实例机群完成整个 2 56 2^{56} 2 56 21 年 ，预期情况需要约 10.6 年 。
然而，由于该工作负载具有“易并行化”（embarrassingly parallel）的特性，时间可以与金钱进行线性交换。作者估计，完成一次完整的穷序搜索大约需要 120 万 ∗ ∗ （预期情况）或 ∗ ∗ 120 万**（预期情况）或 ** 120 万 ∗ ∗ （预期情况）或 ∗ ∗
通过足够大的规模（例如 ≈ 1.4 × 10 5 \approx 1.4 \times 10^5 ≈ 1.4 × 1 0 5
意义与主张
受限子空间攻击： 对于处于已知且可控范围内的密钥空间，此类攻击极其廉价（不足 1 美元）且快速（仅需数分钟）。全量穷举： 虽然昂贵，但对于资金充足的攻击者而言，使用仅有的通用资源进行完整的穷举搜索是“完全可行的”。这不再是一个技术障碍，而是一个预算障碍。经济转型： 与历史上的专用硬件（如 2006 年的 COPACOBANA）相比，云计算提供了极低的准入门槛，且无需前期资本投入。未来展望： 作者指出，目前的 CPU 实现并非最具成本效益的选择；他们建议将系统移植到 GPU 上（引用了可能达到数十亿密钥/秒的吞吐量），这可以将时间与成本降低一到两个数量级。
论文断言，DES 在现代环境下已不再提供任何有意义的安全保障，因为弹性云容量与并行处理能力的结合，使得密钥空间对于任何拥有足够资金的实体来说都是可搜索的。
每周获取最佳 computer science 论文。
受到斯坦福、剑桥和法国科学院研究人员的信赖。
请查收邮箱确认订阅。
出了点问题，再试一次？
无垃圾邮件，随时退订。