第 7 章：分组密码的其他攻击方法
前几章的差分、线性、积分分析都是统计分析方法。这一章介绍另外两类攻击：一是代数攻击，它是确定性的，利用算法内部的代数结构；二是滑动攻击，它利用算法的自相似性，与轮数无关。
§ 01代数攻击
代数攻击 (algebraic cryptanalysis) 区别于差分、线性等统计分析方法，是一类确定性的攻击，主要利用算法内部的代数结构。密码算法总可以建模成一系列多变元的代数方程系统，所以通过求解方程系统就可以攻击算法。如果能成功恢复出密钥，或者恢复出一个与具体密钥值无关的等价表示，就视为攻击成功。
本节先介绍插值攻击，再介绍布尔域 \(\mathbb F_2\) 上的线性化攻击和有限域 \(\mathbb F_q\) 上的 Gröbner 基攻击。
1.1 插值攻击
插值攻击 (interpolation attack) 由 Jakobsen 和 Knudsen 提出，是分组密码的第一个代数攻击。密文总可以表示成明文的一系列多项式。如果这些多项式的次数较低，攻击者就可以通过收集足够多的明密文对恢复多项式的系数，从而得到一个与密钥值无关的算法表示。此时攻击者可以在不知道密钥的情况下任意加密明文，得到对应的密文。
定理 1.1拉格朗日插值公式
对某个多项式函数，给定 \(d+1\) 个取值点 \((x_0,y_0),\cdots,(x_d,y_d)\)，其中 \(x_i,y_i\in\mathbb F_q\) 且 \(x_i\) 两两不同。拉格朗日插值多项式定义为
则 \(y_i=f(x_i)\)，\(0\le i\le d\)。
注
密码学中一般使用有限域 \(\mathbb F_q\) 或 \(\mathbb F_{2^n}\)，\(q\) 为素数。
设分组密码 \(E_k:\mathbb F_{2^n}\to\mathbb F_{2^n}\) 的最高次数为 \(d<2^n\)，则
\(g_i(k)\) 是与密钥有关的多项式。密钥实际上是未知的确定值，所以可以改写为
\(c_0,\cdots,c_d\) 为未知系数。由拉格朗日插值，敌手只需收集 \(d+1\) 个已知明密文对作插值，就能恢复 \(E_k\) 的表达式。构造拉格朗日插值多项式的复杂度为 \(O(d\log d)\)。
例 1.2
设 \(E_k\) 是定义在 \(\mathbb F_{2^n}\) 上的 \(r\) 轮迭代分组密码，第 \(i\) 轮的轮函数为
\(x_0\) 为输入的明文 \(p\)，\(k_0,\cdots,k_{r-1}\) 为独立选取的密钥。当 \(r=2\) 时，求插值攻击所需的数据量和复杂度。
解
记密文为 \(c\)。特征为 2 时 \((a\oplus b)^3=a^3\oplus a^2b\oplus ab^2\oplus b^3\)，\((a\oplus b)^8=a^8\oplus b^8\)，展开得
密钥是未知的确定值，所以可以改写为
\(c_0,\cdots,c_6\) 为方程的系数。方程的最高次数为 9，由拉格朗日插值定理，敌手收集 10 个明密文对，就能通过插值恢复所有系数。复杂度为 \(O(9\log9)\) 次域运算，可以忽略。
习题 1.3
上面的插值攻击如何扩展为密钥恢复攻击？
解
有两种思路。
- 直接从系数解密钥：由 (1)，\(c_0=k_0\)，\(c_1=k_1\)。插值恢复出系数后，直接读出 \(k_0=c_0\)，\(k_1=c_1\)，再用其余系数验证。
- 对更多轮，猜最后一轮密钥后插值（Jakobsen–Knudsen 的通用做法）：对 \(r\) 轮算法，猜测最后一轮密钥 \(k_{r-1}\)，把密文部分解密一轮，得到 \(r-1\) 轮输出关于明文的多项式，次数为 \(3^{r-1}\)。用 \(3^{r-1}+1\) 个明密文对插值出多项式，再用一个额外的明密文对检验：猜对时插值多项式能预测这个额外的值，猜错时一般不能。时间复杂度约为 \(2^n\times O(3^{r-1}\cdot(r-1)\log3)\)。
习题 1.4
上例中多项式次数虽为 9，但只有 7 个未知系数（项是稀疏的）。可以尝试用高斯消元法恢复系数。高斯消元的复杂度和成功率分别是多少？
解
把 \(c_0,\cdots,c_6\) 看作未知量，每个明密文对给出一个关于它们的线性方程
只需 7 个明密文对，比插值少 3 个。求解 \(7\times7\) 的线性系统需 \(O(7^3)\) 次域运算，可以忽略。
成功的条件是系数矩阵（行为 \((p^8,p^6,p^4,p^3,p^2,p,1)\)）满秩。对随机选取的 7 个不同明文，可以把它看作 \(\mathbb F_{2^n}\) 上的随机矩阵，满秩的概率约为 \(\prod_{i\ge1}(1-2^{-ni})\approx1-2^{-n}\)，几乎一定成功。不满秩时再多取一个明文即可。
1.2 线性化
线性化 (linearization) 是求解布尔域 \(\mathbb F_2\) 上多变元方程系统的重要技术：把方程中所有的单项式都看作新的独立变量，利用线性代数求解。具体地说，对 \(n\) 进 \(m\) 出的向量布尔函数 \(F:\mathbb F_2^n\to\mathbb F_2^m\)，\(F_i\) 为其第 \(i\) 个坐标函数。令 \(\mathbb A\) 为 \(F\) 的坐标函数中所有可能出现的指数集合，指数 \(\alpha=(\alpha_1,\cdots,\alpha_n)\in\{0,1\}^n\)，则
于是 \(F\) 可以写成
把每个单项式 \(x^\alpha\) 看作独立的线性变量，就可以用高斯消元法求解。
线性化的有效性主要取决于方程组中线性独立的单项式数目，所以估计单项式数目是计算线性化复杂度的重要步骤。一般地，对最高次数为 \(d\) 的 \(n\) 元向量布尔函数，求解的时间复杂度上界为 \(D^\omega\) 次比特操作（\(\omega\) 一般取 2.8 或 3），数据复杂度上界为 \(D\)，其中 \(D\) 为次数不超过 \(d\) 的单项式个数：
注
若时间复杂度的单位是运行一次加密的时间，则需要把比特操作折算过去。
实际攻击中还可以用先猜后定 (guess-and-determine) 策略降低复杂度：预先猜定 \(g\) 个比特的取值，此时可能出现的单项式数目变为
求解的时间复杂度上界为 \(2^g\times(D_g)^\omega\) 次比特操作，数据复杂度上界为 \(D_g\)。
例 1.5EL 算法的线性化攻击
分组加密算法 EL 是一个 3 轮 SPN 结构算法，分组长度与轮密钥长度均为 12 比特。内部状态是 \(3\times4\) 的比特矩阵：
明密文分别记为 \(p=(p_0,\cdots,p_{11})\)，\(c=(c_0,\cdots,c_{11})\)，\(p_i,c_i\in\mathbb F_2\)。每一轮使用相同的轮密钥 \(k=(k_0,\cdots,k_{11})\)。轮函数包含三步：
- 异或轮密钥：状态矩阵逐比特与轮密钥异或；
-
字节替换：用同一个 3 比特 S 盒对状态矩阵的每一列作替换，\((y_0,y_1,y_2)=S(x_0,x_1,x_2)\)，
\[ y_0=x_0x_2\oplus x_1\oplus1,\qquad y_1=x_0x_1\oplus x_1\oplus x_2\oplus1,\qquad y_2=x_1x_2\oplus x_0\oplus x_2; \] -
行变换：对状态矩阵的每一行用矩阵 \(M\) 作线性变换，
\[ M=\begin{pmatrix}1&1&0&0\\0&1&1&0\\0&0&1&1\\1&0&0&1\end{pmatrix}. \]
三轮 EL 算法线性化攻击的复杂度为多少？
解
线性化攻击中，敌手收集明密文对，构造与密钥变量有关的多项式求解。把 EL 的输出 \(c\) 看成明文 \(p\) 和密钥 \(k\) 的多项式，明密文已知时，每一轮的代数次数为 2，所以三轮后关于密钥 \(k=(k_0,\cdots,k_{11})\) 的多项式次数为 \(d=2^3=8\)。可能出现的单项式数目为
取 \(\omega=2.8\)，时间复杂度为 \(D^\omega\approx2^{33.29}\) 次比特操作。每个明密文对给出 12 个方程，数据复杂度为 \(D/12\approx2^{8.31}\) 个明密文对。
用先猜后定策略，设猜测 \(g\) 个密钥比特（\(1\le g\le12\)），单项式数目为
取 \(\omega=2.8\)，\(g=4\) 时 \(D_4=255\)，时间复杂度为 \(2^4\times255^{2.8}\approx2^{26.4}\) 次比特操作，数据复杂度为 \(255/12\approx2^{4.41}\) 个明密文对。
注
这两个数我用程序重算过：\(D/12\approx2^{8.305}\)，\(D_4/12\approx2^{4.409}\)。教材印的是 \(2^{8.301}\) 和 \(2^{4.415}\)，差别在小数点后第二位，应该是舍入方式不同，不影响结论。
一般化的线性化攻击假定所有次数不超过 \(d\) 的单项式都会出现，但实际算法中单项式可能是稀疏的。在上例中，考虑第一轮字节替换在内部状态位置 1 的输出：
与密钥有关的项只有 1 个二次项和 3 个线性项。简单计算可知，过完整个字节替换后，与密钥有关的项只有 12 个二次项和 12 个线性项，而不是 \(\binom{12}2=66\) 个二次项。过第二轮轮函数也有同样的结论。所以实际攻击中可以根据算法结构进一步确定单项式数目。
习题 1.6
用 SageMath 计算 EL 算法两轮和三轮后与密钥相关的单项式数目。
思路
在 \(\mathbb F_2[p_0,\cdots,p_{11},k_0,\cdots,k_{11}]\) 的商环（模 \(x_i^2-x_i\)）中，用 BooleanPolynomialRing 定义 24 个变量，按定义逐轮计算状态的 12 个多项式。对每个输出多项式取 monomials()，把每个单项式中的明文变量去掉（明文已知，相当于系数），收集只含密钥变量的部分并去重，统计个数。关键代码：
R = BooleanPolynomialRing(24, ['p%d' % i for i in range(12)] + ['k%d' % i for i in range(12)])
P, K = R.gens()[:12], R.gens()[12:]
def S(x0, x1, x2):
return (x0*x2 + x1 + 1, x0*x1 + x1 + x2 + 1, x1*x2 + x0 + x2)
def rnd(s):
s = [s[i] + K[i] for i in range(12)]
for c in range(4):
s[c], s[c+4], s[c+8] = S(s[c], s[c+4], s[c+8])
out = [None] * 12
for r in range(3):
row = s[4*r:4*r+4]
out[4*r:4*r+4] = [row[0]+row[1], row[1]+row[2], row[2]+row[3], row[0]+row[3]]
return out
rnd 中的行变换要按 \(M\) 是左乘还是右乘确定（上面按 \(\boldsymbol y=M\boldsymbol x\) 写）。两轮、三轮后分别统计，就能看到实际单项式数目远小于 \(D\)。
1.3 Gröbner 基攻击
Gröbner 基算法是目前公认可用于求解多变元高次方程系统的有效算法。通常把密码算法建模成多变元方程系统，再用现有的 Gröbner 基算法求解。具体的数学理论可以参考 Cox、Little、O'Shea 的《Ideals, Varieties, and Algorithms》。
对 \(\mathbb F_q[X_1,\cdots,X_{n_v}]\) 上有 \(n_v\) 个变元的多项式系统 \(P_1,\cdots,P_{n_e}\)，记理想 \(\mathcal I=\langle P_1,\cdots,P_{n_e}\rangle\)，可以用 F4 或 F5 算法计算 \(\mathcal I\) 的 Gröbner 基。若算出的 Gröbner 基是字典序的，最后得到的形式为
即可递归求解：先用单变元求根的方法解 \(G_1(X_1)\)，把解代入 \(G_{2,i}(X_1,X_2)\)，依次类推。但直接计算字典序 Gröbner 基的成本太大，所以一般先计算分次反字典序 (grevlex) 的 Gröbner 基，再用 FGLM 算法转为字典序。
定理 1.7算法（Gröbner 基攻击）
- 多项式建模：把密码算法建模成一系列多变元多项式；
- 用 F4 或 F5 算法计算分次反字典序的 Gröbner 基；
- 用 FGLM 算法对得到的 Gröbner 基作项序转换，从分次反字典序转为字典序；
- 用单变元求根法依次回代求解。
复杂度。 第 2 步中，多项式系统通常是非正则系统，而非正则系统的分析较困难，所以通常用等价的正则系统来估计。记 \(d_i\) 为 \(P_i\) 的次数，\(d\) 为理想 \(\mathcal I\) 的次数（即 \(\overline{\mathbb F_q}^n\) 中解的个数），\(D_{\mathrm{reg}}\) 为 \(\mathcal I\) 的正则度，则
系统正则时取等号。在假定系统正则的前提下，计算 Gröbner 基的复杂度为
\(2\le\omega<3\) 为线性代数中高斯消元的指数。
第 3 步中，原始的 FGLM 算法复杂度为 \(O(n_vd^3)\)，也存在一些复杂度更优的概率性算法。第 4 步主要用单变元求根算法，复杂度约为 \(O\big(d\log d(\log d+\log q)\log\log d\big)\) 次运算。
注
从复杂度公式可以看出，Gröbner 基攻击的代价主要由正则度 \(D_{\mathrm{reg}}\) 决定，而 \(D_{\mathrm{reg}}\) 随方程次数 \(d_i\) 线性增长。这就是为什么近年面向零知识证明、多方计算设计的“算术化友好”算法（如 MiMC、Poseidon）特别关注代数次数：它们在大素数域上运算、轮函数次数很低，插值攻击和 Gröbner 基攻击是对它们最主要的威胁。
§ 02滑动攻击
滑动攻击 (slide attack) 是 Biryukov 和 Wagner 在 FSE 1999 上提出的一种利用算法自相似性构造区分器的攻击方法。在 EUROCRYPT 2000 上，他们又扩展了滑动的形式，提出高级滑动攻击 (advanced slide attack)。
滑动攻击可以在已知明文或选择明文两种场景下进行。与相关密钥攻击一样，滑动攻击都基于密钥编排，利用轮密钥之间的关系构造区分器。值得注意的是，滑动攻击与算法轮数无关：一旦存在滑动攻击，就很难通过简单增加轮数来提高抵抗能力。一般而言，若密钥编排存在一定的周期性，就容易受到滑动攻击。所以现在多数密钥编排都通过引入不同的轮常数来消除周期性，避开滑动攻击。
本章只考虑每轮轮密钥都相同这种最简单的情况，更复杂的情形参考 Biryukov 和 Wagner 的两篇原文。
2.1 滑动攻击原理
设加密算法 \(E\) 为 \(r\) 轮迭代，每轮的轮函数都为 \(F\)，分组长度为 \(n\) 比特。
定义 2.1滑动对
若 \(F(K,P_0)=P_1\)，则称 \((P_0,P_1)\) 为滑动对 (slid pair)。
把 \(P_1\) 的加密过程相对 \(P_0\) 的“滑动”一轮：
注
若 \((P_0,P_1)\) 为滑动对，因为两条加密路线只是错开了一轮，易得 \(F(K,C_0)=C_1\) 也成立，于是得到关于密钥 \(K\) 的方程组。对滑动对 \((P_0,P_1)\)：
- 对正确密钥 \(K\)，\(F(K,P_0)=P_1\) 与 \(F(K,C_0)=C_1\) 一定同时成立；
- 对错误密钥 \(K\)，两式以 \(2^{-2n}\) 的概率同时成立。
反过来，若滑动对 \((P_0,P_1)\) 对应的关于 \(K\) 的方程组
有解，就认为该解为正确密钥的候选值。
定理 2.2算法（已知明文环境下的滑动攻击）
- 获取 \(2^{n/2}\) 个已知明密文对 \((P_i,C_i)\)。由生日攻击，其中以不可忽略的概率存在一个滑动对；
-
对所有 \(i,j\in\{1,2,\cdots,2^{n/2}\}\)，\(i\ne j\)，求解关于密钥 \(K\) 的方程组
\[ \begin{cases}F(K,P_i)=P_j,\\F(K,C_i)=C_j.\end{cases} \]若有解，认为该解为正确密钥的候选值，且相应的 \((P_i,P_j)\) 为滑动对；
-
若上一步求出的密钥多于 1 个，再结合穷举攻击或另一个 \(2^{n/2}\) 个明密文对的集合识别出唯一的正确密钥。
可见攻击的数据复杂度为 \(O(2^{n/2})\) 个已知明文，时间复杂度受第 2 步的影响，为 \(O(2^n)\) 次方程组求解。若能利用 \(F\) 的特性降低第 2 步的复杂度，攻击的复杂度就会低于强力攻击，滑动攻击成功。一般来说，滑动攻击要求轮函数 \(F\) 是弱置换。
定义 2.3弱置换
若关于密钥 \(K\) 的方程组
容易求解，则称 \(F\) 为弱置换 (weak permutation)。
注
这里的“容易求解”是一个相对的概念，结合下面 Feistel 结构的滑动攻击来理解。
2.2 Feistel 结构的滑动攻击
下面以 Feistel 结构的算法为例，说明滑动攻击在已知明文环境下的复杂度为 \(O(2^{n/2})\)，在选择明文环境下为 \(O(2^{n/4})\)。
已知明文环境。 按 §2.1 的模型，已知 \(2^{n/2}\) 个明密文对 \((P_i,C_i)\)。在 Feistel 结构中，每个明密文都可以分成长度相等的左右两部分，记作 \((P_{i,L}\Vert P_{i,R},\ C_{i,L}\Vert C_{i,R})\)。若 \((P_a,P_b)\) 为滑动对，则一轮 Feistel 把 \(P_a\) 的右半直接搬到 \(P_b\) 的左半，密文端同理，所以一定满足
反之，不满足这一特性的一定不是滑动对。所以可以用哈希表直接过滤出滑动对：按 \((P_R,C_L)\) 建表，再以 \((P_L,C_R)\) 查表，复杂度为 \(O(2^{n/2})\)。得到滑动对后，代入方程组 (2) 求解正确密钥的候选值。\(F\) 是弱置换，模型第 2 步的时间复杂度降为 \(O(2^{n/2})\)，攻击的总复杂度为 \(O(2^{n/2})\)，低于穷举攻击。
选择明文环境。 这时可以直接选择满足 \(P_{a,R}=P_{b,L}\) 的明文对，进一步降低复杂度。选择两个各由 \(2^{n/4}\) 个明文构成的结构体
其中 \(x\) 为随机选取的 \(n/2\) 比特常数，\(y_i\) 和 \(y_j\) 各遍历 \(2^{n/4}\) 种可能。于是
只需验证 \(C_{i,L}=C_{j,R}\) 是否满足。两个结构体之间共有 \(2^{n/4}\times2^{n/4}=2^{n/2}\) 对，而每对是滑动对的概率约为 \(2^{-n/2}\)（只需 \(F\) 的输出与 \(y_j\) 吻合），所以这两个结构体中以不可忽略的概率存在一个滑动对，且识别滑动对的复杂度为 \(O(2^{n/4})\)。因此攻击的总复杂度为 \(O(2^{n/4})\)，低于穷举攻击。
习题 2.4
若把 DES 由 16 轮改为 96 轮，主密钥由 56 比特改为 96 比特，即 96 比特的主密钥分为 48 比特的两个轮密钥 \((K_0,K_1)\) 循环使用（第一轮用 \(K_0\)，第二轮用 \(K_1\)，第三轮用 \(K_0\)，……），能否对这个变形算法 2K-DES 实施滑动攻击？复杂度为多少？
解
能。把相邻两轮合起来看作一个“大轮” \(F'=F_{K_1}\circ F_{K_0}\)，96 轮 2K-DES 就是 48 个相同的大轮，满足滑动攻击的前提：\((P_0,P_1)\) 是滑动对当且仅当 \(F'(P_0)=P_1\)。
困难在于 \(F'\) 是两轮 Feistel，它的左右两半都被改动，不能再用 \(P_{a,R}=P_{b,L}\) 过滤。Biryukov 和 Wagner 的办法是扭转滑动 (twist) 或互补滑动 (complementation slide)：
- 互补滑动：把 \(P_1\) 的加密相对 \(P_0\) 滑动一轮（不是一个大轮），此时 \(P_0\) 用 \(K_0,K_1,K_0,\cdots\)，\(P_1\) 用 \(K_1,K_0,K_1,\cdots\)。两个加密的每一轮之间密钥差为 \(\Delta=K_0\oplus K_1\)，若同时给中间状态引入差分 \((\Delta,\Delta)\)，可以让它在每一轮的 F 函数输入处抵消。于是又回到单轮滑动对的情形，可用 \(P_{a,R}=P_{b,L}\oplus\Delta\) 一类的条件过滤。
- 复杂度：已知明文下约需 \(2^{n/2}=2^{32}\) 个已知明文和 \(2^{32}\) 量级的时间。由于 DES 的 F 是弱置换（每个滑动对给出关于 48 比特轮密钥的方程，可以通过 S 盒逐个求解），复杂度与轮数无关，远低于 \(2^{96}\) 的穷举。
更细的条件和推导见 Biryukov–Wagner, Advanced Slide Attacks, EUROCRYPT 2000。
习题 2.5
思考：对 Feistel 结构，若轮密钥循环使用 \(K_0,K_1\)，还可以存在哪些滑动形式？
提示
Biryukov–Wagner 的高级滑动攻击给出了两种：
- 互补滑动 (complementation slide)：滑动一轮，利用密钥差 \(K_0\oplus K_1\) 与状态差相互抵消；
- 扭转滑动 (sliding with a twist)：把一个加密与另一个解密对齐（Feistel 的解密与加密结构相同，只是轮密钥顺序相反），对 \(K_0,K_1\) 交替的结构，解密的轮密钥序列恰好与加密错开一轮后吻合。
两者还可以组合使用（complementation + twist），对付更复杂的周期性密钥编排。
§ 03小结
- 代数攻击是确定性攻击：插值攻击利用低次数恢复多项式表示，线性化把单项式当作新变量解线性方程组（可配合先猜后定），Gröbner 基攻击用 F4/F5 + FGLM 解一般多变元方程组，其复杂度主要由正则度决定。
- 滑动攻击利用轮函数的自相似性，复杂度与轮数无关。已知明文下 \(O(2^{n/2})\)，Feistel 结构的选择明文攻击 \(O(2^{n/4})\)。抵抗方法是在密钥编排中加入轮常数，破坏周期性。
参考：王美琴主编，《密码分析学》，科学出版社，2024，第 7 章。
完
评论