二次檢測立方攻擊改進(jìn)與實現(xiàn)*

?

二次檢測立方攻擊改進(jìn)與實現(xiàn)*

王永娟1，丁立人1，任泉宇1，楊程2

(1.解放軍外國語學(xué)院 語言工程系, 河南 洛陽471003; 2.國防科技大學(xué) 計算機(jī)學(xué)院, 湖南 長沙410073)

摘要：對二次檢測立方攻擊預(yù)處理階段的提取二次表達(dá)式的算法進(jìn)行了改進(jìn)以優(yōu)化攻擊效率。將秘密變量的變化引入攻擊中，使得攻擊模型更加靈活；同時，利用時空折中的思想，通過存儲常數(shù)項和一次項的計算結(jié)果，有效降低二次項的計算量。將改進(jìn)的方法應(yīng)用于簡化版的PRESENT算法和Trivium算法上，攻擊效率有顯著提高。

關(guān)鍵詞：立方攻擊；二次檢測；時空折中；改進(jìn)

2003年，Courtois和Meier[1]針對序列密碼提出代數(shù)攻擊，基本原理是將密鑰恢復(fù)歸約為超定多變元非線性方程組的求解。代數(shù)免疫成為了衡量布爾函數(shù)性質(zhì)的重要密碼學(xué)指標(biāo)，具有最優(yōu)代數(shù)免疫的各類布爾函數(shù)[2-3]相繼提出。

2008年，Dinur和Shamir[4]提出了一種基于代數(shù)思想的新攻擊方法，即立方攻擊。它屬于確定性選擇明文攻擊，通過對公開變量和秘密變量賦值，獲得關(guān)于密鑰的線性方程，從而將密鑰恢復(fù)歸約為線性方程組的求解。該攻擊方法基于布爾函數(shù)的唯一代數(shù)標(biāo)準(zhǔn)型建立方程系統(tǒng)，彭昌勇等[5]在對高級加密標(biāo)準(zhǔn)(Advanced Encryption Standard,AES)進(jìn)行分析時也利用了類似的思想。立方攻擊可以被應(yīng)用于序列密碼、分組密碼和哈希函數(shù)上，對Trivium[4,6-7]、Grain[8]、PRESENT[9-10]、AES[11]、KATAN[12]和MD6[13]等密碼算法都有良好的應(yīng)用效果，因此受到廣泛關(guān)注。

然而，立方攻擊在具體應(yīng)用中也會受到一些因素的影響。如果密碼體制主多項式的代數(shù)次數(shù)過高，預(yù)處理階段就會消耗大量的時間和空間。從密碼體制中提取的線性關(guān)系往往比較有限，這也限制了立方攻擊的效率。

2010年，Mroczkowki等[6]首次將Dinur在文獻(xiàn)[4]中提到的二次檢測應(yīng)用于對709輪Trivium算法的立方攻擊中，可以恢復(fù)全部80比特密鑰，其中39比特包含在二次方程中。2011年，Abdul-Latip等[9]針對提取低次非線性方程的算法提出了改進(jìn)的立方攻擊，將改進(jìn)的立方攻擊與旁道攻擊相結(jié)合應(yīng)用于PRESENT-80算法，恢復(fù)全部密鑰的時間復(fù)雜度為216。2013年，F(xiàn)ouque等[7]利用莫比烏斯轉(zhuǎn)換和二次檢測對標(biāo)準(zhǔn)立方攻擊進(jìn)行改進(jìn)，當(dāng)Trivium算法的初始輪數(shù)為799時，利用關(guān)于密鑰的二次方程將窮舉攻擊的復(fù)雜度由268降到240。

二次檢測的引入雖然使立方攻擊的模型更加靈活、高效，但是也增加了預(yù)處理階段的復(fù)雜度。如何有效提升二次檢測立方攻擊的實施效率，是在立方攻擊的發(fā)展中值得研究的問題。

利用時空折中的思想對提取二次表達(dá)式的算法進(jìn)行改進(jìn)，通過存儲表達(dá)式中常數(shù)項和一次項的計算結(jié)果簡化二次項的計算。利用空間換取時間，提高二次檢測立方攻擊在預(yù)處理階段提取二次表達(dá)式的效率。

Mroczkowki在文獻(xiàn)[6]中只給出了二次檢測的結(jié)果，并沒有闡述提取表達(dá)式的具體方法。Abdul-Latip在文獻(xiàn)[9]中提出了提取低次表達(dá)式的方法，其思路是在表達(dá)式通過二次(或低次)檢測后先確定其中存在的變量，再判斷變量的存在形式。確定表達(dá)式中存在的變量涉及大量隨機(jī)檢測，檢測次數(shù)過小會發(fā)生遺漏；過大則會影響算法效率。本文提出的算法，不需要進(jìn)行隨機(jī)測試就可以直接判斷變量在二次方程中的存在形式，提高了計算的準(zhǔn)確率；同時，通過存儲線性檢測的計算結(jié)果，計算二次項的時間復(fù)雜度是標(biāo)準(zhǔn)算法的1/4。

將改進(jìn)的算法應(yīng)用于簡化版的PRESENT算法和Trivium算法上，同時簡化Abdul-Latip算法中的計算條件(將隨機(jī)檢測的次數(shù)由文獻(xiàn)[9]中的300次降為100次)，將其應(yīng)用到相同算法上，對二者的計算效率進(jìn)行比較。對于簡化的PRESENT算法和簡化的Trivium算法，改進(jìn)算法提取二次表達(dá)式的效率為Abdul-Latip算法的4至5倍。

1攻擊方法簡介

1.1　立方攻擊原理

把目標(biāo)密碼體制看成有限域F2上關(guān)于公共變量v=(v1,…,vm)和秘密變量k=(x1,…,xn)的多項式P(v,k)。給定指標(biāo)集I={i1,…,ik}?{1,2,…,m}，令tI=vi1…vik，目標(biāo)多項式分解如下：

P(v1,…,vm,x1,…,xn)=

tI·PS(I)+Q(v1,…,vm,x1,…,xn)

稱形如

∑CIP(v,k)=∑CItI·PS(I)+

∑CIQ(v1,…,vm,x1,…,xn)。

定理1[4]任意目標(biāo)多項式P(v,k)和公共變量都滿足：

∑CIP(v,k)=PS(I)(v,k)mod2

通過立方求和所得的PS(I)(v,k)為超級多項式，如果該超級多項式為線性多項式，則稱對應(yīng)的tI為極大項。

定理2[4]令tI為極大項，則：

① 將所有集合I之外的變量賦值為0，在CI上進(jìn)行立方求和可以得到表達(dá)式的常數(shù)項；

② 將所有集合I之外的公共變量賦值為0，將除第i位秘密變量外其余秘密變量賦值為0，令xi=1，對所有可能的輸入進(jìn)行模2求和，可以得到xi的系數(shù)。

根據(jù)定理2，在PS(I)(v,k)通過線性化檢測之后可以計算出具體的表達(dá)式。

立方攻擊分為預(yù)處理階段和在線階段兩個部分，預(yù)處理階段的目的是通過為公共變量和秘密變量賦值，獲取關(guān)于密鑰的線性表達(dá)式；在線階段只為公共變量進(jìn)行賦值，計算表達(dá)式右邊的值，得到關(guān)于密鑰的線性方程組，進(jìn)而聯(lián)立求解。

1.2　二次檢測原理

二次檢測立方攻擊，即在預(yù)處理階段擴(kuò)展集合的搜索范圍，增加搜索關(guān)于密鑰的二次表達(dá)式的步驟。二次檢測的原理可由線性化檢測推廣而得。

1993年，Blum等[14]針對布爾函數(shù)提出了多種代數(shù)性質(zhì)的檢測方案。其中，對于線性性質(zhì)，他們提出了Blum-Luby-Rubinfeld(BLR)檢測法，具體原理詳見文獻(xiàn)[14]。

f(x)⊕f(y)⊕f(z)⊕

f(x⊕y)⊕f(x⊕z)⊕f(y⊕z)⊕

f(x⊕y⊕z)⊕f(0(n))=0

(1)

2改進(jìn)的二次檢測立方攻擊

2.1　改進(jìn)算法的原理

在研究Cube集合時，不僅考慮了公共變量的變化，還將秘密變量的變化引入其中。定義1給出了Cube集合在秘密變量上的擴(kuò)張，本文在Cube集合擴(kuò)張的基礎(chǔ)上對二次檢測立方攻擊的預(yù)處理階段進(jìn)行改進(jìn)。

定義1給定指標(biāo)集：

I={i1,…,ik}?{1,2,…,m}，

J={j1,…,js}?{1,2,…,n}，

CI為一個Cube集合，定義與1.1節(jié)中相同，稱形如

vi∈F2,i∈I;xj∈F2,j∈J}

的集合為CI在秘密變量上的擴(kuò)張。

依據(jù)定義1，將Dinur和Shamir關(guān)于主多項式和公共變量的定理1擴(kuò)展到秘密變量上，結(jié)論仍然成立，即：

∑CI∪JP(v,k)=PS(I∪J)(v,k)mod2

擴(kuò)展立方集合的搜索范圍，搜索關(guān)于秘密變量的線性和二次表達(dá)式。下文闡述如何利用Cube集合在秘密變量上的擴(kuò)張?zhí)崛￡P(guān)于秘密變量的二次表達(dá)式。

定義2給定集合I，若deg(PS(I))=2，則稱對應(yīng)的tI為2階極大項。

定理4令tI為2階極大項，ai表示PS(I)中xi的系數(shù)，aij表示PS(I)中xixj的系數(shù)，a0表示PS(I)中的常數(shù)項，則

① 令所有xq=0,vl=0,l?I，有a0=∑CIP(v,k)；

② 令所有xq=0,xq∈k{xi},vl=0,l?I，有ai=∑CI∪{i}P(v,k)；

③ 令所有xq=0,xq∈k{xi,xj},vl=0,l?I，有aij=∑CI∪{i,j}P(v,k)；

□

例1目標(biāo)多項式

P(v1,v2,v3,x1,x2,x3,x4)=

v1v2v3x1x2+v1v2v3x4+v1x3+v1v2v3

令I(lǐng)={1,2,3}，進(jìn)行二次檢測可得tI=v1v2v3為2階極大項，PS(I)=x1x2+x4+1。下面根據(jù)定理4判斷該表達(dá)式的代數(shù)標(biāo)準(zhǔn)型：

由例1可知，在計算二次項a12的系數(shù)，包括對a1，a2和a0的計算時，如果分別存儲a1，a2和a0的計算結(jié)果，那么計算a12時只需考慮指標(biāo)索引全1的情況，而不用遍歷2維Cube集合，從而將4次運算簡化為1次運算。

基于上述現(xiàn)象，利用時空折中的思想改進(jìn)二次表達(dá)式的提取。通過存儲常數(shù)項和一次項的系數(shù)，簡化二次項系數(shù)的計算，從而提高二次檢測立方攻擊預(yù)處理階段的效率。下文闡述改進(jìn)算法的理論依據(jù)：

定理5給定目標(biāo)多項式P(v,k)，對任意指標(biāo)集合S，集合R={I|I?S}，有

∑CSP(v,k)=∑R∑CIP(v,k)⊕

∑CSP(v,k)=∑CI1P(v,k)⊕…⊕

□

依據(jù)定理5，存儲常數(shù)項和一次項的計算結(jié)果，可使二次項系數(shù)的計算量減小為之前的1/4，而改進(jìn)算法只需要比標(biāo)準(zhǔn)算法多開辟n+1個存儲空間(其中n為秘密變量個數(shù))。

2.2　改進(jìn)算法的流程

改進(jìn)算法在表達(dá)式通過二次檢測后依次計算其中的常數(shù)項、一次項系數(shù)以及二次項系數(shù)，并將常數(shù)項和一次項的計算結(jié)果存儲在新開辟的數(shù)組中，以便計算二次項系數(shù)時直接調(diào)用。具體過程如算法1所示。

算法1　改進(jìn)算法偽代碼

2.3　復(fù)雜度分析

時間復(fù)雜度比較：

由上述比較可得時間復(fù)雜度優(yōu)化的臨界值，即當(dāng)μ>n+1時，在有限的存儲空間內(nèi)，改進(jìn)算法能有效提高提取二次表達(dá)式的效率。為了確保準(zhǔn)確性，隨機(jī)檢測的次數(shù)一般不小于200次，而Abdul-Latip在文獻(xiàn)[9]中選擇μ=300，理論上新方法將大幅提升二次表達(dá)式的提取效率，本文將在第3節(jié)給出實驗驗證。表1和表2分別比較了標(biāo)準(zhǔn)算法、Abdul-Latip的算法和提出的改進(jìn)算法在時間復(fù)雜度和空間復(fù)雜度上的對比。

表1　各算法時間復(fù)雜度對比

表2　各算法空間復(fù)雜度對比

3對PRESENT和Trivium的實驗結(jié)果

使用配備i-5處理器、1.7GHz主頻、2GB內(nèi)存的筆記本電腦，對3輪的PRESENT-80算法和初始化輪數(shù)為576的Trivium算法進(jìn)行二次檢測立方攻擊，利用改進(jìn)算法提取二次表達(dá)式，驗證其效率。

3.1PRESENT算法上的應(yīng)用

3.1.1PRESENT算法簡介

PRESENT[15]算法是基于硬件實現(xiàn)設(shè)計的輕量級分組密碼，分組長度為64比特，按密鑰長度及生成過程不同分為PRESENT-80和PRESENT-128兩個版本。該算法基于SPN結(jié)構(gòu)，迭代31輪，其中每輪都包括三層子函數(shù)。第一層為輪密鑰函數(shù)，輸入數(shù)據(jù)與該輪密鑰進(jìn)行異或；出于硬件實現(xiàn)的考慮，第二層平行使用16個相同的4比特S盒構(gòu)成非線性代換層；第三層為線性置換層，基于比特置換實現(xiàn)擴(kuò)散。

3.1.2效率分析

對于3輪的PRESENT-80算法，選取2次和3次2階極大項，分別利用Abdul-Latip的算法和改進(jìn)算法提取二次表達(dá)式(其中在Abdul-Latip的算法中令μ=100)，比較時間以驗證改進(jìn)算法的效率。檢測結(jié)果如表3所示，其中時間單位為s，第2列為Abdul-Latip的算法所耗時間，第3列為本文改進(jìn)算法所耗時間。

表3　在PRESENT-80上的應(yīng)用對比

如表3所示，即使令文獻(xiàn)[9]中隨機(jī)檢測的次數(shù)為原文的1/3，利用改進(jìn)算法提取二次表達(dá)式的效率仍為Abdul-Latip的4倍。而且，改進(jìn)算法中不存在隨機(jī)檢測過程，準(zhǔn)確性也高于Abdul-Latip的算法。

PRESENT算法提出后受到了廣泛關(guān)注，2009年，YANG等[16]利用旁道攻擊對其進(jìn)行分析，在空間復(fù)雜度215之內(nèi)恢復(fù)PRESENT-80算法的48比特密鑰。2011年Abdul-Latip等[9]將二次檢測立方攻擊與旁道攻擊結(jié)合，直接恢復(fù)PRESENT-80算法的64比特密鑰。本文將改進(jìn)的二次檢測立方攻擊與旁道攻擊結(jié)合，通過搜索二次表達(dá)式，在文獻(xiàn)[10]的基礎(chǔ)上，能恢復(fù)原文無法恢復(fù)的8比特密鑰，以時間復(fù)雜度215和空間復(fù)雜度215恢復(fù)全部80比特密鑰。

表4比較了各分析方法對PRESENT-80算法的攻擊結(jié)果。

表4　對PRESENT-80的攻擊

3.2Trivium算法上的應(yīng)用

3.2.1Trivium算法簡介

Trivium[17]是eSTREAM計劃的候選算法之一，初始向量長度為80比特，初始密鑰長度為80比特，空跑1152輪后輸出密鑰。它由三個不同長度的非線性移位寄存器構(gòu)成，內(nèi)部狀態(tài)共288比特。其中，每個移位寄存器的反饋都由其他寄存器比特的非線性組合與該寄存器比特進(jìn)行異或而得。每輪的輸出是6個比特的線性組合，每個寄存器選2個比特。

3.2.2效率分析

對于初始輪數(shù)為576的Trivium算法，選取6次2階極大項，分別利用改進(jìn)算法和Abdul-Latip的算法提取二次表達(dá)式(其中在Abdul-Latip的算法中令μ=100)，比較時間以驗證改進(jìn)算法的效率。檢測結(jié)果如表5所示，時間單位為s，第2列為Abdul-Latip的算法所耗時間，第3列為本文改進(jìn)算法所耗時間。

表5　在Trivium上的應(yīng)用對比

如表5所示，即使簡化Abdul-Latip的算法，改進(jìn)算法在Trivium上的應(yīng)用效率仍接近原來的5倍。

立方攻擊和二次檢測立方攻擊提出伊始都被應(yīng)用于Trivium算法上，且具有良好的攻擊結(jié)果。2008年，Dinur和Shamir[4]利用立方攻擊直接恢復(fù)了672輪Trivium算法63比特密鑰。2012年，Mroczkowski[6]首次將二次檢測的思想應(yīng)用于立方攻擊中，恢復(fù)709輪Trivium算法全部密鑰，其中二次檢測所耗時間復(fù)雜度為237。2013年，F(xiàn)ouque[7]將二次檢測立方攻擊應(yīng)用于799輪的Trivium算法上，直接恢復(fù)40比特密鑰，其中二次檢測的時間復(fù)雜度約為251。利用本文提出的改進(jìn)算法，搜索37次2階極大項的時間復(fù)雜度約為248。

表6比較了各分析方法對Trivium算法的攻擊結(jié)果。

表6　對Trivium的攻擊

綜上所述，改進(jìn)的算法在PRESENT算法和Trivium算法上的實驗結(jié)果符合對于算法復(fù)雜度的理論估計。在立方攻擊時利用二次檢測可以恢復(fù)更多密鑰比特，改進(jìn)的算法能夠優(yōu)化提取關(guān)于密鑰的二次表達(dá)式的效率。

4結(jié)論

利用低次關(guān)系(不單是線性關(guān)系)恢復(fù)密鑰已經(jīng)成為立方攻擊發(fā)展的一大趨勢，低次表達(dá)式的提取因此也成為該領(lǐng)域的研究熱點。本文將秘密變量的變化引入立方攻擊中，基于時空折中的思想提出了提取二次表達(dá)式的改進(jìn)算法，主要思想是對常數(shù)項和一次項的計算結(jié)果進(jìn)行存儲，以減少二次項系數(shù)的計算量，從而降低二次檢測立方攻擊預(yù)處理階段的時間復(fù)雜度。

理論上，改進(jìn)算法與Abdul-Latip在文獻(xiàn)[9]中提出的算法相比，效率至少為后者的μ/n+1倍。當(dāng)文獻(xiàn)[9]中的隨機(jī)檢測次數(shù)μ=100時，改進(jìn)算法在簡化的PRESENT-80算法和簡化的Trivium算法上的應(yīng)用效率為其4至5倍。

改進(jìn)的二次檢測立方攻擊有較為廣闊的應(yīng)用前景，在今后的工作中也可參照該算法的改進(jìn)模式，利用時空折中的思想優(yōu)化對其他低次表達(dá)式的提取。

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

[1]Courtois N T, Meier W. Algebraic attacks on stream ciphers with linear feedback[C]//Advances in Cryptology-EUROCRYPT 2003, International Conference on the Theory and Applications of Cryptographic Techniques, Springer Berlin Heidelberg, 2003, 2656: 345-359.

[2]李超, 薛朝紅, 付紹靜. 代數(shù)免疫度最優(yōu)的旋轉(zhuǎn)對稱布爾函數(shù)的構(gòu)造[J]. 國防科技大學(xué)學(xué)報, 2012, 34(2): 34-38.

LI Chao, XUE Chaohong, FU Shaojing. Construction of rotation symmetric Boolean function with maximum algebraic immunity[J]. Journal of National University of Defense Technology, 2012, 34(2): 34-38. (in Chinese)

[3]董德帥, 李超, 屈龍江, 等. 偶變元MAI旋轉(zhuǎn)對稱布爾函數(shù)[J]. 國防科技大學(xué)學(xué)報, 2012, 34(4): 85-89.

DONG Deshuai, LI Chao, QU Longjiang, et al. Rotation symmetric Boolean functions in even-variable with maximum algebraic immunity[J]. Journal of National University of Defense Technology, 2012, 34(4): 85-89. (in Chinese)

[4]Dinur I, Shamir A. Cube attack on tweakable black box polynomials[C]//Advances in Cryptology-EUROCRYPT 2009, Springer Berlin Heidelberg, 2009: 278-299.

[5]彭昌勇, 祝躍飛, 康緋, 等. AES輪變換的代數(shù)正規(guī)型及其應(yīng)用[J]. 國防科技大學(xué)學(xué)報, 2012, 34(2): 14-17.

PENG Changyong, ZHU Yuefei, KANG Fei, et al. The ANFs of the component functions of AES round transformation and its application[J]. Journal of National University of Defense Technology, 2012, 34(2):14-17. (in Chinese)

[6]Mroczkowski P, Szmidt J. The cube attack on stream cipher Trivium and quadraticity tests[J]. Fundamenta Informaticae, 2012, 114(3): 309-318.

[7]Fouque P A, Vannet T. Improving key recovery to 784 and 799 rounds of Trivium using optimized cube attacks[EB/OL]. (2013-12-14)[2014-05-06]. http://fse2013.spms.ntu.edu.sg:80.

[8]Dinur I, Shamir A. Breaking Grain-128 with dynamic cube attacks[C]//Fast Software Encryption, Springer Berlin Heidelberg, 2011: 167-187.

[9]Abdul-Latip S F, Reyhanitabar M R, Susilo W, et al. Extended cubes: enhancing the cube attack by extracting low-degree non-linear equations[C]//Proceedings of the 6th ACM Symposium on Information, Computer and Communications Security, New York: Association for Computing Machinery, 2011: 296-305.

[10]Zhao X J, Wang T, Guo S Z. Improved side channel cube attacks on PRESENT[EB/OL]. (2011-04-10)[2013-06-09]. http://eprint.iacr.org/2011/165.

[11]Dinur I, Shamir A. Side channel cube attacks on block ciphers[EB/OL]. (2009-03-20)[2013-04-16]. http://eprint.iacr.org/2009/127.

[12]Abdul-Latip S F, Reyhanitabar M R, Susilo W, et al. Fault analysis of the KATAN family of block ciphers[C]//Information Security Practice and Experience, Springer Berlin Heidelberg, 2012: 319-336.

[13]Aumasson J P, Dinur I, Meier W, et al. Cube testers and key recovery attacks on reduced-round MD6 and Trivium[C]//Fast Software Encryption, Springer Berlin Heidelberg, 2009: 1-22.

[14]Blum M, Luby M, Rubinfeld R. Self-testing/correcting with applications to numerical problems[J]. Journal of Computer and System Sciences, 1993,47(3): 549-595.

[15]Bogdanov A, Knudsen L R, Leaner G, et al. PRESENT: an ultra-lightweight block cipher[C]//Cryptographic Hardware and Embedded System-CHES 2007, Springer Berlin Heidelberg, 2007: 450-466.

[16]Yang L, Wang M Q, Qiao S Y. Side channel cube attack on PRESENT[C]//Cryptology and Network Security, Springer Berlin Heidelberg, 2009: 379-391.

[17]Canniere C, Preneel B. Trivium-a stream cipher construction inspired by block cipher design principles[EB/OL]. (2005-05-30)[2013-07-01]. http://www.ecrypt.eu.org/stream.

Enhancement and application of cube attack with quadratic test

WANGYongjuan1,DINGLiren1,RENQuanyu1,YANGCheng2

(1.Department of Language Engineering, PLA University of Foreign Languages, Luoyang 410073, China;

2.College of Computer, National University of Defense Technology, Changsha 471003, China)

Abstract：The algorithm of extracting quadratic expressions in the pre-processing phase of cube attack with quadratic test was enhanced to optimize the attack efficiency. The variation of secret keys was introduced into cube attack, which makes the model much more flexible. At the same time, with the help of the trade-off between time and space, the complexity of extracting quadratic terms was reduced by storing the results of the constant and linear terms. The improved method was applied to the simplified PRESENT and Trivium algorithms and it turns out that the attack efficiency is enhanced obviously.

Key words：cube attack; quadratic test; trade-off between time and space; enhancement

中圖分類號：TP309.7

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

文章編號：1001-2486(2015)02-106-06

收稿日期：2014-05-26基金項目：中國博士后科學(xué)基金面上資助項目(2014M552603)

作者簡介：王永娟(1982—),女,河南開封人,博士,碩士生導(dǎo)師,E-mail: pinkywyj@163.com

doi:10.11887/j.cn.201502020

http://journal.nudt.edu.cn