💻 computer science

A Novel Memory-Efficient MitM Attack on Ascon-Hash

本文提出了一种针对轮函数缩减版 Ascon-Hash 的新型内存高效型中间相遇攻击，该攻击利用 SAT 建模、高斯消元法和三角剖分技术，在保持现有最佳时间复杂度的同时，显著降低了内存复杂度。

原作者： Zhiguo Wu, Bo Gao, Jianxiong Wan, Chuyi Liu, Xiaodong Zhang

发布于 2026-08-31

📖 1 分钟阅读☕ 轻松阅读

原作者： Zhiguo Wu, Bo Gao, Jianxiong Wan, Chuyi Liu, Xiaodong Zhang

原始论文采用 CC BY 4.0 许可（https://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

在数字世界中，安全性往往依赖于强度与效率之间的微妙平衡。对于构成物联网的数十亿个微型、电池供电设备——如工厂中的传感器、智能电表和医疗监护仪——而言，计算能力极其匮乏，内存则更加稀缺。这些设备需要既足够强大以保护数据安全，又足够轻量以在不耗尽电池或占满微小芯片的情况下运行的加密工具。Ascon 是应对这一挑战的领先解决方案，它是一个专门为这些资源受限环境设计的加密和哈希方法家族。为了确保 Ascon 保持安全，研究人员不断对其进行复杂的攻击测试，试图找到破解其代码的最短路径。其中最强大的工具之一是“中间相遇”（meet-in-the-middle）攻击，这是一种攻击者从最终结果向后推导，并从起始点向前推导，希望在中间某个点通过匹配相遇的策略。然而，这种策略传统上需要大量的内存来存储数百万个中间步骤，这一要求往往使得针对 Ascon 所旨在保护的那些设备的攻击变得难以实现。

现在，一个研究小组开发出了一种执行此类攻击的新方法，该方法大幅降低了所需的内存，使得这种测试对于轻量级系统来说更加现实。在一项针对 Ascon-Hash 函数的研究中，作者证明了他们可以在一个简化版的系统中执行该攻击，且使用的存储空间比此前认为的要少得多，同时并未牺牲计算速度。通过将问题视为一个复杂的逻辑约束谜题，他们找到了一种在数据进入存储之前就将其过滤掉的方法。他们的工作表明，对于三轮版本的哈希，所需的内存复杂度可以从 $2^{24}$ 降低到 $2^{14}$ 。对于四轮版本，这种降幅更为显著，将需求从 $2^{34}$ 的复杂度降低到了 $2^{12}$ 。这一成就不仅降低了攻击成本，还为 Ascon 在面对资源有限的对手时究竟有多安全，提供了一个更清晰、更准确的图景。

研究人员首先承认，以往使用自动化搜索工具破解 Ascon 的尝试都撞上了内存使用的壁垒。虽然计算机在寻找加密路径方面变得更快了，但这个过程仍然要求攻击者在内存中保留大量的中间结果，就像试图通过在每一张单独的纸上写下你走的每一个转弯来解决迷宫一样。如果迷宫足够大，在你找到出口之前，纸张就会用完。团队意识到，解决问题的关键不仅在于更快地找到路径，还在于更聪明地记录信息。他们使用了一种称为“可满足性求解”（satisfiability solving）的方法，这本质上是要求计算机寻找一组使复杂逻辑陈述成立的条件。这使得他们能够绘制出加密过程中向前和向后计算可能相遇的具体点。

一旦绘制出这些潜在的相遇点，研究人员应用了一系列代数过滤器来清理数据。他们注意到，控制加密的许多约束可以被分解为简单的线性关系和更复杂的非线性关系。线性部分非常直观；它们可以使用标准的数学技术进行简化，以消除冗余信息，从而有效地缩小计算机需要追踪的可能性列表。非线性部分则更为棘手，但团队开发出一种将其重新排列成三角形形状的方法，从而可以基于其他变量来求解某些变量。这个过程消除了显式计算和存储这些特定变量的需求，进一步减少了内存占用。

最重大的创新在于他们如何处理剩余的、无法轻易简化的复杂约束。研究人员并没有存储每一个可能的结果，而是利用这些剩余的约束创建了一个“残差索引”（residual index），这是一种数字标签或标记。在生成潜在的前向路径列表时，他们根据其特定属性为每条路径分配了一个标签。至关重要的是，他们意识到只有当标签兼容时，后向路径才能与前向路径匹配。这意味着计算机不需要在内存中保留所有可能的前向路径；它只需要保留那些带有后向路径可能到达之标签的前向路径。在他们测试的具体配置中，这种过滤非常有效，以至于将整个必要的前向路径列表缩减到了一个极小的、单一的数据桶中。

这种新方法的成果令人瞩目。当应用于三轮版本的 Ascon-Hash 时，该方法在保持与以往攻击相同速度的同时，将内存需求从 $2^{24}$ 降低到了 $2^{14}$ 。对于四轮版本，这种降幅更为惊人，与之前的最佳方法相比，将内存需求从 $2^{34}$ 的复杂度降低到了 $2^{12}$ 。研究人员验证了这种激进的过滤并不会意外丢弃有效解；他们检查了剩余数据是否仍然满足加密系统的所有原始规则。这项研究证实，通过仔细分析加密结构并应用这些逻辑过滤器，可以用极小部分的资源执行深度的安全测试。这项工作表明，在资源受限的环境中，Ascon 的安全裕度正得到更精确的评估，确保着保护我们互联世界的加密标准如其表现般稳固。

技术摘要：一种针对 Ascon-Hash 的新型内存高效型中间相遇攻击（MitM）

问题陈述
Ascon 是一种被 NIST 选中并标准化为 SP 800-232 的轻量级密码标准，专门为物联网（IoT）等资源受限的环境而设计。在这些场景中，内存往往是比计算能力更关键的约束。虽然中间相遇攻击（Meet-in-the-Middle, MitM）是评估简化轮数 Ascon 预映射抗性的主要工具，但现有的自动化方法面临着显著的内存瓶颈。以往基于 SAT 的框架（例如 Degré 等人提出的框架）成功降低了时间复杂度，但在在线阶段仍需要大量的内存（例如对于 4 轮 Ascon-Hash 需要 $2^{34}$ ）来存储哈希表中的中间值。本文旨在解决如何在保持已知最佳时间复杂度的同时，最小化 Ascon-Hash 中 MitM 攻击的总内存使用量。

方法论
作者提出了一种全新的框架，该框架构建在基于 SAT 的 MitM 搜索之上，但引入了一个后处理代数精炼阶段，以大幅减小存储的 RED 侧表格的大小。该方法论按以下步骤进行：

基于 SAT 的配置搜索： 过程始于使用 SAT 求解器来识别有效的 MitM 配置（定义 RED 侧变量、BLUE 侧变量、匹配位置和抵消位置），以实现目标时间指数。
代数分离： 对于每个找到的时间最优配置，重建诱导的抵消关系，并根据其代数形式将其分为线性部分和非线性部分。
线性归约： 提取线性抵消关系（XOR 约束），并使用高斯消元法在 GF(2) 上进行归约。该线性系统的秩决定了 RED 侧自由变量数量的减少量。
非线性关系的三角化： 使用布尔多项式的三角化算法处理非线性抵消关系。这一步尝试将某些 RED 侧变量表示为其他变量的函数，从而有效地消除它们而不进行显式枚举。
剩余索引过滤： 对于无法通过三角化消除的非线性关系，作者定义了一个“剩余索引”。该索引将 RED 侧赋值划分为若干桶（buckets）。在攻击过程中，仅保留其索引与从 BLUE 侧可计算出的值一致的 RED 桶。这种过滤步骤在最终匹配阶段之前丢弃了不兼容的 RED 赋值。
兼容性验证： 作者验证了过滤过程不会改变匹配方程的解集。他们证明，如果匹配表达式中的混合 RED-BLUE 单项式在保留的定义域上消失，那么 MitM 攻击中使用的可分连接（separable join）仍与求解完整的匹配方程等价。

核心贡献

内存优化框架： 本文引入了一种系统化的方法，通过对抵消关系进行代数处理来精炼由 SAT 衍生的 MitM 配置，专门针对降低在线内存复杂度。
三角化与过滤： 集成了布尔多项式三角化和剩余索引过滤技术，实现了变量消除和搜索空间剪枝，且不会增加时间复杂度。
可分性验证： 该工作提供了一个形式化检查（命题 1），通过验证保留定义域上混合项的消失情况，确保内存缩减技术不会损害 MitM 攻击的正确性。

实验结果
作者在 3 轮和 4 轮 Ascon-Hash 上评估了其方法，并将结果与 Degré 等人 [1] 的基于 SAT 的基准进行了对比。

3 轮 Ascon-Hash：
- 时间复杂度： 保持在 $2^{114}$ 。
- 内存复杂度： 从 $2^{24}$ （基准）降低至 $2^{14}$ 。
- 机制： 该配置使用了 14 个 RED 变量。经过线性秩归约（秩为 1）和剩余索引过滤（仅保留零索引桶）后，在对称简化模型下的保留 RED 表大小降至 $2^7$ ，对应于全量设置下的 $2^{14}$ 。
4 轮 Ascon-Hash：
- 时间复杂度： 保持在 $2^{124}$ 。
- 内存复杂度： 从 $2^{34}$ （基准）降低至 $2^{12}$ 。
- 机制： 该配置使用了 38 个 RED 变量。三角化消除了 5 个变量，剩余索引过滤进一步缩小了保留表格。在 64 列的全量设置下，最终内存复杂度为 $2^{12}$ 。

论文中的表 1 总结了这些改进，显示出在保持原有最先进技术的时间指数的同时，实现了内存指数的一致性降低。

意义与声明
本文声称其主要意义在于，为在内存受限环境下提供了对 Ascon 简化轮数安全裕度的更精确评估。由于 Ascon 是为内存稀缺的 IoT 和嵌入式系统设计的，因此证明 MitM 攻击可以在显著降低内存需求的情况下执行（例如将 4 轮的内存从 $2^{34}$ 降至 $2^{12}$ ）对于准确的安全评估至关重要。

作者指出，他们的框架证明了除了寻找时间最优配置外，通过对抵消关系进行进一步的代数处理，可以有效降低在线存储需求。他们并非声称破解了完整的 Ascon 标准，而是旨在精炼对其简化轮数变体的分析。这项工作表明，未来的研究可以将此方法扩展到更多轮数、其他 Ascon 模式以及其他基于海绵（sponge-based）的轻量级原语。

技术摘要：一种针对 Ascon-Hash 的新型内存高效型中间相遇攻击（MitM）

类似论文