第 12 章：序列密码的立方攻击
第十一章介绍了在 LFSR 的基础上增加非线性滤波函数来引入非线性。另一种办法是把移位寄存器的反馈函数改为非线性函数，这就是非线性反馈移位寄存器 (NFSR)。经过多轮非线性迭代后，输出是关于输入的高次非线性方程，直接求解很困难。立方攻击 (cube attack) 通过对高次变量集合求和，得到密钥的低次（如线性）方程，从而恢复密钥信息。
立方攻击和第五章的积分攻击本质上是同一件事：对一个公开变量的子空间求和，把高次项“积”掉。区别在于积分攻击关心求和结果是否为 0（区分器），立方攻击关心求和结果是什么（关于密钥的方程）。
§ 01布尔函数
1.1 代数标准型
记 \([n]=\{1,2,\cdots,n\}\)。对 \(I\subseteq[n]\)，令 \(x^I=\prod_{i\in I}x_i\)。
定义 1.1代数标准型
\(n\) 元布尔函数 \(F\) 的代数标准型 (ANF) 为
加法为模 2 运算，\(a_I\in\{0,1\}\)。\(I\) 中元素的个数称为项 \(x^I\) 的代数次数，所有（\(a_I=1\) 的）项的最大代数次数称为 \(F\) 的代数次数。
布尔函数的另一种表示是真值表：列出所有输入及对应的输出，\(n\) 元函数的真值表大小为 \(2^n\)。已知 ANF 时，把所有输入代入即得真值表。例如三元择多函数 \(f(x)=x_1x_2\oplus x_1x_3\oplus x_2x_3\)：
| \(x_1x_2x_3\) | 000 | 100 | 010 | 110 | 001 | 101 | 011 | 111 |
|---|---|---|---|---|---|---|---|---|
| \(f\) | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 |
（注意这张表的行序：\(x_1\) 是最低位。）还可以把布尔函数表示成逻辑门（与、或、非），这在密码分析中比较少见。
1.2 莫比乌斯变换
真值表到 ANF 的转换可以用莫比乌斯变换 (Möbius transform) 实现，部分文献也叫杨辉三角变换。莫比乌斯变换是可逆的，且逆变换仍是莫比乌斯变换，所以对 ANF 再作一次莫比乌斯变换就得到真值表。
定理 1.2算法（莫比乌斯变换）
输入：\(n\) 元布尔函数 \(f\) 的真值表 \(z[i]\)，\(0\le i<2^n\)。
-
对 \(t=1,\cdots,n\)：
- 对 \(j=0,\cdots,2^{n-t}-1\)：
-
对 \(k=0,\cdots,2^{t-1}-1\)：
\[ z[2^tj+2^{t-1}+k]\leftarrow z[2^tj+2^{t-1}+k]\oplus z[2^tj+k]; \]
-
- 对 \(j=0,\cdots,2^{n-t}-1\)：
-
返回 \(z\)。
变换结束后，所有结果为 1 的位置对应的单项式之和就是 ANF。复杂度为 \(O(n\cdot2^n)\)，与 Hadamard 变换类似。
它为什么对？第 \(t\) 步把“第 \(t\) 个变量为 1 的位置”加上“第 \(t\) 个变量为 0 的对应位置”，相当于对第 \(t\) 个变量作差分 \(f|_{x_t=1}\oplus f|_{x_t=0}\)。\(n\) 步之后，位置 \(u\) 上的值是
即对 \(u\) 所支撑的子立方体求和。这正是 ANF 的系数公式，也正是下面立方攻击定理的特例。
例 1.3择多函数的莫比乌斯变换
以上表的真值表为例，下标 \(i\) 的二进制最低位对应 \(x_1\)：
- \(t=1\)：\(z[1]\mathrel{\oplus}=z[0]\)，\(z[3]\mathrel{\oplus}=z[2]\)，\(z[5]\mathrel{\oplus}=z[4]\)，\(z[7]\mathrel{\oplus}=z[6]\)；
- \(t=2\)：\(z[2]\mathrel{\oplus}=z[0]\)，\(z[3]\mathrel{\oplus}=z[1]\)，\(z[6]\mathrel{\oplus}=z[4]\)，\(z[7]\mathrel{\oplus}=z[5]\)；
- \(t=3\)：\(z[4]\mathrel{\oplus}=z[0]\)，\(z[5]\mathrel{\oplus}=z[1]\)，\(z[6]\mathrel{\oplus}=z[2]\)，\(z[7]\mathrel{\oplus}=z[3]\)。
| \(x_1x_2x_3\) | 真值 | \(t=1\) | \(t=2\) | ANF (\(t=3\)) |
|---|---|---|---|---|
| 000 | 0 | 0 | 0 | 0 |
| 100 | 0 | 0 | 0 | 0 |
| 010 | 0 | 0 | 0 | 0 |
| 110 | 1 | 1 | 1 | 1 |
| 001 | 0 | 0 | 0 | 0 |
| 101 | 1 | 1 | 1 | 1 |
| 011 | 1 | 1 | 1 | 1 |
| 111 | 1 | 0 | 1 | 0 |
\(z[3],z[5],z[6]\) 为 1，对应 110、101、011，即 \(x_1x_2\)、\(x_1x_3\)、\(x_2x_3\)，所以 \(f=x_1x_2\oplus x_1x_3\oplus x_2x_3\)。注意 000 代表常数项 1。
习题 1.4
令 \(f(x)=x_1x_2x_3\oplus x_3x_4\oplus x_2x_4\oplus x_3\) 是一个 4 元布尔函数，根据莫比乌斯变换推导其真值表。
解
ANF 的系数为 1 的位置是 \(\{x_3\}\)、\(\{x_2,x_4\}\)、\(\{x_3,x_4\}\)、\(\{x_1,x_2,x_3\}\)。对这个系数向量作一次莫比乌斯变换就是真值表：\(f(x)=\bigoplus_{u\preceq x}a_u\)，即数一数 \(x\) 覆盖了几个系数为 1 的单项式，奇数个为 1。
| \(x_1x_2x_3x_4\) | 覆盖的单项式 | \(f\) |
|---|---|---|
| 0000 | — | 0 |
| 0001 | — | 0 |
| 0010 | \(x_3\) | 1 |
| 0011 | \(x_3\)，\(x_3x_4\) | 0 |
| 0100 | — | 0 |
| 0101 | \(x_2x_4\) | 1 |
| 0110 | \(x_3\) | 1 |
| 0111 | \(x_3\)，\(x_2x_4\)，\(x_3x_4\) | 1 |
| 1000 | — | 0 |
| 1001 | — | 0 |
| 1010 | \(x_3\) | 1 |
| 1011 | \(x_3\)，\(x_3x_4\) | 0 |
| 1100 | — | 0 |
| 1101 | \(x_2x_4\) | 1 |
| 1110 | \(x_3\)，\(x_1x_2x_3\) | 0 |
| 1111 | 全部 4 个 | 0 |
（我用程序直接代入核对过这 16 个值，再对真值表作莫比乌斯变换，也正好恢复出这 4 个单项式。）
§ 02立方攻击原理
Dinur 和 Shamir 在 EUROCRYPT 2009 上提出了立方攻击，它基于如下定理。
定理 2.1立方攻击
设 \(p(x)\) 是关于 \(n\) 个变量 \(x_1,\cdots,x_n\) 的布尔函数。选择集合 \(I=\{i_1,\cdots,i_{|I|}\}\subseteq[n]\)，令 \(t_I=\prod_{i\in I}x_i\)，则 \(p\) 总可以表示成
其中 \(p_1\) 不含任何 \(x_i\)（\(i\in I\)），\(p_2\) 中的每一项都不能被 \(t_I\) 整除（即至少不含一个 \(x_i\)，\(i\in I\)）。则 \(p\) 在 \(|I|\) 个变量 \(x_{i_1},\cdots,x_{i_{|I|}}\) 的所有可能取值下求和，结果恰好等于 \(p_1\)：
证明
\(t_I\) 只在所有 \(x_i\)（\(i\in I\)）都为 1 时为 1，\(p_1\) 与这些变量无关，所以 \(\sum t_Ip_1=p_1\)。\(p_2\) 的每一项都缺某个 \(x_j\)（\(j\in I\)），这一项在求和时，\(x_j=0\) 和 \(x_j=1\) 两半取值相同，模 2 相消，所以 \(\sum p_2=0\)。
一个密码算法往往以 \(m\) 比特密钥 \(k=(k_1,\cdots,k_m)\) 和 \(n\) 比特明文（或 IV、nonce）\(v=(v_1,\cdots,v_n)\) 为输入，任意一个输出比特都可以表示成 \(k\) 和 \(v\) 的布尔函数 \(p\)。实际应用中，\(t_I\) 通常选为 \(v\) 中一部分比特的乘积，\(v\) 中剩下的比特固定为常数，这使 \(p_1\) 成为只与密钥 \(k\) 相关的表达式。
定义 2.2立方攻击的术语
集合 \(I\) 称为立方索引，它决定了 \(t_I\) 是哪些变量的乘积。\(I\) 确定的变量称为立方变量，\(t_I\) 称为极大项 (maxterm)，\(p_1\) 称为超级多项式 (superpoly)。\(|I|\) 称为立方的维数。
密钥一般被当作（未知）常数，所以 \(p\) 的代数次数只由每一项中的明文比特决定。例如 \(p=k_1k_2v_4v_5\oplus k_1v_1v_2v_3\) 的代数次数为 3。实际应用中可能遇到两种情况：
- 若 \(p_1\) 是关于密钥的简单函数（如线性方程），就可以由定理得到关于密钥的简单方程，获取密钥的部分信息。这就是 Dinur 和 Shamir 的立方攻击：选择多个 \(t_I\)，使对应的 \(p_1\) 都是关于密钥比特的线性方程，求和建立线性方程组，解出密钥的大部分比特，剩下的穷举；
- 若 \(p_1\) 是非平衡的（如常数），可以用来构造区分器。特别地，若 \(p\) 的代数次数为 \(d\)，选取任意 \(d+1\) 维的 \(I\)，对应的 \(p_1\) 都为 0，即 \(p\) 在这 \(|I|\) 个明文比特的所有取值下求和为 0。这就是立方测试 (cube tester)，与第五章的积分区分器一样。
立方攻击分为两个阶段：
- 预计算阶段：攻击者对算法有完全的控制权限，可以随意操纵密钥比特和明文比特。目标是选取尽可能多的 \(t_I\)，恢复它们对应的 \(p_1\) 的具体表达式，\(p_1\) 越简单越好，比如关于密钥的线性表达式；
- 在线攻击阶段：密钥是未知的，但攻击者可以把任意明文作为输入，获取对应的输出。对 \(t_I\) 求和，获得 \(p_1\) 的真实值，从而建立关于密钥的方程组，恢复部分密钥。
例 2.3
设密钥流输出比特 \(z\) 可以表示为 5 个 IV 比特 \(v_0,\cdots,v_4\) 和 5 个密钥比特 \(k_0,\cdots,k_4\) 的布尔函数：
- 预计算阶段，选择极大项 \(t_I=v_1v_2v_4\)，其超级多项式为 \(p_1=k_2\)。在线阶段固定 \(v_0=v_3=0\)，对 \(v_1,v_2,v_4\) 的每一个可能取值获取 \(z\)，把这 8 个值相加，结果即为 \(p_1\) 的真实值 \(a\)，于是建立方程 \(k_2=a\)，恢复出 \(k_2\)。这一步需要 \(2^3=8\) 次异或；
- 同理，选取 \(t_I=v_2v_3v_4\)，\(p_1=k_0\)，固定 \(v_0=v_1=0\)，在 \(v_2,v_3,v_4\) 上求和，就能恢复 \(k_0\)，也是 8 次异或。
注
“固定其余 IV 比特为 0”很要紧。以 \(t_I=v_1v_2v_4\) 为例，含 \(v_1v_2v_4\) 的项只有 \(v_1v_2v_4k_2\)，所以严格的超级多项式就是 \(k_2\)，与 \(v_0,v_3\) 无关；但 \(p_2\) 中的项（如 \(v_0v_1k_2k_4\)）虽然求和后消失，也要求它们在求和中是“缺某个立方变量”的。这里没有问题。我用程序对全部 \(2^5\) 个密钥验证过：两次立方和分别恒等于 \(k_2\) 和 \(k_0\)。
这个例子中已知输出比特关于 IV 和密钥的表达式，可以有针对性地选择 \(t_I\)。在实际的流密码中，密钥流比特与 IV、密钥的关系往往很复杂，写不出具体表达式，也就不知道某个极大项对应的超级多项式。这时可以用立方测试的办法获得极大项和超级多项式，依据是下面的引理。
引理 2.4线性测试
记输出比特关于 \(n\) 比特 IV \(v\) 和 \(m\) 比特密钥 \(k\) 的表达式为 \(z(v,k)\)。令立方索引 \(I\subseteq[n]\)，\(t_I\) 为由 \(I\) 决定的极大项，对应的超级多项式为 \(p_1\)。某个密钥比特 \(k_i\) 在 \(p_1\) 中线性出现（即 \(p_1=k_i\oplus g\)，\(g\) 不含 \(k_i\)）当且仅当对所有 \((k_1,\cdots,k_{i-1},k_{i+1},\cdots,k_m)\in\{0,1\}^{m-1}\)，
注
教材的引理表述是“某个密钥比特 \(k_i\) 在超级多项式 \(p_1\) 中当且仅当……”，句子里缺了一个修饰词。按等式的含义，条件说的是 \(p_1|_{k_i=0}\oplus p_1|_{k_i=1}=1\) 对其余所有密钥恒成立，即 \(\partial p_1/\partial k_i\equiv1\)，这正好是“\(k_i\) 在 \(p_1\) 中线性出现、不与其他密钥比特相乘”。我按这个意思补上了“线性出现”。
由引理，选择一个 IV 变量集合，把 \(m-1\) 比特密钥固定为任意值，把剩下的一比特密钥分别置为 0 和 1，计算输出比特在 \(t_I\) 上的立方和：
- 无论 \(m-1\) 比特密钥取什么，立方和始终不同，则该密钥比特为一个线性项；
- 立方和始终相同，则该密钥比特不在 \(p_1\) 中；
- 其他情况，该密钥比特为非线性项。
对每个密钥比特都执行这样的操作。若每个密钥比特都是线性项或不在 \(p_1\) 中，这个变量集合就是一个（线性的）极大项，可以确定超级多项式的表达式（再通过把所有密钥置 0 求一次立方和得到常数项）。特别地，若 \(p_1\) 不含任何密钥变量，则 \(p_1\) 为常数。
实际中不可能遍历 \(2^{m-1}\) 种其他密钥，只能随机抽取几十到上百组做检验，这就是线性测试（BLR 测试）：线性函数一定通过，非线性函数以较大的概率被淘汰。
习题 2.5
令 \(f(k,v)=k_1k_2v_1v_2\oplus k_3k_4v_1v_2v_3\oplus v_2v_3\oplus k_4v_4\) 是关于 4 比特初始向量 \(v\) 和 4 比特密钥 \(k\) 的布尔函数。指出 \(f\) 的代数次数，并写出极大项 \(t_I=v_1v_2\) 的超级多项式。
解
密钥看作常数，代数次数由 IV 比特决定：各项的 IV 次数分别为 2、3、2、1，所以 \(f\) 的代数次数为 3。
\(t_I=v_1v_2\) 的超级多项式是 \(f\) 中能被 \(v_1v_2\) 整除的项除以 \(v_1v_2\) 之和：
注意它仍含 IV 变量 \(v_3\)。在线阶段把 \(v_3,v_4\) 固定为常数：\(v_3=0\) 时 \(p_1=k_1k_2\)，\(v_3=1\) 时 \(p_1=k_1k_2\oplus k_3k_4\)。两者都是二次的，不是线性超级多项式。但联合两个值可以得到 \(k_1k_2\) 和 \(k_3k_4\) 的值，各自约束了 2 比特密钥（例如 \(k_1k_2=1\) 直接给出 \(k_1=k_2=1\)）。
习题 2.6思考
立方攻击也可以利用非线性的超级多项式。在上面的例子中，若选取极大项 \(t_I=v_0v_1\)，如何利用其超级多项式提取密钥比特的信息？
解
含 \(v_0v_1\) 的项有 \(v_0v_1k_2k_4\)、\(v_0v_1v_3k_2\)、\(v_0v_1v_2v_3\)，所以
它含 IV 变量 \(v_2,v_3\)，可以在在线阶段选择它们的值，得到不同的方程：
- \(v_2=v_3=0\)：立方和 \(=k_2k_4\)；
- \(v_2=0,v_3=1\)：立方和 \(=k_2k_4\oplus k_2\)；
- \(v_2=v_3=1\)：立方和 \(=k_2k_4\oplus k_2\oplus1\)。
（\(v_4\) 不出现在 \(p_1\) 中，取任意值；我用程序对全部密钥核对过这三个等式。）前两个相加就得到线性方程 \(k_2=a_1\oplus a_2\)，再由第一个得到 \(k_2k_4\)，若 \(k_2=1\) 就直接得到 \(k_4\)。可见通过改变非立方 IV 变量的取值，可以把非线性超级多项式“线性化”。这就是后来条件立方攻击、动态立方攻击的出发点。
§ 03动态立方攻击
一般情况下，序列密码经过一定轮数的初始化后，输出密钥流是关于 IV 和密钥的高次稠密布尔函数，对选择的立方变量集合求和后的结果仍是关于密钥的高次非线性方程，直接求解很困难。在基于 LFSR 和 NFSR 的流密码中，输出比特可以表示成寄存器状态比特的布尔多项式，通过控制某些状态比特可以使输出布尔函数简化。Dinur 等提出了动态立方攻击 (dynamic cube attack)，结合立方测试得到的区分器恢复密钥信息，并把它应用到 Grain-128 上。
动态立方攻击的一项关键技术是零化技术：选择部分 IV 比特，使中间部分状态比特的取值为 0，从而简化输出。
下面以缩减轮的 Grain-128（算法见算法附录）为例。考虑初始化运行 128 轮后开始输出密钥流的版本，第一个输出比特是 \(z_{129}\)，在密钥流产生阶段 \(z_i\) 不参与反馈。
3.1 零化技术
Grain-128 的第一个输出比特 \(z_{129}\) 可以用状态比特表示为
\(b_i\) 为 NFSR 状态比特，\(s_i\) 为 LFSR 状态比特。
第一步：找最显著的项。 先计算每个状态比特关于 IV 的代数次数。\(b_{141}b_{224}s_{224}\) 次数最高，能产生更多高次项，是最显著的项。考虑通过零化 \(b_{141}\) 来消掉它。
第二步：零化。 由迭代关系，
选择 \(v_{26}=v_{73}=0\)，\(b_{141}\) 降为 1 次（\(v_{26}v_{33}\) 和 \(v_{73}v_{92}\) 消失）。再选择
就能使 \(b_{141}=0\)。式中的密钥比特是未知的，在实际攻击中要猜测：根据猜测的密钥值选择 \(v_{13}\) 使上式成立。需要猜测的是 \(k_{25}\)、\(k_{108}\)（它们与立方变量 \(v_{21},v_{55}\) 相乘），以及剩下的那个只与密钥有关的表达式的值
（1 比特）。所以只需猜 3 比特信息。
第三步：降次后的输出。 零化 \(b_{141}\) 之后，
涉及的状态比特关于 IV 的代数次数为
| 状态比特 | \(b_{224}\) | \(s_{224}\) | \(s_{171}\) | \(s_{189}\) | \(s_{208}\) | \(s_{142}\) | \(s_{149}\) | \(s_{222}\) |
|---|---|---|---|---|---|---|---|---|
| 次数 | 7 | 7 | 3 | 3 | 5 | 2 | 2 | 7 |
| 状态比特 | \(b_{218}\) | \(b_{202}\) | \(b_{193}\) | \(b_{174}\) | \(b_{165}\) | \(b_{144}\) | \(b_{131}\) |
|---|---|---|---|---|---|---|---|
| 次数 | 5 | 5 | 3 | 3 | 2 | 2 | 2 |
其他状态比特的次数满足
注
这张表我只是照录，没有复算。\(s_{96..127}\) 次数为 0、\(b_{0..127}\) 次数为 0 是因为 Grain-128 的 LFSR 后 32 位初始化为全 1、NFSR 初始化为密钥，都与 IV 无关；LFSR 前 96 位装 IV，次数为 1。
第四步：区分正确与错误的猜测。 在正确的密钥猜测下，零化 \(b_{141}\) 后输出的代数次数
（其余各项次数更低：\(s_{189}s_{208}\) 为 \(3+5=8\)，\(s_{222}\) 为 7，……）所以 \(z_{129}\) 在任意 11 维立方下的求和为 0。而在错误的密钥猜测下，\(b_{141}\) 不能被零化，且 \(\deg(b_{141})=1\)，输出的最高次项为 \(b_{141}b_{224}s_{224}\)，次数可达 \(1+7+7=15\)，\(z_{129}\) 在某些 11 维立方下的和不为 0。
也就是说，可以通过研究 \(z_{129}\) 在 11 维立方下的和来区分正确密钥和错误密钥。随机取若干个 11 维立方（避开 \(v_{13},v_{26},v_{73}\) 这几个被固定的 IV），用立方测试检测超级多项式是否为 0：正确猜测下总为 0，错误猜测下以可观的概率不为 0。测试得到的 11 维立方变量就作为正确密钥与错误密钥的区分器。
注
这是一个用“代数次数降低”作区分器的密钥恢复，与第三章猜部分密钥、看区分器是否成立的统计攻击结构相同，只是区分器换成了立方测试，判定是确定性的。完整 Grain-128 的动态立方攻击要零化多个状态比特，猜测更多密钥表达式，并用大得多的立方（Dinur 等用了 50 维左右，在 GPU 上跑）。
习题 3.1
根据 Grain-128 算法，通过编程或手动推导，计算出上表中状态比特的次数。
思路
用数值映射 (numeric mapping) 估计次数上界：对每个状态比特维护一个次数上界 \(\deg(\cdot)\)，初始化时 IV 比特为 1、密钥比特和常数为 0。按 Grain-128 的更新函数迭代：
- 异或：\(\deg(a\oplus b)\le\max(\deg a,\deg b)\)；
- 与：\(\deg(ab)\le\deg a+\deg b\)。
逐轮计算 \(s_{i+128}=s_i\oplus s_{i+7}\oplus s_{i+38}\oplus s_{i+70}\oplus s_{i+81}\oplus s_{i+96}\oplus z_i\)（初始化阶段 \(z_i\) 参与反馈）和 \(b_{i+128}\)（含若干二次项，见算法附录），就能得到每个状态比特次数的上界。注意在零化 \(v_{26}=v_{73}=0\) 的条件下要把这两个 IV 的次数置为 0，\(v_{13}\) 由密钥决定也置为 0。这样得到的是上界，表中的数字应该与之吻合或更紧（更紧的需要符号计算，例如用 SageMath 的 BooleanPolynomialRing 直接展开前几十轮）。这道题我没有实际跑。
参考：王美琴主编，《密码分析学》，科学出版社，2024，第 12 章。
完
评论