EPCBC密碼旁路立方體攻擊

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

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

0 引言

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

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

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

1 相關知識

1.1 EPCBC算法設計

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

（1）加密過程

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

輪密鑰加 AK:48（96）位輪輸入同48（96）位輪密鑰進行異或。

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

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

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

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

（2）密鑰擴展

為更好抵抗相關密鑰攻擊威脅,EPCBC設計了專門的密鑰擴展算法,將加密輪函數引入到密鑰擴展中,設計比PRESENT復雜,具體密鑰擴展設計細節可參考文獻[14]。

1.2 立方體攻擊

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

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

（1）預處理階段

攻擊者隨機從 V中選取部分公開變量,令I表示所選取公開變量下標索引集合,I?{1,…,m},I即為一個立方體,大小為 λ,I中索引稱為為立方體索引。tI表示所選取公開變量的乘積,又稱極大項。f（X）可表示為

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

式（3）最高次數為4,包含8個變量、17個子多項式。將公開變量相同的子多項式合并后,f（X）可表示為

根據式（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個f（X）累積高階差分即為pS（I）。應用類似方法,可得到4個線性立方體:

（2）在線階段

在線階段中,攻擊者根據預處理階段得到的立方體 I生成2λ個選擇公開變量,通過問詢密碼算法得到p的輸出,并計算高階差分得到對應的超多項式pS（I）的值,然后利用代數方程求解方法恢復相關密鑰變量K。

需要說明的是,在線階段主要是通過問詢密碼得到 f（X）輸出,驗證預處理階段得到的立方體 I和超多項式pS（I）之間關系是否存在。在已知密碼設計時,可將 f（X）精確的表示出來,通過合并極大項的方式得到 I和pS（I）;在未知密碼設計時,攻擊者可以窮舉或者隨機選取 I和pS（I）,通過在線階段驗證二者關系,并求解出密鑰。

1.3 旁路立方體攻擊

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

2 EPCBC旁路立方體攻擊

2.1 漢明重泄露模型

旁路立方體攻擊中,泄露模型的選擇取決于攻擊者的能力,泄露模型不同時目標比特的多項式 f（X）表示方法不同。對于漢明重泄露模型,由于泄露漢明重的一個比特和對應的中間狀態還存在關系,因此還需要進行一定的轉換。以一個字節 X=（x7,x6,x5,x4,x3,x2,x1,x0）的漢明重泄露為例,假如其漢明重Y=H（X）=（y3,y2,y1,y0）,x0和y0分別表示X和Y最低位。Y可用X表示如下

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

2.2 黑盒旁路立方體攻擊

旁路立方體攻擊繼承了立方體攻擊的優點,可在未知算法設計下實施。下面給出黑盒旁路立方體分析的算法。

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

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

步驟3:測試pS（I）的值是否等于這些選擇明文對應泄露比特的高階差分;

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

根據上面算法,黑盒旁路立方體攻擊復雜度取決于選擇明文變量和超多項式中密文變量數量,并隨著二者的增加呈指數級增長。選擇明文變量數量受密碼分組長度限制,超多項式的數量受密碼支持密鑰長度和攻擊者選擇超多項式的階數限制。在實際攻擊中,為降低攻擊數據復雜度,一個好的黑盒立方體攻擊應該具有選擇明文變量（立方體大?。┖统囗検街忻荑€變量數量較小的特點。

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

2.3 EPCBC（48,96）攻擊

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

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

2.4 EPCBC（96,96）攻擊

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

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

3 結束語

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

[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/