跳转至
密码分析学 Part 1 of 16

第 1 章：密码分析学概述

密码学主要分为密码设计学和密码分析学。前者致力于设计安全高效的密码算法，后者则试图发现算法的安全缺陷，打破设计者宣称的安全界限，恢复明文或密钥。新的分析方法催生更完善的设计，新的设计又激发新的分析，二者的博弈推动着密码学发展。

发布于 4,263 字 · 约 12 分钟

一个密码体制抵抗现有各种分析技术的强度，已经成为衡量算法安全性的重要指标。这套笔记围绕对称加密算法、杂凑函数和消息认证码 (Message Authentication Code, MAC) 的安全性分析，整理现代密码分析学的主流技术。本章先给出基本假设、攻击者能力、安全性的定义，以及贯穿全书的攻击模型。

§ 01密码分析学的基本概念

现代密码算法除了用于保密通信的加密算法（如 AES），还有保证完整性的杂凑函数（如 SHA-2）、实现认证性的消息认证码（如 HMAC），以及同时提供机密性和认证性的认证加密算法（如 AES-GCM）。我们先以对称加密算法为例讨论。

1.1 Kerckhoffs 准则与攻击类型

命题 1.1Kerckhoffs 准则

密码体制的安全性仅依赖于密钥，其他一切（包括算法本身）都是公开的。

这是 Kerckhoffs 在 1883 年提出的六条准则的核心思想。从分析者的角度说，评估一个密码体制时，我们总是假设攻击者知道除密钥以外的全部信息，包括每一个设计细节。在此基础上，按攻击者掌握的信息不同，攻击分为五类：

  1. 唯密文攻击 (ciphertext-only attack)：只能获得同一密钥加密的一个或多个密文。例如搭线窃听者。这是对分析者最不利的情况。
  2. 已知明文攻击 (known-plaintext attack)：能获得某些明密文对。例如用户数据总以 “LOGIN” 开头，或可以根据语言习惯预测。这是密码算法至少要抵抗的攻击。
  3. 选择明文攻击 (chosen-plaintext attack)：能选择明文并获得相应密文。文件系统和数据库特别容易受到这种攻击，因为用户可以随意写入明文。对称算法的密钥既用于加密也用于解密，常见的攻击多为这一类，这也是这套笔记讨论的重点。
  4. 选择密文攻击 (chosen-ciphertext attack)：能选择密文并获得相应明文。
  5. 选择文本攻击 (chosen-text attack)：同时具有 3 和 4 的能力，往往是攻击者暂时控制了加密机和解密机。

可见攻击者的能力从上到下逐渐增强，一个算法能抵抗越强的攻击者，安全性就越高。

1.2 无条件安全与计算安全

定义 1.2无条件安全

若无论密码分析者知道多少信息，都不足以唯一确定目标密文对应的明文，则称该密码体制是无条件安全 (unconditionally secure) 的，也称理论安全。

无条件安全与攻击者的计算资源无关：无论有多少明密文、花多少时间和存储，都无法解密。除一次一密外，实际应用的加密算法都不是无条件安全的。原因是由 Kerckhoffs 准则，实际算法的安全性依赖于一个固定长度的密钥，而无论算法多复杂，都可以用穷举、查表等强力攻击恢复密钥。所以我们只能要求实际算法从计算资源的角度看是安全的，这就需要衡量每一种攻击的效率。

设有某种攻击，其效率从两个方面衡量：

  • 成功率 \(P_S\)：恢复出的密钥是正确密钥的概率。（对区分攻击，指做出正确判断的概率。）
  • 复杂度：达到成功率 \(P_S\) 所需的资源，包括
    • 数据复杂度 \(D\)：所需明文或密文的总数；
    • 时间复杂度 \(T\)：分析处理数据所消耗的时间，一般以运行一次加密为单位；
    • 存储复杂度 \(M\)：占用存储空间的大小，一般以字节或比特为单位。

注

复杂度和成功率之间存在约束关系：复杂度不同，能达到的成功率也不同。因此比较两个攻击时，应把复杂度统一在相同的成功率下再比较。

以穷举攻击为例，时间复杂度由穷举的次数决定。对 \(n\) 比特密钥，遍历全部 \(2^n\) 种可能，成功率为 \(100\%\)，复杂度为 \(2^n\) 次加密；若只随机验证一半，复杂度为 \(2^{n-1}\)，成功率约为 \(1/2\)。一般地，复杂度为 \(2^{n-a}\) 时成功率约为 \(2^{-a}\)。

定义 1.3计算安全

若对某密码体制尝试各种攻击，在不可忽略的成功率下，各攻击的复杂度均超出分析者计算资源可达到的合理边界，则称该密码体制是计算安全 (computationally secure) 的。

此外还有所谓实际安全 (practical security)：破译的代价超过密文信息的价值，或破译的时间超过密文信息的有效期。

习题 1.4

密钥长度为 \(n\) 比特的算法，若随机选取 \(2^{n-a}\) 个互不相同的密钥逐一验证，精确的成功率是多少？

解

正确密钥在 \(2^n\) 个密钥中均匀分布，被选中的概率恰为 \(2^{n-a}/2^n=2^{-a}\)。若允许重复选取（每次独立均匀选取），则成功率为 \(1-(1-2^{-n})^{2^{n-a}}\approx1-e^{-2^{-a}}\)，\(a\) 较大时也约为 \(2^{-a}\)，\(a=0\) 时只有约 \(63\%\)。

§ 02各类算法的攻击目标

不同算法的安全属性不同，攻击目标也不同。

对称加密算法用于保障机密性，同时也是随机数生成器、杂凑函数、MAC 的基本部件。主要考虑两类攻击：

  1. 区分攻击：将分组密码与随机置换区分开；
  2. 密钥恢复攻击：恢复加解密所用的密钥。

密钥恢复攻击往往建立在区分成功的基础上。由于强力攻击的存在，密钥长 \(n\) 比特时，这两类攻击的复杂度上界都是 \(2^n\)。

杂凑函数用于保障完整性，也是数字签名的关键技术。对 \(n\) 比特杂凑值的杂凑函数 \(h\)，主要考虑：

  1. 原像攻击：给定 \(n\) 比特的 \(H\)，找消息 \(M\) 使 \(h(M)=H\)；
  2. 第二原像攻击：给定 \(M_1\)，找 \(M_2\ne M_1\) 使 \(h(M_1)=h(M_2)\)；
  3. 碰撞攻击：找两个消息 \(M_1\ne M_2\) 使 \(h(M_1)=h(M_2)\)；
  4. 长度扩展攻击：给定 \(h(M)\)，其中 \(M\) 未知，找数据串 \(N\) 与 \(n\) 比特的 \(H'\)，使 \(h(M\Vert N)=H'\)。

由于强力攻击，前两类和长度扩展攻击的复杂度上界为 \(2^n\)；碰撞攻击有生日攻击，上界为 \(2^{n/2}\)。具体结构的杂凑函数，上界还可能更低。

注

MD 结构的杂凑函数容易受到长度扩展攻击，用它构造 MAC 或认证加密时易被伪造。因此 NIST 在征集 SHA-3 时，要求候选算法抵抗这一攻击。

消息认证码用于保障认证性，收发双方共享的密钥是唯一保密的信息，所以对称加密的攻击目标同样适用于 MAC。此外还有：

  • 区分攻击：
    1. R 型区分 (distinguishing-R)：把 MAC 与随机函数区分开；
    2. H 型区分 (distinguishing-H)：把基于具体密码元件（如 SHA-1）构造的 MAC 与基于随机函数构造的同一种 MAC 区分开。
  • 伪造攻击：设 MAC 的输入为 \(M\)，输出为 \(t\)，攻击者在不知道密钥时输出能通过验证的 \((M,t)\)，即 \(\mathrm{Verf}(M,t)=1\)。
    1. 存在性伪造 (existential forgery)：与 MAC 交互后输出 \((M,t)\)，\(M\) 在交互中没有被询问过；例如询问 \(M_1,\cdots,M_s\)（可以自适应地选择）后，输出 \(M\notin\{M_1,\cdots,M_s\}\) 的合法标签。
    2. 选择性伪造 (selective forgery)：交互之前先选定 \(M\)，交互后输出它的合法标签，且 \(M\) 没有被询问过。
    3. 通用性伪造 (universal forgery)：对交互前任意给定的 \(M\)，都能输出其合法标签。
  • 密钥恢复攻击：恢复 MAC 使用的密钥。

设 MAC 值长 \(n\) 比特，密钥长 \(k\) 比特，则区分和伪造攻击的复杂度上界为 \(\min(2^n,2^k)\)，密钥恢复的上界为 \(2^k\)。对具体结构还可能更低，例如基于杂凑函数的部分 MAC，区分攻击的上界为 \(2^{l/2}\)，\(l\) 为中间链接变量的长度。

注

密码分析并不只分析完整的算法，一般会先从简化版本入手。例如 DES 规定加密 16 轮，分析时可以先缩减到 12 轮。在简化版本上发现的设计问题，随着技术进步，可能最终导致整个算法被攻破。

§ 03密码分析的一般模型

常见的密码分析方法分为三类：

  1. 强力攻击：与算法设计细节无关的通用方法，如穷举攻击、查表攻击、时间-存储权衡攻击。它的复杂度给出了算法的安全上界，即其他攻击复杂度的上界。
  2. 基于数学模型和程序搜索的攻击：如差分分析、线性分析。分析算法的内部结构，把数学推导、统计测试与程序搜索相结合，发现特殊规律。
  3. 侧信道攻击 (side-channel attack)：利用算法在芯片上运行时泄露的物理参量（执行时间、电流、电压、电磁辐射、声音等），这些量与中间状态和运算存在相关性，从而推测密钥。见第十五章。

我们重点关注第二类。它的两个关键要素是区分和分割。

3.1 区分

所谓区分，就是找一个可计算或可统计的指标，对特定密码算法和随机函数（置换）分别计算它，若能在复杂度允许的范围内以不可忽略的概率区分这两种分布，就称这个指标为不随机特征，利用它进行区分的算法称为区分器或区分攻击。区分往往是各类攻击的第一步。

例 3.1区分

分组密码 \(\mathrm{EG}_2\) 为 \(C=F_{K_1}(F_{K_0}(P))\)，\(P,C\) 为 \(n\) 比特，\(F\) 是由密钥 \(K_i\) 决定的置换，\(K_0,K_1\) 相互独立，均为 \(n\) 比特。若攻击者发现等式 \(P\oplus C=1\) 以概率 \(1\) 成立，能否把 \(\mathrm{EG}_2\) 与随机置换 RP 区分开？

解

对随机置换，\(P\oplus C\) 均匀分布，\(\Pr(P\oplus C=1)=2^{-n}\)。于是给一个黑盒，已知 \(x\) 个输入 \(P_i\) 与输出 \(C_i\)：

  1. 计算 \(x\) 个 \(P_i\oplus C_i\)；
  2. 若都等于 \(1\)，输出 \(\mathrm{EG}_2\)；
  3. 否则输出 RP。

设黑盒等可能为 \(\mathrm{EG}_2\) 和 RP。黑盒为 \(\mathrm{EG}_2\) 时一定判断正确；为 RP 时，只有 \(x\) 个值都恰好为 \(1\) 才会判错。故

\[ \begin{aligned} \Pr(\text{成功})&=\frac12\Pr(\text{输出 }\mathrm{EG}_2\mid\mathrm{EG}_2)+\frac12\Pr(\text{输出 RP}\mid\text{RP})\\ &=\frac12\cdot1+\frac12\left(1-\left(\frac1{2^n}\right)^x\right)=1-\frac1{2^{nx+1}}. \end{aligned} \]

可见 \(x=1\) 就能以不可忽略的概率区分成功。

当然这只是个极端的例子，真正分析时很难找到概率为 \(1\) 的不随机特征。

3.2 分割

所谓分割，有两层含义：

  1. 对算法的分割：寻找区分器时往往自下而上，把算法的部件分开考虑，细化到 S 盒、置换 \(P\)，甚至比特，从中发现不随机现象。
  2. 对搜索空间的分割：强力攻击要验证的是与全部密钥比特有关的明密文关系。借助区分器，可以得到只与部分密钥有关的、可验证的关系，于是先恢复这部分密钥，再恢复其余密钥。这种“两步走”的复杂度是相加而不是相乘的关系，从而降低了总复杂度。

例 3.2分割

分组密码 \(\mathrm{EG}_3\) 为 \(C=F_{K_2}(F_{K_1}(F_{K_0}(P)))\)，\(K_0,K_1,K_2\) 相互独立，均为 \(n\) 比特。若发现两轮后的中间结果 \(X\) 满足 \(P\oplus X=1\) 的概率为 \(1\)，能否找到比穷举更有效的密钥恢复攻击？

解

设得到一个明密文对 \((P,C)\)。直接穷举需遍历 \(3n\) 比特密钥，即 \(2^{3n}\) 种情况。

利用 \(P\oplus X=1\)，可得 \(X=P\oplus1\)，即恢复了中间结果。于是得到只与 \(K_2\) 有关的方程

\[ C=F_{K_2}(X). \]

只需猜测 \(K_2\) 的 \(2^n\) 种可能，满足的为候选。候选多于 \(1\) 个时，再用其他明密文对筛选。之后对 \(K_0,K_1\)，利用 \(X=F_{K_1}(F_{K_0}(P))\)，再用中间相遇或穷举恢复。由于分割了密钥搜索空间，复杂度远小于 \(2^{3n}\)。

一般地，对 \(r\) 轮算法的密钥恢复攻击分两步：

  1. 找一个 \(d\) 轮区分器。 注意到区分器对应的不随机现象（如线性关系或差分）与每轮中间值无关，只与区分器的头尾 \((X,Y)\) 有关，所以区分器可以看作一个函数 \(D(X,Y)\)，它在真实算法与随机置换下的取值分布可区分。
  2. 利用区分器分割密钥空间。 只需考虑从明文 \(P\) 加密到区分器头部 \(X\) 涉及的密钥 \(K_0,\cdots,K_i\) 中的部分比特，以及从密文 \(C\) 解密到尾部 \(Y\) 涉及的 \(K_{i+d+1},\cdots,K_r\) 中的部分比特。
\[ P\xrightarrow{K_0,\cdots,K_i}\underbrace{X\xrightarrow{d\text{ 轮区分器}}Y}_{D(X,Y)}\xleftarrow{K_{i+d+1},\cdots,K_r}C \]

可见攻击的复杂度与成功率取决于函数 \(D(X,Y)\)、求解 \((X,Y)\) 的方式和涉及的密钥量。

注

构造区分器时，一般要求不随机现象对随机选取的任意密钥都成立，即对整个密钥空间成立。但也可以只考虑满足某些特定条件的密钥，例如相关密钥或弱密钥下的区分器。

习题 3.3

把 AES 的轮函数去掉列混合 (MC)，其余不变，记为 Test 算法。试对 Test 进行选择明文攻击，使得能解密任何密文对应的明文（可以不恢复密钥），并给出复杂度。

解

去掉 MC 后，每轮只剩字节代换 SB、行移位 SR 和轮密钥加 AK。SB 与 AK 逐字节作用，SR 只是重排字节位置，所以每个密文字节只依赖于一个明文字节，且这种对应关系由 SR 的复合决定，与密钥无关。于是整个算法分割成 16 个相互独立的 8 比特置换 \(c_{\pi(j)}=T_j(p_j)\)。

选 \(2^8\) 个明文 \(P_v=(v,v,\cdots,v)\)，\(v=0,\cdots,255\)，获得密文，就同时得到 16 个置换 \(T_j\) 的完整表。解密时逐字节查逆表即可。

  • 数据：\(2^8\) 个选择明文；
  • 时间：\(2^8\) 次加密；
  • 存储：\(16\times256\) 字节 \(=2^{15}\) 比特。

教材的提示是 \(2^{32}\) 个选择明文、\(2^{32}\) 次加密、\(2^{39}\) 比特存储，那是按 4 个字节一组分割的做法；如上逐字节分割更省，任何低于穷举的方法都可以。

现代密码分析的主要技术就是按区分器构造方式的不同来分类的：

  • 差分分析利用高概率差分路线构造区分器；飞去来器与矩形攻击同时利用两条高概率路线；截断差分把特定差分值放宽为满足某些条件的差分集合；不可能差分反其道而行之，利用概率为 \(0\) 的路线。见第三章。
  • 线性分析利用高偏差的线性逼近式，此后又有基于零偏差线性逼近的零相关线性分析。见第四章。
  • 此外还有积分攻击（第五章）、中间相遇攻击（第六章）等。

不同攻击的侧重点不同，对同一个算法的效果也不同。所以衡量一个算法的安全性，需要考虑各种攻击的影响。特别是新算法发布时，设计者必须给出用现有各种攻击分析得到的详细数据，作为安全性的重要指标。

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

完

评论

查看图表
本文目录