第 11 章：序列密码的经典安全性分析技术
序列密码 (stream cipher)，又称流密码，是最早使用的密码学技术之一，广泛应用于军事、外交和政府等关键应用的保密通信中。序列密码是一种对数据流进行加密的对称密码，一般说的序列密码加密算法指的是密钥流生成算法。许多序列密码逻辑实现简单、占用面积小、速度快，尤其适用于硬件资源受限的环境。
序列密码主要包括 5 类：表驱动型、线性反馈移位寄存器驱动型、非线性反馈移位寄存器驱动型、类分组型和字驱动型。当前主要以线性反馈移位寄存器 (LFSR) 和非线性反馈移位寄存器 (NFSR) 驱动为主。尽管序列密码很早就在军事中得到应用，它的标准化却比分组密码和公钥密码晚得多。欧洲的 NESSIE 和 eSTREAM 两大征集计划极大地促进了序列密码以及基于序列密码的认证加密算法的设计和分析，eSTREAM 的 7 个胜出算法的安全性分析至今仍是热点。
§ 01序列密码概述
序列密码的历史可以追溯到凯撒密码。凯撒密码是一种单表代替密码，明文、密钥和密文在 \(\mathbb Z_{26}=\{0,1,\cdots,25\}\) 中，
扩展密钥长度就得到多表代替密码：密钥 \(k=(k_1,\cdots,k_d)\)，明文 \(m=(m_1,\cdots,m_n)\)，
\(i>d\) 时循环使用密钥。为了适应软硬件实现，现代序列密码多用模 2 运算。
密钥长度扩展到无穷，就是一次一密。它由 Mauborgne 和 Vernam 于 1917 年发明，Shannon 于 1949 年证明一次一密可以抵抗无限计算能力的唯密文攻击。但一次一密的密钥与明文一样长，生成、存储和使用都不现实。所以设计者设想用尽量少的真随机序列生成尽量长的伪随机序列，用较少的密钥加密大量明文。序列密码的设计思想就脱胎于一次一密。
20 世纪初产生的 LFSR 为序列密码提供了很好的驱动部件：\(n\) 级 LFSR 可以产生最长为 \(2^n-1\) 的序列，密码学性质良好。到了 60 年代，B-M 算法的提出使得把 LFSR 输出直接作为密钥流不再安全，非线性改造加入到流密码设计中。主要的改造方式包括前馈模型和钟控模型，代表密码有蓝牙中的 \(E_0\) 算法和 2G 语音与数据加密的 A5 系列算法。
几次征集计划：
- NESSIE（欧洲，2000—2004）：征集到 42 个算法，6 个序列密码（LEVIATHAN、LILI-128、BMGL、SOBER-t32、SNOW、SOBER-t16）进入第二轮评估，但由于存在安全弱点，最终都被淘汰；
- CRYPTREC（日本，2000—2003）：给出了 3 个序列密码推荐算法 MUGI、MULTI-S01 和 RC4-128；
- eSTREAM（欧洲 ECRYPT，2004 年起）：最终 7 个算法胜出，3 个面向硬件（Grain v1、MICKEY v2、Trivium），4 个面向软件（HC-128、Rabbit、Salsa20/12、SOSEMANUK）。
针对序列密码的攻击主要分为唯密文攻击和已知明文攻击两种。已知明文时，密文与明文模 2 加就得到了密钥流，所以本章只考虑已知明文攻击，即已知密钥流。
§ 02B-M 算法
2.1 线性反馈移位寄存器
线性反馈移位寄存器 (LFSR) 由 \(n\) 个寄存器 \(s_{n-1},\cdots,s_0\) 和 \(n\) 个反馈系数 \(c_{n-1},\cdots,c_0\) 组成，每个寄存器存储一个比特，\(n\) 称为级数。更新是通过移位完成的：记时刻 \(t\) 的状态为 \(s_{n-1}^{(t)},\cdots,s_0^{(t)}\)，则
每个时刻输出 \(s_0\)。
\(n\) 级 LFSR 最多有 \(2^n\) 个状态，除去全 0 状态还剩 \(2^n-1\) 种，所以输出序列的最大周期为 \(2^n-1\)，达到最大周期的输出序列称为 m 序列。m 序列中除全 0 状态外的所有状态出现的概率相同，一个周期中有 \(2^{n-1}\) 个 1 和 \(2^{n-1}-1\) 个 0，\(n\) 较大时这种不平衡可以忽略，所以 m 序列有较好的平衡性。
定义 2.1反馈多项式与特征多项式
\(f(x)=x^n+\sum_{i=0}^{n-1}c_ix^i\) 称为 LFSR 的反馈多项式，其互反多项式 \(g(x)=x^nf(x^{-1})=\sum_{i=1}^nc_{n-i}x^i+1\) 称为特征多项式。若 \(f(x)\) 是生成序列 \(\mathbf a\) 的多项式中级数最小的，称为极小反馈多项式。\(f(x)\) 是本原多项式时，生成的序列有最大周期 \(2^n-1\)，即 m 序列。通常把 \(\langle f(x),n\rangle\) 称作 \(\mathbf a\) 的线性反馈移位寄存器。
例 2.2
7 级 LFSR 的输出序列满足 \(a_k=a_{k-4}\oplus a_{k-7}\)，则反馈多项式为 \(x^7+x^3+1\)，特征多项式为 \(x^7+x^4+1\)。
注
“反馈多项式”和“特征多项式”这两个名字在不同教材里正好可能是反过来的。我这里跟教材一致。真正要记的只有递推关系 \(a_k=\bigoplus c_{n-i}a_{k-i}\)：无论叫什么，B-M 算法输出的 \(f_N(x)=1+c_1x+\cdots+c_lx^l\) 对应的递推都是 \(a_k=c_1a_{k-1}\oplus\cdots\oplus c_la_{k-l}\)。
LFSR 的输出直接存在线性关系，直接作为密钥流是不安全的。若已知级数 \(n\) 和输出序列 \(\mathbf a\)，则
求解这个 \(n\) 元线性方程组就能得到反馈系数，进而恢复密钥流的所有比特。所以已知 \(2n\) 个连续输出比特就能恢复 \(n\) 级 LFSR。这要求已知级数；级数未知时，B-M 算法只需至多 \(2n\) 个连续比特就能恢复反馈多项式和初态。
2.2 B-M 算法
给定长度为 \(N\) 的二元序列 \(\mathbf a\)，Berlekamp-Massey (B-M) 算法的主要思想是不断生成前 \(k\) 个比特的最小生成多项式。记 \(\langle f_k(x),l_k\rangle\) 为前 \(k\) 个比特的最小生成多项式和对应的级数。
定理 2.3算法（B-M 算法）
- 取初始值 \(f_0(x)=1\)，\(l_0=0\)；
-
设已求得 \(\langle f_0(x),l_0\rangle,\cdots,\langle f_k(x),l_k\rangle\)，\(l_0\le l_1\le\cdots\le l_k\)。记 \(f_k(x)=1+c_1^{(k)}x+\cdots+c_{l_k}^{(k)}x^{l_k}\)，计算差值
\[ d_k=a_k+c_1^{(k)}a_{k-1}+\cdots+c_{l_k}^{(k)}a_{k-l_k}. \]- 若 \(d_k=0\)，令 \(f_{k+1}(x)=f_k(x)\)，\(l_{k+1}=l_k\)；
- 若 \(d_k\ne0\)：
- 当 \(l_0=l_1=\cdots=l_k=0\) 时，令 \(f_{k+1}(x)=1+x^{k+1}\)，\(l_{k+1}=k+1\)；
-
否则设 \(m\)（\(0\le m<k\)）使 \(l_m<l_{m+1}=l_{m+2}=\cdots=l_k\)（即最后一次级数增长的位置），令
\[ f_{k+1}(x)=f_k(x)+x^{k-m}f_m(x),\qquad l_{k+1}=\max(l_k,\ k+1-l_k); \]
-
最后得到的 \(\langle f_N(x),l_N\rangle\) 就是产生序列 \(\mathbf a\) 的 LFSR。
\(d_k\) 的意义是：用当前的 \(f_k\) 预测第 \(k\) 个比特，\(d_k=0\) 说明预测正确，不用改；\(d_k\ne0\) 说明预测错了，借助上一次出错时的多项式 \(f_m\) 修正——在 \(f_m\) 出错的位置上 \(f_m\) 的差值也是 \(1\)，把它平移 \(k-m\) 位加上去，正好抵消当前的错误。
例 2.4
设序列 \(a_0a_1\cdots a_6=0011101\)，求其最短线性反馈移位寄存器。
解
- 初始值 \(f_0(x)=1\)，\(l_0=0\)；
- \(a_0=0\)，\(d_0=1\cdot a_0=0\)，所以 \(f_1(x)=1\)，\(l_1=0\)；同理 \(d_1=1\cdot a_1=0\)，\(f_2(x)=1\)，\(l_2=0\)；
-
\(a_2=1\)，\(d_2=1\cdot a_2=1\)，又 \(l_0=l_1=l_2=0\)，所以
\[ f_3(x)=1+x^3,\qquad l_3=3; \] -
\(d_3=1\cdot a_3+1\cdot a_0=1\)。\(l_2<l_3\)，所以 \(m=2\)，
\[ f_4(x)=f_3(x)+x^{3-2}f_2(x)=1+x+x^3,\qquad l_4=\max(3,3+1-3)=3; \] -
\(d_4=a_4+a_3+a_1=1+1+0=0\)，\(f_5=f_4\)，\(l_5=3\)；
- \(d_5=a_5+a_4+a_2=0+1+1=0\)，\(f_6=f_5\)，\(l_6=3\)；
- \(d_6=a_6+a_5+a_3=1+0+1=0\)，\(f_7=f_6\)，\(l_7=3\)。
所以最短 LFSR 为 \(\langle1+x+x^3,3\rangle\)，递推为 \(a_k=a_{k-1}\oplus a_{k-3}\)。序列长度 \(7=2^3-1\)，该序列是 m 序列，\(1+x+x^3\) 为本原多项式。（我用程序跑了一遍 B-M，各步的 \(d_k\)、\(l_k\) 与上面一致，并且用 \(a_k=a_{k-1}\oplus a_{k-3}\) 从 \(001\) 递推出了 \(0011101\)。）
习题 2.5
已知序列 \(a_0a_1\cdots a_{10}=00100011101\)，用 B-M 算法通过编程或手动推导计算其最短线性反馈移位寄存器。
解
逐步计算（我用程序核对过每一步）：
| \(k\) | \(a_k\) | \(d_k\) | \(f_{k+1}(x)\) | \(l_{k+1}\) |
|---|---|---|---|---|
| 0 | 0 | 0 | \(1\) | 0 |
| 1 | 0 | 0 | \(1\) | 0 |
| 2 | 1 | 1 | \(1+x^3\) | 3 |
| 3 | 0 | 0 | \(1+x^3\) | 3 |
| 4 | 0 | 0 | \(1+x^3\) | 3 |
| 5 | 0 | 1 | \(1\) | 3 |
| 6 | 1 | 1 | \(1+x^4\) | 4 |
| 7 | 1 | 1 | \(1+x+x^4\) | 4 |
| 8 | 1 | 0 | \(1+x+x^4\) | 4 |
| 9 | 0 | 1 | \(1+x+x^3+x^4\) | 6 |
| 10 | 1 | 1 | \(1+x^2+x^3+x^4+x^5\) | 6 |
\(k=5\) 这一步值得注意：\(f_6=f_5+x^{5-2}f_2=(1+x^3)+x^3=1\)，多项式“退化”成了 \(1\)，但级数仍记为 \(l_6=\max(3,6-3)=3\)。所以 \(l\) 才是真正的线性复杂度，多项式次数可以小于 \(l\)。
最终最短 LFSR 为 \(\langle1+x^2+x^3+x^4+x^5,\ 6\rangle\)，线性复杂度为 6。递推关系 \(a_k=a_{k-2}\oplus a_{k-3}\oplus a_{k-4}\oplus a_{k-5}\) 对 \(k=6,\cdots,10\) 成立：例如 \(k=6\) 时 \(a_4\oplus a_3\oplus a_2\oplus a_1=0\oplus0\oplus1\oplus0=1=a_6\)。（它对 \(k=5\) 不成立，但级数是 6，前 6 个比特是初态，不需要满足递推。）
在序列密码中，若直接把 \(n\) 级 LFSR 生成的序列作为密钥流，已知连续 \(2n\) 比特就能恢复 LFSR，得到所有密钥流比特。所以需要引入非线性变换，打破 LFSR 输出之间的线性关系。
§ 03相关攻击
相关攻击主要用于分析 LFSR 驱动的密码算法，主要原理是利用密钥流序列与 LFSR 生成的线性序列的相关偏差。
定义 3.1相关性与相关偏差
两个序列 \(\mathbf a=(a_1,\cdots,a_N)\) 和 \(\mathbf b=(b_1,\cdots,b_N)\) 的相关性定义为
即对应比特相等的比例。对应的相关偏差为
注
这里的“相关性”是相等的概率，与第八章的“相关度” \(\mathrm{Cor}=2\Pr-1\) 不同，后者是本章相关偏差的 2 倍。看到“相关”两个字要先确认是哪个定义。
相关偏差为负（相关性小于 \(1/2\)）时，把其中一个序列所有比特取反，相关偏差就为正。相关偏差的绝对值越大，两个序列的相关性越好；若无特殊说明，相关偏差大指的是绝对值大。若密码输出序列与任意线性序列的相关性都为 \(1/2\)（相关偏差为 0），称该密码是相关免疫的。
3.1 布尔函数的线性相关性
\(n\) 元布尔函数 \(f(x)\) 与线性函数 \(L(x)\) 的相关性定义为
\(x=(x_1,\cdots,x_n)\) 也可以看作 \(n\) 比特整数 \(\sum_{i=0}^{n-1}x_{i+1}2^i\)。相关偏差为 \(\epsilon(f,L)=\mathrm{cor}(f,L)-\frac12\)。相关偏差最大值对应的相关性称为该布尔函数的线性相关性。
可以枚举线性函数、统计所有输入下输出相同的个数来求，但计算量较大，可以用 Walsh 谱变换来求。
3.2 Walsh-Hadamard 变换
Walsh-Hadamard 变换（又叫 Walsh 谱变换或 Hadamard 变换）给出一个布尔函数与所有线性函数的线性偏差。
定义 3.2Walsh-Hadamard 变换
\(n\) 元布尔函数 \(f(x)\) 的 Walsh-Hadamard 变换为
变换结果称为 Walsh 谱，表示 \(f(x)\) 与线性函数 \(w\cdot x\) 的逼近程度。
记 \(P(f(x)=w\cdot x)\) 为 \(f(x)\) 与 \(w\cdot x\) 相等的概率，则
定理 3.3平衡函数
布尔函数 \(f(x)\) 是平衡函数当且仅当 \(S_f(0)=0\)。
证明
\(S_f(0)=\frac1{2^n}\sum_x(-1)^{f(x)}=\frac{\#\{f=0\}-\#\{f=1\}}{2^n}\)，为 0 当且仅当 \(f\) 取 0 和取 1 的次数相等。
快速 Walsh 变换。 注意到 \((-1)^{w\cdot x+f(x)}=(-1)^{w\cdot x}\cdot(-1)^{f(x)}\)。把真值表 \(f(x)\) 变换为 \((-1)^{f(x)}\)（0 变为 1，1 变为 \(-1\)），Walsh 变换就相当于对变换后的真值表作（\(\mathbb Z_2^n\) 上的）Fourier 变换，可以用蝶形运算快速计算：
定理 3.4算法（快速 Walsh-Hadamard 变换）
- 对真值表作变换 \(z[i]=(-1)^{f(i)}\)；
-
对 \(k=1,\cdots,n\)，对 \(i=1,\cdots,2^{k-1}\)，对 \(j=1,\cdots,2^{n-k}\)，记 \(p=(i-1)\cdot2^{n-k+1}+j\)，\(q=p+2^{n-k}\)：
\[ t_1=z[p]+z[q],\qquad t_2=z[p]-z[q],\qquad z[p]=t_1,\qquad z[q]=t_2; \] -
\(z[i]=z[i]/2^n\)。
最终得到的 \(z[i]\)（\(0\le i<2^n\)）就是 Walsh 谱，其中的非 0 项代表有效的线性逼近。复杂度为 \(O(n\cdot2^{k-1}\cdot2^{n-k}\cdot2)=O(n\cdot2^n)\)。
例 3.5Walsh 谱变换
3 元函数 \(f(x_1,x_2,x_3)=x_1x_2\oplus x_1x_3\oplus x_2x_3\)（多数函数）的蝶形运算过程：
| \(x_1x_2x_3\) | \(f\) | \((-1)^f\) | \(k=1\) | \(k=2\) | \(k=3\) | \(S_f\) |
|---|---|---|---|---|---|---|
| 000 | 0 | 1 | 2 | 2 | 0 | 0 |
| 001 | 0 | 1 | 0 | \(-2\) | 4 | 1/2 |
| 010 | 0 | 1 | 0 | 2 | 4 | 1/2 |
| 011 | 1 | \(-1\) | \(-2\) | 2 | 0 | 0 |
| 100 | 0 | 1 | 0 | 2 | 4 | 1/2 |
| 101 | 1 | \(-1\) | 2 | 2 | 0 | 0 |
| 110 | 1 | \(-1\) | 2 | \(-2\) | 0 | 0 |
| 111 | 1 | \(-1\) | 0 | 2 | \(-4\) | \(-1/2\) |
由 Walsh 谱，
注
表中 \(k=1,2\) 两列是蝶形运算的中间结果，依赖于每一步把哪两个位置配对，我没有逐格核对；最后一列 \(S_f\) 我用直接按 (5) 求和的程序核对过：非零项恰为 \(w=001,010,100\) 处的 \(1/2\) 和 \(w=111\) 处的 \(-1/2\)。
布尔函数的 Walsh 谱决定了相关攻击能否成功：只有相关偏差不为 0 的线性逼近才能用来做密码攻击。下面的定理保证这样的线性逼近一定存在。
定理 3.6能量守恒定律, Parseval 等式
\(n\) 元布尔函数 \(f(x)\) 的 Walsh 谱 \(S_f(w)\) 满足
证明
内层和 \(\sum_w(-1)^{w\cdot z}\) 在 \(z=0\) 时为 \(2^n\)，否则为 \(0\)（\(z\ne0\) 时有一半的 \(w\) 使 \(w\cdot z=1\)）。所以只剩 \(x=y\) 的项：
推论 3.7
任意 \(n\) 元布尔函数都存在某个 \(w\) 使 \(|S_f(w)|\ge2^{-n/2}\)，即至少有一个相关偏差不小于 \(2^{-n/2-1}\) 的线性逼近。
证明
\(2^n\) 个 \(S_f(w)^2\) 之和为 1，最大的一个至少为平均值 \(2^{-n}\)。
这就是“不存在完美非线性”的原因：非线性只能把能量摊平，不能消除。Walsh 谱绝对值全部相等（\(|S_f(w)|=2^{-n/2}\)）的函数称为 Bent 函数，它是非线性度最高的，但不平衡（\(S_f(0)\ne0\)）。
习题 3.8
设 \(f(x)=x_0x_1x_2\oplus x_2x_3\) 是一个 4 元布尔函数，根据 Walsh-Hadamard 变换，通过编程或手动推导找到所有与其相关偏差不为 0 的线性函数。
解
按 (5) 计算（以 \(w=(w_0w_1w_2w_3)\) 表示线性函数 \(w_0x_0\oplus w_1x_1\oplus w_2x_2\oplus w_3x_3\)，我用程序算的）。\(2^4\cdot S_f(w)\) 的非零值为：
| \(w\) | \(2^4S_f(w)\) | \(S_f(w)\) | 相关偏差 \(S_f/2\) |
|---|---|---|---|
| 0000 | 8 | 1/2 | 1/4 |
| 0001 | 4 | 1/4 | 1/8 |
| 0010 | 8 | 1/2 | 1/4 |
| 0011 | \(-4\) | \(-1/4\) | \(-1/8\) |
| 0101 | 4 | 1/4 | 1/8 |
| 0111 | \(-4\) | \(-1/4\) | \(-1/8\) |
| 1001 | 4 | 1/4 | 1/8 |
| 1011 | \(-4\) | \(-1/4\) | \(-1/8\) |
| 1101 | \(-4\) | \(-1/4\) | \(-1/8\) |
| 1111 | 4 | 1/4 | 1/8 |
所以与 \(f\) 相关偏差不为 0 的线性函数有 \(x_3\)、\(x_2\)、\(x_2\oplus x_3\)、\(x_1\oplus x_3\)、\(x_1\oplus x_2\oplus x_3\)、\(x_0\oplus x_3\)、\(x_0\oplus x_2\oplus x_3\)、\(x_0\oplus x_1\oplus x_3\)、\(x_0\oplus x_1\oplus x_2\oplus x_3\)，以及常数 \(0\)（\(w=0000\)，说明 \(f\) 不平衡，\(\Pr(f=0)=3/4\)）。最好的线性逼近是 \(f\approx x_2\)，相等概率 \(3/4\)。
验证能量守恒：\(\frac{8^2+8^2+8\times4^2}{16^2}=\frac{64+64+128}{256}=1\)。
习题 3.9
给出能量守恒定律的数学证明。
解
见上面定理下的证明。核心是特征和的正交性 \(\sum_w(-1)^{w\cdot z}=2^n\delta_{z,0}\)，与第八章引理用的是同一个工具。
3.3 LFSR 驱动的序列密码的相关攻击
线性序列比特之间存在线性关系，LFSR 的输出直接作为密钥流很容易受到攻击。为了破坏输出序列的线性关系，一种办法是把一个或多个 LFSR 的抽头经过非线性函数（通常也叫滤波函数）得到密钥流序列，这种体制叫做前馈逻辑。
相关攻击的思路是：先找到输出序列与 LFSR 某些抽头线性组合的相关偏差，然后分别穷举相关 LFSR 的初态，得到其生成序列，比较生成序列与密钥流序列的相关性。猜测正确时有明显的相关偏差；猜测错误时则随机耦合，无明显相关性。这样就把对整个密钥的穷举拆成了对各个 LFSR 的分别穷举，是一种分而治之。
设正确猜测下的相关偏差为 \(\epsilon\)，密钥流长度为 \(N\)。一般在 \(t=\epsilon\sqrt N\ge3\) 时，有较高的置信度认为猜测值是正确的解，所以数据复杂度为
具体 \(t\) 的取值根据实际分析中要求的置信度确定。
注
这里的 \(t\) 可以这样理解：错误猜测下，\(N\) 比特中相等的个数近似服从均值 \(N/2\)、标准差 \(\sqrt N/2\) 的正态分布；正确猜测下均值是 \(N/2+\epsilon N\)。两者均值之差以错误分布的标准差为单位是 \(\epsilon N/(\sqrt N/2)=2\epsilon\sqrt N=2t\)。\(t=3\) 就是相差 6 个标准差，和第三章信噪比的思路一样。
例 3.10前馈逻辑的相关攻击
两个 7 级 LFSR 的反馈多项式分别为 \(x^7+x^4+1\) 和 \(x^7+x^3+1\)。第一个 LFSR 的一个抽头作为 \(x_1\)，第二个 LFSR 的两个抽头作为 \(x_2,x_3\)，经过非线性函数
输出密钥流。如何恢复两个 LFSR 的初态？
解
恢复第一个 LFSR。 上面已经算过，对 \(z\) 作 Walsh 谱变换得 \(\mathrm{cor}(z,x_1)=3/4\)，即第一个 LFSR 正确初态产生的序列与密钥流对应比特相等的概率为 \(3/4\)，相关偏差 \(\epsilon=1/4\)。穷举第一个 LFSR 的所有 \(2^7\) 种初态，把产生的序列与密钥流比较：若相等的比例接近 \(3/4\)，就是正确初态；猜错时接近 \(1/2\)。由 \(N=9/\epsilon^2=144\)，约 144 比特密钥流就足够。
恢复第二个 LFSR。 可以用同样的办法穷举第二个 LFSR 的 \(2^7\) 种初态（\(\mathrm{cor}(z,x_2)=3/4\)）。但对这个密码有更高效的办法：观察多数函数，\(x_1=0\) 时 \(z=x_2x_3\)，于是 \(z=1\) 时必有 \(x_2=x_3=1\)；\(x_1=1\) 时 \(z=x_2\oplus x_3\oplus x_2x_3=x_2\vee x_3\)，于是 \(z=0\) 时必有 \(x_2=x_3=0\)。即 \(x_1\ne z\) 时，\(x_2=x_3=z\) 可以直接得到。
已知第一个 LFSR 的初态后，就有它的输出序列 \(x_1\)。把密钥流与 \(x_1\) 比对，在不相等的位置上直接得到第二个 LFSR 对应抽头的比特。这是第二个 LFSR 输出序列的间断序列，每个比特都可以表示成初态比特的线性组合，得到关于 7 个初态比特的线性方程组，求解即可得到初态。只需大约 14 个“不相等”的位置（约 56 比特密钥流），复杂度可以忽略。
总复杂度约 \(2^7+2^7\)，而直接穷举两个 LFSR 的联合初态要 \(2^{14}\)。
习题 3.11
若把上例中的非线性函数改为 \(z(x_1,x_2,x_3)=x_1x_2\oplus x_1x_3\oplus x_2x_3\oplus x_2\oplus x_3\)，仿照上例给出相应的相关攻击步骤说明。
解
Walsh 谱。 我用程序算出新 \(z\) 的 Walsh 谱非零项为
（\(w=w_1w_2w_3\) 对应 \(w_1x_1\oplus w_2x_2\oplus w_3x_3\)。）所以
与原例相比，\(z\) 与 \(x_1\) 的相关偏差变成了 \(-1/4\)。（直观上：加上的 \(x_2\oplus x_3\) 在多数函数 \(=x_1\) 的那些位置上恰好把结果翻转。）
恢复第一个 LFSR。 相关偏差为负，把密钥流取反（或把生成序列取反）后比较：穷举 \(2^7\) 种初态，若生成序列与密钥流不相等的比例接近 \(3/4\)，就是正确初态。\(|\epsilon|=1/4\)，同样约需 144 比特。
恢复第二个 LFSR。 仍可利用 \(x_1\) 已知后的确定关系。新函数为
- \(x_1=0\)：\(z=x_2x_3\oplus x_2\oplus x_3=x_2\vee x_3\)，所以 \(z=0\) 时 \(x_2=x_3=0\)；
- \(x_1=1\)：\(z=x_2\oplus x_3\oplus x_2x_3\oplus x_2\oplus x_3=x_2x_3\)，所以 \(z=1\) 时 \(x_2=x_3=1\)。
即 \(x_1=z\) 的位置上，\(x_2=x_3=z\) 可以直接读出（条件从原例的“\(x_1\ne z\)”变成了“\(x_1=z\)”）。\(\Pr(x_1=z)=1/4\)，与原例中 \(\Pr(x_1\ne z)=1/4\) 相同，所以同样约 56 比特密钥流就能得到足够的线性方程，解出第二个 LFSR 的初态。也可以直接对第二个 LFSR 用 \(\Pr(z=x_2)=3/4\) 再做一次相关攻击。
§ 04小结
- 单个 LFSR 的输出不能直接作为密钥流：已知 \(2n\) 个连续比特，B-M 算法就能恢复它（线性复杂度就是 B-M 输出的级数）。
- 加了非线性滤波后，滤波函数总有非零的 Walsh 谱（能量守恒），也就总存在与某个线性组合的相关性。相关攻击利用这种相关性分别穷举各个 LFSR，把 \(2^{\sum n_i}\) 的穷举降为 \(\sum2^{n_i}\)，数据量约 \(9/\epsilon^2\)。
- 设计上的对策是选择相关免疫阶高、非线性度高的滤波函数，或者改用 NFSR 驱动。下一章的立方攻击针对的就是 Trivium、Grain 这类 NFSR 驱动的算法。
参考：王美琴主编，《密码分析学》，科学出版社，2024，第 11 章。
完
评论