密码分析学 Part 10 of 16

第 10 章：分组密码工作模式的攻击概述

分组密码的功能是高度简单的：根据一个 7 字节 (DES) 或 16～32 字节 (AES) 的密钥，把 8 字节 (DES) 或 16 字节 (AES) 的明文变成“不易识别的”密文。但日常需要的密码功能是复杂的：加密方案 (encryption scheme) 要把任意长度的明文变成不易识别的密文，消息认证码要为任意长度的明文产生一个与之唯一对应的“摘要”。

发布于 2026-07-24 8,364 字 · 约 24 分钟

常用的思路是：依赖安全性久经考验的分组密码标准（如 AES），通过一个基于分组密码的结构 (construction) 建构所需的复杂功能，寄望于结构本身能保持密码标准的可靠性。这样的结构称为分组密码的工作模式 (mode of operation)。工作模式的原理通常与所用分组密码的内部细节无关，可以把其中的分组密码换成任何安全的分组密码。以下用 \(E\) 表示分组密码，\(E_K\) 表示装定了密钥 \(K\) 的 \(E\)。\(E\) 的分组长度为 \(n\) 比特、密钥长度为 \(k\) 比特时，称为 \((k,n)\)-分组密码。

工作模式是一个庞大的知识体系，本章只介绍 NIST 建议的四种经典加密模式：ECB、CBC、OFB、CTR。重点在攻击：不考虑分组密码的内部细节、只利用模式结构本身弱点的攻击，称为通用攻击 (generic attack)。

§ 01电码本模式

先考虑明文长度 \(|m|\)（以比特计）是 \(n\) 的整数倍的情形，即 \(m=m_1\Vert m_2\Vert\cdots\Vert m_\ell\) 包含 \(\ell\ge1\) 个 \(n\) 比特分组。最容易想到的办法是用 \(E_K\) 逐个加密每个分组。这个过程类似于把 \(E_K\) 当作一个“电码本 (electronic codebook)”逐个查表，因此得名。

定义 1.1电码本 \(\mathrm{ECB}[E]_K\) 加密模式

加密 \(\mathrm{ECB}[E]_K(m)\)，\(|m|=\ell n\)：

切分明文 \(m=m_1\Vert\cdots\Vert m_\ell\)，\(m_i\in\{0,1\}^n\)；
对 \(i=1,\cdots,\ell\)，\(c_i:=E_K(m_i)\)；
输出 \(c:=c_1\Vert\cdots\Vert c_\ell\)。

解密同样逐分组用 \(E_K^{-1}\)：\(m_i:=E_K^{-1}(c_i)\)。

ECB 显然会把相同的明文分组 \(m_i=m_j\) 加密为相同的密文分组 \(E_K(m_i)=E_K(m_j)\)，暴露明文分组之间的相等关系。这在实际中是危险的。例如很多用户会在邮件末尾附加一段祝福语：同一用户、同一客户端发出的邮件祝福语一般相同，不同用户则一般不同。如果邮件用 ECB 加密传输，相同的祝福语就会被加密为相同的密文分组，窃听者可以根据数据包末尾若干字节的取值给邮件分类，判断哪些邮件来自同一用户、同一客户端。

注意这个攻击完全没有考虑 ECB 使用的是哪种分组密码，是一个通用攻击。窃听者还可以归纳密文的统计特征破解更多信息，原理与用统计特征破解移位密码相同，只是“字母表”从 26 个字母换成了 8 字节或 16 字节的数据分组。

明文是随机比特串时，ECB 可以保证隐藏明文的内容，这种有限的安全性在特殊场景中有用：例如每次会话前用系统主密钥 MK 和一个随机初始向量 IV 导出会话密钥 \(\mathrm{SK}=\mathrm{ECB}[E]_{\mathrm{MK}}(\mathrm{IV})\)。但一般情况下不应使用 ECB 加密数据。

§ 02密文分组链接模式

ECB 的致命弱点在于第 \(i\) 个密文分组 \(c_i\) 只取决于第 \(i\) 个明文分组 \(m_i\)。自然的补救思路是让 \(c_i\) 由多个明文分组决定，这就是密文分组链接 (CBC) 模式：用 \(m_1\) 的密文 \(c_1\) 参与计算 \(m_2\) 的密文 \(c_2\)，用 \(c_2\) 参与计算 \(c_3\)，以此类推。

定义 2.1密文分组链接 \(\mathrm{CBC}[E]_K\) 加密模式

加密 \(\mathrm{CBC}[E]_K(m)\)，\(|m|=\ell n\)：

切分明文 \(m=m_1\Vert\cdots\Vert m_\ell\)；
随机选取 \(n\) 比特初始向量 IV；
\(c_0:=\mathrm{IV}\)，即把 IV 看作“第 0 个”密文分组；
对 \(i=1,\cdots,\ell\)，\(c_i:=E_K(c_{i-1}\oplus m_i)\)；
输出 \(c:=\mathrm{IV}\Vert c_1\Vert\cdots\Vert c_\ell\)。

解密 \(\mathrm{CBC}[E]_K^{-1}(c)\)，\(|c|=(\ell+1)n\)：\(c_0:=\mathrm{IV}\)，对 \(i=1,\cdots,\ell\)，\(m_i:=c_{i-1}\oplus E_K^{-1}(c_i)\)。

解密必须用到 \(c_0=\mathrm{IV}\)，所以 IV 必须作为密文的一部分传给接收方。

前面全部 \(i-1\) 个明文分组都会影响 \(c_i\) 的计算，所以相同的明文分组 \(m_i=m_j\) 不一定导致相同的密文分组，避免了 ECB 的致命弱点。此外最后一个密文分组 \(c_\ell\) 取决于全部 \(\ell\) 个明文分组，可以作为整个明文在某种意义下的“摘要”，基于这一思路的消息认证码称为 CBC-MAC（见第十四章）。要注意区分这两种用途：本章只讨论用于加密的 CBC，它需要随机 IV；用于 MAC 时不需要 IV。

CBC 最大的缺点是不能并行：\(c_{i+1}=E_K(c_i\oplus m_{i+1})\)，加密第 \(i+1\) 个分组要等第 \(i\) 个分组的结果，只能逐分组加密。

2.1 初始向量的作用与注意事项

对 IV 有两种理解方式：

把随机选取 IV 看作 \(\mathrm{CBC}[E]_K\) 内部的一个步骤。从调用者看来，CBC 在内部选一个随机 IV、完成加密、输出包含 IV 的密文，于是 CBC 是概率性加密 (probabilistic encryption)，ECB 是确定性加密 (deterministic encryption)；
Rogaway 的方式：把 IV 看作 CBC 的另一个参数，由调用者在加密前随机选取。这种方式便于深入分析 IV 的性质对安全性的影响。

两种方式实质等价，本章用第一种。

加密多个明文 \(m^{(1)},m^{(2)},\cdots\) 时，每个明文都要随机选取新的 IV。随机选取保证了 IV（以大概率）互不相同，但不是“只要不同就安全”。例如用计数器值 \(\mathrm{IV}^{(1)}=\mathrm{str}(1)\)，\(\mathrm{IV}^{(2)}=\mathrm{str}(2)\)，……（\(\mathrm{str}(c)\) 为整数 \(c\) 的 \(n\) 比特编码）就会导致攻击。一般地：

加密多个明文时，随机 IV 被重复使用，明文的机密性会被破坏；
加密多个明文时，每次选取的 IV 都必须是攻击者不能预测的，否则会导致攻击。这意味着随机 IV 不能用任何形式的计数器值代替。

IV 重用导致的损失。 加密两个明文 \(m,m'\) 时若 \(\mathrm{IV}=\mathrm{IV}'\)，比较 \(c_1\) 与 \(c_1'\) 是否相等，就能推断 \(\mathrm{IV}\oplus m_1\) 与 \(\mathrm{IV}'\oplus m_1'\) 是否相等，即 \(m_1=m_1'\) 与否。考虑一个加密传输试题答案的场景：\(N\) 个判断题的答案编码为 \(N\) 个单分组明文，取值表示“是”或“非”，用 \(\mathrm{CBC}[E]_K\) 加密。若 IV 重用，攻击者就能判断两道题的答案是否一致，显著缩小猜测范围。（IV 可预测导致的攻击见本章习题。）

2.2 明文填充

实际中明文长度不是 \(n\) 的整数倍时，会有不能被分组密码处理的“尾”。可以引入填充方案 (padding) pad，把明文 \(m\) 填充为长度为 \(n\) 整数倍的填充明文 (padded message) \(m^*:=\mathrm{pad}(m)\)，再用 CBC 加密。

定义 2.2带明文填充的 \(\mathrm{CBC}[E,\mathrm{pad}]_K\) 加密模式

加密（\(n\nmid|m|\)）：

按填充规则 pad 得到 \(m^*:=\mathrm{pad}(m)\)；
计算 \(c:=\mathrm{CBC}[E]_K(m^*)\)；
输出 \(c\)。

解密（\(|c|\) 必须是 \(n\) 的整数倍）：

计算 \(m^*:=\mathrm{CBC}[E]_K^{-1}(c)\)；
按填充规则确定使 \(m^*=\mathrm{pad}(m)\) 的 \(m\)：
- 若存在，输出明文 \(m\)；
- 若不存在，终止解密，不输出任何信息。

填充方案要保证不同的明文填充后的 \(m_1^*,m_2^*\) 也不同，避免歧义，同时保证解密时能定位到唯一合法的明文。问题在于解密的情形 2(b)：解密有问题的 \(c\) 可能是攻击者捏造的，接收方不应把错误信息告诉发送方，正如定义中强调的。但处理不当就会导致选择密文攻击，见 §2.4。

RFC 2040 标准填充方案 CBC-PAD

RFC 2040 描述了基于 RC5 的 CBC 加密模式 RC5-CBC-PAD，定义了明文填充方案 CBC-PAD。每个字节看作一个“字 (word)”，每个分组由 \(b=8\) 个字组成。填充规则是：在明文之后填充由 \(r\) 个字构成的“尾”，每个字都是整数 \(r\) 的编码 \([r]\)，\(1\le r\le b\)（至少填 1 个字，最多填 \(b\) 个），使填充后字的个数为 \(b\) 的整数倍。具体地说：

最后一个分组不完整、只有 \(\lambda\) 个字时，令 \(r:=b-\lambda\)，填充 \(r\) 个 \([r]\)：\(m_\ell^*=m_\ell\Vert\underbrace{[r]\Vert\cdots\Vert[r]}_{r\text{ 个}}\)；
最后一个分组完整时，也必须填充，新增一个分组 \(m_{\ell+1}^*=\underbrace{[b]\Vert\cdots\Vert[b]}_{b\text{ 个}}\)。

习题 2.3

证明 CBC-PAD 保证不同的明文 \(m^{(1)}\ne m^{(2)}\) 填充后 \(m^{(1)*}\ne m^{(2)*}\)。

解

不妨设 \(|m^{(1)}|\le|m^{(2)}|\)（另一种情形对称）。

\(m^{(1)}\) 不是 \(m^{(2)}\) 的前缀：存在下标 \(i\) 使两者第 \(i\) 个分组（在原明文范围内）不同，填充不改变这两个分组，所以 \(m^{(1)*}\ne m^{(2)*}\)。
\(m^{(1)}\) 是 \(m^{(2)}\) 的真前缀，且两者最后一个分组的字数不同：设分别有 \(b-r_1\) 和 \(b-r_2\) 个字，\(r_1\ne r_2\)，填充的尾分别以 \([r_1]\) 和 \([r_2]\) 结束，最后一个字不同。
\(m^{(1)}\) 是 \(m^{(2)}\) 的真前缀，且最后一个分组的字数相同：则 \(m^{(2)}\) 比 \(m^{(1)}\) 多出至少一个完整分组，填充的尾长度相同，所以 \(|m^{(1)*}|<|m^{(2)*}|\)，当然不相等。

这里“最后一个分组完整时也必须填充”是关键：否则明文 \(x\) 与 \(x\Vert[1]\)（\(x\) 少一个字时）可能填充成同一个结果。

2.3 CBC 的安全性

工作模式的设计思路是借助安全性久经考验的密码标准，所以分析工作模式安全性的一种标准手段是在可证明安全 (provable security) 框架中论证：任何针对 \(\mathrm{CBC}[E]_K\) 的攻击，都可以转化为针对所用 \(E_K\) 的攻击。可证明安全最初是针对基于数论困难假设的公钥密码的，20 世纪 90 年代 Bellare、Rogaway 等把它迁移到对称密码工作模式领域。

注

这和分组密码本身的安全性分析有显著差别：目前还没有能直接证明实用分组密码安全性的技术，只能穷尽已知攻击手段，论证它们无效。

已有的 CBC 证明结论是：设

\(E\) 是输入输出长度为 \(n\)、密钥长度为 \(k\) 的伪随机函数；
加密每个明文的 IV 都在 \(\{0,1\}^n\) 中随机均匀选取；
攻击者对一个密文 \(c\) 实施选择明文攻击，可以选择明文 \(m_1,m_2,\cdots\) 并获得密文 \(c_1,c_2,\cdots\)；
攻击者的计算复杂度为 \(T\ll2^k\)，选择的明文共 \(\sigma\) 个 \(n\) 比特分组，

则攻击者破解 \(c\) 对应明文 \(m\) 的任何信息（例如 \(m\) 的若干字节、校验和）的概率约为

\[ O\!\left(\frac T{2^k}\right)+O\!\left(\frac{\sigma^2}{2^n}\right).\tag{1} \]

第一项不难理解：穷举 \(E_K\) 的密钥复杂度为 \(O(2^k)\)，搜出密钥就能解密。第二项是生日界，见 §2.5。

CBC 的可证明安全性不是无条件的：攻击者目标（恢复明文的部分信息）、运用方式（IV 随机）、攻击者能力（选择明文，计算与数据复杂度有限）都有明确限制。实际中往往通过上层协议保证攻击者能力不超出限制，但能力超限时就可能成功攻击。下面 §2.4 是“选择明文”限制失效造成的攻击，§2.5 是数据能力超限造成的攻击。

2.4 CBC 的选择密文攻击

CBC 面对选择明文攻击的安全性可以严格证明。但如果攻击者可以选择密文 \(c\) 并获得其明文 \(\mathrm{CBC}[E]_K^{-1}(\mathrm{IV},c)\) 呢？实际场景是：攻击者选择密文、编成合法的数据包发给协议的接收方解密。正常情况下攻击者看不到解密出的明文。但如 §2.2 所述，若解密出的 \(m^*\) 不是正确的填充形式，接收方是否会继续处理、相关处理是否会造成时延等，本身就是 \(c\) 是否有问题的特征。选择不同的 \(c\)，观察这些特征推测解密是否成功，就能实施选择密文攻击。这就是 Vaudenay 提出的填充谕示攻击 (padding oracle attack)。

下面针对 \(\mathrm{CBC}[E,\text{CBC-PAD}]_K\) 描述。以“字”为单位，每个分组 \(b\) 个字，字的取值总数为 \(W\ge b\)。

定义 2.4正确的填充形式

数据分组序列 \(x=x_1\Vert\cdots\Vert x_\ell\)，若最后一个分组 \(x_\ell\) 以 \(\underbrace{[r]\Vert\cdots\Vert[r]}_{r\text{ 个}}\) 结束、\(r>0\)（例如 \([1]\)、\([2]\Vert[2]\)、\([3]\Vert[3]\Vert[3]\)），称 \(x\) 为正确的填充形式，否则不正确。

注意：\(x_\ell\) 最后一个字是 \([1]\) 时，无论之前的字是什么，都是正确的填充形式。

求解填充明文的最后一个字

给定密文分组 \(y\)，求 \(E_K^{-1}(y)\) 的最后一个字。取 \(b\) 个随机字 \(\nu=\nu_1\Vert\cdots\Vert\nu_b\)，把 \(\nu\Vert y\) 当作密文发给接收方。CBC 解密得到的唯一明文分组是 \(E_K^{-1}(y)\oplus\nu\)，所以：

若解密结果是正确的填充形式，则 \(E_K^{-1}(y)\oplus\nu\) 以 \([r]\Vert\cdots\Vert[r]\) 结尾。最可能的情形是 \(r=1\)，于是 \(E_K^{-1}(y)\) 的最后一个字最可能是 \(\nu_b\oplus[1]\)；
若不是正确的填充形式，最后一个字一定不是 \([1]\)，换一个 \(\nu_b\) 再试。

\(\nu\) 是随机的，所以 \(E_K^{-1}(y)\oplus\nu\) 以某个 \(r\) 字尾结束的概率为 \(1/W^r\)。第一次尝试就成功的概率为

\[ \frac1W+\frac1{W^2}+\cdots+\frac1{W^b}\approx\frac1W, \]

平均要尝试约 \(W/2\) 次（见习题）。

成功时 \(r\) 可能大于 1（例如结尾恰为 \([2]\Vert[2]\)），要用“破坏”更靠前的字来确定 \(r\)：若以 \([2]\Vert[2]\) 结尾，改动 \(\nu_{b-1}\) 就会使末尾两个字变成 \(\star\Vert[2]\)，\(\star\ne[2]\)，填充就不正确了；\(r\ge3\) 时同理。但若以 \([1]\) 结尾，改动 \(\nu_{b-1}\) 后仍是正确的填充形式。依次改动 \(\nu_{b-1},\nu_{b-2},\cdots\)，就能确定 \(r\)。

定理 2.5算法（破解 \(y\) 的最后一个字，运气好时破解最后若干字）

随机选取 \(b\) 个字 \(\nu_1,\cdots,\nu_b\)，令 \(i=0\)；
令 \(\nu:=\nu_1\Vert\cdots\Vert\nu_{b-1}\Vert(\nu_b\oplus[i])\)；
若密文 \(\nu\Vert y\) 解密所得的填充明文不是正确的填充形式，令 \(i\leftarrow i+1\)，回到第 2 步；
令 \(\nu_b:=\nu_b\oplus[i]\)；
此时 \(\nu_1\Vert\cdots\Vert\nu_b\Vert y\) 解密得到以 \([r]\Vert\cdots\Vert[r]\)（\(r>0\)）结尾的明文。对 \(j=b,b-1,\cdots,2\) 执行：
1. 令 \(\nu:=\nu_1\Vert\cdots\Vert\nu_{b-j}\Vert(\nu_{b-j+1}\oplus[1])\Vert\nu_{b-j+2}\Vert\cdots\Vert\nu_b\)（只改动第 \(b-j+1\) 个字）；
2. 若 \(\nu\Vert y\) 解密所得的不是正确的填充形式，说明 \(r=j\)，终止，输出 \((\nu_{b-j+1}\oplus[j])\Vert\cdots\Vert(\nu_b\oplus[j])\)；
都正确则 \(r=1\)，输出 \(\nu_b\oplus[1]\)。

破解任意密文分组

设 \(E_K^{-1}(y)=a=a_1\Vert\cdots\Vert a_b\)。用上面的算法破解 \(a_b\)，再递归地依次破解 \(a_{b-1},a_{b-2},\cdots,a_1\)。思路是：调整 \(\nu\) 的末尾使解密后的尾凑成 \([2]\Vert[2]\)，再调整 \(\nu_{b-1}\) 反推 \(a_{b-1}\)；然后凑成 \([3]\Vert[3]\Vert[3]\)，反推 \(a_{b-2}\)；以此类推。

第 \(t\) 轮迭代中（\(1\le t\le b-1\)），已经破解了 \(a_b,\cdots,a_j\)（\(j=b-t+1\)），破解 \(a_{j-1}\)：

令 \(\nu_j=a_j\oplus[t+1],\cdots,\nu_b=a_b\oplus[t+1]\)（使已知的末尾 \(t\) 个字解密后都等于 \([t+1]\)）；
随机选取 \(j-1\) 个字 \(\nu_1,\cdots,\nu_{j-1}\)，令 \(i=0\)；
令 \(\nu=\nu_1\Vert\cdots\Vert\nu_{j-2}\Vert(\nu_{j-1}\oplus[i])\Vert\nu_j\Vert\cdots\Vert\nu_b\)；
若 \(\nu\Vert y\) 解密所得不是正确的填充形式，令 \(i\leftarrow i+1\)，回到上一步；
输出 \(a_{j-1}=\nu_{j-1}\oplus[i]\oplus[t+1]\)。

注

教材第 5 步写的是 \(\nu_{j-1}\oplus[i]\oplus[b-j+2]\)。由 \(j=b-t+1\)，\(b-j+2=t+1\)，两者相同。

平均 \(W/2\) 次尝试破解一个字，破解整个分组 \(E_K^{-1}(y)\) 平均需要 \(bW/2\) 次尝试。

破解完整的明文

给定密文 \(y_1\Vert\cdots\Vert y_\ell\)（以及 IV），用上面的方法依次求出每个 \(E_K^{-1}(y_i)\)，再与前一个密文分组异或，就得到完整的明文。平均需要 \(\ell bW/2\) 次填充形式校验，复杂度为 \(O(\ell bW)\)。例如 \(b=8\)，\(W=256\)（每个字一个字节）时，平均调用 \(1024\ell\) 次解密机就能解密 \(\ell\) 个分组的密文，复杂度很低。

其他填充方案

Schneier 的 Applied Cryptography 中，尾的形式为 \([0]\Vert\cdots\Vert[0]\Vert[r]\)（\(r-1\) 个 \([0]\) 和一个 \([r]\)）；
IPSec 的 ESP 机制中，尾的形式为 \([1]\Vert[2]\Vert\cdots\Vert[r]\)；
NIST 建议的填充，尾的形式为 \([1]\Vert[0]\Vert\cdots\Vert[0]\)（这里 \([1]\)、\([0]\) 指比特）。

上面的选择密文攻击稍作调整，就能用于使用这些填充规则的 CBC 模式。

注

CBC 加密的一个性质是：对密文 \(\mathrm{IV}\Vert c_1\Vert\cdots\Vert c_{\ell-1}\Vert c_\ell\)，修改 \(c_{\ell-1}\) 就能对解密得到的最后一个（填充）明文分组 \(m_\ell^*\) 造成可控、可预测的影响。这一性质称为可延展性 (malleability)，本节的攻击利用的正是它。克服可延展性、抵抗选择密文攻击，需要认证加密模式（如 GCM），或“先加密后认证”。

2.5 数据复杂度为 \(2^{n/2}\) 的 CBC 通用攻击

由 (1)，攻击者破解 \(c\) 对应明文任何信息的概率约为 \(O(T/2^k)+O(\sigma^2/2^n)\)。加密数据量 \(\sigma\) 接近 \(2^{n/2}\) 时，第二项接近 1。Bhargavan 和 Leurent 给出了这种情形下破解明文信息乃至完整明文的方法（Sweet32 攻击）。

加密数据量达到 \(2^{n/2}\) 后的明文信息泄露

设明文分组都在 \(\{0,1\}^n\) 中均匀分布。\(\mathrm{CBC}[E]_K\) 用同一个密钥累计加密约 \(2^{n/2}\) 个分组后，出现一对上下标组合 \(((i,j),(i',j'))\) 满足

\[ c^{(i)}_{j-1}\oplus m^{(i)}_j=c^{(i')}_{j'-1}\oplus m^{(i')}_{j'}, \]

即两次 \(E_K\) 调用的输入相同（称为碰撞）的概率接近 \(\binom{2^{n/2}}2\cdot\frac1{2^n}\approx\frac12\)。碰撞的后果是：

\[ c^{(i)}_j=E_K\big(c^{(i)}_{j-1}\oplus m^{(i)}_j\big)=E_K\big(c^{(i')}_{j'-1}\oplus m^{(i')}_{j'}\big)=c^{(i')}_{j'}. \]

\(E_K\) 是一一映射，所以 \(c^{(i)}_j=c^{(i')}_{j'}\) 与输入碰撞是等价的。因此：

累计加密约 \(2^{n/2}\) 个分组后，有可观的概率观测到相同的密文分组 \(c^{(i)}_j=c^{(i')}_{j'}\)；
一旦观测到，就能反推

\[ m^{(i)}_j\oplus m^{(i')}_{j'}=c^{(i)}_{j-1}\oplus c^{(i')}_{j'-1}, \]

右侧都是可以观测到的密文分组，于是解出了一对明文分组的异或值。

泄露一对明文分组的异或值乍看没有多大危害，其实不然。从信息论的角度看，一对相互独立的明文分组包含 \(2n\) 个未知比特，熵最高为 \(2n\)；攻击者得到它们的异或值后，熵减少了 \(n\) 比特。更进一步，实际应用中的明文往往满足：

明文中的某些内容是已知的，例如邮件末尾的固定祝福语；
某些高价值机密数据被多次加密传输。

这时碰撞泄露的就可能是某个机密分组与某个已知分组的异或值，于是机密分组就被破解了。

碰撞的确切概率

一般地，\(2^d\) 个明文分组的可能取值总数为 \((2^n)^{2^d}\)，两两互异的取值总数为 \(\prod_{i=1}^{2^d}(2^n-i+1)\)。所以遭遇（至少一个）碰撞的概率为

\[ p=1-\prod_{i=0}^{2^d-1}\frac{2^n-i}{2^n}\ \ge\ 1-\prod_{i=0}^{2^d-1}e^{-i/2^n}=1-e^{-2^d(2^d-1)/2^{n+1}}. \]

注

这里用的是 \(1-x\le e^{-x}\)，所以 \(\prod(1-i/2^n)\le\prod e^{-i/2^n}\)，\(p\) 的下界成立。

分类讨论：

\(d>n/2\)：\(p\ge1-e^{-1/2}\approx0.39\)，且

\[ p\ge1-\frac{2^{n+1}}{2^d(2^d-1)+2^{n+1}}\ge1-2^{n-2d+1}, \]

（用 \(e^x\ge1+x\)。）\(d\) 越大，遭遇碰撞的概率越接近 1； - \(d<n/2\)：

\[ p\ge1-\frac{2^d(2^d-1)}{2^{n+2}}\approx2^{2d-n-2}, \]

且（加密约 \(2^d\) 个分组后）遭遇碰撞个数的期望约为 \(2^{2d-n-1}\)。

从信息泄露到破解明文：利用已知明文分组

\(\mathrm{CBC}[E]_K\) 用同一个密钥累计加密 \(2^s\) 个机密明文分组、\(2^t\) 个已知明文分组后，机密分组与已知分组之间出现碰撞的概率约为

\[ \frac{2^s\times2^t}{2^n}, \]

所以 \(s+t\approx n\) 时攻击有可观的成功概率。实际实施时，攻击者收集并存储所有通信，把密文分组排序找碰撞。若知道机密分组和已知分组在明文流中的位置，就只保留两者之间的碰撞，再把碰撞涉及的已知分组与泄露的异或值异或，得到机密分组。

攻击复杂度的讨论

设明文分组中已知分组的比例为 \(\alpha\)，想要破解的机密分组比例为 \(\beta\)（其余 \(1-\alpha-\beta\) 既不已知也不值得破解）。加密 \(2^d\) 个分组后，碰撞个数的期望约为 \(2^d(2^d-1)/2^{n+1}\approx2^{2d}/2^{n+1}\)，其中有用的（机密与已知之间的）约为 \(\alpha2^d\cdot\beta2^d/2^n\)。所以攻击者大约要收集 \(1/(2\alpha\beta)\) 个碰撞，才能遇到一个有用的，即约需处理

\[ \sqrt{\frac1{\alpha\beta}}\cdot2^{n/2}\tag{2} \]

个明文分组。

例 2.6

\(n=64\)（如 3DES、Blowfish），设明文分组中一半已知、一半是想破解的机密分组，\(\alpha=\beta=1/2\)，这是对攻击者最有利的情形。由 (2)，需要

\[ \sqrt{1/(\alpha\beta)}\cdot2^{n/2}=2\cdot2^{32}=2^{33} \]

个分组，即 \(2^{33}\times8\) 字节 \(=64\,\mathrm{GB}\) 的数据。

更现实的场景：加密的明文是 512 字节的 HTTP 查询，其中只有一个 8 字节的机密数据（一个分组），其他内容都已知。\(\alpha=63/64\approx1\)，\(\beta=1/64\)，需要

\[ \sqrt{1/(\alpha\beta)}\cdot2^{n/2}\approx8\cdot2^{32}=2^{35} \]

个分组，即 \(256\,\mathrm{GB}\)。在现实网络中收集 64 GB 或 256 GB 的加密数据是可能办到的。

从信息泄露到破解明文：利用重复传输的明文

设多次加密传输一个固定（但未知）的、包含 \(2^u\) 个分组的明文，攻击者知道其中 \(\alpha\cdot2^u\) 个分组，目标是恢复整个明文。每次加密都选新的随机 IV，所以虽然明文相同，产生的后续密文分组也近似于均匀分布。分两种情形：

只有一个未知分组：\(\alpha\approx1\)，\(\beta=2^{-u}\)，攻击者约需收集 \(\sqrt{1/(\alpha\beta)}\cdot2^{n/2}\approx2^{(n+u)/2}\) 个密文分组。这么多数据产生的碰撞约为 \(\binom{2^{(n+u)/2}}2\cdot\frac1{2^n}\approx2^{u-1}\) 个，有很大的概率其中有一个是机密分组与已知分组之间的碰撞，攻击成功；
未知分组不止一个，但较少：设未知分组数 \(k=(1-\alpha)2^u=\beta2^u\)，逐个破解。破解第一个时 \(\beta=k/2^u\)，需收集约 \(\frac1{\sqrt k}\cdot2^{(u+n)/2}\) 个分组；之后未知分组减少为 \(k-1\) 个，需 \(\frac1{\sqrt{k-1}}\cdot2^{(u+n)/2}\) 个；……；最后一个需 \(2^{(u+n)/2}\) 个。总计约

\[ 2^{\frac{u+n}2}\sum_{i=1}^k\frac1{\sqrt i} \]

个分组。\(\sum_{i=1}^k\frac1{\sqrt i}\) 是广义调和数 \(H_{k,1/2}\approx2\sqrt k\)。

注

碰撞的位置不能控制，所以能破解的第一个未知分组的具体位置也不能控制，但这不影响后续推进：已破解的分组变成已知分组，\(\alpha\) 增大。

实际可行性

网页 HTTPS 往往用 TLS 或 OpenVPN 保护。有些场景下，浏览器每次请求网页都会加密传输一个机密的认证凭据，这恰好符合上面攻击的条件。RFC 6265 定义了 HTTPS 网站管理客户端认证会话的方法：用户登录时服务器设定一个 cookie，之后用户浏览器每次请求都（加密）传输这个 cookie，证实用户身份。例如站点 domain.com 设置了 cookie C=XXXX，后续的请求是

GET /path/to/file HTTP/1.1
User-Agent: Mozilla/4.0 ...
Host: domain.com
Cookie: C=XXXX
Accept-Language: en-us
Accept-Encoding: gzip, deflate
Connection: Keep-Alive

攻击者一旦获得会话的 cookie，就能在另一个浏览器上冒充这个用户登录。除了生存期较短，cookie 和口令的密级相当。而包括 Facebook 在内的站点会长期使用同一个 cookie 不更新，正符合“重复传输的明文”的假设。所以上面的思路可以从传输的密文中恢复 cookie，实现身份伪造。

这个例子也说明：设计和部署加密方案时，一定不能假设攻击者对明文一无所知。攻击者根据安全协议的设计可以判读出明文的数十个字节，这已经接近已知明文攻击了。这也是 64 比特分组的 3DES、Blowfish 在 TLS 中被淘汰的直接原因。

§ 03输出反馈模式

输出反馈 (Output Feedback, OFB) 的加密可以看作两部分：先根据 IV 计算一系列随机数据分组 \(y_1,\cdots,y_\ell\)，再把它们依次与明文分组异或。

定义 3.1输出反馈 \(\mathrm{OFB}[E]_K\) 加密模式

加密 \(\mathrm{OFB}[E]_K(m)\)：

切分明文 \(m=m_1\Vert\cdots\Vert m_{\ell-1}\Vert m_\ell^*\)，\(m_1,\cdots,m_{\ell-1}\in\{0,1\}^n\)，\(m_\ell^*\in\{0,1\}^\lambda\)，\(1\le\lambda\le n\)；
随机选取 \(n\) 比特 IV，\(y_0:=\mathrm{IV}\)；
对 \(i=1,\cdots,\ell-1\)：\(y_i:=E_K(y_{i-1})\)，\(c_i:=y_i\oplus m_i\)；
\(y_\ell^*:=\mathrm{msb}_\lambda(E_K(y_{\ell-1}))\)，即取 \(E_K(y_{\ell-1})\) 的最高 \(\lambda\) 位；\(c_\ell^*:=y_\ell^*\oplus m_\ell^*\)；
输出 \(\mathrm{IV}\Vert c_1\Vert\cdots\Vert c_{\ell-1}\Vert c_\ell^*\)。

解密同样计算 \(y_i\)，\(m_i:=y_i\oplus c_i\)，\(m_\ell^*:=y_\ell^*\oplus c_\ell^*\)。

这实际上构成了一个流密码：先生成密钥流 \(y_1\Vert\cdots\Vert y_\ell\)，再与明文异或得到等长的密文。从宏观上看，流密码（通过与密钥流异或的方式）也是对称加密方案的一类，所以先费尽心机设计分组密码、再转换为流密码并不奇怪。与 CBC 相同，IV 要作为密文的一部分传输。假设 \(E\) 是伪随机函数，也能证明 OFB 面对选择明文攻击时的安全性，结论与 CBC 相似。

OFB 的优势：

不需要填充：明文长度不是 \(n\) 的倍数时，把 \(E_K(y_{\ell-1})\) 截短到与 \(m_\ell^*\) 等长即可（截取最低位也可以），避免了填充带来的安全隐患（§2.4）和额外的密文开销；
只需要 \(E\) 的加密函数，不需要 \(E_K^{-1}\)，缩小了软件代码量和硬件电路规模；
可以离线预计算：收到明文之前就可以预先计算密钥流 \(y_1:=E_K(\mathrm{IV}),y_2:=E_K(y_1),\cdots\) 并存下来，加密的“在线”过程极快，这是相对 CBC 的优势。

与优势 3 相对，OFB 产生的密文 \(c_\ell\) 显然与前 \(\ell-1\) 个明文分组无关，所以不能直接产生消息认证码。

§ 04计数器模式

计数器 (CTR) 模式也是把分组密码转化为流密码的加密模式。

定义 4.1计数器 \(\mathrm{CTR}[E]_K\) 加密模式

加密 \(\mathrm{CTR}[E]_K(m)\)：

切分明文 \(m=m_1\Vert\cdots\Vert m_{\ell-1}\Vert m_\ell^*\)，\(m_\ell^*\in\{0,1\}^\lambda\)，\(1\le\lambda\le n\)；
随机选取 \(n\) 比特 IV；
对 \(i=1,\cdots,\ell-1\)：\(y_i:=E_K(\mathrm{str}(\mathrm{Num}(\mathrm{IV})+i))\)，\(c_i:=y_i\oplus m_i\)；
\(y_\ell^*:=\mathrm{msb}_\lambda(E_K(\mathrm{str}(\mathrm{Num}(\mathrm{IV})+\ell)))\)，\(c_\ell^*:=y_\ell^*\oplus m_\ell^*\)；
输出 \(\mathrm{IV}\Vert c_1\Vert\cdots\Vert c_{\ell-1}\Vert c_\ell^*\)。

解密用同样的 \(y_i\) 与密文异或。\(\mathrm{Num}(\cdot)\) 把比特串看作整数，\(\mathrm{str}(\cdot)\) 把整数编码为 \(n\) 比特串。

这类似于为一个计数器设定随机初始值 IV，然后不断让计数器增值，加密计数器产生“下一个”密钥流分组，因此得名。与 OFB 类似，CTR 同样：

不需要 \(E^{-1}\)，支持截短最后一个密钥流分组，免除填充；
密钥流的计算与待加密明文无关，可以预计算。

CTR 独有的优势是：不同的密钥流分组 \(y_i=E_K(\mathrm{str}(\mathrm{Num}(\mathrm{IV})+i))\) 与 \(y_j\) 相互没有关联，所以加密与解密都可以完全并行。而且解密第 \(i\) 个密文分组只需一次 \(E_K\) 调用，\(m_i:=E_K(\mathrm{str}(\mathrm{Num}(\mathrm{IV})+i))\oplus c_i\)，支持随机访问。所以 CTR 更受欢迎，被集成到 CCM 和 GCM 等认证加密模式标准中。

4.1 初始向量重用对 OFB 与 CTR 的损害

§2.1 讨论了 IV 重用对 CBC 的损害。在 OFB 和 CTR 这类“流密码”模式中，整个密钥流完全由 IV 决定，相同的 \(\mathrm{IV}=\mathrm{IV}'\) 会产生完全相同的密钥流 \(y=y'\)。于是

\[ c\oplus c'=m\oplus y\oplus m'\oplus y'=m\oplus m', \]

直接得到两个明文的异或，信息量很大：根据 \(m\) 中任何一个已知的分组 \(m_i\)，都能直接解出 \(m'\) 对应位置的分组 \(m_i'\)。这与一次一密的密钥流重用的后果一样。所以 IV 重用对 OFB 和 CTR 的损害远大于对 CBC 的损害，实际中要极力避免。

注

CTR 还有一种更隐蔽的“重用”：两次加密的计数器区间重叠。若 \(\mathrm{Num}(\mathrm{IV}')=\mathrm{Num}(\mathrm{IV})+3\)，第二个消息的第 1 个分组就用了第一个消息第 4 个分组的密钥流。随机 IV 下，这种重叠在加密总量接近 \(2^{n/2}\) 个分组时变得可观，又是一个生日界。

§ 05习题

习题 5.1

回顾 §2.1。如果可以预测 \(\mathrm{CBC}[E]_K\) 加密下一个明文所用的 IV，可以如何破解 \(m\) 的信息？针对 \(\mathrm{CTR}[E]_K\)，结论又是什么？

解

CBC。 设攻击者截获了一个密文 \(\mathrm{IV}\Vert c_1\Vert\cdots\)，想验证第 1 个明文分组是否等于某个猜测 \(g\)（例如判断题的“是/非”）。若能预测下一次加密的 IV 为 \(\mathrm{IV}'\)，并能选择明文（例如让用户的浏览器发送某个请求），就让下一个明文的第一个分组为

\[ m_1'=\mathrm{IV}'\oplus\mathrm{IV}\oplus g. \]

则 \(c_1'=E_K(\mathrm{IV}'\oplus m_1')=E_K(\mathrm{IV}\oplus g)\)，它等于 \(c_1\) 当且仅当 \(m_1=g\)。每次选择明文验证一个猜测，候选空间小（如判断题只有两种）时可以完全破解。这正是 TLS 1.0 中 BEAST 攻击的原理：TLS 1.0 用上一个记录的最后一个密文分组作为下一个记录的 IV，攻击者可以预测它。

CTR。 只要计数器区间不重叠，可预测的 IV 不造成损害：\(E_K\) 是伪随机置换，攻击者即使知道计数器的值，也无法预测 \(E_K(\text{计数器})\)，密钥流仍是伪随机的。CTR 对 IV 的要求是不重复（nonce），不要求不可预测。

习题 5.2

回顾 §3。如果可以选择 \(\mathrm{OFB}[E]_K\) 加密下一个明文所用的 IV，可以如何破解 \(m\)？

解

设截获了密文 \(\mathrm{IV}\Vert c_1\Vert c_2\Vert\cdots\)，其密钥流为 \(y_1=E_K(\mathrm{IV}),y_2=E_K(y_1),\cdots\)。

最直接：选择下一次加密的 IV 为同一个 \(\mathrm{IV}\)，并让被加密的明文 \(m'\) 已知（或选择），得到 \(c'\) 后算出 \(y=c'\oplus m'\)，就是同一条密钥流，于是 \(m=c\oplus y\)；
即使攻击者不能让 IV 完全相同，若知道 \(m_1\)（例如固定的协议头），就知道 \(y_1=c_1\oplus m_1\)。选择下一次的 IV 为 \(y_1\)，新消息的密钥流是 \(y_2,y_3,\cdots\)，恰好是原消息密钥流平移一个分组，同样能解出原消息从第 2 个分组起的全部内容。

习题 5.3

§2.4 中说第一次尝试就成功观察到 \(\nu\Vert y\) 解密出正确填充形式的概率约为 \(1/W\)，否则就换别的 \(\nu_b\) 尝试，所需的尝试次数期望为 \(W/2\)。用排列组合与概率论的方法证明这一结论。

解

算法中 \(\nu_b\) 依次取 \(\nu_b\oplus[0],\nu_b\oplus[1],\cdots\)，即不放回地遍历最后一个字的全部 \(W\) 种取值。记 \(a_b\) 为 \(E_K^{-1}(y)\) 的最后一个字，解密结果的最后一个字为 \(a_b\oplus\nu_b\oplus[i]\)。在这 \(W\) 次中，恰好有一次使最后一个字为 \([1]\)，这一次一定是正确的填充形式。

\(\nu_b\) 随机均匀，所以使最后一个字为 \([1]\) 的那个 \(i\) 在 \(\{0,\cdots,W-1\}\) 中均匀分布。忽略 \(r\ge2\) 的情形（它们只会让成功提前，概率之和约为 \(1/W^2+\cdots\)，是高阶小量），所需尝试次数 \(X\) 满足 \(\Pr(X=k)=1/W\)，\(k=1,\cdots,W\)，于是

\[ \mathbb E[X]=\sum_{k=1}^W\frac kW=\frac{W+1}2\approx\frac W2. \]

若改为每次独立随机地选 \(\nu_b\)（有放回），尝试次数服从参数约 \(1/W\) 的几何分布，期望约为 \(W\)，是不放回遍历的两倍。这也说明算法按顺序遍历 \([i]\) 是有意义的。

习题 5.4

为改善 ECB 的安全性，引入 \(n\) 比特随机 IV，定义变体 \(\mathrm{ECBIV}[E]_K(\mathrm{IV},m)\)，\(|m|=\ell n\)：

切分明文 \(m=m_1\Vert\cdots\Vert m_\ell\)；
随机选取 \(n\) 比特 IV；
对 \(i=1,\cdots,\ell\)：\(c_i:=E_K(\mathrm{IV}\oplus m_i)\)，然后 \(\mathrm{IV}\leftarrow\mathrm{IV}+1\)（看作 \(n\) 比特整数，模 \(2^n\) 加）；
输出 \(c:=\mathrm{IV}_{\text{初值}}\Vert c_1\Vert\cdots\Vert c_\ell\)。

此方案可以把相同明文分组加密为不同密文分组。它安全吗？为什么？（提示：借鉴 §1 对 ECB 的分析思路。）

解

不安全。第 \(i\) 个分组实际加密的是 \((\mathrm{IV}+i-1)\oplus m_i\)，而 IV 随密文公开。ECB 的问题是“分组密码输入相等 \(\Leftrightarrow\) 密文分组相等”，这里依然如此，只是输入被一个已知的、结构简单的量掩盖。

选择明文区分：选 \(m_1=x\)，\(m_2=x\oplus1\)。当 IV 的最低位为 \(0\) 时，\(\mathrm{IV}+1=\mathrm{IV}\oplus1\)，于是 \((\mathrm{IV})\oplus m_1=(\mathrm{IV}+1)\oplus m_2\)，\(c_1=c_2\)。这以概率 \(1/2\) 发生，而随机方案中 \(c_1=c_2\) 的概率可以忽略，攻击者看到 IV 就能确认。更一般地，攻击者知道 IV，可以对任意 \(i,j\) 构造 \(m_j=m_i\oplus(\mathrm{IV}+i-1)\oplus(\mathrm{IV}+j-1)\) 使密文分组相等。
明文相等关系泄露：密文分组 \(c_i=c_j\) 当且仅当 \(m_i\oplus m_j=(\mathrm{IV}+i-1)\oplus(\mathrm{IV}+j-1)\)，右边攻击者可以算出。所以观察到密文碰撞就直接得到明文分组的异或值。即使跨消息，两个消息的计数器区间有交叠时，相同位置的相同明文也会产生相同的密文。

根本问题是：分组密码的输入只经过了可预测的掩盖。CBC 用前一个密文分组（攻击者在加密前无法预测）掩盖输入，这才是它比 ECB 安全的原因。

参考：王美琴主编，《密码分析学》，科学出版社，2024，第 10 章。

完