低輪PUFFIN算法的積分攻擊*

趙光耀，成　磊，李瑞林，李　超,，孫　兵

(1.國防科技大學(xué) 計(jì)算機(jī)學(xué)院， 湖南 長沙　410073； 2.國防科技大學(xué) 理學(xué)院， 湖南 長沙　410073；

3.國防科技大學(xué) 電子科學(xué)與工程學(xué)院， 湖南 長沙　410073)

?

低輪PUFFIN算法的積分攻擊*

趙光耀1，成磊2，李瑞林3，李超1,2，孫兵2

(1.國防科技大學(xué) 計(jì)算機(jī)學(xué)院， 湖南 長沙410073； 2.國防科技大學(xué) 理學(xué)院， 湖南 長沙410073；

3.國防科技大學(xué) 電子科學(xué)與工程學(xué)院， 湖南 長沙410073)

摘要：PUFFIN是一個(gè)分組長度為64bit的輕量級(jí)分組密碼算法，其密鑰長度為128bit。對(duì)PUFFIN抵抗積分攻擊的能力進(jìn)行研究，構(gòu)造并證明PUFFIN算法存在5輪和6輪積分區(qū)分器。利用6輪積分區(qū)分器對(duì)8輪PUFFIN進(jìn)行積分攻擊，可恢復(fù)2輪共100bit輪密鑰，攻擊的數(shù)據(jù)復(fù)雜度為220個(gè)選擇明文，時(shí)間復(fù)雜度約為233次8輪加密，存儲(chǔ)復(fù)雜度為220，這是目前為止對(duì)PUFFIN最好的積分分析結(jié)果。

關(guān)鍵詞：PUFFIN；輕量級(jí)分組密碼；積分攻擊

隨著物聯(lián)網(wǎng)等應(yīng)用的興起，適用于資源受限環(huán)境的輕量級(jí)密碼算法得到了飛速發(fā)展，密碼學(xué)者根據(jù)不同的應(yīng)用需求設(shè)計(jì)了許多的輕量級(jí)算法，例如HIGHT[1]，LBlock[2]，LED[3]，PRESENT[4]等。PUFFIN[5]也是一種輕量級(jí)分組密碼算法，采用混淆擴(kuò)散網(wǎng)絡(luò)結(jié)構(gòu)(Substitution Permutation Networks，SPN)型結(jié)構(gòu)，其分組長度為64bit，密鑰長度為128bit。非線性層由16個(gè)相同的4×4的S盒并置組成，線性層則為64bit置換，其S盒及P置換均為對(duì)合結(jié)構(gòu)，使得其加解密結(jié)構(gòu)一致，硬件實(shí)現(xiàn)時(shí)占用芯片面積非常小。文獻(xiàn)[5]中，設(shè)計(jì)者對(duì)PUFFIN抵抗差分分析[6]、線性分析[7]、相關(guān)密鑰攻擊[8]的能力進(jìn)行了分析，并分析了算法的弱密鑰[9]，目前對(duì)PUFFIN的第三方安全性分析結(jié)果主要有線性分析[10]和積分攻擊[11]。文獻(xiàn)[10]主要分析了PUFFIN的線性特征，并對(duì)其進(jìn)行了線性攻擊；文獻(xiàn)[11]則首次對(duì)PUFFIN抵抗積分攻擊的安全性進(jìn)行了研究。

積分攻擊[12]的原理由Knudsen和Wagner提出。自提出以后，積分攻擊在許多基于字節(jié)設(shè)計(jì)的算法上得到了很好的應(yīng)用，例如Camellia[13], CLEFIA[14]等。Z′aba等針對(duì)Noekeon，Serpent，Present等基于比特設(shè)計(jì)的算法對(duì)積分攻擊進(jìn)行了擴(kuò)展，提出了基于比特的積分攻擊[15]。

1基礎(chǔ)理論

1.1　PUFFIN簡介

PUFFIN為SPN型結(jié)構(gòu)分組密碼算法，其分組長度和密鑰長度分別為64bit和128bit，迭代32輪。64bit明文(中間狀態(tài)，輪密鑰及密文)排列成一個(gè)4行16列的二維數(shù)組形式，即p0,p1,…,p63可表示成V0, V1,…, V15共16個(gè)向量，其中Vi=(p4i,p4i+1,p4i+2,p4i+3)T，0≤i≤15，如圖1所示。

V0V1V2V3V4V5V6V7V8V9V10V11V12V13V14V15p0p4p8p12p16p20p24p28p32p36p40p44p48p52p56p60p1p5p9p13p17p21p25p29p33p37p41p45p49p53p57p61p2p6p10p14p18p22p26p30p34p38p42p46p50p54p58p62p3p7p11p15p19p23p27p31p35p39p43p47p51p55p59p63

圖1PUFFIN分組比特順序

Fig.1Block state of PUFFIN

輪函數(shù)包含以下3個(gè)變換：

1)非線性層γ由16個(gè)相同的4×4的S盒并置組成，每列(Vi)通過1個(gè)S盒。S盒映射見表1。

表1　S盒映射(16進(jìn)制表示)

性質(zhì)(S盒表達(dá)式)設(shè)x=(x3,x2,x1,x0)和y=(y3,y2,y1,y0)分別表示S盒的輸入和輸出(如圖2所示)，則x和y滿足：

y0=x0x1x2+x0x1x3+x0x1+x0x2+x0x3+x1x2+x2x3+1,

y1=x0x1x3+x0x1+x0+x1x2+x1+x3,

y2=x0x1x2+x0x2x3+x1x2x3+x1x3+x1+x2x3+x2+1,

y3=x0x1x3+x0x1+x0x2+x0+x1x2x3+x1x2+x1+x2x3+1。

圖2　S盒的輸入輸出Fig.2　Input and output of S box

2)密鑰加σ∶64bit的輪密鑰與64bit的狀態(tài)進(jìn)行異或。

3)線性層進(jìn)行P64 ∶64bit的一個(gè)置換，其映射見表2。變換輸入為(行標(biāo)× 8 + 列標(biāo) + 1)，如表2中(0,0)位置對(duì)應(yīng)的元素為13，即P64(0× 8 + 0+ 1)=P64(1)=13。

加密之初，首先進(jìn)行密鑰白化以及一個(gè)P64轉(zhuǎn)換，然后進(jìn)行32輪輪函數(shù)的迭代，所以PUFFIN加密過程可表示為

表2　P64映射

1.2　基于比特的積分攻擊

Z′aba等提出的基于比特的積分，實(shí)際上是基于計(jì)數(shù)方法來進(jìn)行的，通過統(tǒng)計(jì)每個(gè)比特上不同元素出現(xiàn)的奇偶次數(shù)來判斷其平衡性。實(shí)際上，通過布爾函數(shù)的最高次項(xiàng)系數(shù)取值也可以判定其平衡性。

定理1說明，要確定密文某個(gè)位置是否平衡，可通過研究該位置密文與明文之間多項(xiàng)式函數(shù)的最高項(xiàng)系數(shù)來判斷。定理2則給出了一個(gè)判斷最高項(xiàng)系數(shù)的方法。

令deg(f)表示f的最高次數(shù)，若密文某個(gè)比特位置的表達(dá)式f對(duì)任意的c0,c1,…,cn-m-1都滿足

deg(f) ≤m-1,

則對(duì)此位置上出現(xiàn)的所有2m個(gè)元素(g0,g1,…,g2m-1)求和有

∑gi=0，0 ≤i≤ 2m-1,

即對(duì)應(yīng)的多項(xiàng)式函數(shù)最高次項(xiàng)系數(shù)為0，此時(shí)該比特是平衡的。

2PUFFIN的積分攻擊

2.1　PUFFIN的5輪積分區(qū)分器

定理3設(shè)明文為P= (p0,p1,…,p63) ，則當(dāng)(p6,p24,p31,p60)遍歷{0,1}4時(shí)， 5輪加密后密文有29個(gè)比特是平衡的。

證明：當(dāng)輸入明文的活躍位置為p6,p24,p31,p60時(shí)，狀態(tài)可表示為：

方格內(nèi)數(shù)字表示比特順序，每一輪開始時(shí)重新編號(hào)。

經(jīng)過P64后，活躍位置將位于同一列，即為：

再經(jīng)過第1輪的S盒后，狀態(tài)為：

記這4個(gè)位置的變量分別為y0,y1,y2,y3，則經(jīng)過第1輪的P64后，狀態(tài)變?yōu)椋?/p>

灰色底紋標(biāo)記的位置標(biāo)注有當(dāng)前比特表達(dá)式的最高次項(xiàng)，無底紋的位置為常數(shù)，即其取值不受yi影響。

經(jīng)過第2輪的S盒后，狀態(tài)變?yōu)椋?/p>

再經(jīng)過P64狀態(tài)為：

經(jīng)過第3輪的S盒后，依據(jù)性質(zhì)1，狀態(tài)變?yōu)椋?/p>

其中yijk表示此比特表達(dá)式的最高次項(xiàng)為yiyjyk，0≤i,j,k≤3。第3輪的輸出狀態(tài)為：

依此類推，可得第4輪的輸出狀態(tài)為：

第5輪的輸出狀態(tài)為：

綜上討論，當(dāng)(p6,p24,p31,p60)遍歷{0,1}4時(shí), (y0,y1,y2,y3)也取遍24個(gè)值，則5輪加密后的密文中灰色底紋標(biāo)記的比特位置關(guān)于y0,y1,y2,y3的布爾函數(shù)f(y0,y1,y2,y3)，滿足deg(f)≤ 3，因此這些比特位置平衡。

□

2.2　PUFFIN的6輪積分區(qū)分器

在5輪積分區(qū)分器前加1輪，可將其擴(kuò)展至6輪的積分區(qū)分器。

定理4當(dāng)明文的16個(gè)比特{p5,p8,p9,p10,p11,p26,p27,p28,p29,p30,p35,p42,p50,p51,p61,p63}遍歷{0,1}16時(shí)，6輪PUFFIN算法加密后密文的平衡比特與2.1節(jié)所述的5輪積分區(qū)分器輸出平衡位置相同。

證明：如圖3所示，當(dāng){p5,p8,p9,p10,p11,p26,p27,p28,p29,p30,p35,p42,p50,p51,p61,p63}遍歷{0,1}16時(shí)，經(jīng)過白化和P64變換后，輸出狀態(tài)的V1,V6,V7,V15的級(jí)聯(lián)遍歷{0,1}16，經(jīng)過第1輪非線性層后，第6、第24、第31和第60比特遍歷{0,1}4，從而滿足5輪積分區(qū)分器的輸入狀態(tài)，故原5輪積分區(qū)分器的平衡位置在該6輪積分區(qū)分器中仍然平衡。

□

上述證明說明5輪積分區(qū)分器的29個(gè)平衡位置在擴(kuò)展的6輪高階積分區(qū)分器中仍然平衡，通過實(shí)驗(yàn)測試驗(yàn)證，擴(kuò)展的6輪高階積分區(qū)分器有且僅有這29個(gè)平衡位置。

圖3　將5輪積分區(qū)分器擴(kuò)展至6輪積分區(qū)分器Fig.3　Extend the 5-round integral distinguisher to the 6-round one

2.3　對(duì)8輪PUFFIN的積分攻擊

利用6輪的高階積分區(qū)分器，可以對(duì)8輪的PUFFIN進(jìn)行積分攻擊，從而可獲取部分輪密鑰信息。如圖4所示。

圖4　8輪PUFFIN算法的積分攻擊Fig.4　Integral attack on 8-round PUFFIN

攻擊的主要思想是通過猜測第8輪的輪密鑰RK(8)及第7輪的輪密鑰RK(7)的部分比特，對(duì)密文進(jìn)行部分解密后，觀測第6輪輸出的對(duì)應(yīng)位置是否平衡來篩選密鑰。當(dāng)選擇不同的平衡位置進(jìn)行密鑰篩選時(shí)，能夠篩選的RK(8)和RK(7)的密鑰字(4bit)是不同的，平衡位置與可篩選的密鑰字間的對(duì)應(yīng)關(guān)系見表3。

表3　選擇平衡位置與可篩選密鑰字的對(duì)應(yīng)關(guān)系

以44, 45, 46, 47這4個(gè)平衡位置為例，其攻擊步驟為：

1)選擇一組明文(其中{p5,p8,p9,p10,p11,p26,p27,p28,p29,p30,p35,p42,p50,p51,p61,p63}取遍{0,1}16，其余位置為常數(shù)，故一組明文包含216個(gè)明文)進(jìn)行8輪加密，密文記為C0,C1,…,C216-1。

2)猜測RK(8)的4個(gè)密鑰字(共16bit)RK3(8),RK5(8),RK9(8),RK13(8)，計(jì)算Qj(i)=γ-1(P64-1(Ci)RKj(8)),j∈{3,5,9,13}。

3)計(jì)算Ti=P64-1(Q(i))，猜測RK(7)的一個(gè)密鑰字RK11(7)，計(jì)算t=S-1(T11iRK11(7))。

4)判斷t是否為0，若t=0，則猜測的RK3(8),RK5(8),RK9(8),RK13(8),RK11(7)正確，否則，淘汰。

5)重新選取一組明文，重復(fù)上述步驟，直到唯一確定RK3(8)，RK5(8)，RK9(8)，RK13(8)和RK11(7)。

實(shí)驗(yàn)及結(jié)果：在PC機(jī)上利用C++(Visual C++6.0)編程模擬了密鑰篩選過程。實(shí)驗(yàn)中每組明文的常數(shù)值隨機(jī)生成，首先考慮當(dāng)11次篩選均對(duì)20bit輪密鑰進(jìn)行篩選時(shí)(重復(fù)篩)，共做了500次模擬實(shí)驗(yàn)，統(tǒng)計(jì)唯一確定20bit密鑰平均所需的明文組數(shù)。實(shí)驗(yàn)結(jié)果如圖4所示。

圖4　唯一確定密鑰所需明文組數(shù)(重復(fù)篩選時(shí))Fig.4　Group number of plaintexts to find the right key (when each filtration works on 20bit keys)

若在篩選過程中，已經(jīng)確定的密鑰字不再重新篩選(不重復(fù)篩)，統(tǒng)計(jì)唯一確定猜測密鑰字所需的明文組數(shù)。圖5所示為500次模擬實(shí)驗(yàn)的平均結(jié)果。

圖5　唯一確定密鑰所需明文組數(shù)(不重復(fù)篩選時(shí))Fig.5　Group number of plaintexts to find the right key (when filtrating step by step)

實(shí)驗(yàn)結(jié)果顯示，大部分篩選使用約16組明文即可唯一確定正確密鑰(攻擊時(shí)可按照所需明文組數(shù)由少到多的順序進(jìn)行篩選，保證前面的篩選能夠?qū)⒚荑€字唯一確定)。當(dāng)使用平衡位置{56,59}以及{44,45,46,47}進(jìn)行篩選時(shí)，需要的明文組較多，這主要是由于這些平衡位置比較特殊，對(duì)于猜測的RK(7)密鑰字的所有可能取值，這些位置以較大概率保持平衡，所以在確定正確密鑰過程中需要的明文組數(shù)很多。

3結(jié)論

利用基于比特的積分思想對(duì)PUFFIN算法進(jìn)行了積分分析，構(gòu)造并證明了算法存在5輪和6輪積分區(qū)分器，對(duì)8輪PUFFIN算法進(jìn)行了積分攻擊。構(gòu)造的積分區(qū)分器輸出的平衡位置較多，因此對(duì)8輪PUFFIN算法進(jìn)行積分攻擊時(shí)效率較高，恢復(fù)100bit輪密鑰所需的數(shù)據(jù)復(fù)雜度為220個(gè)選擇明文，時(shí)間復(fù)雜度為233次8輪加密，存儲(chǔ)復(fù)雜度為220。

參考文獻(xiàn)(References)

[1]Hong D, Sung J, Hong S,et al. HIGHT: a new block cipher suitable for low-resource device[C]//Proceedings of Cryptographic Hardware and Embedded Systems,2006,4249: 46-59.

[2]Wu W L, Zhang L. LBlock: a lightweight block cipher[C] //Proceedings of Applied Cryptography and Network Security，2011，6715: 327-344.

[3]Guo J, Peyrin T, Poschmann A, et al. The LED block cipher[C] //Proceedings of Cryptographic Hardware and Embedded Systems, 2011,6917: 326-341.

[4]Bogdanov A, Knudsen L, Leander G,et al. PRESENT: an ultra-lightweight block cipher[C]//Proceedings of Cryptographic Hardware and Embedded Systems,2007,4727: 450-466.

[5]Cheng H, Heys H, Wang C. PUFFIN: a novel compact block cipher targeted to embedded digital systems[C] //Proceedings of 11thEUROMICRO Conference on Digital System Design: Architectures, Methods and Tools,2008: 383-390.

[6]Biham E,Shamir A. Differential cryptanalysis of DES-like cryptosystems[C] //Proceedings of Advances in Cryptology: CRYPTO′90, 1990，537: 2-21.

[7]Matsui M. Linear cryptanalysis method for DES cipher[C]//Proceedings of Advances in Cryptology: EUROCRYPT ′93,1993,765: 386-397.

[8]Biham E. New type of cryptanalytic attacks using related keys[J]. Journal of Cryptology, 1994,7(4): 229-246.

[9]Moore J H, Simmons G J. Cycle structure of the DES for keys having palindromic (or antipalindromic) sequences of round keys[J]. IEEE Transactions on Software Engineering, 1987, 13(2):262-273.

[10]Leander G. On linear hulls, statistical saturation attacks, PRESENT and a cryptanalysis of PUFFIN[C] //Proceedings of Advances in Cryptology-EUROCRYPT,2011,6632: 303-322.

[11]魏悅川，孫兵，李超. 一 種PUFFIN類 SPN型分組密碼的積分攻擊[J]. 國防科技大學(xué)學(xué)報(bào), 2010, 32(3): 139-143.

WEI Yuechuan, SUN Bing, LI Chao. An integral attack on PUFFIN and PUFFIN-like SPN cipher[J]. Journal of National University of Defense Technology, 2010, 32(3): 139-143. (in Chinese)

[12]Knudsen L, Wagner D. Integral cryptanalysis[C]//Proceedings of Fast Software Encryption, 2002, 2365: 112-127.

[13]Lei D, Li C, Feng K Q. New observation on camellia[C]//Proceedings of Selected Areas in Cryptography, 2005, 3897: 51-64．

[14]王薇，王小云．對(duì)CLEFIA算法的飽和度分析[J]．通信學(xué)報(bào)， 2008, 29(10): 88-92.

WANG Wei, WANG Xiaoyun. Saturation cryptanalysis of CLEFIA[J]. Journal on Communications, 2008,29(10): 88-92. (in Chinese)

[15]Z′aba M R, Raddum H, Henricksen M,et al. Bit-pattern based integral attack[C] //Proceedings of Fast Software Encryption, 2008, 5086: 363-381.

[16]李超, 孫兵, 李瑞林. 分組密碼的攻擊方法與實(shí)例分析[M]. 北京:科學(xué)出版社, 2010.

LI Chao, SUN Bing, LI Ruilin. Cryptanalytic methods and instance analysis of block ciphers[M].Beijing:Science Press, 2010.(in Chinese)

http://journal.nudt.edu.cn

Integral cryptanalysis on reduced-round PUFFIN

ZHAOGuangyao1,CHENGLei2,LIRuilin3,LIChao1,2,SUNBing2

(1. College of Computer, National University of Defense Technology, Changsha 410073, China；

2.College of Science, National University of Defense Technology, Changsha 410073, China；

3.College of Electronic Science and Engineering, National University of Defense Technology, Changsha 410073, China)

Abstract：PUFFIN is a lightweight block cipher, in which the block length is 64 bit while the key size is 128 bit. The integral cryptanalysis resistance ability of PUFFIN was analyzed. The existence of 5 and 6 round integral distinguisher in PUFFIN was constructed and proved. An integral attack on 8 round PUFFIN was mounted by 6 round integral distinguisher to recover 2 round 100 bit round cipher. The data complexity of the attack is 220chosen plaintexts, the time complexity is about 2338 round encryptions, and the space complexity is 220. This has been the best integral attack on PUFFIN up to now.

Key words：PUFFIN; lightweight block cipher; integral attack

中圖分類號(hào)：TN918

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-2486(2015)06-129-06

作者簡介：趙光耀(1982—)，男，湖南湘潭人，博士研究生，E-mail：securityzgy@163.com；孫兵(通信作者)，男，講師，博士，E-mail：happycome@163.com

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(61402515)；信息保障技術(shù)國家重點(diǎn)實(shí)驗(yàn)室開放基金資助項(xiàng)目(KJ-14-003)

收稿日期：*2015-01-12

doi:10.11887/j.cn.201506024