針對流密碼HC-256'的區分攻擊

李順波 胡予濮 王 艷

(西安電子科技大學計算機網絡與信息安全教育部重點實驗室 西安 710071）

1 引言

為進一步推進流密碼的研究，2004年歐洲啟動了eSTREAM計劃[1]，主要任務是征集安全快速的流密碼算法，至2005年4月，共征集到34個候選算法。HC-256[2]和HC-128[3]都是基于表驅動的候選流密碼算法，由于其運行速度快、安全性能高，至今未見有效的分析方法。為了避免從系統內部恢復出初始密鑰，文獻[2]設計了HC-256的改進算法——

HC-256'，其內部狀態P和Q每運行一步就交替更新一次，具有更高的安全性；還未發現任何關于HC-256'的分析結果，其安全性分析已經成為一個熱點問題。

文獻[4]利用線性逼近區分攻擊對流密碼HC-256進行了安全性分析，需要約279.82 bit的密鑰流字節就可以把密鑰流序列和隨機序列區分；然而對HC-256的改進算法HC-256'能否利用區分攻擊進行安全性分析是一個有意義的研究課題。本文提出了一種針對流密碼HC-256′的線性區分攻擊。首先利用假設檢驗給出了區分優勢的計算公式；然后，對偶數位置上的輸出序列字節利用不同的非線性函數表示不同的內部狀態更新函數，在最低位比特通過線性逼近構建幾乎最優區分器。結果表明，需要約 2281bit就能以0.9545的區分優勢將HC-256'的密鑰流序列和隨機序列區分開。

2 基礎知識

2.1 區分攻擊

區分攻擊[5](distinguishing attack)是一種靈活有效的密碼分析方法，2002年由Coppersmith等人提出，其基本思想是通過觀察某些輸入與輸出比特之間的關系來判別這些比特是來自真隨機源還是來自密碼，將其轉化為一個假設檢驗問題。盡管從攻擊結果上看，區分攻擊是最弱的，但面對區分攻擊，密碼設計者往往很難做到疏而不漏。因此區分攻擊已經成為判定密碼性質好壞的一個嚴格的安全標準。許多流密碼算法都遭到區分攻擊的威脅，如Shannon[6,7], SN3[8]和 RC4[9,10]等。

區分攻擊的關鍵是尋找適當的區分器，更具體地說，區分器是指區分一串密鑰流和一串真正隨機序列的一種有效算法，且以密鑰流的某些弱點為基礎，而正是這些弱點體現了給定的密鑰流具有的不隨機性。區分器就是利用這些弱點來設計算法的。

一個區分器D將密鑰流生成器與隨機生成器區分開的成功性稱為區分優勢(或成功概率)，由以下兩個概率決定：

(1)當所給序列來自于密鑰流生成器時，回答為“密鑰流序列”的概率P0(D)；

(2)當所給序列來自于隨機生成器時，回答為“密鑰流序列”的概率P1(D)。

定義2[7]設Pr(D)為一個逼近D成立的概率，則偏差e= 2 Pr(D)- 1，即Pr(D) = ( 1/2)(1 +e)。

2.2 假設檢驗

設原假設H0：序列X來自密鑰流生成器，即PX=P0(zi)；

備擇假設H1：序列X來自隨機生成器，即PX=P1(zi)。

區分攻擊算法

輸入：Nbit序列 (z0,z1,… ,zN-1)

輸出：序列來自隨機序列還是密鑰生成序列

(2)如果LLR≥0，輸出“序列來自密碼”，

否則，輸出“序列來自隨機序列”。

由于統計量D(zi) ∈ { 0,1}服從二項分布，且是獨立同分布的隨機變量。當N無限增大時，利用中心極限定理，該二項分布無限趨于標準正態分布，

所以

表1 P j ( zi )和εz的取值

引理1[2]設H是mbit輸入nbit輸出的S-盒，且m≥n。若x1,x2是H的兩個隨機mbit輸入，則Pr[H(x1) =H(x2)]= 2-m+ 2-n- 2-m-n。

3 流密碼HC-256′

流密碼HC-256'是HC-256的改進算法，都是文獻[2]中提出的面向軟件實現的快速同步流密碼，256 bit密鑰(K)和256 bit初始化向量(IV)，內部狀態P和Q都為1024 bit。HC-256'借鑒了RC4的思想，同時引入了面向字節的非線性函數來更新系統的內部狀態，運行速度很快，具有更高的安全性。其初始化和非線性函數都和 HC-256是一樣的；但唯一的差別在于密鑰流生成算法。HC-256的密鑰流生成算法是連續運行1024步更新一次狀態P，再連續運行1024步更新另一個狀態Q。而HC-256'的密鑰流生成算法是內部狀態P和Q每運行一步就需要更新一次。具體算法如3.1節-3.3節所述。

3.1 運算符號

流密碼HC-256'中的運算符號標注如下：

+：x+y表示x+ym od232；

>> ：右平移算子，x＞＞n表示x向右平移nbit；

>>> ：右循環算子，x＞＞＞n表示x向右循環移動nbit，即(x＞＞n) ⊕ (x＜＜ ( 32 -n)), 0≤n＜ 3 2。

3.2 密鑰初始化

密鑰初始化過程中，內部狀態是密鑰和初始化向量的級聯，256 bit的密鑰和初始化向量被分為8個32 bit的字，記為：K=K0||K1||… ||K7和IV=IV0||IV1||… ||IV7。將密鑰和初始化向量擴展到2560個數組Wi(0 ≤i≤2559)

其中

其中h1,h2表示32 bit輸入和32 bit輸出的S盒，32 bit字x=x3||x2||x1||x0中x0表示x的最低位字節(least significant bit)，x3表示x的最高位字節(most significant bit)。

兩數組P和Q表示32 bit內部狀態，分別為：P[i]=Wi+512,Q[i]=Wi+1536, 0 ≤i≤ 1 023。

3.3 密鑰流生成器

初始化4096步后輸出密鑰流比特si，生成的密鑰流長度為 2128bit；其算法如下：

4 區分攻擊HC-256′

本節利用區分攻擊分析流密碼HC-256'的安全性，關鍵是尋找HC-256'密鑰流生成器的弱點，而其困難在于內部狀態P和Q每運行一步就要更新一次，P和Q更新時的非線性函數是不同的。本文提出了一種新的區分攻擊思想，把問題轉化為判斷在偶數(奇數)位置上的輸出序列是來自密鑰流序列還是隨機序列。利用不同的非線性函數來表示不同的內部狀態更新函數，旨在討論在最低位比特狀態P和密鑰流s2i的弱點。

已知在偶數位置上的密鑰流輸出算法為

當10 ≤(imod1024) ＜ 1 023時，記zi=P[i12]為32 bit字，P[im od1024]=s2i⊕h1(zi)，所以P[i10]=P[(i- 1 0)mod1024]=。同理，

因此在偶數位置上的反饋函數可以寫成如下形式：

對于模 232加法，直接把式(1)的密鑰流序列區分開是非常困難的。但值得注意的是，在最低位比特，運算‘+’和‘⊕’是一樣的。因此，利用函數g1(x)，在最低位比特式(1)可以寫成下列形式：

同理，當1024 ·a+ 1 0 ≤i,j＜ 1 024 ·a+ 1 023，且i≠j時有

等價于下面等式成立：

根據上述推理，式(4)就是我們構造的區分器。式(4)成立的概率等價于式(6)成立的概率。而式(6)左邊含有138 bit變量zi-3,zi-10,zi-1023,zi-1024和ri，記x1=zi-3||zi-10||zi-1023||zi-1024||ri。式(6)右邊也含有138 bit變量zj-3,zj-10,zj-1023,zj-1024和rj；記為x2=zj-3||zj-10||zj-1023||zj-1024||rj。我們可以將式(6)兩邊看作兩個S-盒函數，要使得式(6)成立，就要滿足以 138 bit為變量的兩個 S-盒相等，即H(x1)=H(x2)。其中H表示隨機選擇的138 bit輸入-1 bit輸出的 S-盒。利用引理 1，式(6)成立的概率為1/2 + 2-139。

因此，區分器式(4)成立的概率為p=1/2+ 2-139= ( 1/2)(1 + 2-138)。所以該區分器的偏差為e= 2-138。利用定理1，當密鑰流比特N=e-2=2276時，該區分攻擊的區分優勢為 0.3928；當N=16·e-2= 2280時，該攻擊以 0.9545的區分優勢把密鑰流序列和隨機序列區分開。

然而，該區分攻擊只討論了在偶數位置上HC-256'的安全性，用同樣的方法可以分析在奇數位置上的安全性。綜上所述，需要約 2 ·N=2281bit密鑰流就能以0.9545的區分優勢把流密碼HC-256'與隨機序列區分開。

5 結束語

本文利用線性區分攻擊分析了流密碼HC-256'的安全性，通過線性逼近內部狀態尋找密鑰流生成器的弱點建立區分器，區分密鑰流序列和隨機序列需要約 2281bit；且該攻擊的區分優勢為0.9545。雖然該結果超過了密鑰流序列的長度，但從理論上回答了2009年Sekar等人提出的開放問題。然而，近年來對HC-256的簡化算法HC-128的研究僅限于文獻[14-17]，能否利用區分攻擊對流密碼 HC-128進行有效的安全性分析仍然是一個有意義的問題，值得做進一步研究。

[1]eSTREAM—the Ecrypt Stream Cipher Project[EB]. http://www.ecrypt.eu.org /stream/, 2005.

[2]Wu Hong-jun. A new stream cipher HC-256[C]. FSE 2004,New Delhi, India, 2004, 3017: 524-538.

[3]Wu Hong-jun. The stream cipher HC-128[C]. New Stream Cipher Designs, 2008, 4986: 39-47.

[4]Sekar G and Preneel B. Improved distinguishing attacks on HC-256[C]. IWSEC 2009, Toyama, Japan, 2009, 5824: 38-52.

[5]Coppersmith D, Halevi S, and Jutla C. Cryptanalysis of stream ciphers with linear masking[C]. CRYPTO 2002, Santa Barbara, California, 2002, 2442: 515-532.

[6]Ahmadian Z, Mohajeri J, Salmasizadeh M,et al.. A practical distinguisher for the Shannon cipher[J].The Journal of Systems and Software, 2010, 83(4): 543-547.

[7]常亞勤, 金晨輝. 對Shannon算法的線性區分攻擊[J]. 電子與信息學報, 2011, 33(1): 190-193.

Chang Ya-qin and Jin Chen-hui. Linear distinguishing attack on Shannon algorithm[J].Journal of Electronics&Information Technology, 2011, 33(1): 190-193.

[8]Keller N and Miller S D. Distinguishing attack on stream ciphers based on arrays of pseudo-random words[J].Information Processing Letters, 2010, 110(4): 129-132.

[9]Maitra S, Paul G, and Gupta S. Attack on broadcast RC4 revisited[C]. FSE 2011, Lyngby, Denmark, 2011, 6733:199-217.

[10]Sepehrdad P, Vaudenay S, and Vuagnoux M. Statistical attack on RC4 distinguishing WPA[C]. EUROCRYPT 2011,Tallinn, 2011, 6632: 343-363.

[11]Baigneres T, Junod P, and Vandenay S. How far can we go beyond linear cryptanalysis[C]. Asiacrypt 2004, Jeju Island,Korea, 2004, 3329: 432-450.

[12]Hell M, Johansson T, and Brynielsson L. An overview of distinguishing attacks on stream ciphers[J].Cryptography and Communications, 2009, 1(1): 71-94.

[13]Crowley P. Improved cryptanalysis of Py[C]. Workshop on the State of the Art of Stream Ciphers (SASC 2006), Leuven,Belgium, 2006: 52-60.

[14]Liu Yun-yi and Qin Tuan-fa. The key and IV setup of the stream ciphers HC-256 and HC-128[C]. Networks Security,Wireless Communications and Trusted Computing, Wuhan,IEEE, 2009: 430-433.

[15]Maitra S, Paul G, and Raizada S. Some observations on HC-128[J].Designs, Codes and Cryptography, 2010, 57(3):1-15.

[16]Kircanski A and Youssef A M. Differential fault analysis of HC-128[C]. Africrypt 2010, South Africa, 2010, 6055:261-278.

[17]Paul G, Maitra S, and Raizada S. A combinatorial analysis of HC-128[R]. Cryptology ePrint Archive, Report 2010/387,2010.