【密码学百科】流密码：RC4 的兴衰与 ChaCha20 的崛起

在前几篇文章中，我们深入讨论了分组密码（block cipher）的内部结构与工作模式。分组密码每次处理固定长度的数据块，但现实世界中的数据流往往长度不一、到达时间不确定——网络数据包、语音通话、实时视频流都需要一种更灵活的加密方式。流密码（stream cipher）正是为此而生的：它生成一段与明文等长的伪随机密钥流（keystream），再将密钥流与明文逐比特或逐字节进行异或（XOR）运算，从而完成加密。这种设计在概念上直接呼应了香农（Claude Shannon）所证明的一次性密码本（One-Time Pad, OTP）——只要密钥流真正随机且只使用一次，加密便是信息论意义上不可破解的。流密码的工程目标，就是用一个短密钥和一个确定性算法，来尽可能逼近这一理想。

本文将从流密码与分组密码的本质差异出发，追溯线性反馈移位寄存器（LFSR）的经典理论，详细剖析 RC4 从辉煌到退役的全过程，然后转向 Daniel J. Bernstein 设计的 Salsa20/ChaCha20 家族，最后介绍 eSTREAM 项目和 XChaCha20 等现代实践。

一、流密码 vs 分组密码

基本设计差异

分组密码的核心操作单元是固定大小的块（block），例如 AES 的 128 比特。无论输入数据有多大或多小，都需要先被切割或填充（padding）到块大小的整数倍，然后逐块加密。相比之下，流密码不存在”块”的概念。它接受一个密钥（key）和一个初始向量（IV）或随机数（nonce），输出一段理论上无限长的伪随机密钥流。加密时，只需将密钥流与明文逐比特异或即可：

\[C_i = P_i \oplus K_i\]

其中 \(P_i\) 是第 \(i\) 个明文比特，\(K_i\) 是密钥流的第 \(i\) 个比特，\(C_i\) 是对应的密文比特。解密过程完全对称：

\[P_i = C_i \oplus K_i\]

这种对称性意味着加密和解密使用完全相同的算法——这在硬件实现中是一个显著优势。

何时选择流密码

流密码在以下场景中具有天然优势：

第一，当数据以流的形式到达、长度事先未知时，流密码可以立即处理每个到达的字节，而无需等待凑满一个块。这使得它非常适合实时通信协议，如 TLS 记录层、SSH 隧道和无线通信。

第二，在硬件资源极其有限的嵌入式设备中，流密码通常比分组密码需要更少的门电路（gate count）和更低的功耗。一个精心设计的 LFSR 流密码可以在不到一千个门电路中实现，而 AES 的紧凑硬件实现通常需要数千个门。

第三，在没有硬件 AES 加速指令（AES-NI）的处理器上，基于 ARX（Add-Rotate-XOR）操作的流密码（如 ChaCha20）往往在纯软件实现中比 AES 更快。这一点在移动设备和物联网（IoT）场景中尤为重要。

当然，分组密码在 CTR（计数器）模式下本质上也构成了一个流密码——它将分组密码当作密钥流生成器来使用。因此，流密码与分组密码之间的界限并非绝对分明。

同步流密码与自同步流密码

流密码可以分为两大类。同步流密码（synchronous stream cipher）中，密钥流的生成完全独立于明文和密文，仅依赖于密钥和内部状态。发送方和接收方必须保持严格的同步——如果传输中丢失了一个比特，后续所有解密都会错位。RC4、ChaCha20、Salsa20 都属于同步流密码。

自同步流密码（self-synchronizing stream cipher），也称为密文自同步（ciphertext autokey, CTAK）流密码，其密钥流的生成依赖于之前若干个密文比特。这意味着如果传输中发生比特丢失或插入，接收方只需等待有限数量的密文比特即可自动恢复同步。CFB（密文反馈）模式下的分组密码就是一种自同步流密码。然而，自同步特性也带来了错误扩散：一个密文比特的翻转会影响当前和后续若干个明文比特的解密结果。

在现代密码学实践中，同步流密码占据了主导地位，因为它们更容易分析、实现效率更高，且可以通过外层协议处理同步问题。

二、LFSR 基础

线性反馈移位寄存器的结构

线性反馈移位寄存器（Linear Feedback Shift Register, LFSR）是流密码历史上最重要的基础构件之一。一个 \(n\) 级 LFSR 由 \(n\) 个比特的寄存器组成，每个时钟周期执行以下操作：

输出寄存器最右端（或最左端，取决于约定）的比特作为密钥流的一个比特。
将寄存器中特定位置的比特进行异或运算，得到反馈比特。
将所有比特向右移动一位，将反馈比特填入最左端。

哪些位置参与异或运算由反馈多项式（feedback polynomial）决定。例如，一个 4 级 LFSR 的反馈多项式为 \(x^4 + x + 1\)，表示第 4 位和第 1 位参与反馈。

多项式表示与周期

LFSR 的行为可以用有限域 \(\text{GF}(2)\) 上的多项式完全描述。如果反馈多项式是本原多项式（primitive polynomial），则 LFSR 能够产生最大周期 \(2^n - 1\) 的序列（排除全零状态），称为 m-序列（maximal length sequence）。m-序列具有一些良好的统计特性：在一个完整周期内，0 和 1 的数量只差 1；长度为 \(k\) 的连续子序列出现的频率几乎均匀。

然而，这些统计特性只是密码学安全性的必要条件，远非充分条件。

Berlekamp-Massey 算法与 LFSR 的不安全性

LFSR 最致命的弱点在于其线性本质。Berlekamp-Massey 算法可以在已知 \(2n\) 个连续输出比特的情况下，以 \(O(n^2)\) 的时间复杂度恢复出一个 \(n\) 级 LFSR 的完整反馈多项式和初始状态。这意味着攻击者只需截获极少量的密钥流，就能预测全部后续输出。

因此，纯 LFSR 绝不能直接用作流密码的密钥流生成器。在实际应用中，LFSR 通常通过以下方式增强安全性：

非线性组合生成器（nonlinear combination generator）：将多个 LFSR 的输出通过一个非线性布尔函数（Boolean function）组合。安全性取决于布尔函数的代数阶数（algebraic degree）、非线性度（nonlinearity）和相关免疫性（correlation immunity）。

非线性滤波生成器（nonlinear filter generator）：对单个 LFSR 的多个内部状态比特施加非线性函数。

钟控生成器（clock-controlled generator）：一个 LFSR 的输出控制另一个 LFSR 的时钟信号，使得后者的步进速率不规则，从而打破线性关系。著名的 A5/1 算法（用于 GSM 移动通信加密）就采用了钟控结构，但后来被证明安全性不足。

这些构造虽然提升了安全性，但分析其密码学强度仍然极为复杂。随着代数攻击（algebraic attack）和相关攻击（correlation attack）技术的发展，许多基于 LFSR 的设计已被逐步淘汰。

三、RC4 详解

设计背景

RC4 由 Ron Rivest 在 1987 年为 RSA 安全公司设计，最初作为商业机密。1994 年，其算法被匿名泄露到互联网上，从此成为公开算法。RC4 以其极端的简洁性而著称——完整实现只需要几十行代码，且不需要任何乘法或查表操作，只使用字节级的加法、交换和数组索引。这使得它在性能受限的环境中极具吸引力，并被 WEP、WPA-TKIP、SSL/TLS、Microsoft Office 加密、BitTorrent 协议加密等大量系统采用。

密钥调度算法（KSA）

RC4 的内部状态是一个 256 字节的置换数组 \(S[0..255]\)，加上两个索引指针 \(i\) 和 \(j\)。密钥调度算法（Key Scheduling Algorithm, KSA）负责用密钥初始化这个置换数组：

KSA(key, key_len):
    for i = 0 to 255:
        S[i] = i
    j = 0
    for i = 0 to 255:
        j = (j + S[i] + key[i mod key_len]) mod 256
        swap(S[i], S[j])

KSA 结束后，\(S\) 是 \(\{0, 1, \ldots, 255\}\) 的一个（伪随机）置换，且该置换由密钥唯一确定。

伪随机生成算法（PRGA）

密钥调度完成后，伪随机生成算法（Pseudo-Random Generation Algorithm, PRGA）负责逐字节输出密钥流：

PRGA(S):
    i = 0
    j = 0
    loop:
        i = (i + 1) mod 256
        j = (j + S[i]) mod 256
        swap(S[i], S[j])
        K = S[(S[i] + S[j]) mod 256]
        output K

每次迭代输出一个字节的密钥流 \(K\)，将其与明文的对应字节异或即得密文。整个算法只涉及加法、取模和数组索引交换，硬件和软件实现都极为高效。

初始字节偏差

RC4 最广为人知的问题之一是其输出的初始字节存在严重的统计偏差。Mantin 和 Shamir 在 2001 年证明，PRGA 输出的第二个字节等于零的概率约为 \(2/256\) 而非期望的 \(1/256\)——这是理想随机分布的两倍。实际上，前 256 个输出字节中有多个位置都存在类似的偏差。这些偏差为后续的密码分析提供了可利用的统计信号。

更深层的统计弱点

除初始字节偏差外，RC4 的输出还存在更多微妙的统计异常。相邻输出字节之间存在可检测的相关性；密钥流中特定字节值的出现频率偏离均匀分布；连续输出字节对 \((Z_r, Z_{r+1})\) 的联合分布也不均匀。这些弱点虽然单独看来微小，但在大量样本的统计分析下，它们为攻击者提供了足够的信息来推断明文内容。

四、RC4 的攻击与退役

WEP 攻击：Fluhrer-Mantin-Shamir（FMS）攻击

RC4 遭遇的第一次毁灭性打击来自无线网络安全领域。IEEE 802.11 标准采用的有线等效保密协议（Wired Equivalent Privacy, WEP）使用 RC4 作为加密算法，但其密钥管理方案存在致命缺陷：WEP 将一个 24 比特的初始向量（IV）与固定的共享密钥直接拼接后作为 RC4 的密钥。

2001 年，Fluhrer、Mantin 和 Shamir 发表了开创性的论文，揭示了当 RC4 密钥的前几个字节具有特定模式时，KSA 的初始交换操作会导致内部状态泄露密钥信息到输出的前几个字节中。由于 WEP 的 IV 是明文传输的且只有 24 比特，攻击者只需被动收集约 400 万至 600 万个数据包（在繁忙的网络中可能只需要几分钟到几小时），就能通过统计分析恢复出完整的 WEP 密钥。

后续的改进攻击更加高效。2004 年，Klein 提出了更强的统计相关性分析。2007 年，Tews、Weinmann 和 Pyshkin 将所需数据包数量降低到约 40,000 个，使得 WEP 密钥可以在不到一分钟的时间内被破解。开源工具 aircrack-ng 将这些攻击实现为自动化工具，彻底终结了 WEP 作为安全协议的生命。

TLS 中的 RC4 偏差攻击

即便在 TLS 中 RC4 的使用方式避开了 WEP 那样的密钥管理灾难，RC4 自身的统计偏差仍然构成了威胁。2013 年，AlFardan、Bernstein、Paterson 等人发表了一项系统性的研究，识别出 RC4 密钥流中大量的单字节和双字节偏差。他们证明，如果同一明文在不同的 RC4 密钥下被加密足够多次（例如重复发送的 HTTP Cookie），攻击者可以通过收集约 \(2^{30}\) 到 \(2^{34}\) 个密文来恢复明文中特定位置的字节。

Royal Holloway 攻击

2015 年，伦敦大学 Royal Holloway 信息安全组的 Garman、Paterson 和 Van der Merwe 进一步改进了上述攻击，将所需密文数量降低到约 \(9 \times 2^{27}\)（约 7500 万个 TLS 连接），并在 75 小时内成功恢复了一个 16 字节的 TLS Cookie。虽然这个攻击在实际场景中仍需要大量数据，但它清楚地表明 RC4 的安全边际已经薄到了危险的程度。

RFC 7465 与 RC4 的正式退役

2015 年 2 月，IETF 发布了 RFC 7465《Prohibiting RC4 Cipher Suites》，明确禁止在 TLS 的所有版本中使用任何包含 RC4 的密码套件。这一决定标志着 RC4 在互联网安全协议中的正式退役。

回顾 RC4 的衰落时间线：

1994年：算法泄露，开始接受公开审查。
2001年：FMS 攻击摧毁 WEP 安全性。
2001年：Mantin-Shamir 发现初始字节偏差。
2013年：系统性 TLS 偏差攻击发表。
2015年：RFC 7465 禁止在 TLS 中使用 RC4。
2015年：Royal Holloway 攻击进一步降低实际利用门槛。

RC4 的故事是密码学领域的一个经典警示：一个在统计测试中看似”足够好”的算法，可能隐藏着只有在大规模分析下才会暴露的细微弱点。密码算法的安全性不能仅依赖于”目前没有已知攻击”，而需要建立在可证明或至少经过充分分析的数学基础之上。

从工程实践来看，RC4 的故事中最令人警醒的并非算法本身的缺陷——那些统计偏差在 2001 年就已被发现——而是它在已知存在弱点后又存活了整整十四年。从 2001 年 FMS 攻击摧毁 WEP，到 2015 年 RFC 7465 最终禁止 RC4 在 TLS 中使用，这十四年的时间差是向后兼容性（backward compatibility）对密码学安全造成系统性危害的缩影。每一次「但是现有客户端还需要 RC4」的妥协，都在拉长攻击者的窗口期。笔者认为，RC4 的十五年幸存记录应当成为密码学部署中的标准反面教材——它证明了密码算法的退役速度往往不取决于攻击的严重程度，而取决于生态系统中最慢的那个参与者的升级意愿。TLS 1.3 从中吸取了教训：它不是逐步淘汰不安全的选项，而是从一开始就只保留少数经过验证的密码套件，从根本上杜绝了「向下协商到不安全算法」的可能性。

一个经常被忽视的观点是，流密码在概念上是最接近一次性密码本（OTP）的实用密码原语——它们将一个短密钥拉伸为一条长伪随机流，而系统的全部安全性完全悬挂在这条伪随机流的质量之上。这意味着流密码的攻击面高度集中：你不需要攻破复杂的轮函数结构，只需要在密钥流中找到哪怕最微小的统计偏差，就可能将其放大为实际攻击。RC4 的衰落正是这种脆弱性的极致体现——几个百分之几的字节偏差，在足够多的样本下就足以恢复明文。这也解释了为什么 ChaCha20 的设计如此强调安全余量：20 轮变换中，目前最佳攻击仅能触及 7 轮，剩余 13 轮的余量正是对”流密码安全性高度集中于密钥流质量”这一本质特征的工程回应。

从工程实践来看，XSalsa20/XChaCha20 的扩展 nonce 构造是一个值得深入理解的精妙工程方案。其核心思路是：先用密钥和 nonce 的前 16 字节通过 HChaCha20 派生出一个子密钥，然后用子密钥和 nonce 的后 8 字节执行标准 ChaCha20 加密。这看似只是多了一步密钥派生，但它将 nonce 空间从 96 比特扩展到 192 比特，从根本上消除了 nonce 管理的心智负担。在 96 比特 nonce 空间中，约 \(2^{48}\) 条消息后生日碰撞概率就不可忽略——对于高吞吐系统这并不宽裕。而在 192 比特空间中，你可以安全地对每条消息随机生成 nonce，完全无需维护全局计数器或分布式状态。这种”用密码学消除运维复杂性”的设计思路，是 libsodium 将 XChaCha20-Poly1305 作为默认 AEAD 方案的根本原因，也是现代密码学工程中”让正确的使用方式成为最简单的使用方式”这一原则的又一典范。

五、Salsa20 家族

Bernstein 的设计哲学

Daniel J. Bernstein 是当代密码学最具影响力的研究者之一。他在设计 Salsa20 时遵循了几个核心原则：

透明性：算法不依赖任何来源不明的常量（no magic numbers）。Salsa20 使用的常量 “expand 32-byte k” 和 “expand 16-byte k” 完全公开且有明确解释——它们只是 ASCII 字符串，不可能隐藏后门。

简洁性：整个算法仅使用三种基本操作——32 位加法（addition）、固定位数旋转（rotation）和异或（XOR），合称 ARX 范式。不需要 S-盒（S-box）、不需要查表、不需要乘法。这不仅使得实现简单，更重要的是完全消除了缓存时序侧信道（cache-timing side channel）攻击的可能性——因为所有操作的执行时间都与数据无关。

高性能：Salsa20 的设计目标是在通用处理器上比 AES 更快，尤其是在没有硬件加速的平台上。

四分之一轮函数（Quarter-Round）

Salsa20 的核心是作用于四个 32 位字的四分之一轮函数（quarter-round function）。设输入为 \((a, b, c, d)\)，Salsa20 的四分之一轮操作如下：

\[b \mathrel{\oplus}= (a + d) \lll 7\] \[c \mathrel{\oplus}= (b + a) \lll 9\] \[d \mathrel{\oplus}= (c + b) \lll 13\] \[a \mathrel{\oplus}= (d + c) \lll 18\]

其中 \(\lll\) 表示循环左移。每次操作都将两个字相加，结果旋转后异或到第三个字上，形成三操作的扩散链。

列轮与对角轮

Salsa20 的内部状态是一个 \(4 \times 4\) 的 32 位字矩阵（共 512 比特）。一个完整的双轮（double round）包括：

列轮（column round）：对矩阵的四列分别执行四分之一轮函数。
对角轮（diagonal round）：对矩阵的四条对角线分别执行四分之一轮函数。

Salsa20 执行 20 轮（即 10 个双轮），得到变换后的状态矩阵，再将其与初始状态逐字相加。最终的 512 比特输出即为 64 字节的密钥流块。

ARX 范式的优势

ARX（Add-Rotate-XOR）范式在现代密码学中越来越受欢迎，原因是多方面的。首先，这三种操作在几乎所有通用处理器上都是常量时间操作，天然免疫时序侧信道攻击。其次，加法在 \(\text{GF}(2^{32})\) 上引入了非线性——比特进位使得 32 位加法不是 \(\text{GF}(2)\) 上的线性操作，这为对抗线性密码分析和差分密码分析提供了基础。最后，旋转操作以零成本提供了比特间的扩散。三者结合，以最少的操作类型实现了良好的混淆（confusion）与扩散（diffusion）。

六、ChaCha20 详解

从 Salsa20 到 ChaCha20 的改进

ChaCha20 是 Bernstein 在 2008 年提出的 Salsa20 变体。虽然两者的整体结构几乎相同，但 ChaCha20 在四分之一轮函数中做了关键调整，以获得更快的扩散速度。

ChaCha20 的四分之一轮函数如下：

\[a \mathrel{+}= b; \quad d \mathrel{\oplus}= a; \quad d \mathrel{\lll}= 16\] \[c \mathrel{+}= d; \quad b \mathrel{\oplus}= c; \quad b \mathrel{\lll}= 12\] \[a \mathrel{+}= b; \quad d \mathrel{\oplus}= a; \quad d \mathrel{\lll}= 8\] \[c \mathrel{+}= d; \quad b \mathrel{\oplus}= c; \quad b \mathrel{\lll}= 7\]

与 Salsa20 相比，ChaCha20 的四分之一轮包含四次加法（而非 Salsa20 的四次）、四次异或和四次旋转，但操作的排列方式不同。每次加法的结果直接参与下一次异或，形成了更紧密的依赖链。更重要的是，旋转距离的选择（16, 12, 8, 7）经过精心优化，使得每一轮的每个输入比特能够更快地影响到所有输出比特。实验分析表明，ChaCha 在相同轮数下提供了比 Salsa20 更好的扩散特性。

状态矩阵

ChaCha20 的 512 比特内部状态排列为 \(4 \times 4\) 的 32 位字矩阵：

cccccccc  cccccccc  cccccccc  cccccccc
kkkkkkkk  kkkkkkkk  kkkkkkkk  kkkkkkkk
kkkkkkkk  kkkkkkkk  kkkkkkkk  kkkkkkkk
bbbbbbbb  nnnnnnnn  nnnnnnnn  nnnnnnnn

其中： - 第 0 行（4 个字）：常量 “expand 32-byte k” 的 ASCII 编码，即 0x61707865、0x3320646e、0x79622d32、0x6b206574。 - 第 1-2 行（8 个字）：256 比特密钥。 - 第 3 行：一个 32 位块计数器（block counter）和一个 96 比特随机数（nonce）。

这种设计允许用同一密钥和 nonce 加密最多 \(2^{32} \times 64 = 256\) GiB 的数据（即块计数器的范围），对绝大多数应用场景来说绰绰有余。96 比特的 nonce 空间也足够大，可以安全地使用随机生成的 nonce（尽管仍需注意生日悖论边界）。

20 轮核心变换

ChaCha20 的核心操作如下：

将密钥、nonce 和计数器填入状态矩阵。
复制一份初始状态。
执行 20 轮变换（10 个双轮），每个双轮包括：
- 四次列四分之一轮：作用于列 \((0,4,8,12)\)、\((1,5,9,13)\)、\((2,6,10,14)\)、\((3,7,11,15)\)。
- 四次对角四分之一轮：作用于对角 \((0,5,10,15)\)、\((1,6,11,12)\)、\((2,7,8,13)\)、\((3,4,9,14)\)。
将变换后的状态与初始状态逐字相加（模 \(2^{32}\)）。
将结果序列化为 64 字节的密钥流块。

最后一步的逐字相加是至关重要的——它使得攻击者无法从输出直接反推内部状态的中间值，因为加法操作是不可逆的（在不知道两个加数的情况下）。

C 语言实现

以下是 ChaCha20 四分之一轮和核心块函数的 C 语言实现：

#include <stdint.h>
#include <string.h>

#define ROTL32(v, n) (((v) << (n)) | ((v) >> (32 - (n))))

/* ChaCha20 四分之一轮函数 */
static void quarter_round(uint32_t *a, uint32_t *b, uint32_t *c, uint32_t *d)
{
    *a += *b; *d ^= *a; *d = ROTL32(*d, 16);
    *c += *d; *b ^= *c; *b = ROTL32(*b, 12);
    *a += *b; *d ^= *a; *d = ROTL32(*d,  8);
    *c += *d; *b ^= *c; *b = ROTL32(*b,  7);
}

/* 从小端字节序读取 32 位无符号整数 */
static uint32_t le32_load(const uint8_t *p)
{
    return (uint32_t)p[0]       | ((uint32_t)p[1] << 8)
         | ((uint32_t)p[2] << 16) | ((uint32_t)p[3] << 24);
}

/* 将 32 位无符号整数以小端字节序写入 */
static void le32_store(uint8_t *p, uint32_t v)
{
    p[0] = (uint8_t)(v);
    p[1] = (uint8_t)(v >> 8);
    p[2] = (uint8_t)(v >> 16);
    p[3] = (uint8_t)(v >> 24);
}

/*
 * ChaCha20 核心块函数
 * key:     256 位密钥 (32 字节)
 * counter: 32 位块计数器
 * nonce:   96 位随机数 (12 字节)
 * out:     输出 64 字节密钥流块
 */
void chacha20_block(const uint8_t key[32],
                    uint32_t counter,
                    const uint8_t nonce[12],
                    uint8_t out[64])
{
    /* 初始化状态矩阵 */
    uint32_t state[16];
    state[ 0] = 0x61707865;  /* "expa" */
    state[ 1] = 0x3320646e;  /* "nd 3" */
    state[ 2] = 0x79622d32;  /* "2-by" */
    state[ 3] = 0x6b206574;  /* "te k" */
    state[ 4] = le32_load(key +  0);
    state[ 5] = le32_load(key +  4);
    state[ 6] = le32_load(key +  8);
    state[ 7] = le32_load(key + 12);
    state[ 8] = le32_load(key + 16);
    state[ 9] = le32_load(key + 20);
    state[10] = le32_load(key + 24);
    state[11] = le32_load(key + 28);
    state[12] = counter;
    state[13] = le32_load(nonce + 0);
    state[14] = le32_load(nonce + 4);
    state[15] = le32_load(nonce + 8);

    /* 保存初始状态 */
    uint32_t working[16];
    memcpy(working, state, sizeof(state));

    /* 20 轮 (10 个双轮) */
    for (int i = 0; i < 10; i++) {
        /* 列轮 */
        quarter_round(&working[ 0], &working[ 4],
                      &working[ 8], &working[12]);
        quarter_round(&working[ 1], &working[ 5],
                      &working[ 9], &working[13]);
        quarter_round(&working[ 2], &working[ 6],
                      &working[10], &working[14]);
        quarter_round(&working[ 3], &working[ 7],
                      &working[11], &working[15]);
        /* 对角轮 */
        quarter_round(&working[ 0], &working[ 5],
                      &working[10], &working[15]);
        quarter_round(&working[ 1], &working[ 6],
                      &working[11], &working[12]);
        quarter_round(&working[ 2], &working[ 7],
                      &working[ 8], &working[13]);
        quarter_round(&working[ 3], &working[ 4],
                      &working[ 9], &working[14]);
    }

    /* 与初始状态相加并序列化输出 */
    for (int i = 0; i < 16; i++) {
        le32_store(out + 4 * i, working[i] + state[i]);
    }
}

这段代码忠实地反映了 RFC 8439 中对 ChaCha20 的规范描述。所有操作——加法、异或和旋转——都是常量时间的，因此该实现天然抵抗时序侧信道攻击。

七、ChaCha20 的安全性与性能

安全性分析

ChaCha20 自 2008 年发表以来，经受了广泛而深入的密码学分析，目前没有已知的实际攻击。

在差分密码分析方面，对缩减轮数的 ChaCha 的最佳已知攻击可以破解 7 轮 ChaCha（256 比特密钥），但需要约 \(2^{235}\) 的时间复杂度和 \(2^{232}\) 的数据量，远高于实际可行的门槛。完整的 20 轮 ChaCha20 则有着极为充裕的安全边际。

在可证明安全性方面，虽然 ChaCha20 本身没有严格的归约证明（reduction proof），但其设计者提供了详细的安全性论证：20 轮变换提供了充分的扩散和混淆，使得其输出在计算上与随机函数不可区分。结合最终的加法操作，攻击者即使能够获得大量的密钥流输出，也无法恢复内部状态。

值得注意的是，ChaCha20 的 256 比特密钥空间远超当前及可预见的计算能力。即使考虑量子计算中 Grover 算法将暴力搜索的复杂度降低至 \(2^{128}\)，这仍然是一个安全的边际。

软件性能优势

ChaCha20 的一个突出优势在于其纯软件实现的性能。在没有 AES-NI 指令的处理器上——例如大量的 ARM 移动处理器和低端嵌入式芯片——ChaCha20 的吞吐量通常是 AES-128-CTR 的 2 到 3 倍。

这种性能优势来源于几个因素：

第一，ChaCha20 仅使用 32 位加法、32 位异或和 32 位循环旋转。这三种操作在几乎所有处理器架构上都有原生支持且执行延迟极低。

第二，ChaCha20 的状态可以完全装入通用寄存器中，不需要访问任何查找表（lookup table）。AES 在没有专用硬件的情况下通常依赖 T-table 实现，而 T-table 的缓存访问模式不仅影响性能，还可能泄露时序信息。

第三，ChaCha20 的 SIMD（单指令多数据）向量化非常自然。四次列四分之一轮可以完全并行执行，四次对角四分之一轮同样可以并行。在支持 128 位 SIMD 指令的处理器上（如 ARM NEON 或 x86 SSE2），ChaCha20 的性能可以进一步翻倍。

正是由于这些优势，Google 在 2014 年率先在 Chrome 浏览器和 Android 平台上部署了 ChaCha20-Poly1305 密码套件，用于与不支持 AES-NI 的设备通信。随后，ChaCha20-Poly1305 被 IETF 标准化为 RFC 8439（原 RFC 7539），并纳入 TLS 1.2 和 TLS 1.3 的推荐密码套件。

与 AES-GCM 的互补关系

需要强调的是，ChaCha20 与 AES 并非替代关系，而是互补关系。在支持 AES-NI 的现代桌面和服务器处理器上，AES-GCM 的吞吐量通常优于 ChaCha20-Poly1305。因此，最佳实践是：服务器同时支持 AES-GCM 和 ChaCha20-Poly1305，并根据客户端的硬件能力动态选择——有 AES-NI 时优先使用 AES-GCM，否则优先使用 ChaCha20-Poly1305。TLS 1.3 的密码套件协商机制正是为此而设计的。

八、eSTREAM 与其他流密码

eSTREAM 项目概述

eSTREAM（ECRYPT Stream Cipher Project）是欧洲 ECRYPT 网络于 2004 年发起的流密码竞赛，旨在为下一代应用推荐高效且安全的流密码算法。项目将候选算法分为两个方向（profile）：

Profile 1（软件方向）：面向通用处理器上的高性能软件实现。最终推荐的算法包括 HC-128、Rabbit、Salsa20/12（12 轮变体）和 SOSEMANUK。

Profile 2（硬件方向）：面向资源受限环境中的轻量级硬件实现。最终推荐的算法包括 Grain v1、MICKEY v2 和 Trivium。

eSTREAM 项目的意义不仅在于选出了几个优秀算法，更在于它建立了一套系统的流密码评估框架，涵盖安全性分析、性能基准测试和实现复杂度等多个维度。

Grain 家族

Grain 是一个面向硬件实现的轻量级流密码家族，由 Hell、Johansson 和 Meier 设计。其核心结构由两个移位寄存器组成：一个 LFSR 提供统计良好的序列，一个非线性反馈移位寄存器（NLFSR）引入非线性。两者的输出通过一个非线性滤波函数组合产生密钥流。Grain-128a 是当前推荐版本，使用 128 比特密钥和 96 比特 IV，特别适合射频识别（RFID）标签和传感器网络等极低功耗场景。

Trivium

Trivium 是 De Canniere 和 Preneel 设计的极简流密码，内部状态仅由三个移位寄存器组成，总计 288 比特。Trivium 使用 80 比特密钥和 80 比特 IV（因此不适合高安全性需求），但其硬件实现只需约 3,500 个门电路，且在高频时钟下可以每周期输出一个比特。Trivium 的设计理念是：用最少的组件和最透明的结构来实现足够的安全性，使得密码分析者能够充分审查每一个设计决策。

SNOW 家族

SNOW 是由 Ekdahl 和 Johansson 设计的面向软件的高速流密码家族。SNOW 2.0 被 3GPP 标准采纳为 UEA2/UIA2 加密算法的基础（用于 UMTS 移动通信）。其后续版本 SNOW 3G 进一步增强了安全性。SNOW-V 是最新的演进版本，专为 5G 通信场景设计，支持 256 比特密钥，目标是在硬件中提供超过 100 Gbps 的加密吞吐量。SNOW 家族的核心结构结合了 LFSR 和有限状态机（Finite State Machine, FSM），兼顾了 LFSR 的数学可分析性和非线性组件的安全性。

HC-128

HC-128 是吴洪波设计的软件向流密码，也是 eSTREAM 的 Profile 1 推荐算法之一。HC-128 使用两个 512 元素的 32 位字数组作为内部状态（共 32,768 比特），通过查表和非线性组合生成密钥流。巨大的内部状态使得代数攻击和状态恢复攻击极其困难。HC-128 在 x86 处理器上的性能极为出色，每字节仅需约 1 个时钟周期。但其初始化阶段较为耗时，不适合需要频繁更换密钥或 nonce 的场景。

九、XChaCha20 与现代实践

扩展随机数的需求

标准 ChaCha20 使用 96 比特的 nonce。在需要随机生成 nonce 的场景中，生日悖论（birthday paradox）限制了安全的消息数量——大约在 \(2^{48}\) 条消息后，两个随机 nonce 碰撞的概率就变得不可忽略。对于某些大规模分布式系统而言，这个限制可能不够宽裕。

HChaCha20 构造

XChaCha20 通过 HChaCha20 函数解决了这个问题。HChaCha20 本质上是一个哈希函数，它接受一个 256 比特密钥和一个 128 比特输入（通常是扩展 nonce 的前 16 字节），执行完整的 20 轮 ChaCha 变换，但不进行最终的加法操作。相反，它直接从变换后的状态中提取特定位置的字（第 0-3 字和第 12-15 字，即常量和计数器/nonce 位置），输出一个 256 比特的子密钥（subkey）。

XChaCha20 的工作流程

XChaCha20 使用 192 比特（24 字节）的扩展 nonce，其加密过程分为两步：

将 256 比特原始密钥和 192 比特 nonce 的前 16 字节作为输入，通过 HChaCha20 导出一个 256 比特的子密钥。
使用该子密钥和 nonce 的后 8 字节（填充为标准的 96 比特 nonce，前 4 字节置零用作计数器）作为标准 ChaCha20 的参数，执行常规加密。

这种两级密钥导出结构使得 XChaCha20 的 nonce 空间扩展到了 192 比特。在这个空间中，即使生成 \(2^{96}\) 个随机 nonce，碰撞概率也微乎其微。对于需要随机 nonce 的应用场景——尤其是无状态加密（stateless encryption），即不需要维护 nonce 计数器的场景——XChaCha20 是理想的选择。

XChaCha20-Poly1305 与 libsodium

在实际应用中，XChaCha20 几乎总是与 Poly1305 消息认证码（MAC）结合使用，构成 XChaCha20-Poly1305 认证加密（AEAD）方案。Poly1305 是 Bernstein 设计的一次性 MAC 算法，我们将在后续文章中详细讨论。

libsodium 是目前最广泛使用的现代密码学库之一，它将 XChaCha20-Poly1305 作为默认的对称加密方案。libsodium 的 crypto_aead_xchacha20poly1305_ietf_encrypt 和对应的解密函数提供了简洁而安全的 API：用户只需提供密钥、消息和可选的附加认证数据（AAD），nonce 可以安全地随机生成。这极大地降低了密码学 API 误用的风险——回想 RC4 在 WEP 中的惨痛教训，密钥管理和 nonce 处理中的错误往往是实际系统被攻破的根本原因。

WireGuard VPN 协议同样选择了 ChaCha20-Poly1305 作为其核心密码套件，进一步证明了这一方案在现代网络安全基础设施中的重要地位。

流密码与 AEAD：现代默认配置

回顾流密码从 LFSR 到 RC4 再到 ChaCha20 的演进，一个清晰的趋势已经浮现：在现代密码工程中，纯流密码几乎不再被单独使用。原因很简单——流密码本身只提供保密性，不提供完整性保护。裸的异或加密对密文篡改完全透明：攻击者翻转密文的第 \(i\) 个比特，解密后明文的第 \(i\) 个比特也会被翻转，而通信双方对此一无所知。

因此，现代实践中流密码几乎总是以 AEAD（Authenticated Encryption with Associated Data）的形式出场，将加密与认证绑定为不可分割的单一操作：

ChaCha20-Poly1305（RFC 8439）是当前最广泛部署的流密码 AEAD 方案。ChaCha20 负责加密，Poly1305 提供一次性 MAC 认证。该方案被 TLS 1.3、WireGuard、SSH（OpenSSH 6.5+）、QUIC 等主流协议采用，是在缺乏 AES-NI 硬件加速的平台上性能最优的 AEAD 选择。
XChaCha20-Poly1305 将 nonce 扩展到 192 比特，适用于需要随机生成 nonce 的无状态加密场景（如文件加密、数据库字段加密）。libsodium 将其作为默认 AEAD 方案。
AES-256-GCM 则是有 AES-NI 硬件加速时的对标方案——从功能角度看，ChaCha20-Poly1305 与 AES-GCM 是等价的竞争者，选择依据主要是硬件支持情况。

对于遗留场景中确实需要流式加密但无法使用 AEAD 的极端情况（例如某些嵌入式实时系统），至少应当叠加独立的 MAC（如 HMAC-SHA-256）并采用 Encrypt-then-MAC 的组合顺序。但在 2020 年代的新系统设计中，这种分离式组合已经没有正当理由——AEAD 是唯一应当考虑的默认配置。

未来展望

展望未来，流密码领域面临几个值得关注的方向。首先是后量子安全性（post-quantum security）：ChaCha20 的 256 比特密钥在 Grover 算法下仍提供 128 比特的安全性，被普遍认为在量子计算时代仍然安全。其次是新兴的轻量级密码学（lightweight cryptography）标准，NIST 在 2023 年选定了 Ascon 作为轻量级加密标准，其中包含了流密码式的设计元素。再次是 SNOW-V 等面向超高带宽场景的新设计，旨在满足 5G 和未来 6G 通信的加密需求。

从 LFSR 的数学优雅到 RC4 的戏剧性衰落，再到 ChaCha20 的工程胜利，流密码的发展史深刻地展示了密码学设计的核心张力：简洁与安全、性能与分析可行性之间的平衡。在这场持续的演化中，唯一不变的原则是——密码算法的安全性必须经受开放、持续和严格的公开审查。

密码学百科系列 · 第 09 篇

← 上一篇：分组密码工作模式 | 系列目录 | 下一篇：密码学哈希函数 →