EPCBC密碼旁路立方體攻擊

趙新杰, 郭世澤, 王 韜, 張 帆

（1.軍械工程學(xué)院計(jì)算機(jī)工程系,河北石家莊 050003;2.北方電子設(shè)備研究所,北京 100083;3.康涅狄格大學(xué)計(jì)算機(jī)科學(xué)與工程系,斯托斯康涅狄格州 06269）

0 引言

早在2008年美密會(huì)的Rump Session討論中[1],Dinur和Shamir在高階差分分析[2]基礎(chǔ)上,提出了一種新的密碼分析方法——立方體攻擊（Cube Attack）,并聲稱只要密碼算法的一個(gè)密文比特能夠用公開(kāi)變量和密鑰相關(guān)變量的低次多元多項(xiàng)式表示,立方體攻擊就能夠攻破此密碼算法。此外,立方體攻擊的一大亮點(diǎn)是可在黑盒攻擊場(chǎng)景下成功實(shí)施,即適用于密碼算法未知情況下。目前,立方體攻擊在流密碼分析中卓有成效,已經(jīng)對(duì)低輪的Trivium[3]、MD6[4]密碼,甚至全輪Hitag2[5]、Grain-128[6]密碼進(jìn)行了成功分析。在分組密碼Cube分析中,分組密碼的多項(xiàng)式次數(shù)和項(xiàng)數(shù)隨著輪數(shù)的延伸呈指數(shù)級(jí)增長(zhǎng),多項(xiàng)式的存儲(chǔ)和表示十分困難。因此在傳統(tǒng)密碼分析場(chǎng)景下,立方體攻擊僅對(duì)約簡(jiǎn)輪的分組密碼分析有效,攻擊遇到了NP-完全問(wèn)題的瓶頸。

隨著電子信息技術(shù)和普適計(jì)算的發(fā)展,RFID標(biāo)簽和無(wú)線傳感器網(wǎng)絡(luò)深入到人們生活的方方面面,如何在此類資源受限的環(huán)境下提供信息安全保障成為尚待解決的問(wèn)題。輕量級(jí)密碼算法正是在這種趨勢(shì)上發(fā)展起來(lái)的,這些算法都要求在2000個(gè)門電路內(nèi)硬件實(shí)現(xiàn),特別適用于RFID標(biāo)簽等輕量級(jí)密碼設(shè)備的加密需要。由于輕量級(jí)密碼算法結(jié)構(gòu)設(shè)計(jì)相對(duì)比較簡(jiǎn)單緊湊,中間狀態(tài)的多項(xiàng)式復(fù)雜度較低,且輕量級(jí)的實(shí)現(xiàn)防護(hù)措施較少,極易遭受旁路立方體攻擊的威脅。密碼學(xué)者在仿真環(huán)境下對(duì)大量的輕量級(jí)密碼進(jìn)行了旁路立方體分析,如PRESENT[8-11],NOEKEON[12]、KATAN[13]。EPCBC密碼[14]是Yap等在CANS 2011國(guó)際會(huì)議提出的輕量級(jí)分組密碼,算法采用類PRESENT密碼設(shè)計(jì)思想,其96位的密鑰長(zhǎng)度設(shè)計(jì)特別適用于RFID標(biāo)簽上的密碼算法實(shí)現(xiàn),加密效率優(yōu)于AES和PRESENT。此外,設(shè)計(jì)者聲稱EPCBC可有效防御積分攻擊、線性攻擊、高階差分攻擊、滑動(dòng)攻擊,特別是改進(jìn)的密鑰擴(kuò)展設(shè)計(jì)使其可有效抵抗相關(guān)密鑰攻擊。目前,在EPCBC抗旁路攻擊安全性分析方面,尤其是抗旁路立方體攻擊方面尚未發(fā)現(xiàn)有公開(kāi)發(fā)表結(jié)果。

文獻(xiàn)[11]基于8比特漢明重泄露模型,對(duì)PRESENT密碼抗旁路立方體攻擊能力進(jìn)行了評(píng)估,在PRESENT算法設(shè)計(jì)已知情況下,28.95個(gè)選擇明文可恢復(fù)PRESENT-80的72比特密鑰,29.78個(gè)選擇明文可恢復(fù)PRESENT-128的121比特密鑰,攻擊最大立方體大小僅為5;并對(duì)8位微控制器ATMEGA324P上的PRESENT密碼進(jìn)行物理實(shí)驗(yàn),驗(yàn)證了攻擊實(shí)際可行性。由于EPCBC密碼基于PRESENT密碼思想設(shè)計(jì),根據(jù)文獻(xiàn)[11]中攻擊結(jié)果,認(rèn)為EPCBC密碼可能易遭受旁路立方體攻擊。特別是,如果在EPCBC密碼旁路立方體攻擊中,提取的立方體大小仍然很小的話,攻擊在黑盒場(chǎng)景下實(shí)施的復(fù)雜度應(yīng)該較低。為了驗(yàn)證上述推測(cè),基于漢明重泄露模型,對(duì)EPCBC密碼抗黑盒旁路立方體攻擊能力進(jìn)行分析。結(jié)果表明:EPCBC密碼易遭受黑盒旁路立方體攻擊,攻擊提取的最大立方體大小僅為5372個(gè)選擇明文可恢復(fù)EPCBC（48,96）的48比特密鑰,將其主密鑰搜索空間降低到248610個(gè)選擇明文可恢復(fù)EPCBC（96,96）的全部96比特主密鑰。

1 相關(guān)知識(shí)

1.1 EPCBC算法設(shè)計(jì)

EPC（Electronic Product Code）[15]是EPCglobal提出的一種工業(yè)標(biāo)準(zhǔn),標(biāo)準(zhǔn)主要利用Class 1 Gen 2的RFID標(biāo)簽作為EPC的載體,其中規(guī)定了低成本應(yīng)用的標(biāo)識(shí)符長(zhǎng)度為96位。但是目前現(xiàn)有的分組長(zhǎng)度和密鑰長(zhǎng)度均為96位的密碼算法很少。比如PRESENT-80的分組長(zhǎng)度為64位,需要執(zhí)行2次加密才能生成標(biāo)識(shí),而AES-128一次加密則會(huì)浪費(fèi)掉32位標(biāo)識(shí)符。EPCBC[14]分組密碼正是為了解決該問(wèn)題而設(shè)計(jì)的,通過(guò)在PRESENT算法設(shè)計(jì)基礎(chǔ)上進(jìn)行改造而成。EPCBC有EPCBC（48,96）和EPCBC（96,96）兩個(gè)變種,分別對(duì)應(yīng)48位和96位分組,密鑰長(zhǎng)度均為96位,加密均使用32輪。EPCBC密碼加密結(jié)構(gòu)同PRESENT類似,只是分組長(zhǎng)度、查找表次數(shù)和置換函數(shù)有所變化。

（1）加密過(guò)程

輪函數(shù)由輪密鑰加、S盒代換、線性置換3部分組成,并在32輪使用后期白化操作。

輪密鑰加 AK:48（96）位輪輸入同48（96）位輪密鑰進(jìn)行異或。

趙天亮瞪著齊勇的背影說(shuō)道:“這件事,不能就這么算完了!這可是我們新知青來(lái)到連隊(duì)的第一天,我一定要代表新知青向連里抗議這件事!”

S盒代換層SL:將輪密鑰加48（96）位輸出查找12（24）個(gè)4進(jìn)4出S盒,S盒沿用PRESENT密碼設(shè)計(jì)。

線性置換層DL:輸入的第i位被置換到輸出的第P[i]位,P[i]計(jì)算方法為:

其中對(duì)于EPCBC（48,96）,n=12;對(duì)于EPCBC（96,96）,n=24。

（2）密鑰擴(kuò)展

為更好抵抗相關(guān)密鑰攻擊威脅,EPCBC設(shè)計(jì)了專門的密鑰擴(kuò)展算法,將加密輪函數(shù)引入到密鑰擴(kuò)展中,設(shè)計(jì)比PRESENT復(fù)雜,具體密鑰擴(kuò)展設(shè)計(jì)細(xì)節(jié)可參考文獻(xiàn)[14]。

1.2 立方體攻擊

立方體攻擊將黑盒密碼算法的輸出比特看成有限域GF（2）上的包含公開(kāi)變量（對(duì)于分組密碼即明文變量）和密鑰變量的未知多項(xiàng)式p。攻擊分為兩個(gè)階段:預(yù)處理階段,攻擊者控制所有公開(kāi)和密鑰變量向密碼算法詢問(wèn)p輸出,等價(jià)于攻擊者在密碼分析中使用不同明文和密鑰運(yùn)行算法,分析得到選擇明文、p輸出和部分密鑰比特相關(guān)多項(xiàng)式關(guān)系;在線階段,攻擊者生成選擇明文,通過(guò)分析 p輸出獲取密鑰比特相關(guān)多項(xiàng)式值,然后通過(guò)方程組求解方法獲取密鑰。

假定密碼由 m個(gè)公共變量V={v1,…,vm}和 n個(gè)密鑰變量K={k1,…,kn}組成。令X=V∪K,則密碼任意輸出比特可用關(guān)于X的一個(gè)多變量多項(xiàng)式f（X）表示,令多項(xiàng)式次數(shù)表示為Deg（f）。下面詳細(xì)闡述攻擊的兩個(gè)階段:

（1）預(yù)處理階段

攻擊者隨機(jī)從 V中選取部分公開(kāi)變量,令I(lǐng)表示所選取公開(kāi)變量下標(biāo)索引集合,I?{1,…,m},I即為一個(gè)立方體,大小為 λ,I中索引稱為為立方體索引。tI表示所選取公開(kāi)變量的乘積,又稱極大項(xiàng)。f（X）可表示為

pS（I）是關(guān)于密鑰變量的一個(gè)多項(xiàng)式,又稱I相關(guān)的一個(gè)超多項(xiàng)式。qI中包括了所有不能被tI整除的子多項(xiàng)式。為更好的解釋定義,這里給出一個(gè)簡(jiǎn)單例子

式（3）最高次數(shù)為4,包含8個(gè)變量、17個(gè)子多項(xiàng)式。將公開(kāi)變量相同的子多項(xiàng)式合并后,f（X）可表示為

根據(jù)式（4）,以大小為3的立方體I={1,2,3}為例,1,2,3為立方體索引值。顯然,tI=v1v2v3,pS（I）=k1+k2+1,qI=v1v4（k1+k3）+…+1。如果將 tI中的所有變量取遍0/1值,V中其他變量取0,則所得到的8個(gè)f（X）累積高階差分即為pS（I）。應(yīng)用類似方法,可得到4個(gè)線性立方體:

（2）在線階段

在線階段中,攻擊者根據(jù)預(yù)處理階段得到的立方體 I生成2λ個(gè)選擇公開(kāi)變量,通過(guò)問(wèn)詢密碼算法得到p的輸出,并計(jì)算高階差分得到對(duì)應(yīng)的超多項(xiàng)式pS（I）的值,然后利用代數(shù)方程求解方法恢復(fù)相關(guān)密鑰變量K。

需要說(shuō)明的是,在線階段主要是通過(guò)問(wèn)詢密碼得到 f（X）輸出,驗(yàn)證預(yù)處理階段得到的立方體 I和超多項(xiàng)式pS（I）之間關(guān)系是否存在。在已知密碼設(shè)計(jì)時(shí),可將 f（X）精確的表示出來(lái),通過(guò)合并極大項(xiàng)的方式得到 I和pS（I）;在未知密碼設(shè)計(jì)時(shí),攻擊者可以窮舉或者隨機(jī)選取 I和pS（I）,通過(guò)在線階段驗(yàn)證二者關(guān)系,并求解出密鑰。

1.3 旁路立方體攻擊

在分組密碼立方體攻擊中,多項(xiàng)式 f（X）的次數(shù)和項(xiàng)數(shù)隨著輪數(shù)延伸呈指數(shù)級(jí)增長(zhǎng),在有限復(fù)雜度內(nèi)將其存儲(chǔ)和表示是一個(gè)NP-完全問(wèn)題,攻擊僅對(duì)約簡(jiǎn)輪分組密碼有效。而當(dāng)考慮到密碼實(shí)現(xiàn)物理泄露時(shí),通過(guò)各種旁路泄露分析得到的中間狀態(tài)可作為天然的多項(xiàng)式f（X）輸出,等效于約簡(jiǎn)輪立方體攻擊的場(chǎng)景。更重要的是,旁路信息的引入使得立方體攻擊對(duì)分組密碼安全性可構(gòu)成現(xiàn)實(shí)威脅,二者的結(jié)合即稱為旁路立方體攻擊。

2 EPCBC旁路立方體攻擊

2.1 漢明重泄露模型

旁路立方體攻擊中,泄露模型的選擇取決于攻擊者的能力,泄露模型不同時(shí)目標(biāo)比特的多項(xiàng)式 f（X）表示方法不同。對(duì)于漢明重泄露模型,由于泄露漢明重的一個(gè)比特和對(duì)應(yīng)的中間狀態(tài)還存在關(guān)系,因此還需要進(jìn)行一定的轉(zhuǎn)換。以一個(gè)字節(jié) X=（x7,x6,x5,x4,x3,x2,x1,x0）的漢明重泄露為例,假如其漢明重Y=H（X）=（y3,y2,y1,y0）,x0和y0分別表示X和Y最低位。Y可用X表示如下

根據(jù)式（6）可知,Y的每一個(gè)比特值都可以作為旁路立方體攻擊中利用的泄露比特。其中y0的次數(shù)是最低的,意味著其對(duì)應(yīng)f（X）的復(fù)雜度是最低的,可以作為漢明重泄露的最佳泄露利用比特。另外,y3,y2,y1也可以在攻擊中使用,但是對(duì)應(yīng) f（X）復(fù)雜度可能較高,需要一些特殊的算法去提取超多項(xiàng)式。

2.2 黑盒旁路立方體攻擊

旁路立方體攻擊繼承了立方體攻擊的優(yōu)點(diǎn),可在未知算法設(shè)計(jì)下實(shí)施。下面給出黑盒旁路立方體分析的算法。

步驟1:攻擊者設(shè)定立方體中明文變量的數(shù)量和超多項(xiàng)式中密鑰變量的數(shù)量,并根據(jù)前面設(shè)定窮舉生成立方體I和超多項(xiàng)式 pS（I）;

步驟2:利用I生成選擇明文和隨機(jī)密鑰,采集加密實(shí)現(xiàn)物理泄露并分析推斷出泄露比特位;

步驟3:測(cè)試pS（I）的值是否等于這些選擇明文對(duì)應(yīng)泄露比特的高階差分;

步驟4:如果步驟3成立,則重復(fù)步驟2～3共N次。如果 N次步驟3結(jié)果都成立,則步驟1中的立方體 I和超多項(xiàng)式pS（I）是有效的;否則無(wú)效,攻擊者重新返回步驟1。

根據(jù)上面算法,黑盒旁路立方體攻擊復(fù)雜度取決于選擇明文變量和超多項(xiàng)式中密文變量數(shù)量,并隨著二者的增加呈指數(shù)級(jí)增長(zhǎng)。選擇明文變量數(shù)量受密碼分組長(zhǎng)度限制,超多項(xiàng)式的數(shù)量受密碼支持密鑰長(zhǎng)度和攻擊者選擇超多項(xiàng)式的階數(shù)限制。在實(shí)際攻擊中,為降低攻擊數(shù)據(jù)復(fù)雜度,一個(gè)好的黑盒立方體攻擊應(yīng)該具有選擇明文變量（立方體大小）和超多項(xiàng)式中密鑰變量數(shù)量較小的特點(diǎn)。

應(yīng)用2.2節(jié)方法,基于漢明重泄露模型,對(duì)EPCBC（48,96）和EPCBC（96,96）分別進(jìn)行了黑盒攻擊。攻擊中,設(shè)定最大立方體大小僅為5,超多項(xiàng)式中密鑰變量數(shù)量最大為3,N=100。參考文獻(xiàn)[11]中泄露比特位置,選取EPCBC加密第三輪輪密鑰加字節(jié)漢明重量的最低泄露比特進(jìn)行密鑰分析。

2.3 EPCBC（48,96）攻擊

EPCBC（48,96）攻擊中,利用加密第三輪輪密鑰加前兩個(gè)字節(jié)的最低位分別作為泄露比特,成功提取出48個(gè)超多項(xiàng)式,使用372個(gè)選擇明文恢復(fù)第一輪48比特密鑰,將其主密鑰搜索空間降低到248。攻擊結(jié)果如表1所示。

表1 EPCBC（48,96）黑盒旁路立方體攻擊結(jié)果

2.4 EPCBC（96,96）攻擊

EPCBC（96,96）攻擊中,利用加密第三輪輪密鑰加的前兩個(gè)字節(jié)的最低位分別作為泄露比特,成功提取出96個(gè)超多項(xiàng)式,使用610個(gè)選擇明文直接恢復(fù)96比特密鑰。攻擊結(jié)果如表2所示。

表2 EPCBC（96,96）黑盒旁路立方體攻擊結(jié)果

3 結(jié)束語(yǔ)

基于8位漢明重泄露模型,對(duì)EPCBC密碼抗黑盒旁路立方體攻擊能力進(jìn)行評(píng)估。結(jié)果表明:EPCBC密碼易遭受黑盒旁路立方體攻擊,如果攻擊者能夠精確獲取加密過(guò)程漢明重信息泄露,提取出的立方體大小最大僅為5;372和610個(gè)選擇明文可分別恢復(fù)EPCBC（48,96）的48比特密鑰和EPCBC（96,96）的全部96比特主密鑰;EPCBC密碼實(shí)現(xiàn)應(yīng)增加旁路立方體攻擊的防護(hù)措施以提高其安全性。

[1] I Dinur,A Shamir.Cube Attacks on Tweakable Black-box Polynomials[EB/OL].http://eprint.iacr.org/2008/385.pdf.

[2] X Lai.Higher Order Derivatives and Differential Cryptanalysis[J].Communications and Cryptography,227-233.

[3] I Dinur,A Shamir.Cube Attacks on Tweakable Black-box Polynomials[A].EUROCRYPT 2009[C].LNCS,2009,5479:278-299.

[4] J P Aumasson,I Dinur,W Meier,et al.Cube Testers and Key Recovery attacks on Reduced-Round MD6 and Trivium[A].In FSE 2009[C].LNCS,2009,5665:1-22.

[5] S Sun,L Hu,Y Xie,et al.Cube Cryptanalysis of Hitag2 Stream Cipher[A].In CANS 2011[C].LNCS,2011,7092:15-25.

[6] I Dinur,A Shamir.Breaking Grain-128 with Dynamic Cube Attacks[A].In FSE 2011[C].LNCS,2011,6733:167-187.

[7] I Dinur,A Shamir.Side Channel Cube Attacks on Block Ciphers[EB/OL].http://eprint.iacr.org/2009/127.pdf.

[8] L Yang,M Wang,S Qiao.Side Channel Cube Attack on PRESENT[A].CANS 2009[C].LNCS,2009,5888:379-391.

[9] S F Abdul-Latip,M R Reyhanitabar,W Susilo,et al.Extended Cubes:Enhancing the cube attack by Extracting Low-Degree Non-linear Equations[A].ASIACCS 2011[C].2011:296-305.

[10] X Zhao,S Guo,F Zhang,T Wang,et al.Enhanced Side-Channel Cube Attacks on PRESENT[J].IEICE T RANS.FUNDAMENTALS,2003,E96-A（1）.

[11] X Zhao,S Guo,F Zhang,et al.Efficient Hamming Weight-based Side-Channel Cube Attacks on PRESENT[J].The Journal of Systems&Software（2010）,doi:10.1016/j.jss.2012.11.007.

[12] S F Abdul-Latip,M R Reyhanitabar,W Susilo,et al.On the Security of NOEKEON against Side Channel Cube Attacks[A].ISPEC 2010[C].LNCS,2010,6047:45-55.

[13] G V Bard,N T Courtois,J Nakahara,et al.Algebraic,AIDA/Cube and Side Channel Analysis of KATAN Family of Block Ciphers[A].INDOCRYPT 2010[C],LNCS,2010,6498:176-196.

[14] H Yap,K Khoo,A Poschmann,et al.EPCBC-A Block Cipher Suitable for Electronic Product Code Encryption[A].In CANS 2011[C].LNCS,2011,6715:34-45.

[15] EPC global.EPC Tag Data Standard Version 1.5.EPC global Specification[S].August 2010,available at www.gs1.org/gsmp/kc/epcglobal/tds/