SNOW 3G加密算法的BDD攻擊

吳泳鋼，古天龍，徐周波

(桂林電子科技大學 廣西可信軟件重點實驗室，廣西 桂林　541004)

?

SNOW 3G加密算法的BDD攻擊

吳泳鋼，古天龍，徐周波

(桂林電子科技大學 廣西可信軟件重點實驗室，廣西 桂林541004)

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

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

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

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

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

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

1　相關知識

1.1SNOW 3G加密算法[5]

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

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

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

(1)

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

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

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

x8+x7+x5+x3+1

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

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

(2)

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

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)是布爾函數的一種有效圖形、數學描述技術。

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

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

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

1.3基于BDD的密碼分析技術

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

圖3　LFSR密鑰流發生器結構Fig.3　Structure of LFSR stream ciphers

從圖3可看出，LFSR的初始狀態包含在輸出的內部線性比特流中，即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根據LFSRs的反饋多項式構造，用來判斷內部比特流是否符合LFSR的反饋多項式。

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

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

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

P←Qn;

form←n+1 tom*do:

P←(P∧Qm∧Tm);

returnz*thatP(z*)=1。

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

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

2.1攻擊條件

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

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

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

2.2BDD生成過程

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

繼續構建第2類OBDD，將其表示為Q，它是以LFSR的輸出內部狀態st為核心構成的。st由32 bit構成，共有232種狀態。用OBDD結構保存這32 bit所有可能的組成。為了描述方便，將此OBDD結構稱為基礎鏈。當前時刻的基礎鏈所包含的每條路徑都連接相應的下一時刻的基礎鏈。因此，可用前7個時鐘的基礎鏈s0～s6組成初始Q。

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

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

表1　s7～s14推出過程

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

表2　s15～s22推出過程

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

表3　驗證過程

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

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

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

2.3復雜度分析

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

1)所有指向終節點1的路徑的集合記為H，其與P的關系為：

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

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

其中|Q|為總節點數。

3　比較分析

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

表4　4種攻擊方法的比較

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

4　結束語

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

[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]關杰，丁林，劉樹凱.SNOW3G與ZUC流密碼的猜測決定攻擊[J].軟件學報，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]古天龍，徐周波.有序二叉決策圖及應用[M].北京：科學出版社，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

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

古天龍(1964―),男，山西芮城人，教授，博士，研究方向為形式化方法、符號計算。E-mail:cctlgu@guet.edu.cn

TP309

A

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

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