吳泳鋼，古天龍，徐周波

(桂林電子科技大學(xué) 廣西可信軟件重點(diǎn)實(shí)驗(yàn)室，廣西 桂林　541004)

?

SNOW 3G加密算法的BDD攻擊

吳泳鋼，古天龍，徐周波

(桂林電子科技大學(xué) 廣西可信軟件重點(diǎn)實(shí)驗(yàn)室，廣西 桂林541004)

為了對SNOW 3G加密算法進(jìn)行安全性分析，提出一種改進(jìn)的BDD攻擊。依據(jù)線性反饋移位寄存器的反饋多項(xiàng)式選擇特定內(nèi)部比特流構(gòu)造第一類OBDD。利用猜測決定攻擊的思想，猜測若干有限狀態(tài)機(jī)的內(nèi)部狀態(tài)，并尋找其與SNOW 3G加密算法輸出的密鑰流之間的聯(lián)系來推測密碼器內(nèi)部比特流，以此構(gòu)造第二類OBDD。將2類OBDD進(jìn)行交集操作得到SNOW 3G加密算法的初始密鑰。分析結(jié)果表明，改進(jìn)的BDD攻擊優(yōu)于原BDD攻擊，對SNOW 3G加密算法的安全性更具威脅。

密碼分析；BDD攻擊；SNOW 3G加密算法；猜測決定攻擊

隨著通信技術(shù)的日益普及，人們對通信過程的保密性和完整性提出更高的要求。3G網(wǎng)絡(luò)保留了2G網(wǎng)絡(luò)的安全性優(yōu)點(diǎn)，并且提出保證空中接口數(shù)據(jù)傳輸保密性和完整性的要求，使數(shù)據(jù)不被篡改和竊聽。LTE系統(tǒng)沿用了第三代移動通信的安全策略，采用SNOW 3G加密算法，它不僅具有強(qiáng)大的抗攻擊能力，而且能適應(yīng)高速率通信。

在3GPP安全體系中，標(biāo)準(zhǔn)化算法包括保密性算法(UEA2)和完整性算法(UIA2)，這2種算法的核心是SNOW 3G加密算法。SNOW 3G加密算法屬于流加密算法，即將明文的比特流與密鑰生成器生成的密鑰流進(jìn)行異或操作，從而生成所需密文，實(shí)現(xiàn)加密。解密時將相同的密鑰流與密文再進(jìn)行一次異或操作，就可得到明文。SNOW 3G加密算法是基于線性反饋移位寄存器(linear feedback shift register，簡稱LFSR)的密鑰流發(fā)生器。其主要原理是：由一個16級的線性反饋移位寄存器生成偽隨機(jī)序列，該序列通過一個32 bit有限狀態(tài)機(jī)進(jìn)行變換，從而形成用于加密的密鑰流。

SNOW 3G加密算法是現(xiàn)今移動通信的主流加密算法，對其安全性的研究一直都是一個熱點(diǎn)。對SNOW 3G加密算法進(jìn)行攻擊，可以探究它對外部威脅的抵抗能力，確認(rèn)它的安全性。文獻(xiàn)[1]針對SNOW 3G加密算法進(jìn)行線性區(qū)分攻擊，所需的密鑰流和計算復(fù)雜度皆為2274。文獻(xiàn)[2]構(gòu)造了一個Multiset區(qū)分器，并利用此區(qū)分器對SNOW 3G加密算法(簡化版)進(jìn)行區(qū)分攻擊，計算復(fù)雜度為28。文獻(xiàn)[3]對SNOW 3G加密算法進(jìn)行了猜測決定攻擊，計算復(fù)雜度為2320。

BDD攻擊是2002年Krause[4]首先提出的，主要用于對基于LFSR密鑰流生成器進(jìn)行安全分析。其主要原理是利用BDD分析優(yōu)化搜索路徑，在圖生成的同時排除一些不可能的情況，從而降低攻擊所需要的算法復(fù)雜度，在藍(lán)牙的E0加密算法、手機(jī)GSM網(wǎng)絡(luò)的A5/1算法、自收縮序列生成器上均取得了良好的攻擊效果。鑒于此，利用BDD攻擊，同時結(jié)合猜測決定攻擊算法的思想，對SNOW 3G加密算法進(jìn)行攻擊。相較于原BDD攻擊，改進(jìn)后的BDD攻擊大大降低了計算復(fù)雜度和所需的密鑰流，對SNOW 3G加密算法的安全性更具威脅。

1　相關(guān)知識

1.1SNOW 3G加密算法[5]

SNOW 3G加密算法是基于字的流密碼加密算法，利用128 bit密鑰和128 bit初始化變量，輸出一串32 bit數(shù)據(jù)，用于加密明文流。SNOW 3G加密算法是從SNOW 2.0算法改進(jìn)而來，能有效保護(hù)通信網(wǎng)絡(luò)中的數(shù)據(jù)安全。SNOW 3G加密算法原理如圖1所示。

圖1　SNOW 3G加密算法原理Fig.1　Principle of SNOW 3G encryption algorithm

SNOW 3G加密算法由有限域GF(223)上的16級LFSR和有限狀態(tài)機(jī)(FSM)兩部分組成。LFSR由16個單元組成，每個單元包含32 bit數(shù)據(jù)，共512 bit。在每個時鐘t，LFSR輸出其內(nèi)部狀態(tài)st。LFSR內(nèi)部狀態(tài)的反饋多項(xiàng)式為：

(1)

式(1)基于有限域GF(223)上的本原多項(xiàng)式為：

其中：α為有限域GF(28)上的多項(xiàng)式

的一個根；β為在有限域GF(2)上的多項(xiàng)式

x8+x7+x5+x3+1

的一個根。FSM包括R1、R2和R3三個寄存器，大小均為32 bit，用于保存FSM的內(nèi)部狀態(tài)。記FSM的輸出為ft，密鑰發(fā)生器的輸出為zt，t時刻R1、R2、R3的內(nèi)部狀態(tài)分別為R1,t、R2,t、R3,t，則存在輸出規(guī)則：

zt=ft⊕st=(st+15□+R1,t)⊕R2,t⊕st，

(2)

其中“□+”表示模232整數(shù)加。R1、R2和R3的刷新變換規(guī)則為：

R1,t+1=(st+5⊕R3,t)□+R2,t，

(3)

R2,t+1=S1(R1,t)，

(4)

R3,t+1=S2(R2,t)，

(5)

其中S1、S2為32×32的S盒變換。

1.2OBDD

有序二叉決策圖(ordered binary decision diagrams，簡稱OBDD)是布爾函數(shù)的一種有效圖形、數(shù)學(xué)描述技術(shù)。

定義[6]對于從{0,1}n到{0,1}的布爾函數(shù)f(x1,x2,…,xn)和給定變量序π，在表示布爾函數(shù)族#f(x1,x2,…,xn)的二叉樹圖(BDD)中，若任一有向路徑上的變量x1,x2,…,xn均以變量序π所規(guī)定的順序依次出現(xiàn)，則稱該BDD為布爾函數(shù)f(x1,x2,…,xn)的OBDD。

OBDD是一個有向無環(huán)圖，節(jié)點(diǎn)分為根節(jié)點(diǎn)、終節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)3類。其中終節(jié)點(diǎn)有且僅有2個，用來表示布爾常量的0、1。每個非終節(jié)點(diǎn)都有2條輸出的分支分別連接到下一節(jié)點(diǎn)，即0分支(虛線)和1分支(實(shí)線)。在OBDD任何一條路徑上，每個變量都依照變量序π所限定的順序出現(xiàn)一次。布爾函數(shù)f(x1,x2,x3)=(x1+x2)x3在變量序π：x1

圖2　布爾函數(shù)f(x1,x2,x3)=(x1+x2)x3的OBDD表示Fig.2　OBDD for Boolean function f(x1,x2,x3)=(x1+x2)x3

1.3基于BDD的密碼分析技術(shù)

由于BDD能對所有有序出現(xiàn)的輸入變量進(jìn)行合并，有效地將其簡化，并可對所有滿足要求的情況進(jìn)行窮舉，在密碼分析領(lǐng)域具有較大的作用。BDD攻擊通過給定的密鑰流z，計算LFSRs的初始狀態(tài)x。對于一個LFSR密鑰流發(fā)生器，其生成規(guī)則為z=C(L(x))，其中L表示由一個或多個LFSR組成的線性比特流發(fā)生器，C:{0,1}n→{0,1}m為非線性壓縮函數(shù)。非線性壓縮函數(shù)的作用是將內(nèi)部的線性比特流L(x)轉(zhuǎn)化為非線性的密鑰流z。一般來說，包含n個LFSR的發(fā)生器產(chǎn)生內(nèi)部比特流的規(guī)則為L(x)=L0(x),L1(x),…,Lm(x)[7]。LFSR密鑰流發(fā)生器結(jié)構(gòu)如圖3所示。

圖3　LFSR密鑰流發(fā)生器結(jié)構(gòu)Fig.3　Structure of LFSR stream ciphers

從圖3可看出，LFSR的初始狀態(tài)包含在輸出的內(nèi)部線性比特流中，即L(x)的前幾位包含LFSR的密鑰x。通過給定的密鑰流z，求滿足z=C(L(x))的密鑰x。此問題可等價為尋找一個最小的自由二元決策圖 (free binary decision diagram，簡稱FBDD)來判斷密鑰x是否滿足z=C(L(x))。

BDD攻擊的具體步驟如下[8-9]：

1)對于任意的m≥n，用Tm表示一個最小的FBDD。此FBDD根據(jù)LFSRs的反饋多項(xiàng)式構(gòu)造，用來判斷內(nèi)部比特流是否符合LFSR的反饋多項(xiàng)式。

2)對于任意的m≥1，用Qm表示另一個最小的FBDD。此FBDD根據(jù)LFSR輸出的內(nèi)部比特流L(x)構(gòu)造，用來判斷C(L(x))是否與密鑰流z相符。

3)構(gòu)造第3個FBDD，用Pm表示。其是Qm和Tm交集操作的結(jié)果，也就是Pm=SYNTH(Qm,Tm)，其中SYNTH為BDD的交集操作，m、n分別為BDD變量的個數(shù)和密鑰x的個數(shù)。

BDD攻擊偽代碼[10]如下：

P←Qn;

form←n+1 tom*do:

P←(P∧Qm∧Tm);

returnz*thatP(z*)=1。

其中：m*為內(nèi)部比特的長度；z*為LFSR的初始密鑰。

2　SNOW 3G加密算法的BDD攻擊

2.1攻擊條件

在SNOW 3G加密算法中有5個表達(dá)式：LFSR的各狀態(tài)之間的關(guān)系，即式(1)；FSM與LFSR之間的關(guān)系，即式(2)；SNOW 3G加密算法中的3個32位寄存器R1、R2、R3所包含的狀態(tài)之間的轉(zhuǎn)化關(guān)系，即式(3)、(4)、(5)。

SNOW 3G加密算法的內(nèi)部狀態(tài)由FSM的寄存器R1、R2、R3所決定。內(nèi)部狀態(tài)經(jīng)過32 bit32 bit 的S盒變換和LFSR內(nèi)部狀態(tài)的混淆，使得FSM的當(dāng)前狀態(tài)與下一狀態(tài)之間的關(guān)系變得十分復(fù)雜，因此引入猜測決定攻擊的思想來應(yīng)對這一問題。猜測決定攻擊基本思想是：分析密碼器中的數(shù)學(xué)原理、內(nèi)部狀態(tài)、輸出密鑰流三者之間的關(guān)系，并猜測若干的內(nèi)部狀態(tài)作為假設(shè)條件，以推導(dǎo)出其他的內(nèi)部狀態(tài)，從而得到在當(dāng)前假設(shè)條件下輸出的密鑰流。該密鑰流與已知的密鑰流進(jìn)行比對，可判定假設(shè)條件的正誤。

BDD攻擊是一種狀態(tài)恢復(fù)攻擊，即根據(jù)輸出的密鑰流恢復(fù)密鑰發(fā)生器的初始狀態(tài)。因此，以輸出的密鑰流作為已知條件，可獲取密鑰發(fā)生器前8個時鐘輸出的密鑰流z0～z7。根據(jù)猜測決定攻擊的思想，猜測前11個時鐘R1的內(nèi)部狀態(tài)為R1,0～R1,10，將其作為假設(shè)條件。

2.2BDD生成過程

根據(jù)BDD攻擊的步驟，先生成第一類OBDD，將其表示為T。此OBDD是以LFSR輸出的特定內(nèi)部狀態(tài)st作為輸入，st的選取依據(jù)式(1)的規(guī)定。若作為輸入的st滿足式(1)，則在T中代表該組取值的路徑指向終節(jié)點(diǎn)1，否則，指向終節(jié)點(diǎn)0。也就是說，若t時刻st、st+2、st+11、st+16的某組取值滿足LFSR的反饋多項(xiàng)式，則在OBDD中，該組取值的路徑指向終節(jié)點(diǎn)1，否則指向終節(jié)點(diǎn)0。不同時刻存在不同的OBDD。

繼續(xù)構(gòu)建第2類OBDD，將其表示為Q，它是以LFSR的輸出內(nèi)部狀態(tài)st為核心構(gòu)成的。st由32 bit構(gòu)成，共有232種狀態(tài)。用OBDD結(jié)構(gòu)保存這32 bit所有可能的組成。為了描述方便，將此OBDD結(jié)構(gòu)稱為基礎(chǔ)鏈。當(dāng)前時刻的基礎(chǔ)鏈所包含的每條路徑都連接相應(yīng)的下一時刻的基礎(chǔ)鏈。因此，可用前7個時鐘的基礎(chǔ)鏈s0～s6組成初始Q。

由式(4)可知，從R1的內(nèi)部狀態(tài)R1,t可得到t+1時刻R2的內(nèi)部狀態(tài)R2,t+1。因此，根據(jù)已知假設(shè)條件R1,0～R1,10的取值，可求得R2,0～R2,9。同理依據(jù)式(5)，從R2的內(nèi)部狀態(tài)R2,t可得到t+1時刻R3的內(nèi)部狀態(tài)R3,t+1。根據(jù)R2,0～R2,9的取值，求得R3,1～R3,9。至此就獲得了攻擊所需要的所有內(nèi)部狀態(tài)。

依據(jù)式(3)，從t時刻R2、R3的內(nèi)部狀態(tài)R2,t、R3,t與t+1時刻R1的內(nèi)部狀態(tài)R1,t+1，可求得t+5時刻LFSR輸出的內(nèi)部狀態(tài)st+5。因此，由得到的R1、R2、R3內(nèi)部的狀態(tài)信息，可求得s7～s14的值，如表1所示。

表1　s7～s14推出過程

同樣，根據(jù)式(2)，利用已知的密鑰流z0～z7和R1、R2、R3內(nèi)部的狀態(tài)信息得到s15～s22的值，如表2所示。

表2　s15～s22推出過程

由s0～s6和s7～s22，可構(gòu)造出完整的Q。對T、Q進(jìn)行交集操作，最終得到P，即P=SYNTH(Q,T)。此交集的過程將大大簡化OBDD，從而剔除不正確的路徑，得到唯一一組路徑s0～s6，使P的取值為1。驗(yàn)證過程如表3所示。

表3　驗(yàn)證過程

交集過程的簡化原理為：選取s0與s1的一種可能情況，根據(jù)表3和式(1)，確定s2～s6的值，并判斷選取的s0、s1與求解結(jié)果間是否存在矛盾，若矛盾，則拋棄該組取值，反之，則保留。步驟1中，已知s16、s11和選取的s0，其中s16是由s1決定的，s11為現(xiàn)有條件下確定的值，則由式(1)可知當(dāng)前條件下s2的取值。以此類推，從步驟2～5求得現(xiàn)有條件下s3～s6的取值，然后，依據(jù)步驟6，求得s16。由式(2)可知，利用s16可推出s1，將其與選取的s1作比較，判斷是否矛盾：

1)若矛盾，則表示此s1不是正確的LFSR的初值。

2)若不矛盾，則繼續(xù)步驟7，判斷s0的值是否矛盾。若矛盾，則表示此s0不是正確的LFSR初值；若不矛盾，則說明選取的s0和s1正確，此時OBDD的路徑s0～s15就是要求取的LFSR初值。

2.3復(fù)雜度分析

本算法的計算復(fù)雜度由所合成的OBDD的空間復(fù)雜度決定。在整個BDD生成過程的每個階段，所合成的OBDD被2個條件約束。

1)所有指向終節(jié)點(diǎn)1的路徑的集合記為H，其與P的關(guān)系為：

其中m為OBDD包含的變量數(shù)目。假設(shè)時鐘t>0，則：

2)由于P是T與Q交集操作的結(jié)果，可得到另一個約束：

其中|Q|為總節(jié)點(diǎn)數(shù)。

3　比較分析

根據(jù)現(xiàn)有的文獻(xiàn)，針對SNOW 3G加密算法的攻擊方法主要有線性區(qū)分攻擊[1]、Multiset碰撞攻擊[2]和猜測決定攻擊[3]。將本BDD攻擊與上述3種方法比較，結(jié)果如表4所示。

表4　4種攻擊方法的比較

文獻(xiàn)[1]和文獻(xiàn)[2]的方法主要是構(gòu)造區(qū)分器，并不以恢復(fù)線性反饋移位寄存器LFSR的內(nèi)部狀態(tài)為目的。BDD攻擊是一種狀態(tài)恢復(fù)攻擊，因此主要與文獻(xiàn)[3]比較。文獻(xiàn)[3]的方法的計算復(fù)雜度為2320，所需的密鑰流為9，本BDD攻擊所需要的密鑰流為8，計算復(fù)雜度為2362，雖然計算復(fù)雜度較高，但是利用BDD攻擊，可直接得到所需攻擊結(jié)果，不需要額外的操作。然而在文獻(xiàn)[3]中，攻擊得到的密鑰流與已知的密鑰流需要進(jìn)行對比分析，這部分計算花銷在文獻(xiàn)[3]中并未提及。本BDD攻擊結(jié)合了猜測決定攻擊的思想，大大優(yōu)化了Krause的算法，降低了計算復(fù)雜度和所需的密鑰流。本BDD攻擊在利用更少的密鑰流的同時，可直接得到所需數(shù)據(jù)，在實(shí)際操作中更有優(yōu)勢。

4　結(jié)束語

對SNOW 3G加密算法的安全性進(jìn)行了分析，以考察其安全性。通過改進(jìn)的BDD攻擊，利用少量的密鑰流來獲取SNOW 3G加密算法內(nèi)部LFSR的初始狀態(tài)。改進(jìn)后的BDD攻擊，結(jié)合了猜測決定攻擊的思想，大大優(yōu)化了Krause的算法，降低了計算復(fù)雜度。但是，本研究在計算復(fù)雜度方面還有提升的空間，主要體現(xiàn)在2個方面：1)尋找更加合適的結(jié)構(gòu)來表示基礎(chǔ)鏈；2)繼續(xù)發(fā)掘FSM前后狀態(tài)的變化規(guī)律。

[1]NYBERG K,WALLéN J.Improved linear distinguishers for SNOW 2.0[C]//Fast Software Encryption.Berlin:Springer Berlin Heidelberg,2006:144-162.

[2]BIRYUKOV A,PRIEMUTH-SCHMID D,ZHANG B.Multiset collision attacks on reduced-round SNOW 3G and SNOW 3G⊕[C]//Applied Cryptography and Network Security.Berlin:Springer Berlin Heidelberg,2010:139-153.

[3]關(guān)杰，丁林，劉樹凱.SNOW3G與ZUC流密碼的猜測決定攻擊[J].軟件學(xué)報，2013(6):1324-1333.

[4]KRAUSE M.BDD-based cryptanalysis of keystream generators[C]//Advances in Cryptology:EUROCRYPT 2002.Berlin:Springer Berlin Heidelberg,2002:222-237.

[5]ETSI/SAGE.Specification of the 3GPP confidentiality and integrity algorithms UEA2&UIA2[OL].(2006-12-18)[2016-3-18].http://cryptome.org/uea2-uia2/uea2-uia2.htm.

[6]古天龍，徐周波.有序二叉決策圖及應(yīng)用[M].北京：科學(xué)出版社，2009:22-51.

[7]STEGEMANN D.BDD-based cryptanalysis of the A5/1 keystream generator-experimental results[C]//The State of the Art of Stream Ciphers,2004:1-6.

[8]SHAKED Y,WOOL A.Cryptanalysis of the bluetooth E0 cipher using OBDD’s[C]//Information Security.Berlin:Springer Berlin Heidelberg,2006:187-202.

[10]GHASEMZADEH M,MEINEL C,SHIRMOHAMMADI M,et al.ZDD-based cryptanalysis of E0 keystream generator[C]//Proceedings of 3th International Conference on Mathematical Sciences,2008:1-6.

編輯：張所濱

BDD attack on SNOW 3G encryption algorithm

WU Yonggang, GU Tianlong, XU Zhoubo

(Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guilin 541004, China)

In order to analyze the security of SNOW 3G encryption algorithm, an improved BDD attack method is proposed. The feedback polynomial of the linear feedback shift register is used to choose specific internal bit stream, which can construct the first kind of OBDD. Using the idea of guess and determine attack to guess internal state of finite state machine and find the connection between internal state and the keystream of SNOW 3G encryption algorithm for surmising the internal bit stream of cipher, which can construct the second kind of OBDD. The initial key of SNOW 3G encryption algorithm is obtained by the intersection operation of two kinds of OBDD. The analysis results show that the improved algorithm is better than original BDD attack and more threatening to SNOW 3G encryption algorithm.

cryptanalysis; BDD attack; SNOW 3G encryption algorithm; guess and determine attack

2016-03-18

國家自然科學(xué)基金(61262030,61572146,61363030)；廣西自然科學(xué)基金(2015GXNSFAA139285,2014GXNSFAA118354)

古天龍(1964―),男，山西芮城人，教授，博士，研究方向?yàn)樾问交椒?、符號計算。E-mail:cctlgu@guet.edu.cn

TP309

A

1673-808X(2016)03-0199-05

引文格式： 吳泳鋼，古天龍，徐周波.SNOW 3G加密算法的BDD攻擊[J].桂林電子科技大學(xué)學(xué)報，2016,36(3):199-203.