趙躍華，劉文山，韓 牟

（江蘇大學計算機科學與通信工程學院，江蘇鎮(zhèn)江212013）

一種針對祖沖之算法的猜測決定攻擊

趙躍華，劉文山，韓 牟

（江蘇大學計算機科學與通信工程學院，江蘇鎮(zhèn)江212013）

為了分析ZUC算法在抵御猜測決定攻擊方面的安全性，針對ZUC算法在比特重組以及非線性函數(shù)中獨特的16比特半字的運算，提出基于16比特半字的猜測決定攻擊.該攻擊方法首先將ZUC中的狀態(tài)轉換運算變換為半位的運算，將線性反饋移位寄存器中的每個狀態(tài)分為上下半位，然后通過使用Viterbi-like算法計算出猜測決定攻擊的基本點，根據(jù)已知的基本點狀態(tài)和變換后的半位運算，決定出其他未知的狀態(tài)，從而實現(xiàn)對內部狀態(tài)的恢復.結果表明，這種猜測決定攻擊計算復雜度為2398，所需數(shù)據(jù)量為6個32比特密鑰字，該結果優(yōu)于已有的針對ZUC的猜測決定攻擊.

3GPP；ZUC；猜測決定攻擊；密碼分析；流密碼；Viterbi-like算法

ZUC算法即祖沖之算法［1］，是3GPP（3rd generation partnership project，第3代合作伙伴計劃）機密性算法EEA3和完整性算法EIA3的核心［2］，是中國自主設計的加密算法，目前已成為國內TD-LTE（time-division long term evolution，分時長期演進）行業(yè)標準，主要用于移動通信系統(tǒng)空中傳輸信道的信息加密和身份認證，以確保用戶通信安全.如適用于車載網(wǎng)的通信［3］，實現(xiàn)車載通信的隱私保護等.ZUC算法于2011年9月正式被3GPPSA全會通過，成為繼SNOW 3G和AES（advanced encryption standard，高級加密標準）之后的3GPP LTE第3套加密標準核心算法.

算法標準組ETSI SAGE和2個專業(yè)團隊分別對ZUC進行了內部和外部評估，認為ZUC算法健壯.隨后中國科學院數(shù)據(jù)保護與通信安全研究中心（date assurance and communication security research center，DACAS）公開ZUC v1.4，算法進入公開評估階段.Wu Hongjun等［4］發(fā)現(xiàn)ZUC v1.4安全漏洞，DACAS發(fā)布新的ZUC v1.5.目前，針對ZUC v1.5安全分析的成果較少，其中周春芳等針對其構造了一條24輪的選擇IV差分傳遞鏈［5］.丁林等基于求解特征非線性方程，提出對ZUC的猜測決定攻擊，計算復雜度為2403，所需密鑰為9個比特字［5］.杜紅紅等［6］針對初始化2輪的ZUC v1.5算法進行猜測決定攻擊，證明了初始化33輪的必要性.

文中利用猜測決定攻擊的方法對ZUC算法進行分析，攻擊的基本思路是，針對ZUC獨特的16比特半字的運算，將基于32比特的非線性函數(shù)轉化為基于16比特半字的非線性函數(shù)，利用一種對流密碼通用的猜測攻擊方法進行猜測攻擊.

1 ZUC算法簡介

ZUC是一個同步流密碼算法，密鑰規(guī)模為128比特.ZUC邏輯上采用3層結構，即線性反饋移位寄存器（linear feedback shift register，LFSR）、比特重組（bit Reorganization，BR）和非線性函數(shù)F，其整體結構如圖1所示［7］.

圖1 ZUC整體結構圖

1.1 線性反饋移位寄存器（LFSR）

LFSR由16個31位的寄存器（s0，s1，…，s15）組成，每一個都是定義在素域GF（231-1）上.其中寄存器內部狀態(tài)更新方式如下：

1）st+16=215st+15+217st+13+221st+10+220st+4+（1+28）stmod（231-1）.

2）如果st+16=0，設定st+16=231-1.

3）（s1，s2，…，s15，s16）→（s0，s1，…，s14，s15）.

1.2 比特重組（BR）

比特重組是一個過渡層，其主要從LFSR中抽取128比特內容組成4個32比特的字X0，X1，X2，X3，以供下層非線性函數(shù)F和密鑰輸出使用，重組方式如下：

其中SH，SL分別表示S的高16位和低16位.

1.3 非線性函數(shù)F

非線性函數(shù)F有2個32位的存儲單元R1，R2，輸入為X0，X1，X2，輸出為32位的W.F的更新方式如下：

其中，S表示S盒變換，且有

1.4 密鑰產(chǎn)生

經(jīng)過33輪的初始化過程后，進入密鑰流生成過程，每個時刻產(chǎn)生一個密鑰字Z，產(chǎn)生方式如下：

比特重組生成X0，X1，X2，X3

2 ZUC猜測決定攻擊

猜測決定攻擊（guess and determine attack）是針對流密碼的一類攻擊方法［8］.猜測決定攻擊的基本思想是攻擊者可以通過猜測流密碼算法中部分記憶單元的數(shù)值，然后利用該部分記憶單元的數(shù)值和得到的密鑰流以較少的復雜度計算出流密碼算法中其他記憶單元的值.攻擊者往往會運行算法一定拍數(shù)，將算法輸出和已知的真實密鑰流進行對比，以檢驗猜測部分的正確性.如果不正確，則重復上面猜測確定過程，直到正確恢復出算法的內部狀態(tài).自從Hawkes和Rose提出針對SNOW1.0的猜測決定攻擊后，猜測決定攻擊逐漸成為一種針對面向字的流密碼的有效攻擊方法.近期出現(xiàn)了一些具有代表性的研究成果，如對Loiss，SOSEMUNK，SNOW 3G的猜測決定攻擊［9-11］.

文中利用ZUC算法的獨特結構，提出一種半比特字節(jié)的猜測決定攻擊方法，進而恢復出ZUC算法的內部狀態(tài).

根據(jù)ZUC獨特的半比特位的重組運算，對內部狀態(tài)更新的公式進行變換，具體如下.

1）LFSR內部狀態(tài)更新.

變換后：

其中c1t表示1比特進位，滿足如下關系：

2）非線性函數(shù)F內部狀態(tài)更新.

變換后：

其中c2t表示1比特進位，滿足如下關系：

變換后：

3）內部狀態(tài)的狀態(tài)更新.

4）密鑰流生成變換.

變換后：

其中c3t表示1比特進位，滿足如下關系：

針對ZUC算法的猜測決定攻擊的過程如下.

1）根據(jù)Viterbi-like算法，將公式2），（3），（5），（6），（8），（9）作為基本式，找到猜測的基本點，即內部狀態(tài)st，H，st+1，H，st+2，st+3，L，st+4，st+6，L，st+15，st+16，st+17，H，st+18，L，st+19，H，R1t，R1t+1，R1t+2，R1t+4，然后猜測c10，c11，c15，c20，c21，c23.

2）根據(jù)已猜測的內部狀態(tài)，決定st，st+1，st+2，…，st+15，R1t，R2t，決定過程見表1.

表1 ZUC的猜測決定攻擊的決定過程

續(xù)表

至此，得到連續(xù)的ZUC的內部狀態(tài)（s0，s1，s2，…，s15，），R10，R20.

3 復雜度分析

本次對ZUC的猜測決定攻擊中猜測的內部狀態(tài)有s0，H，s1，H，s2，s3，L，s4，s6，L，s14，s15，s16，s17，H，s18，L，s19，H，R10，R11，R12，R14，c10，c11，c15，c20，c21，c23（共401比特），此時的猜測量為2401.通過驗證步驟7得到的s6，H的最低比特與步驟8猜測的s6，L最高比特是否相等.對于正確的猜測，該驗證式一定相等，對于錯誤的猜測，相等的可能性為0.5，所以猜測量可以降低一半，為2400；同理，步驟4的S11，L與步驟18的s11，H，步驟17的s20，L與步驟21的s20，H也存在這樣的關系，所以猜測量可以降為2398.因此，該攻擊的計算復雜度為2398，攻擊所需的數(shù)據(jù)量Z0，Z1，Z2，Z4，Z5，Z6共6個32比特字節(jié).

目前針對ZUC的分析結果主要是猜測決定攻擊和選擇IV差分攻擊，下面就文中的分析結果與已有的分析結果進行比較，見表2.

表2 與已有的針對ZUC分析結果的比較

從表2可以看出，文中的猜測結果優(yōu)于目前已有的猜測決定攻擊.

4 結 論

文中利用猜測決定攻擊方法對ZUC算法進行了分析，在分析過程中，利用ZUC獨特的算法結構，提出半比特字節(jié)的猜測決定攻擊，根據(jù)Viterbi-like算法，找出猜測的基本點，進而恢復全部的內部狀態(tài).分析得最終結果：計算復雜度為2398，所需數(shù)據(jù)量為6個32比特密鑰字.

（

）

［1］馮秀濤.3GPP LTE國際加密標準ZUC算法［J］.信息安全與通信保密，2011，19（12）：45-46. Feng Xiutao.ZUC algorithm：3GPP LTE international encryption standard［J］.Information Security and Communications Privacy，2011，19（12）：45-46.（in Chinese）

［2］ETSI/SAGE TS 35.223-2011.Specification of the 3GPP confidentiality and integrity algorithms 128-EEA3 &128-EIA3；document3：implementors′test data［S］.

［3］馬世典，江浩斌，韓 牟，等.車載網(wǎng)環(huán)境下車載電控系統(tǒng)信息安全綜述［J］.江蘇大學學報：自然科學版，2014，35（6）：635-643. Ma Shidian，Jiang Haobin，Han Mu，et al.Survey of information security research for vehicle electronic control system in vehicle Internet environment［J］.Journal of Jiangsu University：Natural Science Edition，2014，35（6）：635-643.（in Chinese）

［4］Wu Hongjun，Huang Tao，Nguyen Phuong Ha，et al. Differential attacks against stream cipher ZUC［C］∥Proceeding of 18th International Conference on the Theory and Application of Cryptology and Information Security.Beijing：Springer Verlag，2012：262-277.

［5］Zhou Chunfang，F(xiàn)eng Xiutao，Lin Dongdai.The initialization stage analysis of ZUC v1.5［C］∥Proceeding of the 10th International Conference on Cryptography and Network Security.Sanya：Springer Verlag，2011：40-53.

［6］杜紅紅，張文英.祖沖之算法的安全分析［J］.計算機技術與發(fā)展，2012，22（6）：151-155. Du Honghong，Zhang Wenying.Security analysis onZUC stream cipher［J］.Computer Technology and Development，2012，22（6）：151-155.（in Chinese）

［7］Orhanou G，EIHajji S，Lakbabi A，et al.Analytical evaluation of the stream cipher ZUC［C］∥Proceedings of2012 International Conference on Multimedia Computing and Systems.Tangiers：IEEE Computer Society，2012：927-930.

［8］關 杰，丁 林，劉樹凱.SNOW3G與ZUC流密碼的猜測決定攻擊［J］.軟件學報，2013，24（6）：1324-1333. Guan Jie，Ding Lin，Liu Shukai.Guess and determine attack on SNOW3G and ZUC［J］.Journal of Software，2013，24（6）：1324-1333.（in Chinese）

［9］Feng Xiutao，Liu Jun，Zhou Zhaocun，et al.A bytebased guess and determine attack on SOSEMANUK［C］∥Proceeding of the16th International Conference on the Theory and Application of Cryptology and Information Security.Singapore：Springer Verlag，2010：146-157.

［10］Nia M SN，Eghlidos T.Improved Heuristic guess and determine attack on SNOW 3G stream cipher［C］∥Proceeding of the 7th International Symposium on Telecommunications.Tehran：IEEE Computer Society，2014：972-976.

［11］周照存，劉 駿，馮登國.對Loiss算法的猜測確定分析［J］.中國科學院研究生院學報，2012，29（1）：125-130. Zhou Zhaocun，Liu Jun，F(xiàn)eng Dengguo.Guess-and-determine attacks on Loiss［J］.Journal of Graduate University of Chinese Academy of Sciences，2012，29（1）：125-130.（in Chinese）

（責任編輯 梁家峰）

A guess and determine attack on ZUC algorithm

Zhao Yuehua，Liu Wenshan，Han Mu
（School of Computer Science and Communication Engineering，Jiangsu University，Zhenjiang，Jiangsu 212013，China）

To analyze the security of ZUC algorithm for resisting guess and determine attack，a guess and determine attack was proposed based on unique 16 bite half word for ZUC algorithm in half word operation.The operation of state transition was transformed to the halfword operation，and every state in LFSR was divided into up and down half word.The basic point of the guess and determine attack was computed out by Viterbi-like algorithm.The other unknown states were determined according to the known state of basic points and the operation of halfword to recover all internal states.The results show that the proposed attack on ZUC has a computational complexity of2398and requires 6 key stream words，which is better than the previous guess and determine attack on ZUC.

3GPP；ZUC；guess and determine attack；cryptanalysis；stream cipher；Viterbi-like algorithm

TP309

A

1671-7775（2015）05-0578-05

趙躍華，劉文山，韓 牟.一種針對祖沖之算法的猜測決定攻擊［J］.江蘇大學學報：自然科學版，2015，36（5）：578-582.

10.3969/j.issn.1671-7775.2015.05.015

2015-01-09

國家自然科學基金資助項目（61300229）；中國博士后基金資助項目（2013M531283）；江蘇省博士后基金資助項目（1201037C）；江蘇省“六大人才高峰”計劃項目（DZXX-012）；江蘇省高校自然科學基金資助項目（12KJD580002）；江蘇省研究生創(chuàng)新基金資助項目（KYLX-1057）

趙躍華（1958—），男，江蘇鎮(zhèn)江人，教授（zhaoyh@ujs.edu.cn），主要從事信息安全研究.

劉文山（1991—），男，江蘇鹽城人，碩士研究生（1296465272@qq.com），主要從事信息安全、密碼學研究.