💻 computer science

A Generalized PNE Framework: Taking ChaCha Further in Syncopated Rhythm

本文引入了一种广义的概率中性表达式（PNE）框架，该框架结合了切分（syncopation）和进位保持（carry-preserving）等新技术，显著提升了针对轮缩减 ChaCha 的密钥恢复攻击，实现了对 ChaCha8 的首次相关密钥攻击，并破解了 256 位 ChaCha 的 7.5 轮。

原作者： Shichang Wang, Meicheng Liu, Shiqi Hou, Chengan Hou, Dongdai Lin

发布于 2026-08-31

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Shichang Wang, Meicheng Liu, Shiqi Hou, Chengan Hou, Dongdai Lin

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

在我们的私人信息、金融交易和安全连接穿梭其中的广袤数字景观中，存在着一种被称为流密码的沉默守护者。可以将它想象成一台高速运转的机器，它生成一段看似随机的长数字流来扰乱数据，确保只有持有正确密钥的人才能解密并读取原始信息。这类机器中最受信任的型号之一被称为 ChaCha。它是许多日常互联网协议背后的引擎，保护着从你的网页浏览到加密电子邮件的一切。由于其应用极其广泛，它的强度不断受到密码分析师的测试——这些专家试图破解这些代码，并非为了窃取秘密，而是为了理解它们的极限并确保它们保持安全。破解像 ChaCha 这样的密码的核心挑战在于，它构建于一种将加法、位旋转和开关翻转等简单操作以一种迅速变得极其复杂的方式混合在一起的结构之上。为了寻找弱点，研究人员必须追踪输入中的微小变化如何通过这些操作产生涟漪，以观察是否会在输出中产生可预测的模式。

一组研究人员现在通过开发一种分析这些“涟漪”如何行为的新方法，在理解 ChaCha 的极限方面迈出了重要一步。他们专注于一种称为“差分密码分析”的具体技术，该技术涉及向密码输入两个略有不同的输入，并观察这些差异如何演变。在以往尝试破解 ChaCha 的尝试中，研究人员必须猜测海量的可能密钥，以观察哪一个密钥符合观察到的模式，这个过程通常过于缓慢而无法投入实际应用。这项新研究引入了一种改进的方法，使用了名为“切分”（syncopation）的概念。在这一密码的语境下，这种技术允许研究人员识别出在某些特定条件下对最终扰乱输出几乎没有影响的特定密钥部分。通过隔离这些非影响力部分，研究人员可以有效地在攻击的初始阶段忽略它们，从而大幅减少了需要测试的可能性。这类似于通过首先撇开那些显然不属于中心图像的碎片来解决一个复杂的拼图，从而让你能够将精力集中在真正关键的碎片上。

利用这种“切分”技术，结合一种猜测剩余密钥位的全新策略，研究人员成功破解了此前被认为在面对此类攻击时依然安全的某些版本的 ChaCha。具体而言，他们展示了对一个经过 7.5 轮处理的密码版本的成功攻击。虽然完整的标准版 ChaCha 使用 20 轮处理，但破解 7.5 轮是一项显著的成就，因为这是第一次有人针对这一特定轮数的版本执行了比单纯逐一猜测所有可能密钥更快的密钥恢复攻击。研究人员还表明，他们的方法可以改进对 7 轮版本密码的攻击，使其比之前的尝试效率显著提高。此外，他们还将这些技术应用于一个仅使用 8 轮处理的相关版本密码 ChaCha8。在攻击者可以使用两个非常相似的密钥这一场景下，他们找到了一种破解 ChaCha8 的方法，这表明如果这种情况发生，该特定变体可能无法提供其设计者所预期的完整安全水平。

该研究还研究了一个使用 128 位密钥而非标准 256 位密钥的较短版本密码。在这里，研究人员在移除扰乱过程的最末一步的情况下，成功破解了一个 7 轮版本的短密钥密码。这些结果并不意味着目前用于你浏览器等现实世界应用中的完整版 20 轮 ChaCha 已被破解。完整版本仍然是安全的。然而，这些发现至关重要，因为它们推向了已知密码内部机制的边界。通过证明密码在特定的、受控的条件下可以被削弱，研究人员为密码学界提供了宝贵的反馈。这有助于确保保护我们数字生活的算法是稳健的，并确保任何潜在的漏洞在被现实世界利用之前都能被识别并得到解决。这项工作代表了在理解并保障我们数字隐私的数学基础这一持续努力中，迈出的虽小但艰难的一步。

技术摘要：一种广义 PNE 框架：通过切分节奏（Syncopated Rhythm）进一步推进 ChaCha 研究

1. 问题陈述

流密码 ChaCha，特别是 256 位变体，已被广泛部署在 TLS、SSH 和 QUIC 等现实世界的协议中。尽管其应用广泛，但减轮 ChaCha 的安全裕度一直是密码分析研究的热点。在此项工作之前，针对 256 位 ChaCha 最有效的密钥恢复攻击局限于 7 轮（时间复杂度通常超过 $2^{220}$ ）或 7.25 轮，并且在单密钥设置下，尚未有任何比暴力破解（ $2^{256}$ ）更快的针对 7.5 轮的攻击被成功演示。此外，8 轮变体（ChaCha8）在相关密钥设置下的安全性在很大程度上仍未得到充分探索。

差分密码分析中的核心挑战在于识别出的概率中性位（PNB）数量与后向近似（backward approximation）相关性之间的权衡。传统方法往往难以找到既能拥有大量 PNB 又能保持高相关性的集合，从而限制了中间相遇攻击（meet-in-the-middle attacks）的效率。此外，以往对“强密钥”（即不存在合适的 IV 来满足差分特性的密钥）的分析缺乏全面的理论证明。

2. 方法论

本文引入了一种基于概率中性位（PNB）的改进型差分密码分析框架，并将其推广为基于概率中性表达式（PNE）的框架。该方法由三个主要的的技术支柱组成：

2.1 用于 PNB 的切分节奏（Syncopation）技术

作者引入了“切分节奏”（syncopation）来解决寻找大量 PNB 与保持高相关性之间的矛盾。

概念： 后向近似函数 $f$ 被分解为 $f = f_1 \circ f_0$ 。该技术通过对特定非 PNB 位（受限位）施加限制，以确保第一部分（ $f_0$ ）的输出与 PNB（切分位）无关。
机制： 通过利用 ARX 结构中模加法和模减法的性质，作者推导出了控制进位传播的条件。这使得特定段的输出可以仅由已知的公开值和非 PNB 决定，从而有效地实现了对未知 PNB 依赖性的“切分节奏化”。
结果： 该技术显著增强了后向近似的相关性。作者还提供了一个工具（算法 1）用于系统地确定有利的切分段，以及一个贪心算法（算法 2）用于构建最优的条件 PNB（CPNB）集合。

2.2 广义 PNE 框架

为了进一步提高效率，本文将 PNB 的概念推广到了概率中性表达式（PNE）。

密钥猜测策略： 攻击不再直接猜测原始密钥位，而是猜测一个等效密钥 $H(K)$ ，其中 $H$ 是根据密码结构定制的可逆函数（例如涉及旋转和异或的线性组合）。
进位保持技术： 引入了一种针对模加法的创新技术。通过对公开数据施加线性条件，可以在不知道未知密钥位（PNB）的情况下确定模加法的进位向量。这简化了非线性操作，使得近似过程可以在保持高相关性的同时忽略密钥的未知部分。
集成： 该框架允许在传统 PNB 稀缺的情况下（特别是在后期轮次或状态矩阵的特定对角线上）发现更多的中性元素（PNE）。

2.3 精细化前向差分分析

本文对控制 ChaCha 第一轮的差分方程进行了更深入的理论分析。

强密钥分析： 作者为“强密钥”（即不存在满足差分的 IV 的密钥）的存在提供了全面的理论解释，涵盖了内部状态变量的所有八种情况，而以往的工作仅涵盖了两种情况。他们证明了大约 29.6875% 的密钥是强密钥。
高效配对生成： 通过分析差分方程，作者识别了可以翻转以高概率满足差分约束的特定 IV 位，从而降低了寻找正确配对所需的数据复杂度。

3. 主要贡献

切分节奏技术： 一种通过利用 ARX 结构特性来放大后向近似相关性的新方法，从而实现更高效的 PNB 选择。
广义 PNE 框架： 使用等效密钥表达式和进位保持技术的 PNB 方法的扩展，实现了使用更少猜测位和更高相关性的攻击。
理论完整性： 对第一轮中所有差分情况下的强密钥概率进行了完整的理论推导，修正并扩展了以往的部分分析。
新的攻击结果：
- 256 位 ChaCha： 首个比暴力破解（ $2^{256}$ ）更快的 7.5 轮 密钥恢复攻击（时间复杂度为 $2^{254.6}$ ）。同时也改进了针对 7 轮和 7.25 轮的攻击，降低了复杂度。
- ChaCha8（相关密钥）： 首个针对 256 位 ChaCha8（8 轮）的相关密钥攻击，当使用一对具有固定差分的密钥时，展示了 $2^{253.3}$ 的时间复杂度。
- 128 位 ChaCha： 改进了针对 6.5 轮的攻击，并提出了针对 7 轮（排除最后一次旋转，记作 $7\ll$ ）的新攻击。

4. 结果

论文给出了以下具体的攻击复杂度（时间/数据）：

256 位 ChaCha7：
- $2^{210.3}$ 时间 / $2^{103.3}$ 数据（使用 89 个 CPNB）。
- $2^{216.9}$ 时间 / $2^{68.9}$ 数据（使用 74 个 CPNB）。
- 使用切分节奏技术作用于 5 轮 DL 分类器后，改进为 $2^{187.2}$ 时间 / $2^{108.2}$ 数据。
256 位 ChaCha7.25：
- $2^{220.0}$ 时间 / $2^{109}$ 数据。
256 位 ChaCha7.5：
- $2^{254.6}$ 时间 / $2^{125.3}$ 数据。 这是第一个比暴力破解（ $2^{256}$ ）更快的 7.5 轮攻击。
256 位 ChaCha8（相关密钥）：
- $2^{253.3}$ 时间 / $2^{99.2}$ 数据。 这打破了 ChaCha8 在相关密钥模型下的 256 位安全声明。
128 位 ChaCha：
- ChaCha6.5： $2^{114.3}$ 时间 / $2^{100.3}$ 数据。
- ChaCha7 $\ll$ ： $2^{122.9}$ 时间 / $2^{108.8}$ 数据。

实验验证在具有 64 个未知密钥位的 5 轮和 6 轮 ChaCha 上进行，证实了理论上的相关性提升和成功概率（5 轮约为 70%，6 轮为 62.5%-71.4%）。

5. 意义与主张

本文声称在 ChaCha 的安全性分析中迈出了“虽小但艰难的一步”。其主要意义在于：

突破 7.5 轮屏障： 这是首次演示出针对 256 位 ChaCha 7.5 轮的密钥恢复攻击比暴力搜索更有效。
首个 ChaCha8 相关密钥攻击： 它表明如果允许使用具有特定差分的密钥对，ChaCha8 将无法实现 256 位安全性，这对 8 轮变体的实际安全性假设提出了挑战。
方法论的进步： 切分节奏（Syncopation）技术和广义 PNE 框架（包括进位保持和新的密钥猜测策略）的引入，提供了一个更强大的工具包，用于分析基于 ARX 的密码，这些方法可能同样适用于 Salsa 或 Chaskey 等其他设计。

作者明确指出，这些攻击并不威胁实际部署中的全 20 轮 ChaCha，但它们显著缩小了减轮变体的安全裕度，并突显了 8 轮相关密钥设置下的理论弱点。