針對流密碼HC-256'的區(qū)分攻擊

李順波 胡予濮 王 艷

(西安電子科技大學(xué)計算機(jī)網(wǎng)絡(luò)與信息安全教育部重點實驗室 西安 710071）

1 引言

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

HC-256'，其內(nèi)部狀態(tài)P和Q每運(yùn)行一步就交替更新一次，具有更高的安全性；還未發(fā)現(xiàn)任何關(guān)于HC-256'的分析結(jié)果，其安全性分析已經(jīng)成為一個熱點問題。

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

2 基礎(chǔ)知識

2.1 區(qū)分攻擊

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

區(qū)分攻擊的關(guān)鍵是尋找適當(dāng)?shù)膮^(qū)分器，更具體地說，區(qū)分器是指區(qū)分一串密鑰流和一串真正隨機(jī)序列的一種有效算法，且以密鑰流的某些弱點為基礎(chǔ)，而正是這些弱點體現(xiàn)了給定的密鑰流具有的不隨機(jī)性。區(qū)分器就是利用這些弱點來設(shè)計算法的。

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

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

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

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

2.2 假設(shè)檢驗

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

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

區(qū)分攻擊算法

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

輸出：序列來自隨機(jī)序列還是密鑰生成序列

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

否則，輸出“序列來自隨機(jī)序列”。

由于統(tǒng)計量D(zi) ∈ { 0,1}服從二項分布，且是獨立同分布的隨機(jī)變量。當(dāng)N無限增大時，利用中心極限定理，該二項分布無限趨于標(biāo)準(zhǔn)正態(tài)分布，

所以

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

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

3 流密碼HC-256′

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

3.1 運(yùn)算符號

流密碼HC-256'中的運(yùn)算符號標(biāo)注如下：

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

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

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

3.2 密鑰初始化

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

其中

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

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

3.3 密鑰流生成器

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

4 區(qū)分攻擊HC-256′

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

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

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

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

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

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

等價于下面等式成立：

根據(jù)上述推理，式(4)就是我們構(gòu)造的區(qū)分器。式(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-盒函數(shù)，要使得式(6)成立，就要滿足以 138 bit為變量的兩個 S-盒相等，即H(x1)=H(x2)。其中H表示隨機(jī)選擇的138 bit輸入-1 bit輸出的 S-盒。利用引理 1，式(6)成立的概率為1/2 + 2-139。

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

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

5 結(jié)束語

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

[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算法的線性區(qū)分攻擊[J]. 電子與信息學(xué)報, 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.