抗滑動攻擊的LEX算法改進及分析*

李佳雨,石 會,鄧元慶,龔 晶,關 宇(解放軍理工大學通信工程學院,江蘇南京210007)

抗滑動攻擊的LEX算法改進及分析*

李佳雨,石 會,鄧元慶,龔 晶,關 宇
(解放軍理工大學通信工程學院,江蘇南京210007)

為增強流密碼算法LEX抵抗滑動攻擊的能力,基于變換密鑰的思想,采取雙行LEX關聯的做法對其進行了改進。在此基礎上,分析了改進算法的安全性和運算速度,并用一個實例仿真來檢驗了改進算法的密鑰流隨機性。結果表明,改進的LEX算法能夠抵抗滑動攻擊,并保持了與原LEX算法相同的運算速度和密鑰流隨機性,提高了LEX算法的密碼性能。

流密碼 LEX 安全性 滑動攻擊 隨機性

0 引 言

ECRYPTⅡ(European Network of Excellence for CryptologyⅡ)是歐洲委員會FP7(7 Framwork Programme)在ICT(Information&Communication Technologies)資金資助下的一個項目。為了推動流密碼的發展,幫助密碼研究人員開展對流密碼的研究和設計,ECRYPT于2004年啟動了eSTREAM流密碼研究計劃[1]。

LEX(Leak EXtraction)算法[2]是進入eSTREAM計劃第二階段的流密碼候選算法,設計思想是基于分組密碼算法AES[3-4]來構造流密碼,并繼承了AES便于硬件實現[5]的特點。但與其它類似方式構造的流密碼相比較,其突出優點在于提高了密鑰流的產生速度,使得加密效率約是AES算法的2.5倍[6]。

當前,針對完整AES算法還沒有有效的攻擊手段。但是,2006年Wu Hong-jun等人卻給出了針對LEX算法的滑動攻擊[7]。本文旨在改進LEX算法的抗滑動攻擊能力。

1 LEX算法及滑動攻擊

1.1 LEX算法描述

LEX算法采用了128比特密鑰和明文分組的AES算法作為密鑰流產生部件。圖1為LEX算法的初始化和運行過程:給定一個初始向量IV作為輸入,在加密密鑰K的作用下,用一次標準AES對IV進行加密,得到密文S=AESK(IV)。此后,每執行一次AES會有10輪輪函數迭代,每一輪迭代后所得的128 bit中間狀態將有4個字節(共32比特)被提取出來作為輸出密鑰流的一部分,10輪迭代最終構成320 bit的密鑰流輸出。

圖1 LEX的初始化和密鑰流生成Fig.1 Initialization and key-stream generation

AES部件的10輪加密中,LEX算法對每一輪加密得到的數據的提取方式有所不同。如圖2所示,方框內的一個bi,j表示一個字節,第奇數輪提取b0,0,b0,2,b2,0,b2,2四個字節,第偶數輪提取b0,1,b0,3, b2,1,b2,3四個字節。其過程可用公式表達為:

公式中ti=(bi,0,bi,1,bi,2,bi,3),i=0或者2,代表每輪加密結果的第0或者第2個行向量,各由4個字節組成。

圖2 奇數輪和偶數輪提取字節位置Fig.2 Leak positions in even and odd rounds

1.2 針對LEX算法的滑動攻擊

針對LEX算法的攻擊可以有兩種途徑。一是攻擊它的核心部件AES加密算法,而AES算法的高度安全性決定了這種攻擊方法無效。二是針對LEX的構造特性進行攻擊。目前,這類攻擊方式最有效的是滑動攻擊[8]。2006年,Wu Hongjun等人給出了針對LEX算法的滑動攻擊,分析過程如圖3所示[7,9]。令Si=AE(IV),Si表示IV經過i個AES部件加密后的中間狀態(S0=IV),mi(i逸2)表示經過第i次AES加密后輸出的320 bit的密鑰流(第一次沒有輸出)。取兩個不同的初始向量IV憶和IV″,如果存在j使得=j>2),則有=成立,進而得出S,而是狀態S輸入經過一次AES加密所產生的密鑰流,這樣就可以認為m″j-1是由初始向量IV憶所產生的密鑰流,同時也就獲取了IV憶經K加密第一輪后提取的32 bit數據。根據文獻[7],如果總共有4對類似的碰撞對,那么就可以完全恢復出LEX的密鑰。

圖3 針對LEX算法的滑動攻擊Fig.3 Slide attack on LEX

文獻[7]對LEX算法的滑動攻擊中,大約只需要261個初始輸入IV和2×104個字節的密鑰流,就可以完全恢復出128比特密鑰[10]。故而LEX算法是存在安全隱患的,需要對其設計進行改進。為此, LEX的設計者Alex Biryukov對其進行了簡單的變形:在實施第一組AES時,使用加密密鑰K和初始值IV,AES不去掉最后一輪的列混合操作。從第二組AES加密開始,使用相同的加密密鑰K,但是AES部件去掉了最后一輪的列混合操作。這樣的改變以后,初始置換函數和后面的置換函數不同,所以能夠抵抗滑動攻擊。然而,尤加勇等人在2007年又給出了這種改進不能抵抗截斷滑動攻擊的證明[11]。

2 LEX算法的改進及分析

2.1 抗滑動攻擊的LEX算法改進

本文采用雙行LEX關聯的方法,設計了LEX的一種改進算法——DLEX(Double-lines LEX),其結構如圖4所示。

圖4 DLEX算法結構Fig.4 Construction of DLEX

算法說明如下:

1)整體結構:DLEX包括“初始化模塊”和“密鑰流生成模塊”。其中每個密鑰流生成模塊含有2個相同的AES部件,不妨分別稱為AES1、AES2。圖4中字母的下標ij,i=1或者2,j=1,2,3,…。該算法結構形如相關聯的兩行,i代表行號,j代表第j個640 bit密鑰流生成模塊。

2)初始化:DLEX算法的初始明文和密鑰輸入均為128 bit。該模塊中的AES部件與LEX算法初始化相同,最后一輪包括了列混淆運算。

3)密鑰流生成:初始化的密鑰作為S11,加密結果作為S21,分別作為第一個“640 bit密鑰流生成模塊”中AES1和AES2的輸入,S11和S21異或后的數據作為AES1和AES2的密鑰,K11=K21。AES1和AES2分別進行一組LEX算法密鑰流提取操作,各得到320 bit的兩組密鑰流輸出m1j和m2j,共640 bit密鑰流,同時得到兩組加密結果S12和S22。重復該步驟持續產生密鑰流。

2.2 DLEX算法抗滑動攻擊能力分析

以下從兩個方面對DLEX算法抗滑動攻擊的能力進行分析。此兩方面的分析同樣適用于截斷滑動攻擊。下文公式中的字母E表示一個AES部件加密提取密鑰流的操作。

一方面,分別對DLEX算法的某一行進行滑動攻擊,不妨以第一行為例。

假設任取文獻[7,11]所需的明文,并找到碰撞對m1j=m1k(j,k>1,j屹k),其中

故而有EK1j(S1j)=EK1k(S1k)。但由于DLEX算法中,每一個AES部件的Kij和Sij都來自于上一個模塊的加密結果,在不斷地變化,即使存在EK1j(S1j)= EK1k(S1k),由于無法證明K1j=K1k,所以無法推出S1j=S1k,從而無法實現滑動攻擊。

另一方面,將DLEX算法的640 bit密鑰流生成模塊整體看作一個置換函數F來進行滑動攻擊。

同樣假設任取文獻[7,11]所需的明文,并找到碰撞:

但根據文獻[8],由生日碰撞原理,需要選取2128對長度為256 bit的明密文對((S1j,S2j),(S1k, S2k))來找到滑動碰撞對(S1j,S2j)=(S1k,S2k)。采用此種方法對DLEX算法實施滑動攻擊,僅尋找一對滑動碰撞對的工作,其難度就大于對AES-128算法進行強力攻擊。

因此,DLEX能夠抵抗任何形式滑動攻擊。

2.3 輸出密鑰流的雪崩效應

DLEX算法的核心部件仍然是AES,因此,其輸出密鑰流的雪崩效應可以由AES算法S盒的特性[12]所保證。

2.4 輸出密鑰流的周期性

LEX算法在本質上是對AES采取輸出反饋模式(OFB)來提取320 bit的密鑰流。由于對每一個AES使用了相同的加密密鑰K,因此,對于一個確定中間狀態的Si,至多只需經過2128次AES加密后,就可以得到相同的Si,并且兩次輸出的320 bit密鑰流相同,存在明顯的周期性。

DLEX算法中,綜合采用了輸出反饋(OFB)和密碼反饋(CFB)相結合的模式,由于每一個AES部件的輸入和加密密鑰都不相同,并且輸出的密鑰流由兩行LEX共同產生,其周期為2256個640 bit密鑰流生成模塊,遠大于原LEX算法。

2.5 速度分析

LEX算法中,每組128 bit的AES加密算法,可以得到320 bit的密鑰流輸出。因此,LEX算法的速度約為AES的2.5倍(320/128=2.5)。

DLEX算法中,每兩組128 bit的AES加密算法,可以得到640 bit的密鑰流輸出。因此,DLEX算法與原LEX算法速度相同,同樣可以達到AES算法的2.5倍。

3 隨機性檢測仿真實例與分析

密鑰流的隨機性是評判流密碼算法優劣的一個重要指標。2012年,國家密碼管理局第23號公告批準了編號為GM/T 0005-2012的《隨機性檢測規范》[13],本規范共收納了15種隨機性檢測方法,它們分別是:單比特頻數檢測、塊內頻數檢測、撲克檢測、重疊子序列檢測、游程總數檢測、游程分布檢測、塊內最大1游程檢測、二元推導檢測、自相關檢測、矩陣秩檢測、累加和檢測、近似熵檢測、線性復雜度檢測、Maurer通用統計檢測、離散傅里葉檢測。該《隨機性檢測規范》針對隨機數發生器的性能評價步驟如下:

1)用隨機數發生器產生1 000個長度為1 000 000位的0-1隨機數序列作為待檢樣本。

2)對產生的1 000個樣本,依次使用上述15種隨機性檢測方法對其進行檢測。

3)對于每一種隨機性檢測方法,統計P-value值不小于顯著性水平琢(本規范建議取琢=0.01)的樣本個數。單個樣本的P-value不小于琢,則表示該樣本通過該項檢測。

4)記樣本數量為s,則通過檢測的樣本個數應不小于s(1-琢-3)。當樣本數量為1 000個時,如果通過的樣本個數不小于981(未通過的樣本個數不大于19),則隨機數發生器通過此項檢測;否則未通過此項檢測。

如果隨機數發生器通過本規范規定的所有檢測項目,則隨機數發生器通過本規范檢測;否則,未通過本規范檢測。

本文采用C++編程工具,分別編寫了基于LEX和DLEX算法的密鑰流產生器的程序,并依據《隨機性檢測規范》搭建了隨機性檢測平臺,分別對LEX和DLEX產生的1 000個1 000 000位0-1隨機序列進行了隨機性檢測。為了避免由于密鑰流產生器的輸入不同而影響評價結果,每產生一個樣本時,LEX和DLEX都采用了相同的輸入向量和密鑰。

對LEX和DLEX各自產生的1 000個樣本分別進行15種隨機性檢測,統計數據見表1。

從兩種算法產生的隨機序列樣本未通過檢測的個數來看,都不大于19,符合《隨機性檢測規范》要求。

根據《隨機性檢測規范》的原理,對多個樣本進行隨機性檢測,統計得到的P-value值應當均勻分布在閉區間[0,1]內,其均值約為0.5。對表1進行數據分析可以看出,LEX和DLEX兩種算法產生樣本的P-value值的期望值均在0.5左右一定區間內分布,并且兩者的P-value值的期望值和方差都非常接近,符合統計規律,說明了DLEX算法與LEX算法產生的隨機序列,其隨機性的統計特性相當。

表1 樣本隨機性統計分析Table 1 Statistical analysis of samples’randomness

4 結 語

LEX算法以分組密碼AES作為密鑰流生成的核心部件,架起了分組密碼與流密碼之間的橋梁。但是由于其結構特性,導致其對于滑動攻擊、截斷滑動攻擊存在安全隱患。本文基于LEX算法,改進設計了DLEX算法,在保持LEX算法的運算速度和密鑰流隨機性的前提下,采取兩行LEX關聯的結構,使每一個AES部件的輸入和密鑰都完全不同,從而能夠有效抵抗滑動攻擊和截斷滑動攻擊,增強了LEX的密碼性能。

[1] 劉依依.eSTREAM和流密碼分析現狀[J].信息安全與通信保密,2009(12):47-49. LIU Yi-yi.eSTREAM and the Present State of Streamcipher Analysis[J].Information Security and Communications Privacy,2009,31(12):47-49.(In Chin-ese).

[2] Alex Biryukov.A new 128 bit key stream cipher LEX [EB/OL].ECRYPT Stream Cipher Project Rep-ort 2005/013,(2005-06-13)[2014-10-20].http:// www.ecrypt.eu.org/stream/ciphers/lex/lex.pdf

[3] NationalInstitute of Standards and Technolo-gy(NIST). Announcing the ADVANCED ENCRYPTION STANDARD (AES)[EB/OL].U.S.A.:NIST,(2001-11-26) [2014-10-20].http://csrc.nist.gov/publications/fips/ fips197/fips-197.pdf

[4] 鄧元慶,龔晶,石會.密碼學簡明教程[M].北京:清華大學出版社,2011:71-93. DENG Yuan-qing,GONG Jing,SHIHui.Concise Course of Cryptography[M].Beijing:Tsinghua Univ-ersity press,2011:71-93.

[5] 張慧霞,趙建平,李曉麗,等.AES密碼算法的FPGA實現與仿真[J].通信技術,2013,46(09):83-85. ZHANG Hui-xia,ZHAO Jian-ping,LIXiao-li,et al. Implementation and Simulation of AESEncrypt-ion Algorithm basedon FPGA[J].Communications Technology, 2013,46(009):83-85.

[6] Matt Henricksen.Flexible Block Ciphers:Modif-ying LEX [C]//ICCSIT2010.Chengdu:IEEE,2010:630-634.

[7] Wu Hong-jun,Preneel B.Attacking the IV Setup of Stream Cipher LEX[EB/OL].Graz,Austria:FSE2006, (2006-03-15)[2014-10-20].http://www.ecrypt. eu.org/stream/papersdir/059.pdf

[8] Biryukov A,Wagner D.Slide Attacks[C]//FSE6.R-ome,Italy:Springer Berlin Heidelberg,1999:245-259.

[9] 李欣,譚曉青.抵抗滑動攻擊的LEX算法改進[J].計算機工程與應用,2012,48(26):101-103. LIXin,TAN Xiao-qing.Improved algorit-hm to resist slide attack for LEX[J].Computer Eng-ineering and Applications,2-012,48(26):101-103.(In Chinese).

[10] 張中亞,關杰.對流密碼算法LEX的差分故障攻擊[J].上海交通大學學報,2012,40(06):865-869. ZHANG Zhong-ya,GUAN Jie.Differential Fault Analysis on the Stream Cipher LEX[J].Journal of Shanghai Jiao Tong University,2012,40(6):865-869. (In Chinese).

[11] 尤加勇,李超.針對LEX算法的截斷滑動攻擊[J].信息安全與通信保密,2007(09):96-98. YOU Jia-yong,LIChao.Interruption Slide Att-ack against Stream Cipher LEX Algorithm[J].Information Security and Communications Privacy,2007,29(9):96-98.(In Chinese).

[12] 劉景偉,韋寶典,呂繼強,等.Rijndael S盒代數性質研究[J].計算機工程與應用,2003(31):45-47. LIU Jing-wei,WEIBao-dian,LV Ji-qiang,et al.The Study of the Algebra Properties for the Rijndael S-Box [J].Computer Engineering and Applications,2003,31: 45-47.

[13] GM/T 0005-2012,隨機性檢測規范[S].北京:中國標準出版社,2012. GM/T 0005-2012,Randomness Test Specification[S]. Beijing:Standards Press of China,2012.

LI Jia-yu(1985-),male,graduate student,mainly engaged in information security;

石 會(1982—),女,碩士,講師,主要研究方向為信息安全;

SHIHui(1982-),famale,M.Sci.,lecturer,mainly engaged in information security;

鄧元慶(1958—),男,碩士,教授,主要研究方向為信息安全;

DENG Yuan-qing(1958-),male,M.Sci.,professor, mainly engaged in information security;

龔 晶(1968—),女,碩士,副教授,主要研究方向為信息安全;

GONG Jing(1968-),famale,M.Sci.,associate professor,mainly engaged in information security;

關 宇(1962—),男,碩士,教授,主要研究方向為信息安全。

GUAN Yu(1962-),male,M.Sci.,professor,mainly engaged in information security.

Improvement and Analysis on Slide Attack-Resistant Stream Cipher LEX

LIJia-yu,SHIHui,DENG Yuan-qing,GONG Jing,GUAN Yu
(Institute of Communication Engineering,PLAUST,Nanjing Jiangsu 210007,China)

In order to enhance its ability in resisting slide attack and based on key-transformation idea,the stream cipher LEX algorithm ismodified with a double LEX-line structure.In light of this,the safety and operating speed of themodified LEX algorithm is analyzed,and a simulation also conducted to test the randomness of the key stream.Simulation results show that thismodified algorithm can resist slide attack while keeping the same computing speed and keystream randomness of the original LEX algorithm,and thus greatly improves the performance of LEX algorithm.

stream cipher;LEX;security;slide attack;randomness

National Natural Science Foundation of China(No.61271254)

date：2014-09-01;Revised date：2014-12-08

國家自然科學基金項目(No.61271254)

TN918.4

A

1002-0802(2015)02-0203-05

李佳雨(1985—),男,碩士研究生,主要研究方向為信息安全;

10.3969/j.issn.1002-0802.2015.02.018

2014-09-01;

2014-12-08