流密码分析方法研究综述

周照存，冯登国

（1.中国科学院软件研究所可信计算与信息保障实验室，北京 100190；2.中国科学院大学，北京 100049）

0 引言

随着云计算、大数据、物联网等的发展和应用，具有快速、安全、轻量等特点的信息处理技术成为信息安全研究的重要需求。密码技术作为信息安全的核心技术，发挥着日益重要的作用。密码算法通常作为信息安全解决方案中的关键基元，其安全性、速率与资源占用等性质关系到整个方案的安全性与适用性。密码分析技术是设计安全、高效、轻量的密码算法中不可或缺的关键技术。

流密码算法是一类重要的对称密码算法，一般具有加解密效率高、实现简单等特点，因此应用广泛。一般来说，流密码算法由一个固定大小的内部状态，以及作用在该状态上的更新函数与输出函数组成。更新函数将前一时序的内部状态更新为下一时序的状态。输出函数则从内部状态中抽取信息以生成用于加解密的密钥流。

相对来说，流密码算法形式更为灵活，其常使用的密码构件有密码逻辑函数、移位寄存器以及常见的基本运算等。从上层结构看，常见的流密码包括线性反馈移位寄存器（LFSR,linear feedback shift register），例如，ZUC 系列[1-2]、SNOW 系列[3-5]算法，还包括非线性反馈移位寄存器（NFSR,nonlinear feedback shift register），例如，Grain 系列[6-10]、Trivium[11]算法。更为详细的流密码分类可以参考文献[12-13]。

传统的流密码通常每个时序产生长为1 bit 至数字节的密钥流。近年来，随着高速数据处理等新需求的出现，部分流密码也采用与分组密码构件组合设计的方式输出更长的密钥流，例如，SNOW-V[5]等算法以AES 轮函数作为构件。从设计思想上看，这些算法与分组密码工作模式之间的边界更加模糊。

正因为流密码所呈现出的灵活多变的形式，流密码的分析方法也体现出多样化、专门化的特点。多样化是指不同分析方法所采用的关键技术与基本思想差异很大；专门化是指有些分析方法利用了流密码算法的特殊设计并对该类型的流密码算法更有效。根据安全模型的不同，可以将这些分析方法分为传统机密性分析和认证加密安全性分析。根据敌手能力的不同，可以分为唯密文分析、已知明文分析、选择明文分析和选择密文分析。根据密钥数量的不同，可以分为单密钥分析和多密钥分析。根据分析对象的不同，可以分为初始化分析、密钥流生成阶段分析和认证码生成阶段分析。根据分析结果的不同，可以分为区分分析和状态（密钥）恢复分析。根据数学工具的不同，可以分为确定性分析和统计性分析。

鉴于此，流密码分析方法的分类也是一个值得研究的课题。文献[14]回顾了部分流密码分析方法，但仅限于线性分析、相关分析方面的一些研究进展讨论，没有进一步阐述分析方法的理论细节。文献[15]将流密码的分析方法分为时间存储数据折中（TMDTD,time-memory data trade-off）类、相关分析类、线性分析类、代数分析类和猜测确定类，并结合具体流密码算法阐述了多种流密码分析方法。本文从主要技术特点的角度对流密码的主要分析方法进行分类研究，将现有的主要流密码分析方法分为基于相关性质的分析方法、基于差分性质的分析方法、基于代数方程组的分析方法和基于时间存储数据折中的分析方法4 种，重点阐述分析方法本身的技术原理、所依赖的性质和相关公开问题，还涵盖了一些新的研究进展。这种分类方法与之前不同，更强调主要技术，有利于研究者把握流密码分析方法之间的区别和联系。例如，线性区分分析与相关分析被归为同一类，因两者都基于线性逼近技术；立方分析则被归为基于差分性质的分析方法，因其与高阶差分/积分分析技术有密切联系，故对利用划分性质改进立方分析显得非常重要；猜测确定分析则被归为基于代数方程组的分析方法，因为该方法实际上是从另一个角度求解代数方程组的。

1 基础知识

1.1 符号

1.2 基本定义

定义1线性反馈移位寄存器。一个LFSR 一般包含l个寄存器单元 (x0,…,xl-1)和线性反馈关系xl=c1xl-1+…+clx0。

LFSR 有2 种实现形式：Fibonacci 形式和Galois形式。2 种不同形式的LFSR 在初态上相差一个线性变换。当反馈关系为非线性时，称之为NFSR。

定义2线性逼近。令Γ和Λ分别表示mbit输入掩码和nbit 输出掩码，一个m入n出的布尔函数f的线性逼近可表示为Λy⊕Γx=e，其中，e表示二元噪声变量。

一般地，当Γ和Λ分别表示 F2上的r×m和r×n矩阵时，称之为多维线性逼近。

定义3相关性与偏差。一个二元随机变量e的相关性定义为cor(e)=Pr(e=0)-Pr(e=1)，偏差则定义为。

线性逼近中的二元变量e的相关性简称为线性相关性。当噪声为向量时，一般采用平方欧几里得不平衡性（SEI,squared Euclidean imbalance）来度量其偏差。

定义4SEI。令e∈表示一个m维的随机向量，定义其概率分布的SEI 为

在研究线性相关性时，常用的一个工具是Walsh 谱。

定义5Walsh-Hadamard 变换（WHT,Walsh-Hadamard transform）。令f:{0,1}n→ℤ 表示一个n变元函数，其WHT 定义为

划分性质是立方分析中常用的概念，比特划分性质如定义6 所示。

2 基于相关性质的分析方法

本节阐述基于线性逼近相关性的流密码分析方法，主要包括线性区分分析和相关分析两类。线性区分分析与相关分析虽然理论方法不同，但都利用流密码算法有限状态自动机（FSW,finite state machine）输入与密钥流之间的线性相关性。这两类方法主要适用于使用LFSR 构件的流密码算法。

2.1 线性区分分析

线性区分分析属于统计分析，其目标是将密钥流序列与随机序列区分开。Coppersmith[18]提出了一种流密码的线性区分分析方法，并应用该方法分析了SNOW 2.0 算法的安全性。该方法利用分组密码中线性掩码传播技术来寻找流密码算法的LFSR 状态与密钥流之间相关性较大的线性逼近关系，基本步骤如算法1 所示。

算法1线性区分分析基本方法

输入密钥流序列

输出区分结果

/*预计算阶段*/

1) 寻找LFSR 状态和密钥流之间相关性较大的线性逼近关系；

2) 寻找一个LFSR 反馈多项式l(x)的低代数次数、低汉明重量倍式g，即g的代数次数不太大且项数很少（根据实际情况，通常取为3 项或4 项）；

3) 利用倍式g和堆积引理，建立关于密钥流的一个线性关系；/*在线阶段*/

4) 利用关于密钥流的线性关系进行区分分析。具体来说，设步骤1)找到的线性逼近关系为

步骤2)中寻找校验式可以归结为k子集和问题[19-21]。假设关于密钥流的线性关系的相关性为cor，根据最优基本区分器的相关结论，步骤4)所需的数据和时间复杂度都为O(cor-2)[16]。

Yang 等[22]应用有限域上的区分分析方法分析了SNOW 3G 算法。F2n上的区分分析与前述方法的原理类似。注意到，相关性cor 由个二元噪声et+k的相关性堆积得到；而应用非二元域上的区分分析时，导出噪声是个非二元噪声之和，故其概率分布由个非二元噪声分布卷积得到。因此，导出噪声的SEI 因卷积损失明显。为减少卷积损失，提高区分能力，要求g(x)的系数都是1，但代价是g(x)的代数次数升高了。

Yang 等[23]又提出有限域Fp上的线性区分分析方法并分析了ZUC-256 算法，提出了谱值重合的启发式技术，以减少噪声卷积损失。

2.2 相关分析

相关分析是一种状态恢复分析，其基本原理是将流密码LFSR 状态恢复问题转化为译码问题：将LFSR 部分看作一个线性码，其中，初态视作信息位；将LFSR 输出序列看作发送的码字；将非线性组合生成器或者带记忆有限状态机看作一个噪声信道。噪声信道一般选取二元对称信道（BSC,binary symmetric channel）。流密码输出的密钥流序列则可以看作所收到的码字，如图1 所示。

图1 快速相关分析的二元信道译码模型

Siegenthaler[24]提出了对非线性组合生成器类型流密码的分别征服相关分析方法。其思想是利用组合函数的输入和输出之间的相关性，穷举搜索并恢复某个（或几个）特定LFSR 的初始状态。这是最早的流密码相关分析方法。在此之后，流密码的相关分析得到了进一步发展，主要包含条件相关分析和快速相关分析两类分析方法。

2.2.1 条件相关分析

本节阐述2 种条件相关分析方法，它们的共同点是利用条件相关性以获得更好的分析效果，区别是条件不同。

1) 基于输入相关性的条件相关分析

Lee 等[25]在Anderson[26]提出的条件相关性思想的基础上，提出了一种条件相关分析方法。这种方法利用在特定输出条件下输入变量的相关性进行密码分析。由于条件相关性通常要比一般相关性更大，该方法可有效分析基于滤波生成器的流密码。该思想又被推广为混合相关分析和浓缩分析[27]。Lee 等提出的条件相关分析方法具体如算法2 所示。

算法2Lee 等提出的条件相关分析方法

2) 基于输出相关性的条件相关分析

Lu 等[28]扩展了条件相关分析方法。该方法利用在部分输入未知且均匀随机的条件下，任意一个函数输出的条件相关性进行密码分析。这种条件相关性是前述输入条件相关性的反向推广，适用于敌手不仅可以看到密钥流，还可以访问由密钥部分控制的不确定的计算过程的场景。Zhang等[29]进一步推广了计算条件相关性的函数。Lu 等提出的方法的原理如下。

区分器。猜测2L个所有可能的密钥值，对于每一个猜测值K，设一个权重G(K)，其初值置0。对于n个样本，累计计算

以使G(K)最大的猜测值K作为正确密钥候选值。

2.2.2 快速相关分析

快速相关分析是一类非常重要的流密码分析方法。Meier 等[30]提出快速相关分析方法，以改进分别征服相关分析中复杂度与LFSR 长度呈指数关系的缺点。按照译码方式的不同，快速相关分析主要可以分为基于概率迭代译码的快速相关分析和基于硬判定译码的快速相关分析。

1) 基于概率迭代译码的快速相关分析

Meier 等[30]提出的译码算法（算法B）是一种概率迭代译码算法，如算法3 所示。译码算法的输入是一段长为N的连续密钥流z t=xt⊕et。若成功译码，则算法的输出为xt。

算法3概率迭代译码算法

算法3 中，概率阈值pth和个数阈值Nw需要根据初始错误率p、奇偶校验式成立的个数以及奇偶校验式抽头的个数由正态分布导出。后验概率p*可根据贝叶斯公式导出，主要依据为：对于某个位置0≤t≤N，若观察到较多的校验式为0，那么p*应当增大。

Johansson 等[31-32]基于卷积码理论改进了译码方法。与之前方法相比，改进方法的校验式更容易生成。Canteaut 等[33]将LDPC 码的译码方法应用到快速相关分析中，以使用汉明重量为4 或5 的校验式。Golic[34]提出了将编码理论中最优的逐符号译码算法H-R 算法应用于快速相关分析，该方法可以利用非正交的校验等式。虽然理论上概率迭代译码的快速相关分析的译码能力更接近香农界，但基于此类译码方法的快速相关分析通常难刻画精确可靠的复杂度，因而很少应用于分析现实世界中的流密码算法。Zhou 等[35]将二元迭代译码算法推广至向量迭代译码算法，并分析了其部分理论复杂度。

2) 基于硬判定译码的快速相关分析

Chepyzhov 等[36]提出了一种基于信息集译码的快速相关分析方法。该方法通过折叠噪声来分析时间存储数据折中的复杂度，主要优势在于能够给出可靠的复杂度和成功概率理论估计。Johansson 等[37]提出了通过重建多项式的方法来进行快速相关分析，其基本原理与信息集译码方法相似，恢复对象由内部状态变为多项式。Mihaljevi 等[38]进一步提出可以用列表译码的方法进行快速相关分析。

Chose 等[39]提出通过构造关于密钥流数据的公开函数，并在预计算阶段对其进行FWHT，避免校验式求值过程中的冗余计算。该方法大大提高了快速相关分析的效率，使快速相关分析成为分析基于LFSR 的流密码最重要的方法之一。下面，阐述基于信息集译码和FWHT 技术加速的快速相关分析的基本原理，如算法4 所示。

算法4基于信息集译码和FWHT 技术加速的快速相关分析

在线阶段根据构造译码函数w(x)，并计算Walsh 谱(s)。因为Walsh 谱实际上表示经验相关性，且当猜测值正确时，经验相关性绝对值可能更大，故以最大的s作为s(0)的l′bit。

算法4 的复杂度主要受步骤2)～步骤4)的影响，译码所需的校验式个数M受码率不超过信道容量的限制。借助于FWHT 加速，步骤3)和步骤4)所需复杂度由原来的O(M2l′)降为O(M+l′2l′)。

在预计算阶段，一般可以通过寻找线性路径的方式建立LFSR 状态和密钥流之间的高相关性线性逼近关系。线性路径中线性掩码的传播与分组密码线性分析类似。因此，可以通过专门化算法或建立并求解自动化搜索模型的方式解决。

基于信息集译码快速相关分析方法已经很成熟，目前，研究者往往更专注在具体流密码中的应用。Zhang等[40]将前述快速相关分析的方法推广到利用有限域上的线性逼近，改进了对SNOW 2.0 算法的分析结果。Shi 等[41]使用SMT/SAT 模型搜索了SNOW-V的高相关性线性逼近，并改进了快速相关分析结果。

Todo 等[42]提出快速相关分析方法，优势是可以同时降低时间和数据复杂度。该方法主要出发点是观察到 F2m上线性掩码的乘法具备特殊交换性质。因此，在快速相关分析中可以考虑恢复中间状态而非初态，如算法5 所示。

算法5Todo 等提出的快速相关分析方法

输入密钥流序列

输出LFSR 初态

/*预计算阶段*/

1) 寻找LFSR 状态和密钥流之间的多个高相关性且密钥流掩码相同的线性逼近关系；

/*在线阶段*/

2) 绕过βbit，构造关于密钥流的公开函数；

3) 计算公开函数的Walsh 谱，保留所有的经验相关性大于某一阈值corth的中间状态；

4) 对于步骤3)保留的每个中间状态，尝试恢复正确的LFSR 初态。

具体来说，设步骤1)中共找到m个相关性为cor(e) 的线性逼近，步骤2)构造关于剩余(l-β)bit中间状态的译码函数并计算Walsh 谱，该过程与算法4 类似。记 ∈1和 ∈2分别表示正确和错误中间状态相关性大于阈值corth的概率并设2 种状态分别服从参数为λ1≈m2-β∈1和λ2≈m2-β∈2的泊松分布，只要λ1相比λ2较小，就可以筛选出正确初态。当N≈ (l-β) 2l-β≈m2l-β∈1时，时间复杂度为O(3(l-β) 2l-β)，数据复杂度为O((l-β) 2l-β)。

在预计算阶段，同样可以通过建立并求解自动化搜索模型的方式寻找所需的线性逼近。特别地，当有限状态自动机由NFSR 和滤波函数组成时，可以采用分析NFSR 更新函数和滤波函数Walsh 谱的方式，例如，Grain 系列算法。

此后，Wang 等[43]又证明了当有多条线性逼近时，校验式个数下界为。这意味着当线性逼近较多时，所需的数据量更少。

2.3 小结

线性区分分析与相关分析都是针对密钥流生成阶段的分析方法。这类分析方法主要适用于基于LFSR 的流密码算法。特别地，Todo 等[42]提出的快速相关分析方法适用于可以找到很多高相关性线性逼近关系，且不能够折叠噪声的情况。虽然大部分公开研究结果都是针对同步流密码的，但是该类分析方法建立在对数据的统计分析基础上，故理论上它们也适用于自同步流密码算法。在此情况下，线性掩码的传播应当同时考虑明文和密钥流。

与线性区分分析相比，快速相关分析需要考虑校验式快速求值问题，因此如何结合FWHT 或FFT加速是分析的重要一环。这就要求所构造的译码函数谱值具有明确的现实意义。在非二元相关性质的快速相关分析中，这是一项具有挑战性的工作。

线性区分分析、条件相关分析、快速相关分析的一些典型分析应用如表1 所示。值得注意的是，文献[42]中提出的快速相关分析方法也可以应用于分析Plantlet 等类Grain 轻量化流密码算法，但是复杂度折中关系有差别[43]，本文不再一一列举。

对于基于相关性质的流密码分析方法，降低FSM 的输入输出相关性是一种有效的防护手段，在设计阶段就可以通过自动化搜索或人工推导的方式来分析最优化线性路径（逼近）的相关性。另外，增大LFSR 的规模也是一种很有效的抵抗此类分析方法的防护手段。

基于信息集译码的快速相关分析技术目前已经较为完善，但几种条件相关分析应用局限性较强。如何改进条件相关分析方法以应用于分析现代流密码算法也是一个值得研究的具体课题。

基于相关性质流密码分析方法的特点如表2所示。

表2 基于相关性质流密码分析方法的特点

3 基于差分性质的分析方法

本节阐述基于差分性质的流密码分析方法，主要包括碰撞分析和立方分析。这两类方法主要适用于分析流密码算法的初始化过程或者认证流密码算法的认证码生成过程。

3.1 碰撞分析

3.1.1 差分分析

由于流密码的初始化过程类似于分组密码的轮迭代，因此可以采用分组密码的差分分析思想分析流密码的初始化过程。对于流密码，可利用初始向量（IV,initialization vector）对之间的输入差分与密钥生成阶段的输出差分性质构造区分器。文献[45]中研究了一般的（密钥，IV）差分对的差分特征，即(ΔK,ΔIV) →Δs。这种分析方法在原理上与分组密码的差分分析类似，本文不再展开阐述。

2007 年以后，差分分析方法的基本思想得到了推广，派生出选择IV 分析方法[46-48]。通过选择IV的一个比特子集，并固定这个子集之外的IV 变量和密钥变量，然后遍历该子集变量的所有可能取值，得到对应的所有的密钥流输出。这等效于生成以该子集变量为输入，以一个密钥流符号为输出的布尔函数真值表，并试图发现该函数的一些统计弱点。这种一般化的选择IV 分析方法已经接近于后面将阐述的立方分析方法。

3.1.2 滑动分析

滑动分析基本思想源于分组密码滑动密钥分析。Biryukov 等[49]提出了滑动密钥分析，主要适用于分析轮对称性强的迭代型分组密码，随后被用于分析流密码算法初始化过程。滑动分析是一种多密钥分析，其基本思想是寻找一个密钥和初始向量对(K,IV)，经过初始过程的数轮迭代后，流密码算法的内部状态恰好是另一对(K′,IV′)对应的初态，然后通过这种对称性质恢复出K或K′。该方法与流密码算法的初始化轮数没有关系，主要利用部分流密码算法初始化过程中的对称性。

3.1.3 近似碰撞分析

Zhang 等[50]提出了近似碰撞分析，并用于分析Grain-v1 算法。动机是观察到该算法NFSR 和LFSR等长且LFSR 独立更新，若2 个时刻的内部状态仅相差很小，那么输出的密钥流片段彼此近似。根据近似生日碰撞原理，只要密钥流足够长，就可以找到内部状态上的近似碰撞。根据密钥流差分，检测出内部状态上的近似碰撞可以用于恢复LFSR 状态。近似碰撞分析与时间存储数据折中分析有较密切的关联。下面，介绍其基本模型。

预计算阶段主要建立一些结构性的差分表。首先，穷举所有的汉明重量较小的内部状态差分，计算对应的所有密钥流差分。然后，为每个可能的密钥流差分建立一个表。每个表包含了所有可能产生该密钥流差分的内部状态差分，并将表中的内部状态差分按照所占比例进行排序。

在线阶段根据密钥流和预计算表提取内部状态的差分信息。因为LFSR 独立更新，一旦得到正确的内部状态差分，就可以得到LFSR 内部状态。

文献[50]还提出使用BSW 采样技术改进近似碰撞。随后Zhang 等[51]又对近似碰撞分析进行了改进，移除之前需要的假设，并将全状态的近似碰撞转换为部分状态的近似碰撞。

3.2 立方分析

立方分析最早由Dinur 等[52]提出，是高阶差分分析的一种扩展，适用于更新函数代数次数较低的流密码算法。立方分析比较特殊，既可以是密钥恢复分析，也可以是区分分析。本节主要阐述传统立方分析、动态立方分析、基于划分性质的立方分析和条件立方分析。

3.2.1 传统立方分析

立方分析将初始化过程看作输入为初始变量v和密钥变量x、输出为第一比特密钥流z的一个布尔函数z=f(x,v)。其后计算f的高阶差分得到简化的多项式，并用于恢复密钥或者建立区分器。具体来说，令f=t I pI⊕q，其中，I是v下标索引的子集，tI是仅包含公开变量的单项式，pI不包含vi∈I中任何变量且q不能被tI整除。因此可得。一般将vi∈I中的变量称为立方变量，其余公开变量称为非立方变量。所有可能的立方赋值的集合CI称为d维立方，pI称为CI在f中的超级多项式。

立方分析包括预处理阶段和在线阶段。预处理阶段找到可以得到低次超级多项式的立方，并由此恢复出超级多项式。在线阶段通过询问加密预言机得到z，再通过解低次方程组恢复一些密钥变量。

立方分析中有2 个重要问题，一是选择合适的立方，二是测试超级多项式的线性或恢复超级多项式。对于后者，当攻击者把算法看作一个黑盒多项式时，在预处理阶段，可以使用随机测试法来确定给定的立方集超级多项式是否为线性并恢复超级多项式。

立方分析还可以用于区分流密码算法和随机函数，此时一般称为立方检验[53-54]。立方检验将v分成互补的两部分，即立方变量（CV）和超级多项式变量（SV）。通过选取特定的CV 和SV，检验超级多项式的性质，实现区分分析。常见的可用于立方检验的超级多项式性质有平衡性、常数函数、低次数、线性变量的存在性和变量退化等。

3.2.2 动态立方分析

Dinur 等[55]提出了动态立方分析。类似于立方分析，动态立方分析也是对立方变量遍历之后的输出结果求和。在立方分析和立方检验中，立方变量之外的所有公开变量设定为固定值，因此可称为静态变量；在动态立方分析中，某些非立方变量的值不是固定的，而是由定义在公开变量和秘密变量上的函数决定，称为动态变量。通常选取那些可以保持某些状态比特为0 的函数，从而放大立方检验的非随机性。显然，动态立方分析是立方检验的推广和优化，攻击者能够直接推导密钥信息，不需要求解代数方程组。此外，选取适当的动态变量能够降低立方检验的时间复杂度（通常动态立方检验所需立方集的规模更小）。动态立方分析需要建立在对内部状态进行更加复杂的分析的基础上，基本原理如下。

3.2.3 基于划分性质的立方分析

划分性质是Todo[17]提出的一种寻找分组密码高阶差分（积分）特征的新技术。随后，基于比特级的划分性质被提出并应用于多个算法的分析中[56]。文献[56-58]提出了划分性质的一些传播法则。自立方分析提出以来，立方的大小一直受实验限制。这种情况一直到Todo 等[57]提出利用划分性质分析代数正规型的系数来恢复超级多项式的方法后才得到改观。计算划分性质的传播并不容易，Xiang 等[58]通过混合整数线性规划（MILP,mixed-integer linear programming）有效地计算了划分性质的传播。

算法6基于MILP 估计超级多项式中的秘密变量

利用算法 6 分析超级多项式可知，只有x j(j∈J)与立方集CI对应的超级多项式有关。攻击者选择IV 的常数部分为某一固定常数并得到一个立方集CI，随后通过组合所有可能的秘密变量来恢复超级多项式，其时间复杂度为O(2|I|+|J|)。

Wang 等[59]提出了Flag 技术，进一步改进了立方分析MILP 模型的精确性。改进的模型能够识别那些可得到非常数超级多项式的非立方变量赋值。同时，还改进了对于超级多项式项数的估计。Wang 等[60]采用三子集可分性的概念改进了求超级多项式的算法，并降低了时间复杂度。Hao等[61]提出了基于完善的三子集的多重集合的可分性定义，使MILP 模型在计算超级多项式时更准确，同时也回答了如何准确恢复超级多项式的问题。Sun[62]回答了如何搜索好的立方的问题，并给出了启发式的自动化搜索算法。所谓好的立方是指其对应的超级多项式至少有一个平衡的秘密变量。同时，Sun 基于此算法改进了Hao 等对Trivium 算法的分析结果。目前，基于划分性质的立方分析是一个研究热点。

3.2.4 条件立方分析

Huang 等[63]提出了条件立方分析。条件立方分析一般针对基于Sponge 结构的Keccak-MAC 及类似密码算法。该方法受动态立方分析方法的启发，试图通过增加对IV的条件来降低立方变量多项式的次数。这种技术与消息修改技术[64]和条件差分分析[65]有类似之处，也是通过一些比特条件来控制差分传播。基于这些条件的立方测试器一般被称为条件立方测试器。Li 等[66]推广了此方法并用于Ascon 认证加密算法的分析。下面，简单阐述Li 等的方法。

假设一个类Keccak-MAC 算法一次输出lbit。每1 bit 输出可以写成秘密变量和公开变量的布尔函数f i(x,v)，0≤i＜l。选择一个公共立方CI，将fi重写为f i=t I Pi+Qi。在条件立方分析中，寻找多项式Pi的公因子，即，因此，当立方求和后得到。如果公因式g的形式足够简单，如g=x0，则可以采用立方测试器确定x0。

3.3 小结

本节所阐述的基于差分性质的分析方法都是分析流密码算法初始化过程，因而对于自同步流密码也适用。差分分析是一种一般化的分析方法，对初始化过程扩散混淆性质较弱的流密码效果较好。滑动分析则仅适用于初始化迭代对称性强的流密码算法。近似碰撞分析则适用于具有紧凑的NFSR-LFSR 型流密码算法。立方分析针对初始化阶段的代数性质，目标是构造立方区分器和恢复密钥。目前，立方攻击主要适用于更新函数简单的轻量级流密码。而基于字的流密码一般采用代数次数和扩散性较强的更新函数，因而，立方分析应用较少。表3 列出了基于差分性质分析方法的部分典型应用。

表3 基于差分性质分析方法的部分典型应用

对于差分分析、滑动分析的防护设计已经较为成熟，通过增强更新函数密码性质、引入初态常数可以较为有效地抵抗此类分析。由于近似碰撞分析与时间存储数据折中分析有关联，且利用了密钥流差分与内部状态差分之间的近似性，因此合理地增大出口函数规模和内部状态规模（含轮密钥）可以增强近似碰撞分析的安全性。

值得注意的是，立方分析与MILP 方法结合后突破了之前仅能使用小立方集的限制，实现了更大的立方集搜索和更多轮数的区分器。一方面，尽管更复杂的更新函数和更多的初始化轮数有助于抵抗立方分析，但在公开轻量级流密码设计中，更新函数和初始化轮数是需要平衡的重要设计指标。另一方面，近年来，立方分析技术在不断进步。因此，立方分析在轻量级流密码的分析与设计中还将会发挥很大作用，并不断发展。

表4 简单总结了基于差分性质流密码分析方法的特点。各种立方分析的基本思想类似，但技术细节有所不同。

表4 基于差分性质流密码分析方法的特点

4 基于代数方程组的分析方法

本节阐述基于代数方程组的流密码分析方法。该类分析方法都是通过求解代数方程组来恢复内部状态，但求解策略有所不同。一种方式是猜测可能的原象，根据函数值验证正确性，即猜测确定分析；另一种方式是通过数学理论求解方程组得到原象，即代数分析。

4.1 猜测确定分析

Knudsen等[70]在分析RC4时提出了猜测确定分析的思想。Pasalic[71]提出了针对过滤生成器的猜测确定分析方法。

猜测确定分析的基本思想是将流密码内部状态划分为2 个集合：猜测集合和确定集合。攻击者穷举猜测集合状态可能值，然后利用该部分内部状态值来求得确定集合内部状态。最后，攻击者还需将算法输出和密钥流进行比较，以检验猜测的正确性。因此，猜测确定分析的目标是寻找更小的猜测集，并以较少的复杂度来得到确定集合状态。

Feng 等[72]利用猜测确定方法分析了SOSEMANUK。根据SOSEMANUK 特殊的反馈多项式，改进为面向字节而非32 bit 字的猜测确定分析。Yang 等[73]提出了D 方程技术以改进猜测确定路径，并改进了对SNOW-V 算法的分析结果。下面，简单阐述其基本原理。

一条猜测路径是指所有有序的猜测并由此确定的变量元组。如果能够以合理的顺序猜测这些变量，则有可能猜测量更少或者截断那些包含了不能满足中间代数方程的已知猜测值。在猜测确定的中间过程中，如果要求所有的解都要满足一些限定条件或者方程，则可以利用一些特殊的枚举方法（如递归枚举算法等）来代替直接的循环穷举。

接下来，举例说明Yang 等利用D 方程截断猜测路径的技术。令A=B(C⊕X)(X⊕D)表示第一类D 方程。设A,B,C,D是nbit 变量且服从均匀分布，而X的值未知。首先，计算出X的解数量分布表。设上述D 方程存在解的概率为2-r，那么对于所有可能的猜测值A,B,C,D组合，平均只有|(A,B,C,D) |2-r个组合是合法的。由此，就可以在中间过程中去掉不合法的猜测组合，而不必遍历并验证(A,B,C,D)所有可能值。

4.2 代数分析

代数分析最初应用于公钥和分组密码中。Courtois 等[74]将其应用于分析流密码Toyocrypt 和LILI-128。传统代数分析的基本思想是将流密码视作多变元函数，建立关于内部状态和密钥流之间的超定非线性方程组，再通过求解代数方程组的数学技术来恢复内部状态。例如

其中，A表示LFSR 的更新变换。代数分析中建立并求解大规模非线性方程组的复杂度通常较大。

在求解代数方程组方面，目前的方法主要有Gröbner 基法[75]、再线性化法[76]、XL（extensible language）法[76]、XSL（extensible style sheet language）法[77]等。代数次数是非线性方程组求解中的重要影响因素。注意到，将布尔函数f与另一个合理选择的布尔函数g相乘，有可能大大降低f的代数次数。文献[78]将其概括为代数免疫度的概念。对于变量数量较多的一般布尔函数，目前仍无有效的代数免疫度计算方法。布尔函数的代数免疫性质是代数分析中需要进一步研究的课题。

另外一个研究课题是如何建立并使用低次数多变元非线性方程组。不同的代数分析方法使用的代数方程类型一般不同，获得方程的技术也有所差别。下面，本节简单阐述一种使用双层甲板方程的快速代数分析的原理[74]。该方法可利用如下形式的代数方程

其中，L是关于密钥的代数次数小于或等于d次的多项式，R是关于密钥和密钥流比特的多项式，满足每项中密钥变量的代数次数不超过d，密钥流变量的代数次数不超过2。快速代数分析需在预计算阶段生成约个此类方程。当密钥流连续（或等间隔）且LFSR 是周期的时，前述代数方程即可按时序t迭代下去，以生成更多的方程。

以上过程中，B-M 算法的时间复杂度为O(SlbS+Sn)，求解代数方程组的复杂度则由具体求解算法给出。

Armknecht[79]证明了预计算过程的合理性，并改进了预计算方法。Braeken 等[80]提出概率代数分析方法，允许方程以低于1 的概率成立，但仅考虑了概率代数分析的应用可能性。如何求解大规模概率非线性方程组仍然是个公开问题。

4.3 小结

猜测确定分析是一类一般化的流密码分析方法，可以应用于分析不同类型的流密码。快速代数分析方法主要适用于滤波函数型流密码算法，或者FSM 中记忆单元很少的流密码算法。相比于代数分析，快速代数分析改进了代数方程的生成方式，但是对密钥流的要求提高了。

表5 给出了基于差分性质分析方法的部分典型应用。

表5 基于差分性质分析方法的部分典型应用

公开流密码算法在设计上一般采用较大的状态，并结合自动化搜索等方式评估内部状态之间的依赖性，以提高抵抗猜测确定分析的能力。而增强FSM更新函数的性质（如代数次数）并结合较大规模的FSM 状态，可增强抵抗代数分析类方法的能力。

目前，猜测确定分析最优猜测集的选取是一个值得研究的课题。近年来，采用自动化搜索技术（如MILP 建模）搜索最优猜测集的技术发展很快，往往可以获得更优更精细的结果。对于现代流密码来说，单纯地猜测确定分析、代数分析的分析效果可能不能令人满意，但这些技术与其他分析方法结合使用有可能得到更好的分析结果。这是代数分析和猜测确定分析中一个值得研究的课题。

表6 简单总结了基于代数方程组流密码分析方法的特点。

表6 基于代数方程组流密码分析方法的特点

5 基于时间存储数据折中的分析方法

时间存储数据折中分析方法最早由Hellman[82]提出并应用于分析分组密码算法。随后Biryukov 等[83]将此方法用于分析流密码，也称为BSW 时间存储数据折中分析，其基本原理如下。

令N表示内部状态大小，P表示预计算阶段时间，M表示存储空间大小，T表示在线阶段时间，D表示数据量大小，fi表示从内部状态到密钥流前缀的函数，目标是建立一个离线表以尽可能大地覆盖内部状态空间。因为对于流密码算法，部分重叠的密钥流前缀并不意味着内部状态也相邻，所以可以把内部状态看作随机点。如果D个前缀中有一个可以在离线表中找到，则可以回溯表中的那条链以恢复内部状态。因此，离线表需要覆盖的空间大小变为。同时，若Hellman 时间存储数据折中离线表中包含t个m×t的矩阵，且满足生日终止规则mt2=N，在TMDTO 中，矩阵大小不变，但数量变为，因此仍然满足mt2=N。由于每个矩阵大小仍然为m×t，但数量减少了，因此存储空间大小降低为，预计算的时间也降低为。根据生日终止规则，可以得到新的折中曲线TM2D2=N2。

为了避免在线阶段频繁查询离线表，在TMDTO 方法中引入特殊点技术，即只有迭代生成特殊点时才查询离线表，但折中曲线仍然不变。同时，可以采用BSW 采样技术，使T的选择更加灵活[84]。BSW 采样的基本思想是在很多流密码中，在输出下一比特密钥流前，内部状态更新有限。因此，就可以找到所有的能够生成kbit 全0 密钥流的特殊状态。若流密码内部状态大小为N=2n，即内部状态共nbit，则称每个特殊状态有一个(n-k)bit 的缩略名。由此可以导出一个从内部状态到密钥流的随机映射，此时折中曲线仍然不变。

Maitra 等[85]提出可以通过固定一些比特以更容易地得到特殊状态，并可以通过密钥流导出部分内部状态值，但是该方法会增加数据量。

相比其他分析方法，时间存储数据折中分析方法是一类一般化的分析方法，它将流密码算法看作一个黑盒，并不注重算法逻辑。该分析方法的复杂度度量单位可以是一次加密，因而受算法的工作效率影响很大。

时间存储数据折中分析方法的典型应用包括对轻量级算法Sprout、Lizard 等的分析，如表7 所示。值得注意的是，对于Sprout 算法的分析，尽管该算法采用了2 种状态：内部状态和密钥状态，但是仍然不能抵抗TMDTO 分析。

表7 基于时间存储数据折中分析方法的部分典型应用

为了防护TMDTO 分析，公开非轻量流密码算法一般遵循“内部状态大小至少是密钥长度的2 倍”准则。

虽然Sprout 算法不能抵抗TMDTO 分析，但后来设计的一些小状态轻量级流密码算法吸取有关设计经验，采用了一些特殊的设计，也声称具有良好的抵抗TMDTO 分析的效果。这类算法的分析是一个值得思考的问题。

表8 总结了基于时间存储数据折中的流密码分析方法的特点。

表8 基于时间存储数据折中的流密码分析方法的特点

6 未来研究展望

流密码分析方法已经历了几十年的发展，至今仍在不断更新完善。回顾其发展历程，注意到近年来的流密码分析方法研究呈现出一些特点。这些特点可能会进一步影响未来一段时间流密码分析方法的发展。

1) 寻找新的密码性质，改进流密码分析方法。从流密码分析方法发展过程中可以发现，每当有可利用的新性质时，流密码的分析方法都会快速发展。因此，寻找新的密码性质，改进流密码分析方法仍然是重要的研究方向。例如，Todo等[42]发现了线性掩码在限域上的交换性，并利用这种性质提出了一种新的快速相关分析方法。这类研究需要建立在对流密码分析方法深刻理解和细致观察的基础上。

2) 发掘不同密码分析技术之间的关联性，改进流密码分析方法。不同的密码分析方法采用不同技术对同一密码算法进行分析，这些分析方法之间可能存在联系。这种联系已经在分组密码分析方法中被发现，并得到了大量研究，例如，分组密码不可能差分分析、积分分析、零相关分析等方法之间的联系。在流密码分析中的一个典型例子是立方分析。一方面，自立方分析提出后，立方分析主要受限于实验规模对立方大小的限制[52]。另一方面，Todo[17]提出了针对分组密码的基于划分性质的广义积分分析，随后Xiang 等[58]提出了划分迹的概念并将MILP技术引入划分性质的传播评估中。注意到，立方分析与积分分析技术具有密切联系，Todo 等[57]将划分性质引入立方分析中，并结合MILP 技术用于恢复超级多项式。这是立方分析的一个里程碑式的发展。因此，发掘不同密码分析技术之间的关联性，对于改进现有流密码分析方法具有重要作用。这可能是流密码分析的一个突破方向。

3) 改进自动化搜索建模技术，提高流密码分析效果。目前，将流密码分析中的问题转化为MILP模型或SAT/SMT 模型，寻求高质量解的技术在流密码分析中的应用越来越广泛。例如，应用于相关分析中寻找好的线性逼近关系[87]，应用于立方分析中恢复超级多项式[57]，应用于猜测确定分析中寻找好的猜测集[88]等，同时密码分析中的需求也促进了MILP 建模技术的发展[89]。可以说，流密码分析方法与自动化分析技术结合越来越紧密。目前，一般通过约束关系刻画具体流密码算法中运算环节的密码性质的方式建立模型。例如，刻画S 盒的线性逼近分布表。因此，建立更加精确的自动化模型，优化已有的分析方法仍然是一个值得研究的方向。

4) 组合使用多种流密码分析技术。近年来，有些流密码的分析已不再局限于单一方法，往往在一个算法的分析中组合使用多种分析技术。例如，猜测确定分析与线性分析和中间相遇的组合使用[90]、中间相遇与立方分析的结合[91]等。

5) 探索建立关于流密码分析方法更深刻的理论。Beyne[92]提出了线性分析的几何方法理论。该理论给出了常见的分组密码线性分析技术及其变体的统一描述，例如，一般线性分析、多维线性分析、不变子空间分析、非线性不变量分析等分析方法和技术。这种数学化的刻画对深刻认识线性分析的基础和不同分析方法之间的内在联系具有重要作用。一些流密码分析技术与分组密码分析技术之间具有密切的联系。建立类似的理论也将是流密码分析方法发展过程中的重要进展。

综上所述，流密码分析方法方面还有很多值得研究的方向[93-95]。未来，还需要研究者不断加深对流密码分析的认识，以创新流密码分析方法。

7 结束语

研究流密码分析方法不仅可以促进密码分析技术的进步，对设计安全、高效的流密码算法也具有重要的指导价值。流密码分析方法种类多，差异明显。本文对目前常见的流密码分析方法按照技术特点的不同进行了分类汇总，并阐述了4 大类10余种流密码分析方法的基本原理、主要技术以及研究进展。同时，也对流密码分析方法进行了展望。