一種抗滑動攻擊的密鑰流提取改進(jìn)算法

丁 杰,石 會,龔 晶,鄧元慶

(解放軍理工大學(xué) 通信工程學(xué)院,南京 210007)

0 概述

為推動流密碼更好的發(fā)展,促進(jìn)密碼界開發(fā)出新的流密碼設(shè)計(jì)思想與設(shè)計(jì)理念,ECRYPT項(xiàng)目[1]于2004年啟動了eSTREAM流密碼研究計(jì)劃[2]。自從eSTREAM計(jì)劃啟動以來,國際上密碼研究得到了極大發(fā)展,其中,基于分組密碼思想構(gòu)造流密碼成為流密碼設(shè)計(jì)的一個重要方向。

進(jìn)入eSTREAM計(jì)劃第二階段的流密碼候選算法泄露提取(Leak Extraction,LEX)[3],是基于分組密碼算法高級加密標(biāo)準(zhǔn)(Advanced Encryption Standard,AES)[4]來構(gòu)造的,并因其較高的密鑰流生成速度以及便于硬件實(shí)現(xiàn)的特點(diǎn)倍受關(guān)注,與其他類似方式構(gòu)造的流密碼相比,其密鑰流生成速度約是AES算法OFB模式的2.5倍[5]。

自LEX算法提出以來,出現(xiàn)了很多針對該算法的分析結(jié)果[6],許多針對分組密碼提出的分析手段也被用來分析該流密碼算法[7]。其中,文獻(xiàn)[8]提出的針對LEX算法的滑動攻擊給LEX算法的安全性帶來了很大的隱患。本文研究旨在改進(jìn)LEX算法的薄弱環(huán)節(jié),增強(qiáng)其抗滑動攻擊能力。

1 LEX算法

LEX算法采用128 bit分組密碼高級加密標(biāo)準(zhǔn)AES作為密鑰流產(chǎn)生部件,它的出現(xiàn)架起了分組密碼與序列密碼設(shè)計(jì)的橋梁,具有十分重要的意義。

1.1 LEX算法結(jié)構(gòu)

與AES算法一致,LEX算法延續(xù)了128 bit的密鑰與明文規(guī)模,其算法結(jié)構(gòu)如圖1所示[3],具體分為初始化和密鑰流提取2個階段。初始化階段:對于給定的128 bit密鑰K,以初始向量IV作為輸入,運(yùn)行一組AES,得到加密結(jié)果C1=AESk(IV),該組AES不輸出任何密鑰流;密鑰流提取階段:從第2組AES開始,每執(zhí)行一組AES會有10輪輪函數(shù)迭代,從每一輪迭代后所得的128 bit中間變量提取32 bit(共4個字節(jié)),作為輸出密鑰流的一部分,10輪迭代后共輸出320 bit密鑰流。在該階段中,每組的輸入向量不斷更新,具體為前一組的加密輸出IVi′=Ci(i=1,2,…);加密密鑰K′=K,始終為初始加密密鑰,保持不變。

圖1 LEX算法的結(jié)構(gòu)框圖

在LEX算法中最關(guān)鍵的部分是輸出密鑰流的提取位置。具體提取方式如圖2所示。方框內(nèi)一個bi,j代表某輪變換后的一個字節(jié)的中間變量,按行序讀取共16 Byte,為一組完整的中間狀態(tài)。LEX算法中奇數(shù)輪與偶數(shù)輪輸出密鑰流的位置不同,其中,奇數(shù)輪輸出b0,0、b2,0、b0,2、b2,2共4個字節(jié),偶數(shù)輪輸出b0,1、b2,1、b0,3、b2,3共4個字節(jié),公式表示為:

oddout32=

(t0& 0xFF00FF00)⊕((t2& 0xFF00FF00)>>8)

evenout32=

((t0& 0xFF00FF00)<<8)⊕(t2& 0xFF00FF00)

其中,ti=(bi,0,bi,1,bi,2,bi,3),i=0,1,2,3,根據(jù)i的不同取值,可代表每輪迭代后中間狀態(tài)的第0,1,2,3個行向量,各由4個字節(jié)組成。

圖2 奇數(shù)輪和偶數(shù)輪提取的字節(jié)位置

1.2 密鑰擴(kuò)展算法

LEX算法的密鑰擴(kuò)展運(yùn)算依托其核心部件AES算法實(shí)現(xiàn),通過密鑰擴(kuò)展將16 Byte的初始密鑰K擴(kuò)展為176 Byte,具體過程如下[9]:

1)將128 bit的初始密鑰K按順序劃分為4個4 Byte的密鑰字w0、w1、w2和w3(1個密鑰字長度為4 Byte),用作AES初始階段的輪密鑰加運(yùn)算。

2)10輪迭代過程所需的wi(i=4,5,…,43),共40個,由下述方法生成。

當(dāng)i(mod 4)≠0時,密鑰字:

wi=wi-1⊕wi-4

(1)

當(dāng)i(mod 4)=0時,密鑰字:

wi=ti⊕wi-4

(2)

ti為中間變量,其表達(dá)式為:

ti=Subword[RotWord(wi-1)]⊕Rconi/4

(3)

其中,RotWord函數(shù)表示將變量左移一個字節(jié),Subword函數(shù)代表基于S盒的字節(jié)代替,Rconi/4為輪常量,由有限域GF(28)中的01循環(huán)左移定義,同樣為長度是4 Byte的一個字。

1.3 針對LEX的滑動攻擊

AES作為美國和歐洲分組密碼加密標(biāo)準(zhǔn),其算法本身的安全性是非常高的,可以說,至今還沒有找到針對完整AES算法的有效攻擊。LEX算法雖然以AES作為密鑰流生成部件提高了算法的安全性能,但由于每組AES加密過程使用相同的加密密鑰K,且把輪變換過程中的部分中間狀態(tài)作為密鑰流輸出,易遭到攻擊。比較典型的是針對LEX算法的滑動攻擊,分析過程如圖3所示[8, 10-11]。

圖3 針對LEX算法的滑動攻擊

(4)

(5)

2 LEX算法的改進(jìn)及分析

2.1 LEX算法的改進(jìn)

由前述分析可知,LEX算法無法較好地抵抗滑動攻擊的根源是密鑰體系不完整,每組AES都使用了相同的加密密鑰K,從而導(dǎo)致各輪迭代的加密密鑰對應(yīng)相同,存在隱患。通過改進(jìn)LEX算法的密鑰體系,減少各組密鑰的關(guān)聯(lián)性,加強(qiáng)算法抗滑動攻擊能力,具體方法如下:

1)根據(jù)初始向量IV和種子密鑰K執(zhí)行一次變形的AES(第10輪包含列混合操作),即算法的初始化階段,此過程中不輸出密鑰流。128 bit密鑰K經(jīng)過密鑰擴(kuò)展得到44個密鑰字wi(i=0,1,…,43),每輪迭代運(yùn)算需要4個wi(i>3),由式(2)和式(3)可知,此過程中還需要產(chǎn)生10個中間變量t4i(i=1,2,…,10),t4i完全由初始密鑰K和輪常量Rconi/4通過一系列復(fù)雜變化生成,t4i長度為4 Byte。

2)第2組AES的初始向量C1為上組AES的輸出,加密密鑰K發(fā)生改變,從第1組AES的密鑰擴(kuò)展過程中提取t24、t28、t32、t36共16個字節(jié),按順序排列,作為此組AES的初始加密密鑰K1。此后每組AES的加密密鑰K′=Ki(i≥1)均依托上一組AES密鑰擴(kuò)展中的t4i(i=6,7,8,9)組成,不僅延續(xù)了AES良好的安全性能,而且使各組加密密鑰不再相同。ki(i≥2)表示第i組AES加密后輸出的320 bit密鑰流(第一次沒有輸出)。改進(jìn)后的LEX算法結(jié)構(gòu)如圖4所示。

圖4 改進(jìn)的LEX算法結(jié)構(gòu)

通過C++編程工具實(shí)現(xiàn)對算法的改進(jìn),密鑰擴(kuò)展部分的偽代碼形式如下:

void KeyExpansion(int key_ronud[4][Nb])

{

{ int i,j,k,x,y;

int temp[4];

int key_temp[4];

int Rcon[11][4]=

{0x00,0x00,0x00,0x00,

0x01,0x00,0x00,0x00,

0x02,0x00,0x00,0x00,

0x04,0x00,0x00,0x00,

0x08,0x00,0x00,0x00,

0x10,0x00,0x00,0x00,

0x20,0x00,0x00,0x00,

0x40,0x00,0x00,0x00,

0x80,0x00,0x00,0x00,

0x1b,0x00,0x00,0x00,

0x36,0x00,0x00,0x00};

for(k=1;k<11;k++)

{

{ for(i=1;i<4;i++)

for(j=0;j<4;j++)

{temp[j]=w[k-1][(j+1)%4][3];//k=i=1,

//RotWor變換;

w[k][j][0]=temp[j];

x=w[k][j][0]/16;//除法取整

y=w[k][j][0]%16;//除法取余

w[k][j][0]=Sbox[x][y];//S變換,即Subword()

w[k][j][0]=w[k][j][0]^Rcon[k][j];//生成ti(1字節(jié)) key_temp[j]=w[k][j][0];//通過j循環(huán)提取ti(1字節(jié))

w[k][j][0]=w[k][j][0]^w[k-1][j][0];

//i(mod 4)=0

w[k][j][i]=w[k-1][j][i]^w[k][j][i-1];

//i(mod 4)≠0

}

}

key_1[k-1][0]=key_temp[0];//將10輪ti提取出來

key_1[k-1][1]=key_temp[1];

key_1[k-1][2]=key_temp[2];

key_1[k-1][3]=key_temp[3];

}

for(int p=0;p<4;p++)

//提取6-9輪ti值賦給初始種子密鑰

{

key[0][p]=key_1[5][p];

key[1][p]=key_1[6][p];

key[2][p]=key_1[7][p];

key[3][p]=key_1[8][p];

}

}

}

程序中套用3個循環(huán),k循環(huán)表示10輪迭代,每輪迭代需要4個密鑰字wi,i循環(huán)代表每輪迭代中4個wi,j循環(huán)代表每個wi中的4個字節(jié)。ti的生成與提取都是在j循環(huán)內(nèi)按單個字節(jié),分4次完成的。

2.2 安全性分析

研究表明,改進(jìn)后的LEX算法可以有效地抵抗滑動攻擊,具體分析如下:

分析可知,改進(jìn)后的LEX算法,各AES模塊加密密鑰發(fā)生變化,阻斷了各AES模塊上的直接關(guān)聯(lián),使各組密鑰不會通過對比分析而泄露出來,在根源上破解了滑動攻擊的攻擊點(diǎn),從而使攻擊者無法找到可以實(shí)施滑動攻擊的碰撞對,提高算法安全性。

2.3 速度分析

改進(jìn)后的LEX算法較原算法略為復(fù)雜,各組AES加密密鑰均發(fā)生變化。但是,算法改進(jìn)的重點(diǎn)是在密鑰擴(kuò)展階段提取了部分中間變量t4i(i=6,7,8,9),通過兩步代碼存儲到原初始密鑰的位置,供下一組AES運(yùn)行時直接調(diào)用。算法的整個改進(jìn)過程中沒有產(chǎn)生新的變量,沒有增加額外的計(jì)算,兩步儲存所需時間與整個算法的運(yùn)行時間相比可以忽略不計(jì)。因此,改進(jìn)后的算法在速度上保持了原LEX快速的特點(diǎn),約為OFB模式下AES的2.5倍(320/128=2.5)。

3 特性仿真實(shí)例與分析

合格的流密碼算法必須要保證生成的密鑰流具備良好的隨機(jī)特性。根據(jù)我國隨機(jī)性檢測標(biāo)準(zhǔn)《隨機(jī)性檢測規(guī)范》[13]規(guī)定,隨機(jī)性合格的序列須通過單比特頻數(shù)檢測、二元推導(dǎo)檢測、近似熵檢測、重疊子序列檢測、塊內(nèi)頻數(shù)檢測、游程總數(shù)檢測、塊內(nèi)最大1游程檢測、撲克檢測、游程分布檢測、自相關(guān)檢測、線性復(fù)雜度檢測、矩陣秩檢測、累加和檢測、Maurer通用統(tǒng)計(jì)檢測、離散傅里葉檢測等15種隨機(jī)性檢測。

序列隨機(jī)性的檢測方法如下[13]:

1)用隨機(jī)數(shù)發(fā)生器產(chǎn)生1 000個長度為105bit的0-1序列作為待檢樣本。

2)對待檢驗(yàn)的1 000個樣本依次進(jìn)行上述15項(xiàng)隨機(jī)性檢測。

3)對于每一項(xiàng)隨機(jī)性檢測項(xiàng)目,統(tǒng)計(jì)P-value值不小于顯著性水平α(建議取α=0.01),表示該樣本通過該項(xiàng)檢測。

下面以塊內(nèi)頻數(shù)檢測為例進(jìn)行簡要說明[13]。

塊內(nèi)頻數(shù)檢測的目的是檢測待檢序列的長度為

m位的子序列中1的個數(shù)是否接近m/2。對隨機(jī)序列來說,其任意長度的m位子序列中1的個數(shù)都應(yīng)該接近m/2。檢測步驟為:

1)將待檢序列ε分為N2=?n/m2」個長度為m2的非重疊子序列,將多余的比特舍棄。本規(guī)范取m2=100。

2)計(jì)算每個子序列中1所占的比例:

5)若P-value≥α,則認(rèn)為待檢序列通過該項(xiàng)檢測。

以C++編程軟件和《隨機(jī)性檢測規(guī)范》為依托,搭建針對LEX改進(jìn)算法的隨機(jī)性檢測平臺,對LEX改進(jìn)算法產(chǎn)生的1 000個105bit 0-1序列進(jìn)行隨機(jī)性檢測。如果每項(xiàng)檢測未通過數(shù)不大于19,則通過該項(xiàng)檢測;如果本規(guī)范所規(guī)定的15項(xiàng)檢測全部通過,則改進(jìn)后的LEX算法通過本規(guī)范檢測;否則,未通過本規(guī)范檢測。

改進(jìn)的LEX算法隨機(jī)性檢測總體情況如表1所示。為便于對比分析,表1同時列出了同等條件的LEX算法的檢測結(jié)果[14]。從檢測結(jié)果可知,2種方案15項(xiàng)檢測未通過數(shù)均小于19,通過隨機(jī)性檢測。對比來看,雖然改進(jìn)后的LEX算法在15個單項(xiàng)檢測中未通過組數(shù)較原始算法有所差別,但P-value值期望和方差分基本保持一致,除矩陣秩與離散傅里葉2項(xiàng)檢測值略有差別,其余項(xiàng)目均在0.5與0.08之間上下浮動,未發(fā)生明顯變化,說明改進(jìn)后的算法保持了原LEX算法良好的隨機(jī)特性,通過隨機(jī)性檢測,符合序列隨機(jī)性要求。

表1 樣本隨機(jī)性檢測結(jié)果分析

4 結(jié)束語

以分組密碼AES為核心設(shè)計(jì)的流密碼算法LEX是現(xiàn)代流密碼算法設(shè)計(jì)的一種重要方法。但LEX算法的結(jié)構(gòu)缺陷,引發(fā)了眾多密碼界學(xué)者對其進(jìn)行分析和攻擊,其中又以滑動攻擊最為有效,只需要261個初始輸入IV和2×104Byte的密鑰流,就可以完全恢復(fù)出128 bit密鑰[15]。本文以LEX算法為基礎(chǔ),對其密鑰體系進(jìn)行改進(jìn),使其每組AES的加密密鑰均不同,具備抵抗滑動攻擊的能力,提高了LEX算法的安全性,并且保持了LEX算法較高的運(yùn)行速度。同時,實(shí)驗(yàn)仿真結(jié)果表明,改進(jìn)后的算法延續(xù)了LEX算法良好的隨機(jī)特性。由于算法本身的結(jié)構(gòu)與運(yùn)算并未做調(diào)整,因此改進(jìn)后的算法在其他方面性能與LEX算法相當(dāng)。

[1] ECRYPT.eSTREAM:ECRYPT Stream Cipher Project,IST-2002-507932[EB/OL].(2004-02-11).http://www.ecrypt.eu.org/stream.

[2] HASTAD J,NASLUND M.The Stream Cipher Polar Bear[EB/OL].(2005-02-10).http://www.ecrypt.eu.org /strearm/.

[3] BIRYUKOV A.A New 128-bit Key Stream Cipher LEX[EB/OL].(2005-06-13).http://www.ecrypt.eu.org/stream/ciphers/lex/lex.pdf.

[4] National Institute of Standards and Technology.Announcing the Advanced Encryption Standard(AES)[EB/OL].(2001-11-26).http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf.

[5] HENRICKSEN M.Flexible Block Ciphers:Modifying LEX[C]//Proceedings of IEEE International Conference on Computer Science & Information Technology.Washington D.C.,USA:IEEE Press,2010:630-634.

[6] VELICHKOV V,RIJMEN V,PRENEEL B.Algebraic Cryptanalysis of a Small-scale Version of Stream Cipher LEX[J].Information Security,2010,4(2):49-61.

[7] 張中亞,關(guān) 杰.對流密碼算法LEX的差分故障攻擊[J].上海交通大學(xué)學(xué)報(自然科學(xué)版),2012,46(6):865-869.

[8] WU Hongjun,PRENEEL B.Attacking the IV Setup of Stream Cipher LEX[EB/OL].(2006-03-15).http://www.ecrypt.eu.org/stream/papersdir/059.pdf.

[9] 鄧元慶,龔 晶,石 會.密碼學(xué)簡明教程[M].北京:清華大學(xué)出版社,2011.

[10] 李佳雨,石 會,鄧元慶,等.抗滑動攻擊的LEX算法改進(jìn)及分析[J].通信技術(shù),2015,48(2):203-207.

[11] 李 欣,譚曉青.抵抗滑動攻擊的LEX算法改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(26):101-103.

[12] 尤加勇,李 超.針對LEX算法的截?cái)嗷瑒庸鬧J].信息安全與通信保密,2007(9):96-98.

[13] 國家秘密管理局.隨機(jī)性檢測檢測規(guī)范:GM/T0005-2012[M].北京:中國標(biāo)準(zhǔn)出版社,2012.

[14] 李佳雨,石 會,鄧元慶,等.針對流密碼LEX的差分故障攻擊及算法改進(jìn)分析[J].計(jì)算機(jī)科學(xué),2015,42(11):352-356.

[15] 李佳雨.流密碼算法DLEX設(shè)計(jì)與分析[D].南京:解放軍理工大學(xué),2015.