💻 computer science

Full-Key Recovery and Forgery from One MQOM v2.1 Signature

本文提出了一种针对 NIST 第三轮签名候选算法 MQOM v2.1 的全密钥恢复与伪造攻击，证明了仅需一个接受的签名就足以推导出完整的秘密密钥并伪造新签名，且其计算成本低于 NIST 所有类别下的安全基准。

原作者： José Luis Delgado

发布于 2026-08-11

📖 1 分钟阅读☕ 轻松阅读

原作者： José Luis Delgado

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

想象一下，你正试图给你的朋友发送一条秘密信息，但你生活在一个未来可能存在超级快速计算机（被称为量子计算机）的世界里。这些未来的机器可能会破解我们今天用来保护秘密的大多数锁。为了应对这种情况，科学家们正在构建一种新的、极其坚固的数字锁，叫做“后量子签名”。你可以把它们想象成写在信件上的特殊蜡封。即使有一个盗贼拥有能砸碎普通锁具的魔法锤，这种新的蜡封所用的材料也应该能够经受住考验。

其中一个正在被测试的最有前途的锁被称为 MQOM。它的工作方式有点像一个巨大的、复杂的谜题。为了对信件进行签名，发送者使用一个秘密的“见证人”（隐藏密钥）来解决一个涉及许多变量的数学问题。为了证明自己解决了这个问题而不暴露秘密本身，他们使用了一种巧妙的技巧，叫做“头脑中的多方计算”（MPC-in-the-head）。想象一下，发送者假装自己是一个整个团队，每个人都握着秘密的一小部分。他们玩一场游戏，只展示足够多的信息，以证明这个团队共同解决了谜题，但又不足以揭示实际的秘密碎片。如果数学逻辑成立，那么签名就是有效的。我们之所以关注这一点，是因为如果这些新锁存在隐藏的裂缝，我们未来的数字安全可能会在威胁到来之前就崩塌。

现在，让我们谈谈这篇论文中的故事。研究人员 José Luis Delgado 仔细检查了这种特定版本的 MQOM 锁（版本 2.1），并发现了一种出人意料的简单破解方法。论文指出，如果攻击者只要获得该系统的一个有效签名，他们就能推导出整个秘密密钥，并为任何消息伪造新的签名。这就像是一个小偷看到你打开家门一次，仅仅通过这一次窥视，就足以让他们制造出一把能打开你家所有锁的万能钥匙。

以下是这个“魔术戏法”是如何运作的，通过一个故事来解释。想象一下，秘密密钥是一张长长的、隐藏的藏宝图。MQOM 系统将这张地图隐藏在一棵由树枝组成的巨大树木之中。当你签名时，系统会向你展示一条通往特定隐藏叶片（地图上的一个点）的路径，但它会保持叶片本身处于遮盖状态。然而，它也会给你一个“兄弟路径”——即隐藏叶片相邻的树枝列表。由于这棵树的构建方式，如果你知道叶片旁边的树枝，你就能推算出如果已知秘密地图的一个微小前缀，那个隐藏叶片将会是什么。

论文发现，系统还留下了一个“承诺”，这就像是一个装着隐藏叶片的密封信封。研究人员意识到，通过将兄弟路径（树枝）与密封信封结合起来，他们可以写下一个单一的、巨大的方程。这个方程只有一个未知数：秘密地图的那个微小前缀。攻击者不需要猜测整张地图；他们只需要解出这个方程，就能找到这个微小前缀。

一旦他们找到了这个前缀，他们手头已有的签名就会提供一个“修正后缀”——这就像是一张小纸条，上面写着：“这是配合你刚刚找到的前缀所需的地图剩余部分。”通过将这个前缀和这张纸条拼接在一起，攻击者就可以重建整个秘密地图（完整的签名密钥）。有了这个密钥，他们可以为任何新消息签名，且系统会将其视为真实有效。

这篇论文并不只是猜测这行得通；他们通过数学计算和计算机实验证明了这一点。他们精确计算了解决这个方程所需的计算能力，针对不同的锁强度等级（称为类别 I、III 和 V）。他们发现，对于所有三个类别，所需的努力程度都低于 NIST 为这些锁设定的安全限值。

对于最简单的级别（类别 I），攻击大约需要 $2^{142.335112}$ 次运算。对于中等级别（类别 III），根据他们扫描地图的方式，大约需要 $2^{206.774558}$ 或 $2^{206.988658}$ 次运算。对于最难的级别（类别 V），则需要大约 $2^{271.794162}$ 次运算。在每种情况下，攻击者所需的步骤都低于该锁原本设计要求具备的安全步骤数。

研究人员不仅做了数学推导，还构建了一个实际运行该攻击的计算机程序。他们获取了一个真实的签名，解出了方程，逐字节地恢复了精确的秘密密钥，然后使用该密钥签署了一个全新的消息。系统的验证器检查了新签名，并表示：“是的，这是有效的！”这证明了该攻击在现实世界中是成立的，而不仅仅是在纸面上。

论文还探讨了改变某些设置是否能解决问题。他们发现，仅仅在过程中添加一个“盐值”（一个随机数）虽然改变了方程中的数字，但并不能阻止攻击。方程依然存在，只是看起来略有不同。要真正修复这个问题，设计者必须改变树路径与秘密之间的关系、叶片是如何被承诺的，或者修正说明是如何生成的。

简而言之，这篇论文表明，当前的 MQOM 锁存在一个足以让人直接走过去的漏洞。它能将单个签名转化为一把万能钥匙，让攻击者能以比锁的设计初衷更低的成本伪造消息。作者分享了他们的代码和结果，以便他人核实，并建议 MQOM 的设计者需要在其被视为安全可靠之前，修补这些特定的系统部分。

技术摘要：基于单次 MQOM v2.1 签名的全密钥恢复与伪造

问题陈述
本文针对 NIST 第三轮候选签名方案 MQOM v2.1 提出了一种密码分析攻击。该攻击证明，仅需一个被接受的签名即可恢复完整的长期签名密钥。一旦密钥被恢复，攻击者即可伪造新消息的签名，且该签名能被参考验证器接受。该漏洞源于相关 GGM 种子树、隐藏叶子承诺机制以及签名转录中包含的见证修正后缀（witness correction suffix）之间的相互作用。

方法论
该攻击通过基于公开转录字段对签名见证进行确定性重构来实现。核心方法包括以下步骤：

推导公开方程：
签名揭示了相关二叉种子树中的兄弟路径。由于该树的构造特性（其父节点是其子节点的异或结果），隐藏叶子 $s_e$ 可以表示为长期见证前缀 $\delta = \text{FirstBits}_\lambda(x)$ 与公开路径值 $A_e$ 的仿射函数：
$s_e = \delta \oplus A_e$
签名还包含对此隐藏叶子的承诺： $C_{e,c} = \text{Enc}_{K_{e,c}}(s_e) \oplus \text{LinOrtho}(s_e)$ 。将该仿射恒等式代入承诺方程，可得到一个以 $\delta$ 为唯一未知数的公开方程：
$\text{Enc}_{K_{e,c}}(\delta \oplus A_e) = T_{e,c} \oplus \text{LinOrtho}(\delta)$
其中 $K$ 、 $T$ 和 $A$ 完全由被接受的转录生成。
通过保留状态遍历进行候选枚举：
为了求解 $\delta$ ，攻击者必须在 $\lambda$ 位定义域上评估该方程。为了避免为每个候选值重新评估固定的 AES/Rijndael 电路，本文采用了格雷码反射遍历（reflected Gray code traversal）。通过在相邻候选值（其差异仅为一个比特）之间保留电路状态，攻击者只需更新受改变位影响的依赖锥（dependency cone）。这种“保留状态计算”显著降低了扫描所需的总门电路计数。
见证重构与密钥恢复：
对于每一个满足公开方程的候选值 $\hat{\delta}$ ，攻击者利用发布的修正后缀（ $\text{NextBits}_\lambda(\Delta x)$ ）和兄弟路径来重构完整的 MQ 见证 $\hat{x}$ 。随后评估公开 MQ 关系 $Q(\hat{x}) = y$ 。若该关系成立，则将 $\hat{x}$ 序列化为有效的私钥。
伪造：
利用恢复的私钥对新消息进行签名。参考验证器接受该签名，从而证实了全密钥恢复以及存在性不可伪造性（EUF-CMA）的破坏。

主要贡献与结果

单次签名实现全密钥恢复： 本文证明，对于 NIST 第一、三、五类（使用 F256 fast-r3 代表元）标准，单个签名即可破解该方案。
具体成本评估： 作者提供了攻击的精确布尔门计数，并利用独立生成的源语法电路进行 AES/Rijndael 置换计算。
- 第一类： $2^{142.335112}$ 个门（基准： $2^{143}$ ）。
- 第三类： 半覆盖度为 $2^{206.774558}$ 个门，高覆盖度为 $2^{206.988685}$ 个门（基准： $2^{207}$ ）。
- 第五类： $2^{271.794162}$ 个门（基准： $2^{272}$ ）。
  所有攻击成本均严格低于相应的 NIST 安全基准。
伪造验证： 参考执行成功恢复了所有三个类别中的字节级精确见证和密钥，并生成了被参考验证器接受的新消息伪造签名。
理论界限： 本文确立了一个精确的阶乘矩量界限，用于衡量到达公开 MQ 验证阶段的假阳性（额外方程原像）数量。在理想密码模型（ICM）下，在完整定义域内超过 64 次验证的概率被限制在 $1/64!$ 以内，确保了攻击在计算上的可行性。

意义与主张
本文声称，MQOM v2.1 特有的接口设计——特别是路径到前缀的恒等关系、隐藏叶子承诺谓词以及修正到见证的映射组合——创建了一个“单签名恢复通道”。

转录独立性： 该攻击适用于通过随机预言机模型（ROM）、量子随机预言机模型（QROM）或具体的 SHAKE 实例化生成的转录，因为方程仅依赖于固定的公开字段。
盐值绑定持久性： 作者证明，即使全局根扩展与签名盐值绑定（导致公开常量 $A_e$ 和 $T_{e,c}$ 发生变化），恢复方程的形式保持不变，从而保留了攻击向量。
设计启示： 本文结论指出，防止此类攻击需要修改基础映射：例如使用非仿射开启方式改变路径到前缀的恒等关系、通过使用每签名私有状态改变隐藏叶子谓词，或者将修正过程与长期见证的恢复解耦。

作者提供了一个公开的制品，用于重现所有计算结果、源代码以及攻击和电路生成过程。

类似论文