一种用于对 AndRX 密码进行微分中间相遇攻击的自动化模型

这项研究为何重要

每次我们使用智能手机、进行在线支付或连接医疗设备时，被称为分组密码的小型数字锁会保护我们的数据。安全专家不断尝试攻破这些锁以设计更安全的方案。本文提出了一种自动化实施对广泛使用的轻量级密码家族进行强力攻击的新方法，帮助研究人员检验这些数字锁的实际强度。

现代破译工作的运作方式

现代分组密码通过许多小步骤（或轮）对数据进行混淆，这些步骤由秘密密钥控制。为判断密码是否安全，密码分析学家会寻找在系统应当表现为纯随机时不应出现的模式。两种经典工具是微分密码分析，它追踪输入上微小变化如何传递到输出；以及中间相遇（meet-in-the-middle）攻击，它从密码的两端计算并在中间寻找匹配。单独使用每种工具都有局限，但将它们结合能更敏锐地探测密码结构。

融合两种攻击思路

本研究聚焦于一种混合技术，称为微分中间相遇攻击（differential meet-in-the-middle）。在这里，密码被分成三部分：输入段、中间段和输出段。在中间，攻击者寻找一个“微分判别器”——一种在若干轮中出现概率高于随机的输入与输出差分模式。围绕这一核心，攻击者从开始处部分加密并从末尾部分解密，只猜测选定的密钥位。当两个方向在相同的内部状态处相遇时，猜测更可能对应真实密钥，从而缩小搜索空间。

将手工技艺转为自动化工具

手工设计这种组合攻击极为棘手，尤其是对比特导向的密码，其内部状态可能为 64、96 或 128 位。作者构建了一个使用约束编程的自动化框架，这是一种描述复杂逻辑条件以便求解器探索所有有效可能性的办法。首先，他们对基于 AND、旋转和 XOR 操作的密码基础构件中差分如何传播进行了编码，这类设计统称为 AndRX。然后他们建模了哪些密钥位影响每一阶段以及必须实际猜测的位数。求解器在多种将密码划分为输入、中间和输出段的方式上搜索，选择能最小化整体攻击代价的布局。

额外技巧以削减密钥空间

在基础模型之上，该框架为类似 SIMON 和 Simeck 的 Feistel 风格 AndRX 密码加入了两种专门的优化技巧。第一种称为等效子密钥（equivalent subkey）思想，通过数学上将部分轮密钥前移或后移，使若干不同的密钥位表现得如同相同位，从而减少攻击者需考虑的独立位数。第二种是选择性密钥猜测（selective key guessing），研究非线性 AND 操作如何使用其输入，并表明在特定条件下一个猜测位可以替代两个位。作者还描述了但尚未完全自动化的两项改进：并行分区（parallel partitioning），可在不增加时间的情况下为攻击添加额外一轮；以及一种数据减少技巧，可降低所需的选择明文数量。

该工具对实际密码的揭示

为验证方法，研究人员将其自动模型应用于所有标准版本的轻量级密码 SIMON 和 Simeck，这些密码是用于传感器和嵌入式控制器等受限设备的候选方案。对每个变体，工具都找到了一种微分中间相遇攻击并估算其数据、时间与内存代价。在许多情况下，这些攻击覆盖的轮数超过了此前的中间相遇或相关技术，并且在轮数覆盖方面常常也优于早期的不可能差分和零相关攻击。例如，该工具针对带有 256 位密钥的 128 位版本 SIMON 找到了多达 51 轮的攻击，扩展了先前方法的攻击深度，同时将工作量保持在低于穷举全密钥搜索的水平。

对未来密码学的总体展望

对于非专业读者，关键信息并不是说 SIMON 或 Simeck 在实际场景中已被“破坏”，而是自动化工具已变得足够强大，能够发现人工很难察觉的微妙弱点。此处介绍的框架在比特级别上具有通用性，原则上可适配到其他密码家族。通过帮助设计算法的人快速测试新算法在面对高级组合攻击时的表现，此类工具有助于实现长期目标：构建即便在分析技术日益成熟时仍保持稳固的加密方案。

引用: Chakraborty, D., Sahoo, S., Nguyen, P.H. et al. An automated model for differential meet in the middle attacks on AndRX ciphers. Sci Rep 16, 14773 (2026). https://doi.org/10.1038/s41598-026-41390-w

关键词: 分组密码密码分析, 微分中间相遇, SIMON 密码, Simeck 密码, 约束编程