一種抗滑動攻擊的密鑰流提取改進算法

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

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

0 概述

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

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

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

1 LEX算法

LEX算法采用128 bit分組密碼高級加密標準AES作為密鑰流產生部件,它的出現架起了分組密碼與序列密碼設計的橋梁,具有十分重要的意義。

1.1 LEX算法結構

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

圖1 LEX算法的結構框圖

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

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,根據i的不同取值,可代表每輪迭代后中間狀態的第0,1,2,3個行向量,各由4個字節組成。

圖2 奇數輪和偶數輪提取的字節位置

1.2 密鑰擴展算法

LEX算法的密鑰擴展運算依托其核心部件AES算法實現,通過密鑰擴展將16 Byte的初始密鑰K擴展為176 Byte,具體過程如下[9]:

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

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

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

wi=wi-1⊕wi-4

(1)

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

wi=ti⊕wi-4

(2)

ti為中間變量,其表達式為:

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

(3)

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

1.3 針對LEX的滑動攻擊

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

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

(4)

(5)

2 LEX算法的改進及分析

2.1 LEX算法的改進

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

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

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

圖4 改進的LEX算法結構

通過C++編程工具實現對算法的改進,密鑰擴展部分的偽代碼形式如下:

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字節) key_temp[j]=w[k][j][0];//通過j循環提取ti(1字節)

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個循環,k循環表示10輪迭代,每輪迭代需要4個密鑰字wi,i循環代表每輪迭代中4個wi,j循環代表每個wi中的4個字節。ti的生成與提取都是在j循環內按單個字節,分4次完成的。

2.2 安全性分析

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

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

2.3 速度分析

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

3 特性仿真實例與分析

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

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

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

2)對待檢驗的1 000個樣本依次進行上述15項隨機性檢測。

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

下面以塊內頻數檢測為例進行簡要說明[13]。

塊內頻數檢測的目的是檢測待檢序列的長度為

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

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

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

5)若P-value≥α,則認為待檢序列通過該項檢測。

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

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

表1 樣本隨機性檢測結果分析

4 結束語

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

[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] 張中亞,關 杰.對流密碼算法LEX的差分故障攻擊[J].上海交通大學學報(自然科學版),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] 鄧元慶,龔 晶,石 會.密碼學簡明教程[M].北京:清華大學出版社,2011.

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

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

[12] 尤加勇,李 超.針對LEX算法的截斷滑動攻擊[J].信息安全與通信保密,2007(9):96-98.

[13] 國家秘密管理局.隨機性檢測檢測規范:GM/T0005-2012[M].北京:中國標準出版社,2012.

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

[15] 李佳雨.流密碼算法DLEX設計與分析[D].南京:解放軍理工大學,2015.