周照存，馮登國(guó)

（1.中國(guó)科學(xué)院軟件研究所可信計(jì)算與信息保障實(shí)驗(yàn)室，北京 100190；2.中國(guó)科學(xué)院大學(xué)，北京 100049）

0 引言

隨著云計(jì)算、大數(shù)據(jù)、物聯(lián)網(wǎng)等的發(fā)展和應(yīng)用，具有快速、安全、輕量等特點(diǎn)的信息處理技術(shù)成為信息安全研究的重要需求。密碼技術(shù)作為信息安全的核心技術(shù)，發(fā)揮著日益重要的作用。密碼算法通常作為信息安全解決方案中的關(guān)鍵基元，其安全性、速率與資源占用等性質(zhì)關(guān)系到整個(gè)方案的安全性與適用性。密碼分析技術(shù)是設(shè)計(jì)安全、高效、輕量的密碼算法中不可或缺的關(guān)鍵技術(shù)。

流密碼算法是一類重要的對(duì)稱密碼算法，一般具有加解密效率高、實(shí)現(xiàn)簡(jiǎn)單等特點(diǎn)，因此應(yīng)用廣泛。一般來(lái)說(shuō)，流密碼算法由一個(gè)固定大小的內(nèi)部狀態(tài)，以及作用在該狀態(tài)上的更新函數(shù)與輸出函數(shù)組成。更新函數(shù)將前一時(shí)序的內(nèi)部狀態(tài)更新為下一時(shí)序的狀態(tài)。輸出函數(shù)則從內(nèi)部狀態(tài)中抽取信息以生成用于加解密的密鑰流。

相對(duì)來(lái)說(shuō)，流密碼算法形式更為靈活，其常使用的密碼構(gòu)件有密碼邏輯函數(shù)、移位寄存器以及常見的基本運(yùn)算等。從上層結(jié)構(gòu)看，常見的流密碼包括線性反饋移位寄存器（LFSR,linear feedback shift register），例如，ZUC 系列[1-2]、SNOW 系列[3-5]算法，還包括非線性反饋移位寄存器（NFSR,nonlinear feedback shift register），例如，Grain 系列[6-10]、Trivium[11]算法。更為詳細(xì)的流密碼分類可以參考文獻(xiàn)[12-13]。

傳統(tǒng)的流密碼通常每個(gè)時(shí)序產(chǎn)生長(zhǎng)為1 bit 至數(shù)字節(jié)的密鑰流。近年來(lái)，隨著高速數(shù)據(jù)處理等新需求的出現(xiàn)，部分流密碼也采用與分組密碼構(gòu)件組合設(shè)計(jì)的方式輸出更長(zhǎng)的密鑰流，例如，SNOW-V[5]等算法以AES 輪函數(shù)作為構(gòu)件。從設(shè)計(jì)思想上看，這些算法與分組密碼工作模式之間的邊界更加模糊。

正因?yàn)榱髅艽a所呈現(xiàn)出的靈活多變的形式，流密碼的分析方法也體現(xiàn)出多樣化、專門化的特點(diǎn)。多樣化是指不同分析方法所采用的關(guān)鍵技術(shù)與基本思想差異很大；專門化是指有些分析方法利用了流密碼算法的特殊設(shè)計(jì)并對(duì)該類型的流密碼算法更有效。根據(jù)安全模型的不同，可以將這些分析方法分為傳統(tǒng)機(jī)密性分析和認(rèn)證加密安全性分析。根據(jù)敵手能力的不同，可以分為唯密文分析、已知明文分析、選擇明文分析和選擇密文分析。根據(jù)密鑰數(shù)量的不同，可以分為單密鑰分析和多密鑰分析。根據(jù)分析對(duì)象的不同，可以分為初始化分析、密鑰流生成階段分析和認(rèn)證碼生成階段分析。根據(jù)分析結(jié)果的不同，可以分為區(qū)分分析和狀態(tài)（密鑰）恢復(fù)分析。根據(jù)數(shù)學(xué)工具的不同，可以分為確定性分析和統(tǒng)計(jì)性分析。

鑒于此，流密碼分析方法的分類也是一個(gè)值得研究的課題。文獻(xiàn)[14]回顧了部分流密碼分析方法，但僅限于線性分析、相關(guān)分析方面的一些研究進(jìn)展討論，沒有進(jìn)一步闡述分析方法的理論細(xì)節(jié)。文獻(xiàn)[15]將流密碼的分析方法分為時(shí)間存儲(chǔ)數(shù)據(jù)折中（TMDTD,time-memory data trade-off）類、相關(guān)分析類、線性分析類、代數(shù)分析類和猜測(cè)確定類，并結(jié)合具體流密碼算法闡述了多種流密碼分析方法。本文從主要技術(shù)特點(diǎn)的角度對(duì)流密碼的主要分析方法進(jìn)行分類研究，將現(xiàn)有的主要流密碼分析方法分為基于相關(guān)性質(zhì)的分析方法、基于差分性質(zhì)的分析方法、基于代數(shù)方程組的分析方法和基于時(shí)間存儲(chǔ)數(shù)據(jù)折中的分析方法4 種，重點(diǎn)闡述分析方法本身的技術(shù)原理、所依賴的性質(zhì)和相關(guān)公開問(wèn)題，還涵蓋了一些新的研究進(jìn)展。這種分類方法與之前不同，更強(qiáng)調(diào)主要技術(shù)，有利于研究者把握流密碼分析方法之間的區(qū)別和聯(lián)系。例如，線性區(qū)分分析與相關(guān)分析被歸為同一類，因兩者都基于線性逼近技術(shù)；立方分析則被歸為基于差分性質(zhì)的分析方法，因其與高階差分/積分分析技術(shù)有密切聯(lián)系，故對(duì)利用劃分性質(zhì)改進(jìn)立方分析顯得非常重要；猜測(cè)確定分析則被歸為基于代數(shù)方程組的分析方法，因?yàn)樵摲椒▽?shí)際上是從另一個(gè)角度求解代數(shù)方程組的。

1 基礎(chǔ)知識(shí)

1.1 符號(hào)

1.2 基本定義

定義1線性反饋移位寄存器。一個(gè)LFSR 一般包含l個(gè)寄存器單元 (x0,…,xl-1)和線性反饋關(guān)系xl=c1xl-1+…+clx0。

LFSR 有2 種實(shí)現(xiàn)形式：Fibonacci 形式和Galois形式。2 種不同形式的LFSR 在初態(tài)上相差一個(gè)線性變換。當(dāng)反饋關(guān)系為非線性時(shí)，稱之為NFSR。

定義2線性逼近。令Γ和Λ分別表示mbit輸入掩碼和nbit 輸出掩碼，一個(gè)m入n出的布爾函數(shù)f的線性逼近可表示為Λy⊕Γx=e，其中，e表示二元噪聲變量。

一般地，當(dāng)Γ和Λ分別表示 F2上的r×m和r×n矩陣時(shí)，稱之為多維線性逼近。

定義3相關(guān)性與偏差。一個(gè)二元隨機(jī)變量e的相關(guān)性定義為cor(e)=Pr(e=0)-Pr(e=1)，偏差則定義為。

線性逼近中的二元變量e的相關(guān)性簡(jiǎn)稱為線性相關(guān)性。當(dāng)噪聲為向量時(shí)，一般采用平方歐幾里得不平衡性（SEI,squared Euclidean imbalance）來(lái)度量其偏差。

定義4SEI。令e∈表示一個(gè)m維的隨機(jī)向量，定義其概率分布的SEI 為

在研究線性相關(guān)性時(shí)，常用的一個(gè)工具是Walsh 譜。

定義5Walsh-Hadamard 變換（WHT,Walsh-Hadamard transform）。令f:{0,1}n→? 表示一個(gè)n變?cè)瘮?shù)，其WHT 定義為

劃分性質(zhì)是立方分析中常用的概念，比特劃分性質(zhì)如定義6 所示。

2 基于相關(guān)性質(zhì)的分析方法

本節(jié)闡述基于線性逼近相關(guān)性的流密碼分析方法，主要包括線性區(qū)分分析和相關(guān)分析兩類。線性區(qū)分分析與相關(guān)分析雖然理論方法不同，但都利用流密碼算法有限狀態(tài)自動(dòng)機(jī)（FSW,finite state machine）輸入與密鑰流之間的線性相關(guān)性。這兩類方法主要適用于使用LFSR 構(gòu)件的流密碼算法。

2.1 線性區(qū)分分析

線性區(qū)分分析屬于統(tǒng)計(jì)分析，其目標(biāo)是將密鑰流序列與隨機(jī)序列區(qū)分開。Coppersmith[18]提出了一種流密碼的線性區(qū)分分析方法，并應(yīng)用該方法分析了SNOW 2.0 算法的安全性。該方法利用分組密碼中線性掩碼傳播技術(shù)來(lái)尋找流密碼算法的LFSR 狀態(tài)與密鑰流之間相關(guān)性較大的線性逼近關(guān)系，基本步驟如算法1 所示。

算法1線性區(qū)分分析基本方法

輸入密鑰流序列

輸出區(qū)分結(jié)果

/*預(yù)計(jì)算階段*/

1) 尋找LFSR 狀態(tài)和密鑰流之間相關(guān)性較大的線性逼近關(guān)系；

2) 尋找一個(gè)LFSR 反饋多項(xiàng)式l(x)的低代數(shù)次數(shù)、低漢明重量倍式g，即g的代數(shù)次數(shù)不太大且項(xiàng)數(shù)很少（根據(jù)實(shí)際情況，通常取為3 項(xiàng)或4 項(xiàng)）；

3) 利用倍式g和堆積引理，建立關(guān)于密鑰流的一個(gè)線性關(guān)系；/*在線階段*/

4) 利用關(guān)于密鑰流的線性關(guān)系進(jìn)行區(qū)分分析。具體來(lái)說(shuō)，設(shè)步驟1)找到的線性逼近關(guān)系為

步驟2)中尋找校驗(yàn)式可以歸結(jié)為k子集和問(wèn)題[19-21]。假設(shè)關(guān)于密鑰流的線性關(guān)系的相關(guān)性為cor，根據(jù)最優(yōu)基本區(qū)分器的相關(guān)結(jié)論，步驟4)所需的數(shù)據(jù)和時(shí)間復(fù)雜度都為O(cor-2)[16]。

Yang 等[22]應(yīng)用有限域上的區(qū)分分析方法分析了SNOW 3G 算法。F2n上的區(qū)分分析與前述方法的原理類似。注意到，相關(guān)性cor 由個(gè)二元噪聲et+k的相關(guān)性堆積得到；而應(yīng)用非二元域上的區(qū)分分析時(shí)，導(dǎo)出噪聲是個(gè)非二元噪聲之和，故其概率分布由個(gè)非二元噪聲分布卷積得到。因此，導(dǎo)出噪聲的SEI 因卷積損失明顯。為減少卷積損失，提高區(qū)分能力，要求g(x)的系數(shù)都是1，但代價(jià)是g(x)的代數(shù)次數(shù)升高了。

Yang 等[23]又提出有限域Fp上的線性區(qū)分分析方法并分析了ZUC-256 算法，提出了譜值重合的啟發(fā)式技術(shù)，以減少噪聲卷積損失。

2.2 相關(guān)分析

相關(guān)分析是一種狀態(tài)恢復(fù)分析，其基本原理是將流密碼LFSR 狀態(tài)恢復(fù)問(wèn)題轉(zhuǎn)化為譯碼問(wèn)題：將LFSR 部分看作一個(gè)線性碼，其中，初態(tài)視作信息位；將LFSR 輸出序列看作發(fā)送的碼字；將非線性組合生成器或者帶記憶有限狀態(tài)機(jī)看作一個(gè)噪聲信道。噪聲信道一般選取二元對(duì)稱信道（BSC,binary symmetric channel）。流密碼輸出的密鑰流序列則可以看作所收到的碼字，如圖1 所示。

圖1 快速相關(guān)分析的二元信道譯碼模型

Siegenthaler[24]提出了對(duì)非線性組合生成器類型流密碼的分別征服相關(guān)分析方法。其思想是利用組合函數(shù)的輸入和輸出之間的相關(guān)性，窮舉搜索并恢復(fù)某個(gè)（或幾個(gè)）特定LFSR 的初始狀態(tài)。這是最早的流密碼相關(guān)分析方法。在此之后，流密碼的相關(guān)分析得到了進(jìn)一步發(fā)展，主要包含條件相關(guān)分析和快速相關(guān)分析兩類分析方法。

2.2.1 條件相關(guān)分析

本節(jié)闡述2 種條件相關(guān)分析方法，它們的共同點(diǎn)是利用條件相關(guān)性以獲得更好的分析效果，區(qū)別是條件不同。

1) 基于輸入相關(guān)性的條件相關(guān)分析

Lee 等[25]在Anderson[26]提出的條件相關(guān)性思想的基礎(chǔ)上，提出了一種條件相關(guān)分析方法。這種方法利用在特定輸出條件下輸入變量的相關(guān)性進(jìn)行密碼分析。由于條件相關(guān)性通常要比一般相關(guān)性更大，該方法可有效分析基于濾波生成器的流密碼。該思想又被推廣為混合相關(guān)分析和濃縮分析[27]。Lee 等提出的條件相關(guān)分析方法具體如算法2 所示。

算法2Lee 等提出的條件相關(guān)分析方法

2) 基于輸出相關(guān)性的條件相關(guān)分析

Lu 等[28]擴(kuò)展了條件相關(guān)分析方法。該方法利用在部分輸入未知且均勻隨機(jī)的條件下，任意一個(gè)函數(shù)輸出的條件相關(guān)性進(jìn)行密碼分析。這種條件相關(guān)性是前述輸入條件相關(guān)性的反向推廣，適用于敵手不僅可以看到密鑰流，還可以訪問(wèn)由密鑰部分控制的不確定的計(jì)算過(guò)程的場(chǎng)景。Zhang等[29]進(jìn)一步推廣了計(jì)算條件相關(guān)性的函數(shù)。Lu 等提出的方法的原理如下。

區(qū)分器。猜測(cè)2L個(gè)所有可能的密鑰值，對(duì)于每一個(gè)猜測(cè)值K，設(shè)一個(gè)權(quán)重G(K)，其初值置0。對(duì)于n個(gè)樣本，累計(jì)計(jì)算

以使G(K)最大的猜測(cè)值K作為正確密鑰候選值。

2.2.2 快速相關(guān)分析

快速相關(guān)分析是一類非常重要的流密碼分析方法。Meier 等[30]提出快速相關(guān)分析方法，以改進(jìn)分別征服相關(guān)分析中復(fù)雜度與LFSR 長(zhǎng)度呈指數(shù)關(guān)系的缺點(diǎn)。按照譯碼方式的不同，快速相關(guān)分析主要可以分為基于概率迭代譯碼的快速相關(guān)分析和基于硬判定譯碼的快速相關(guān)分析。

1) 基于概率迭代譯碼的快速相關(guān)分析

Meier 等[30]提出的譯碼算法（算法B）是一種概率迭代譯碼算法，如算法3 所示。譯碼算法的輸入是一段長(zhǎng)為N的連續(xù)密鑰流z t=xt⊕et。若成功譯碼，則算法的輸出為xt。

算法3概率迭代譯碼算法

算法3 中，概率閾值pth和個(gè)數(shù)閾值Nw需要根據(jù)初始錯(cuò)誤率p、奇偶校驗(yàn)式成立的個(gè)數(shù)以及奇偶校驗(yàn)式抽頭的個(gè)數(shù)由正態(tài)分布導(dǎo)出。后驗(yàn)概率p*可根據(jù)貝葉斯公式導(dǎo)出，主要依據(jù)為：對(duì)于某個(gè)位置0≤t≤N，若觀察到較多的校驗(yàn)式為0，那么p*應(yīng)當(dāng)增大。

Johansson 等[31-32]基于卷積碼理論改進(jìn)了譯碼方法。與之前方法相比，改進(jìn)方法的校驗(yàn)式更容易生成。Canteaut 等[33]將LDPC 碼的譯碼方法應(yīng)用到快速相關(guān)分析中，以使用漢明重量為4 或5 的校驗(yàn)式。Golic[34]提出了將編碼理論中最優(yōu)的逐符號(hào)譯碼算法H-R 算法應(yīng)用于快速相關(guān)分析，該方法可以利用非正交的校驗(yàn)等式。雖然理論上概率迭代譯碼的快速相關(guān)分析的譯碼能力更接近香農(nóng)界，但基于此類譯碼方法的快速相關(guān)分析通常難刻畫精確可靠的復(fù)雜度，因而很少應(yīng)用于分析現(xiàn)實(shí)世界中的流密碼算法。Zhou 等[35]將二元迭代譯碼算法推廣至向量迭代譯碼算法，并分析了其部分理論復(fù)雜度。

2) 基于硬判定譯碼的快速相關(guān)分析

Chepyzhov 等[36]提出了一種基于信息集譯碼的快速相關(guān)分析方法。該方法通過(guò)折疊噪聲來(lái)分析時(shí)間存儲(chǔ)數(shù)據(jù)折中的復(fù)雜度，主要優(yōu)勢(shì)在于能夠給出可靠的復(fù)雜度和成功概率理論估計(jì)。Johansson 等[37]提出了通過(guò)重建多項(xiàng)式的方法來(lái)進(jìn)行快速相關(guān)分析，其基本原理與信息集譯碼方法相似，恢復(fù)對(duì)象由內(nèi)部狀態(tài)變?yōu)槎囗?xiàng)式。Mihaljevi 等[38]進(jìn)一步提出可以用列表譯碼的方法進(jìn)行快速相關(guān)分析。

Chose 等[39]提出通過(guò)構(gòu)造關(guān)于密鑰流數(shù)據(jù)的公開函數(shù)，并在預(yù)計(jì)算階段對(duì)其進(jìn)行FWHT，避免校驗(yàn)式求值過(guò)程中的冗余計(jì)算。該方法大大提高了快速相關(guān)分析的效率，使快速相關(guān)分析成為分析基于LFSR 的流密碼最重要的方法之一。下面，闡述基于信息集譯碼和FWHT 技術(shù)加速的快速相關(guān)分析的基本原理，如算法4 所示。

算法4基于信息集譯碼和FWHT 技術(shù)加速的快速相關(guān)分析

在線階段根據(jù)構(gòu)造譯碼函數(shù)w(x)，并計(jì)算Walsh 譜(s)。因?yàn)閃alsh 譜實(shí)際上表示經(jīng)驗(yàn)相關(guān)性，且當(dāng)猜測(cè)值正確時(shí)，經(jīng)驗(yàn)相關(guān)性絕對(duì)值可能更大，故以最大的s作為s(0)的l′bit。

算法4 的復(fù)雜度主要受步驟2)～步驟4)的影響，譯碼所需的校驗(yàn)式個(gè)數(shù)M受碼率不超過(guò)信道容量的限制。借助于FWHT 加速，步驟3)和步驟4)所需復(fù)雜度由原來(lái)的O(M2l′)降為O(M+l′2l′)。

在預(yù)計(jì)算階段，一般可以通過(guò)尋找線性路徑的方式建立LFSR 狀態(tài)和密鑰流之間的高相關(guān)性線性逼近關(guān)系。線性路徑中線性掩碼的傳播與分組密碼線性分析類似。因此，可以通過(guò)專門化算法或建立并求解自動(dòng)化搜索模型的方式解決。

基于信息集譯碼快速相關(guān)分析方法已經(jīng)很成熟，目前，研究者往往更專注在具體流密碼中的應(yīng)用。Zhang等[40]將前述快速相關(guān)分析的方法推廣到利用有限域上的線性逼近，改進(jìn)了對(duì)SNOW 2.0 算法的分析結(jié)果。Shi 等[41]使用SMT/SAT 模型搜索了SNOW-V的高相關(guān)性線性逼近，并改進(jìn)了快速相關(guān)分析結(jié)果。

Todo 等[42]提出快速相關(guān)分析方法，優(yōu)勢(shì)是可以同時(shí)降低時(shí)間和數(shù)據(jù)復(fù)雜度。該方法主要出發(fā)點(diǎn)是觀察到 F2m上線性掩碼的乘法具備特殊交換性質(zhì)。因此，在快速相關(guān)分析中可以考慮恢復(fù)中間狀態(tài)而非初態(tài)，如算法5 所示。

算法5Todo 等提出的快速相關(guān)分析方法

輸入密鑰流序列

輸出LFSR 初態(tài)

/*預(yù)計(jì)算階段*/

1) 尋找LFSR 狀態(tài)和密鑰流之間的多個(gè)高相關(guān)性且密鑰流掩碼相同的線性逼近關(guān)系；

/*在線階段*/

2) 繞過(guò)βbit，構(gòu)造關(guān)于密鑰流的公開函數(shù)；

3) 計(jì)算公開函數(shù)的Walsh 譜，保留所有的經(jīng)驗(yàn)相關(guān)性大于某一閾值corth的中間狀態(tài)；

4) 對(duì)于步驟3)保留的每個(gè)中間狀態(tài)，嘗試恢復(fù)正確的LFSR 初態(tài)。

具體來(lái)說(shuō)，設(shè)步驟1)中共找到m個(gè)相關(guān)性為cor(e) 的線性逼近，步驟2)構(gòu)造關(guān)于剩余(l-β)bit中間狀態(tài)的譯碼函數(shù)并計(jì)算Walsh 譜，該過(guò)程與算法4 類似。記 ∈1和 ∈2分別表示正確和錯(cuò)誤中間狀態(tài)相關(guān)性大于閾值corth的概率并設(shè)2 種狀態(tài)分別服從參數(shù)為λ1≈m2-β∈1和λ2≈m2-β∈2的泊松分布，只要λ1相比λ2較小，就可以篩選出正確初態(tài)。當(dāng)N≈ (l-β) 2l-β≈m2l-β∈1時(shí)，時(shí)間復(fù)雜度為O(3(l-β) 2l-β)，數(shù)據(jù)復(fù)雜度為O((l-β) 2l-β)。

在預(yù)計(jì)算階段，同樣可以通過(guò)建立并求解自動(dòng)化搜索模型的方式尋找所需的線性逼近。特別地，當(dāng)有限狀態(tài)自動(dòng)機(jī)由NFSR 和濾波函數(shù)組成時(shí)，可以采用分析NFSR 更新函數(shù)和濾波函數(shù)Walsh 譜的方式，例如，Grain 系列算法。

此后，Wang 等[43]又證明了當(dāng)有多條線性逼近時(shí)，校驗(yàn)式個(gè)數(shù)下界為。這意味著當(dāng)線性逼近較多時(shí)，所需的數(shù)據(jù)量更少。

2.3 小結(jié)

線性區(qū)分分析與相關(guān)分析都是針對(duì)密鑰流生成階段的分析方法。這類分析方法主要適用于基于LFSR 的流密碼算法。特別地，Todo 等[42]提出的快速相關(guān)分析方法適用于可以找到很多高相關(guān)性線性逼近關(guān)系，且不能夠折疊噪聲的情況。雖然大部分公開研究結(jié)果都是針對(duì)同步流密碼的，但是該類分析方法建立在對(duì)數(shù)據(jù)的統(tǒng)計(jì)分析基礎(chǔ)上，故理論上它們也適用于自同步流密碼算法。在此情況下，線性掩碼的傳播應(yīng)當(dāng)同時(shí)考慮明文和密鑰流。

與線性區(qū)分分析相比，快速相關(guān)分析需要考慮校驗(yàn)式快速求值問(wèn)題，因此如何結(jié)合FWHT 或FFT加速是分析的重要一環(huán)。這就要求所構(gòu)造的譯碼函數(shù)譜值具有明確的現(xiàn)實(shí)意義。在非二元相關(guān)性質(zhì)的快速相關(guān)分析中，這是一項(xiàng)具有挑戰(zhàn)性的工作。

線性區(qū)分分析、條件相關(guān)分析、快速相關(guān)分析的一些典型分析應(yīng)用如表1 所示。值得注意的是，文獻(xiàn)[42]中提出的快速相關(guān)分析方法也可以應(yīng)用于分析Plantlet 等類Grain 輕量化流密碼算法，但是復(fù)雜度折中關(guān)系有差別[43]，本文不再一一列舉。

對(duì)于基于相關(guān)性質(zhì)的流密碼分析方法，降低FSM 的輸入輸出相關(guān)性是一種有效的防護(hù)手段，在設(shè)計(jì)階段就可以通過(guò)自動(dòng)化搜索或人工推導(dǎo)的方式來(lái)分析最優(yōu)化線性路徑（逼近）的相關(guān)性。另外，增大LFSR 的規(guī)模也是一種很有效的抵抗此類分析方法的防護(hù)手段。

基于信息集譯碼的快速相關(guān)分析技術(shù)目前已經(jīng)較為完善，但幾種條件相關(guān)分析應(yīng)用局限性較強(qiáng)。如何改進(jìn)條件相關(guān)分析方法以應(yīng)用于分析現(xiàn)代流密碼算法也是一個(gè)值得研究的具體課題。

基于相關(guān)性質(zhì)流密碼分析方法的特點(diǎn)如表2所示。

表2 基于相關(guān)性質(zhì)流密碼分析方法的特點(diǎn)

3 基于差分性質(zhì)的分析方法

本節(jié)闡述基于差分性質(zhì)的流密碼分析方法，主要包括碰撞分析和立方分析。這兩類方法主要適用于分析流密碼算法的初始化過(guò)程或者認(rèn)證流密碼算法的認(rèn)證碼生成過(guò)程。

3.1 碰撞分析

3.1.1 差分分析

由于流密碼的初始化過(guò)程類似于分組密碼的輪迭代，因此可以采用分組密碼的差分分析思想分析流密碼的初始化過(guò)程。對(duì)于流密碼，可利用初始向量（IV,initialization vector）對(duì)之間的輸入差分與密鑰生成階段的輸出差分性質(zhì)構(gòu)造區(qū)分器。文獻(xiàn)[45]中研究了一般的（密鑰，IV）差分對(duì)的差分特征，即(ΔK,ΔIV) →Δs。這種分析方法在原理上與分組密碼的差分分析類似，本文不再展開闡述。

2007 年以后，差分分析方法的基本思想得到了推廣，派生出選擇IV 分析方法[46-48]。通過(guò)選擇IV的一個(gè)比特子集，并固定這個(gè)子集之外的IV 變量和密鑰變量，然后遍歷該子集變量的所有可能取值，得到對(duì)應(yīng)的所有的密鑰流輸出。這等效于生成以該子集變量為輸入，以一個(gè)密鑰流符號(hào)為輸出的布爾函數(shù)真值表，并試圖發(fā)現(xiàn)該函數(shù)的一些統(tǒng)計(jì)弱點(diǎn)。這種一般化的選擇IV 分析方法已經(jīng)接近于后面將闡述的立方分析方法。

3.1.2 滑動(dòng)分析

滑動(dòng)分析基本思想源于分組密碼滑動(dòng)密鑰分析。Biryukov 等[49]提出了滑動(dòng)密鑰分析，主要適用于分析輪對(duì)稱性強(qiáng)的迭代型分組密碼，隨后被用于分析流密碼算法初始化過(guò)程?；瑒?dòng)分析是一種多密鑰分析，其基本思想是尋找一個(gè)密鑰和初始向量對(duì)(K,IV)，經(jīng)過(guò)初始過(guò)程的數(shù)輪迭代后，流密碼算法的內(nèi)部狀態(tài)恰好是另一對(duì)(K′,IV′)對(duì)應(yīng)的初態(tài)，然后通過(guò)這種對(duì)稱性質(zhì)恢復(fù)出K或K′。該方法與流密碼算法的初始化輪數(shù)沒有關(guān)系，主要利用部分流密碼算法初始化過(guò)程中的對(duì)稱性。

3.1.3 近似碰撞分析

Zhang 等[50]提出了近似碰撞分析，并用于分析Grain-v1 算法。動(dòng)機(jī)是觀察到該算法NFSR 和LFSR等長(zhǎng)且LFSR 獨(dú)立更新，若2 個(gè)時(shí)刻的內(nèi)部狀態(tài)僅相差很小，那么輸出的密鑰流片段彼此近似。根據(jù)近似生日碰撞原理，只要密鑰流足夠長(zhǎng)，就可以找到內(nèi)部狀態(tài)上的近似碰撞。根據(jù)密鑰流差分，檢測(cè)出內(nèi)部狀態(tài)上的近似碰撞可以用于恢復(fù)LFSR 狀態(tài)。近似碰撞分析與時(shí)間存儲(chǔ)數(shù)據(jù)折中分析有較密切的關(guān)聯(lián)。下面，介紹其基本模型。

預(yù)計(jì)算階段主要建立一些結(jié)構(gòu)性的差分表。首先，窮舉所有的漢明重量較小的內(nèi)部狀態(tài)差分，計(jì)算對(duì)應(yīng)的所有密鑰流差分。然后，為每個(gè)可能的密鑰流差分建立一個(gè)表。每個(gè)表包含了所有可能產(chǎn)生該密鑰流差分的內(nèi)部狀態(tài)差分，并將表中的內(nèi)部狀態(tài)差分按照所占比例進(jìn)行排序。

在線階段根據(jù)密鑰流和預(yù)計(jì)算表提取內(nèi)部狀態(tài)的差分信息。因?yàn)長(zhǎng)FSR 獨(dú)立更新，一旦得到正確的內(nèi)部狀態(tài)差分，就可以得到LFSR 內(nèi)部狀態(tài)。

文獻(xiàn)[50]還提出使用BSW 采樣技術(shù)改進(jìn)近似碰撞。隨后Zhang 等[51]又對(duì)近似碰撞分析進(jìn)行了改進(jìn)，移除之前需要的假設(shè)，并將全狀態(tài)的近似碰撞轉(zhuǎn)換為部分狀態(tài)的近似碰撞。

3.2 立方分析

立方分析最早由Dinur 等[52]提出，是高階差分分析的一種擴(kuò)展，適用于更新函數(shù)代數(shù)次數(shù)較低的流密碼算法。立方分析比較特殊，既可以是密鑰恢復(fù)分析，也可以是區(qū)分分析。本節(jié)主要闡述傳統(tǒng)立方分析、動(dòng)態(tài)立方分析、基于劃分性質(zhì)的立方分析和條件立方分析。

3.2.1 傳統(tǒng)立方分析

立方分析將初始化過(guò)程看作輸入為初始變量v和密鑰變量x、輸出為第一比特密鑰流z的一個(gè)布爾函數(shù)z=f(x,v)。其后計(jì)算f的高階差分得到簡(jiǎn)化的多項(xiàng)式，并用于恢復(fù)密鑰或者建立區(qū)分器。具體來(lái)說(shuō)，令f=t I pI⊕q，其中，I是v下標(biāo)索引的子集，tI是僅包含公開變量的單項(xiàng)式，pI不包含vi∈I中任何變量且q不能被tI整除。因此可得。一般將vi∈I中的變量稱為立方變量，其余公開變量稱為非立方變量。所有可能的立方賦值的集合CI稱為d維立方，pI稱為CI在f中的超級(jí)多項(xiàng)式。

立方分析包括預(yù)處理階段和在線階段。預(yù)處理階段找到可以得到低次超級(jí)多項(xiàng)式的立方，并由此恢復(fù)出超級(jí)多項(xiàng)式。在線階段通過(guò)詢問(wèn)加密預(yù)言機(jī)得到z，再通過(guò)解低次方程組恢復(fù)一些密鑰變量。

立方分析中有2 個(gè)重要問(wèn)題，一是選擇合適的立方，二是測(cè)試超級(jí)多項(xiàng)式的線性或恢復(fù)超級(jí)多項(xiàng)式。對(duì)于后者，當(dāng)攻擊者把算法看作一個(gè)黑盒多項(xiàng)式時(shí)，在預(yù)處理階段，可以使用隨機(jī)測(cè)試法來(lái)確定給定的立方集超級(jí)多項(xiàng)式是否為線性并恢復(fù)超級(jí)多項(xiàng)式。

立方分析還可以用于區(qū)分流密碼算法和隨機(jī)函數(shù)，此時(shí)一般稱為立方檢驗(yàn)[53-54]。立方檢驗(yàn)將v分成互補(bǔ)的兩部分，即立方變量（CV）和超級(jí)多項(xiàng)式變量（SV）。通過(guò)選取特定的CV 和SV，檢驗(yàn)超級(jí)多項(xiàng)式的性質(zhì)，實(shí)現(xiàn)區(qū)分分析。常見的可用于立方檢驗(yàn)的超級(jí)多項(xiàng)式性質(zhì)有平衡性、常數(shù)函數(shù)、低次數(shù)、線性變量的存在性和變量退化等。

3.2.2 動(dòng)態(tài)立方分析

Dinur 等[55]提出了動(dòng)態(tài)立方分析。類似于立方分析，動(dòng)態(tài)立方分析也是對(duì)立方變量遍歷之后的輸出結(jié)果求和。在立方分析和立方檢驗(yàn)中，立方變量之外的所有公開變量設(shè)定為固定值，因此可稱為靜態(tài)變量；在動(dòng)態(tài)立方分析中，某些非立方變量的值不是固定的，而是由定義在公開變量和秘密變量上的函數(shù)決定，稱為動(dòng)態(tài)變量。通常選取那些可以保持某些狀態(tài)比特為0 的函數(shù)，從而放大立方檢驗(yàn)的非隨機(jī)性。顯然，動(dòng)態(tài)立方分析是立方檢驗(yàn)的推廣和優(yōu)化，攻擊者能夠直接推導(dǎo)密鑰信息，不需要求解代數(shù)方程組。此外，選取適當(dāng)?shù)膭?dòng)態(tài)變量能夠降低立方檢驗(yàn)的時(shí)間復(fù)雜度（通常動(dòng)態(tài)立方檢驗(yàn)所需立方集的規(guī)模更?。?。動(dòng)態(tài)立方分析需要建立在對(duì)內(nèi)部狀態(tài)進(jìn)行更加復(fù)雜的分析的基礎(chǔ)上，基本原理如下。

3.2.3 基于劃分性質(zhì)的立方分析

劃分性質(zhì)是Todo[17]提出的一種尋找分組密碼高階差分（積分）特征的新技術(shù)。隨后，基于比特級(jí)的劃分性質(zhì)被提出并應(yīng)用于多個(gè)算法的分析中[56]。文獻(xiàn)[56-58]提出了劃分性質(zhì)的一些傳播法則。自立方分析提出以來(lái)，立方的大小一直受實(shí)驗(yàn)限制。這種情況一直到Todo 等[57]提出利用劃分性質(zhì)分析代數(shù)正規(guī)型的系數(shù)來(lái)恢復(fù)超級(jí)多項(xiàng)式的方法后才得到改觀。計(jì)算劃分性質(zhì)的傳播并不容易，Xiang 等[58]通過(guò)混合整數(shù)線性規(guī)劃（MILP,mixed-integer linear programming）有效地計(jì)算了劃分性質(zhì)的傳播。

算法6基于MILP 估計(jì)超級(jí)多項(xiàng)式中的秘密變量

利用算法 6 分析超級(jí)多項(xiàng)式可知，只有x j(j∈J)與立方集CI對(duì)應(yīng)的超級(jí)多項(xiàng)式有關(guān)。攻擊者選擇IV 的常數(shù)部分為某一固定常數(shù)并得到一個(gè)立方集CI，隨后通過(guò)組合所有可能的秘密變量來(lái)恢復(fù)超級(jí)多項(xiàng)式，其時(shí)間復(fù)雜度為O(2|I|+|J|)。

Wang 等[59]提出了Flag 技術(shù)，進(jìn)一步改進(jìn)了立方分析MILP 模型的精確性。改進(jìn)的模型能夠識(shí)別那些可得到非常數(shù)超級(jí)多項(xiàng)式的非立方變量賦值。同時(shí)，還改進(jìn)了對(duì)于超級(jí)多項(xiàng)式項(xiàng)數(shù)的估計(jì)。Wang 等[60]采用三子集可分性的概念改進(jìn)了求超級(jí)多項(xiàng)式的算法，并降低了時(shí)間復(fù)雜度。Hao等[61]提出了基于完善的三子集的多重集合的可分性定義，使MILP 模型在計(jì)算超級(jí)多項(xiàng)式時(shí)更準(zhǔn)確，同時(shí)也回答了如何準(zhǔn)確恢復(fù)超級(jí)多項(xiàng)式的問(wèn)題。Sun[62]回答了如何搜索好的立方的問(wèn)題，并給出了啟發(fā)式的自動(dòng)化搜索算法。所謂好的立方是指其對(duì)應(yīng)的超級(jí)多項(xiàng)式至少有一個(gè)平衡的秘密變量。同時(shí)，Sun 基于此算法改進(jìn)了Hao 等對(duì)Trivium 算法的分析結(jié)果。目前，基于劃分性質(zhì)的立方分析是一個(gè)研究熱點(diǎn)。

3.2.4 條件立方分析

Huang 等[63]提出了條件立方分析。條件立方分析一般針對(duì)基于Sponge 結(jié)構(gòu)的Keccak-MAC 及類似密碼算法。該方法受動(dòng)態(tài)立方分析方法的啟發(fā)，試圖通過(guò)增加對(duì)IV的條件來(lái)降低立方變量多項(xiàng)式的次數(shù)。這種技術(shù)與消息修改技術(shù)[64]和條件差分分析[65]有類似之處，也是通過(guò)一些比特條件來(lái)控制差分傳播?；谶@些條件的立方測(cè)試器一般被稱為條件立方測(cè)試器。Li 等[66]推廣了此方法并用于Ascon 認(rèn)證加密算法的分析。下面，簡(jiǎn)單闡述Li 等的方法。

假設(shè)一個(gè)類Keccak-MAC 算法一次輸出lbit。每1 bit 輸出可以寫成秘密變量和公開變量的布爾函數(shù)f i(x,v)，0≤i＜l。選擇一個(gè)公共立方CI，將fi重寫為f i=t I Pi+Qi。在條件立方分析中，尋找多項(xiàng)式Pi的公因子，即，因此，當(dāng)立方求和后得到。如果公因式g的形式足夠簡(jiǎn)單，如g=x0，則可以采用立方測(cè)試器確定x0。

3.3 小結(jié)

本節(jié)所闡述的基于差分性質(zhì)的分析方法都是分析流密碼算法初始化過(guò)程，因而對(duì)于自同步流密碼也適用。差分分析是一種一般化的分析方法，對(duì)初始化過(guò)程擴(kuò)散混淆性質(zhì)較弱的流密碼效果較好?；瑒?dòng)分析則僅適用于初始化迭代對(duì)稱性強(qiáng)的流密碼算法。近似碰撞分析則適用于具有緊湊的NFSR-LFSR 型流密碼算法。立方分析針對(duì)初始化階段的代數(shù)性質(zhì)，目標(biāo)是構(gòu)造立方區(qū)分器和恢復(fù)密鑰。目前，立方攻擊主要適用于更新函數(shù)簡(jiǎn)單的輕量級(jí)流密碼。而基于字的流密碼一般采用代數(shù)次數(shù)和擴(kuò)散性較強(qiáng)的更新函數(shù)，因而，立方分析應(yīng)用較少。表3 列出了基于差分性質(zhì)分析方法的部分典型應(yīng)用。

表3 基于差分性質(zhì)分析方法的部分典型應(yīng)用

對(duì)于差分分析、滑動(dòng)分析的防護(hù)設(shè)計(jì)已經(jīng)較為成熟，通過(guò)增強(qiáng)更新函數(shù)密碼性質(zhì)、引入初態(tài)常數(shù)可以較為有效地抵抗此類分析。由于近似碰撞分析與時(shí)間存儲(chǔ)數(shù)據(jù)折中分析有關(guān)聯(lián)，且利用了密鑰流差分與內(nèi)部狀態(tài)差分之間的近似性，因此合理地增大出口函數(shù)規(guī)模和內(nèi)部狀態(tài)規(guī)模（含輪密鑰）可以增強(qiáng)近似碰撞分析的安全性。

值得注意的是，立方分析與MILP 方法結(jié)合后突破了之前僅能使用小立方集的限制，實(shí)現(xiàn)了更大的立方集搜索和更多輪數(shù)的區(qū)分器。一方面，盡管更復(fù)雜的更新函數(shù)和更多的初始化輪數(shù)有助于抵抗立方分析，但在公開輕量級(jí)流密碼設(shè)計(jì)中，更新函數(shù)和初始化輪數(shù)是需要平衡的重要設(shè)計(jì)指標(biāo)。另一方面，近年來(lái)，立方分析技術(shù)在不斷進(jìn)步。因此，立方分析在輕量級(jí)流密碼的分析與設(shè)計(jì)中還將會(huì)發(fā)揮很大作用，并不斷發(fā)展。

表4 簡(jiǎn)單總結(jié)了基于差分性質(zhì)流密碼分析方法的特點(diǎn)。各種立方分析的基本思想類似，但技術(shù)細(xì)節(jié)有所不同。

表4 基于差分性質(zhì)流密碼分析方法的特點(diǎn)

4 基于代數(shù)方程組的分析方法

本節(jié)闡述基于代數(shù)方程組的流密碼分析方法。該類分析方法都是通過(guò)求解代數(shù)方程組來(lái)恢復(fù)內(nèi)部狀態(tài)，但求解策略有所不同。一種方式是猜測(cè)可能的原象，根據(jù)函數(shù)值驗(yàn)證正確性，即猜測(cè)確定分析；另一種方式是通過(guò)數(shù)學(xué)理論求解方程組得到原象，即代數(shù)分析。

4.1 猜測(cè)確定分析

Knudsen等[70]在分析RC4時(shí)提出了猜測(cè)確定分析的思想。Pasalic[71]提出了針對(duì)過(guò)濾生成器的猜測(cè)確定分析方法。

猜測(cè)確定分析的基本思想是將流密碼內(nèi)部狀態(tài)劃分為2 個(gè)集合：猜測(cè)集合和確定集合。攻擊者窮舉猜測(cè)集合狀態(tài)可能值，然后利用該部分內(nèi)部狀態(tài)值來(lái)求得確定集合內(nèi)部狀態(tài)。最后，攻擊者還需將算法輸出和密鑰流進(jìn)行比較，以檢驗(yàn)猜測(cè)的正確性。因此，猜測(cè)確定分析的目標(biāo)是尋找更小的猜測(cè)集，并以較少的復(fù)雜度來(lái)得到確定集合狀態(tài)。

Feng 等[72]利用猜測(cè)確定方法分析了SOSEMANUK。根據(jù)SOSEMANUK 特殊的反饋多項(xiàng)式，改進(jìn)為面向字節(jié)而非32 bit 字的猜測(cè)確定分析。Yang 等[73]提出了D 方程技術(shù)以改進(jìn)猜測(cè)確定路徑，并改進(jìn)了對(duì)SNOW-V 算法的分析結(jié)果。下面，簡(jiǎn)單闡述其基本原理。

一條猜測(cè)路徑是指所有有序的猜測(cè)并由此確定的變量元組。如果能夠以合理的順序猜測(cè)這些變量，則有可能猜測(cè)量更少或者截?cái)嗄切┌瞬荒軡M足中間代數(shù)方程的已知猜測(cè)值。在猜測(cè)確定的中間過(guò)程中，如果要求所有的解都要滿足一些限定條件或者方程，則可以利用一些特殊的枚舉方法（如遞歸枚舉算法等）來(lái)代替直接的循環(huán)窮舉。

接下來(lái)，舉例說(shuō)明Yang 等利用D 方程截?cái)嗖聹y(cè)路徑的技術(shù)。令A(yù)=B(C⊕X)(X⊕D)表示第一類D 方程。設(shè)A,B,C,D是nbit 變量且服從均勻分布，而X的值未知。首先，計(jì)算出X的解數(shù)量分布表。設(shè)上述D 方程存在解的概率為2-r，那么對(duì)于所有可能的猜測(cè)值A(chǔ),B,C,D組合，平均只有|(A,B,C,D) |2-r個(gè)組合是合法的。由此，就可以在中間過(guò)程中去掉不合法的猜測(cè)組合，而不必遍歷并驗(yàn)證(A,B,C,D)所有可能值。

4.2 代數(shù)分析

代數(shù)分析最初應(yīng)用于公鑰和分組密碼中。Courtois 等[74]將其應(yīng)用于分析流密碼Toyocrypt 和LILI-128。傳統(tǒng)代數(shù)分析的基本思想是將流密碼視作多變?cè)瘮?shù)，建立關(guān)于內(nèi)部狀態(tài)和密鑰流之間的超定非線性方程組，再通過(guò)求解代數(shù)方程組的數(shù)學(xué)技術(shù)來(lái)恢復(fù)內(nèi)部狀態(tài)。例如

其中，A表示LFSR 的更新變換。代數(shù)分析中建立并求解大規(guī)模非線性方程組的復(fù)雜度通常較大。

在求解代數(shù)方程組方面，目前的方法主要有Gr?bner 基法[75]、再線性化法[76]、XL（extensible language）法[76]、XSL（extensible style sheet language）法[77]等。代數(shù)次數(shù)是非線性方程組求解中的重要影響因素。注意到，將布爾函數(shù)f與另一個(gè)合理選擇的布爾函數(shù)g相乘，有可能大大降低f的代數(shù)次數(shù)。文獻(xiàn)[78]將其概括為代數(shù)免疫度的概念。對(duì)于變量數(shù)量較多的一般布爾函數(shù)，目前仍無(wú)有效的代數(shù)免疫度計(jì)算方法。布爾函數(shù)的代數(shù)免疫性質(zhì)是代數(shù)分析中需要進(jìn)一步研究的課題。

另外一個(gè)研究課題是如何建立并使用低次數(shù)多變?cè)蔷€性方程組。不同的代數(shù)分析方法使用的代數(shù)方程類型一般不同，獲得方程的技術(shù)也有所差別。下面，本節(jié)簡(jiǎn)單闡述一種使用雙層甲板方程的快速代數(shù)分析的原理[74]。該方法可利用如下形式的代數(shù)方程

其中，L是關(guān)于密鑰的代數(shù)次數(shù)小于或等于d次的多項(xiàng)式，R是關(guān)于密鑰和密鑰流比特的多項(xiàng)式，滿足每項(xiàng)中密鑰變量的代數(shù)次數(shù)不超過(guò)d，密鑰流變量的代數(shù)次數(shù)不超過(guò)2?？焖俅鷶?shù)分析需在預(yù)計(jì)算階段生成約個(gè)此類方程。當(dāng)密鑰流連續(xù)（或等間隔）且LFSR 是周期的時(shí)，前述代數(shù)方程即可按時(shí)序t迭代下去，以生成更多的方程。

以上過(guò)程中，B-M 算法的時(shí)間復(fù)雜度為O(SlbS+Sn)，求解代數(shù)方程組的復(fù)雜度則由具體求解算法給出。

Armknecht[79]證明了預(yù)計(jì)算過(guò)程的合理性，并改進(jìn)了預(yù)計(jì)算方法。Braeken 等[80]提出概率代數(shù)分析方法，允許方程以低于1 的概率成立，但僅考慮了概率代數(shù)分析的應(yīng)用可能性。如何求解大規(guī)模概率非線性方程組仍然是個(gè)公開問(wèn)題。

4.3 小結(jié)

猜測(cè)確定分析是一類一般化的流密碼分析方法，可以應(yīng)用于分析不同類型的流密碼?？焖俅鷶?shù)分析方法主要適用于濾波函數(shù)型流密碼算法，或者FSM 中記憶單元很少的流密碼算法。相比于代數(shù)分析，快速代數(shù)分析改進(jìn)了代數(shù)方程的生成方式，但是對(duì)密鑰流的要求提高了。

表5 給出了基于差分性質(zhì)分析方法的部分典型應(yīng)用。

表5 基于差分性質(zhì)分析方法的部分典型應(yīng)用

公開流密碼算法在設(shè)計(jì)上一般采用較大的狀態(tài)，并結(jié)合自動(dòng)化搜索等方式評(píng)估內(nèi)部狀態(tài)之間的依賴性，以提高抵抗猜測(cè)確定分析的能力。而增強(qiáng)FSM更新函數(shù)的性質(zhì)（如代數(shù)次數(shù)）并結(jié)合較大規(guī)模的FSM 狀態(tài)，可增強(qiáng)抵抗代數(shù)分析類方法的能力。

目前，猜測(cè)確定分析最優(yōu)猜測(cè)集的選取是一個(gè)值得研究的課題。近年來(lái)，采用自動(dòng)化搜索技術(shù)（如MILP 建模）搜索最優(yōu)猜測(cè)集的技術(shù)發(fā)展很快，往往可以獲得更優(yōu)更精細(xì)的結(jié)果。對(duì)于現(xiàn)代流密碼來(lái)說(shuō)，單純地猜測(cè)確定分析、代數(shù)分析的分析效果可能不能令人滿意，但這些技術(shù)與其他分析方法結(jié)合使用有可能得到更好的分析結(jié)果。這是代數(shù)分析和猜測(cè)確定分析中一個(gè)值得研究的課題。

表6 簡(jiǎn)單總結(jié)了基于代數(shù)方程組流密碼分析方法的特點(diǎn)。

表6 基于代數(shù)方程組流密碼分析方法的特點(diǎn)

5 基于時(shí)間存儲(chǔ)數(shù)據(jù)折中的分析方法

時(shí)間存儲(chǔ)數(shù)據(jù)折中分析方法最早由Hellman[82]提出并應(yīng)用于分析分組密碼算法。隨后Biryukov 等[83]將此方法用于分析流密碼，也稱為BSW 時(shí)間存儲(chǔ)數(shù)據(jù)折中分析，其基本原理如下。

令N表示內(nèi)部狀態(tài)大小，P表示預(yù)計(jì)算階段時(shí)間，M表示存儲(chǔ)空間大小，T表示在線階段時(shí)間，D表示數(shù)據(jù)量大小，fi表示從內(nèi)部狀態(tài)到密鑰流前綴的函數(shù)，目標(biāo)是建立一個(gè)離線表以盡可能大地覆蓋內(nèi)部狀態(tài)空間。因?yàn)閷?duì)于流密碼算法，部分重疊的密鑰流前綴并不意味著內(nèi)部狀態(tài)也相鄰，所以可以把內(nèi)部狀態(tài)看作隨機(jī)點(diǎn)。如果D個(gè)前綴中有一個(gè)可以在離線表中找到，則可以回溯表中的那條鏈以恢復(fù)內(nèi)部狀態(tài)。因此，離線表需要覆蓋的空間大小變?yōu)?。同時(shí)，若Hellman 時(shí)間存儲(chǔ)數(shù)據(jù)折中離線表中包含t個(gè)m×t的矩陣，且滿足生日終止規(guī)則mt2=N，在TMDTO 中，矩陣大小不變，但數(shù)量變?yōu)?，因此仍然滿足mt2=N。由于每個(gè)矩陣大小仍然為m×t，但數(shù)量減少了，因此存儲(chǔ)空間大小降低為，預(yù)計(jì)算的時(shí)間也降低為。根據(jù)生日終止規(guī)則，可以得到新的折中曲線TM2D2=N2。

為了避免在線階段頻繁查詢離線表，在TMDTO 方法中引入特殊點(diǎn)技術(shù)，即只有迭代生成特殊點(diǎn)時(shí)才查詢離線表，但折中曲線仍然不變。同時(shí)，可以采用BSW 采樣技術(shù)，使T的選擇更加靈活[84]。BSW 采樣的基本思想是在很多流密碼中，在輸出下一比特密鑰流前，內(nèi)部狀態(tài)更新有限。因此，就可以找到所有的能夠生成kbit 全0 密鑰流的特殊狀態(tài)。若流密碼內(nèi)部狀態(tài)大小為N=2n，即內(nèi)部狀態(tài)共nbit，則稱每個(gè)特殊狀態(tài)有一個(gè)(n-k)bit 的縮略名。由此可以導(dǎo)出一個(gè)從內(nèi)部狀態(tài)到密鑰流的隨機(jī)映射，此時(shí)折中曲線仍然不變。

Maitra 等[85]提出可以通過(guò)固定一些比特以更容易地得到特殊狀態(tài)，并可以通過(guò)密鑰流導(dǎo)出部分內(nèi)部狀態(tài)值，但是該方法會(huì)增加數(shù)據(jù)量。

相比其他分析方法，時(shí)間存儲(chǔ)數(shù)據(jù)折中分析方法是一類一般化的分析方法，它將流密碼算法看作一個(gè)黑盒，并不注重算法邏輯。該分析方法的復(fù)雜度度量單位可以是一次加密，因而受算法的工作效率影響很大。

時(shí)間存儲(chǔ)數(shù)據(jù)折中分析方法的典型應(yīng)用包括對(duì)輕量級(jí)算法Sprout、Lizard 等的分析，如表7 所示。值得注意的是，對(duì)于Sprout 算法的分析，盡管該算法采用了2 種狀態(tài)：內(nèi)部狀態(tài)和密鑰狀態(tài)，但是仍然不能抵抗TMDTO 分析。

表7 基于時(shí)間存儲(chǔ)數(shù)據(jù)折中分析方法的部分典型應(yīng)用

為了防護(hù)TMDTO 分析，公開非輕量流密碼算法一般遵循“內(nèi)部狀態(tài)大小至少是密鑰長(zhǎng)度的2 倍”準(zhǔn)則。

雖然Sprout 算法不能抵抗TMDTO 分析，但后來(lái)設(shè)計(jì)的一些小狀態(tài)輕量級(jí)流密碼算法吸取有關(guān)設(shè)計(jì)經(jīng)驗(yàn)，采用了一些特殊的設(shè)計(jì)，也聲稱具有良好的抵抗TMDTO 分析的效果。這類算法的分析是一個(gè)值得思考的問(wèn)題。

表8 總結(jié)了基于時(shí)間存儲(chǔ)數(shù)據(jù)折中的流密碼分析方法的特點(diǎn)。

表8 基于時(shí)間存儲(chǔ)數(shù)據(jù)折中的流密碼分析方法的特點(diǎn)

6 未來(lái)研究展望

流密碼分析方法已經(jīng)歷了幾十年的發(fā)展，至今仍在不斷更新完善?；仡櫰浒l(fā)展歷程，注意到近年來(lái)的流密碼分析方法研究呈現(xiàn)出一些特點(diǎn)。這些特點(diǎn)可能會(huì)進(jìn)一步影響未來(lái)一段時(shí)間流密碼分析方法的發(fā)展。

1) 尋找新的密碼性質(zhì)，改進(jìn)流密碼分析方法。從流密碼分析方法發(fā)展過(guò)程中可以發(fā)現(xiàn)，每當(dāng)有可利用的新性質(zhì)時(shí)，流密碼的分析方法都會(huì)快速發(fā)展。因此，尋找新的密碼性質(zhì)，改進(jìn)流密碼分析方法仍然是重要的研究方向。例如，Todo等[42]發(fā)現(xiàn)了線性掩碼在限域上的交換性，并利用這種性質(zhì)提出了一種新的快速相關(guān)分析方法。這類研究需要建立在對(duì)流密碼分析方法深刻理解和細(xì)致觀察的基礎(chǔ)上。

2) 發(fā)掘不同密碼分析技術(shù)之間的關(guān)聯(lián)性，改進(jìn)流密碼分析方法。不同的密碼分析方法采用不同技術(shù)對(duì)同一密碼算法進(jìn)行分析，這些分析方法之間可能存在聯(lián)系。這種聯(lián)系已經(jīng)在分組密碼分析方法中被發(fā)現(xiàn)，并得到了大量研究，例如，分組密碼不可能差分分析、積分分析、零相關(guān)分析等方法之間的聯(lián)系。在流密碼分析中的一個(gè)典型例子是立方分析。一方面，自立方分析提出后，立方分析主要受限于實(shí)驗(yàn)規(guī)模對(duì)立方大小的限制[52]。另一方面，Todo[17]提出了針對(duì)分組密碼的基于劃分性質(zhì)的廣義積分分析，隨后Xiang 等[58]提出了劃分跡的概念并將MILP技術(shù)引入劃分性質(zhì)的傳播評(píng)估中。注意到，立方分析與積分分析技術(shù)具有密切聯(lián)系，Todo 等[57]將劃分性質(zhì)引入立方分析中，并結(jié)合MILP 技術(shù)用于恢復(fù)超級(jí)多項(xiàng)式。這是立方分析的一個(gè)里程碑式的發(fā)展。因此，發(fā)掘不同密碼分析技術(shù)之間的關(guān)聯(lián)性，對(duì)于改進(jìn)現(xiàn)有流密碼分析方法具有重要作用。這可能是流密碼分析的一個(gè)突破方向。

3) 改進(jìn)自動(dòng)化搜索建模技術(shù)，提高流密碼分析效果。目前，將流密碼分析中的問(wèn)題轉(zhuǎn)化為MILP模型或SAT/SMT 模型，尋求高質(zhì)量解的技術(shù)在流密碼分析中的應(yīng)用越來(lái)越廣泛。例如，應(yīng)用于相關(guān)分析中尋找好的線性逼近關(guān)系[87]，應(yīng)用于立方分析中恢復(fù)超級(jí)多項(xiàng)式[57]，應(yīng)用于猜測(cè)確定分析中尋找好的猜測(cè)集[88]等，同時(shí)密碼分析中的需求也促進(jìn)了MILP 建模技術(shù)的發(fā)展[89]?？梢哉f(shuō)，流密碼分析方法與自動(dòng)化分析技術(shù)結(jié)合越來(lái)越緊密。目前，一般通過(guò)約束關(guān)系刻畫具體流密碼算法中運(yùn)算環(huán)節(jié)的密碼性質(zhì)的方式建立模型。例如，刻畫S 盒的線性逼近分布表。因此，建立更加精確的自動(dòng)化模型，優(yōu)化已有的分析方法仍然是一個(gè)值得研究的方向。

4) 組合使用多種流密碼分析技術(shù)。近年來(lái)，有些流密碼的分析已不再局限于單一方法，往往在一個(gè)算法的分析中組合使用多種分析技術(shù)。例如，猜測(cè)確定分析與線性分析和中間相遇的組合使用[90]、中間相遇與立方分析的結(jié)合[91]等。

5) 探索建立關(guān)于流密碼分析方法更深刻的理論。Beyne[92]提出了線性分析的幾何方法理論。該理論給出了常見的分組密碼線性分析技術(shù)及其變體的統(tǒng)一描述，例如，一般線性分析、多維線性分析、不變子空間分析、非線性不變量分析等分析方法和技術(shù)。這種數(shù)學(xué)化的刻畫對(duì)深刻認(rèn)識(shí)線性分析的基礎(chǔ)和不同分析方法之間的內(nèi)在聯(lián)系具有重要作用。一些流密碼分析技術(shù)與分組密碼分析技術(shù)之間具有密切的聯(lián)系。建立類似的理論也將是流密碼分析方法發(fā)展過(guò)程中的重要進(jìn)展。

綜上所述，流密碼分析方法方面還有很多值得研究的方向[93-95]。未來(lái)，還需要研究者不斷加深對(duì)流密碼分析的認(rèn)識(shí)，以創(chuàng)新流密碼分析方法。

7 結(jié)束語(yǔ)

研究流密碼分析方法不僅可以促進(jìn)密碼分析技術(shù)的進(jìn)步，對(duì)設(shè)計(jì)安全、高效的流密碼算法也具有重要的指導(dǎo)價(jià)值。流密碼分析方法種類多，差異明顯。本文對(duì)目前常見的流密碼分析方法按照技術(shù)特點(diǎn)的不同進(jìn)行了分類匯總，并闡述了4 大類10余種流密碼分析方法的基本原理、主要技術(shù)以及研究進(jìn)展。同時(shí)，也對(duì)流密碼分析方法進(jìn)行了展望。