立方攻擊成功率分析

宋海欣，范修斌，武傳坤，馮登國(guó)

（1．中國(guó)科學(xué)院 軟件研究所信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100190；

2．中國(guó)科學(xué)院 研究生院，北京 100049）

1 引言

在 2009年歐洲密碼年會(huì)上，Dinur和 Shamir提出了立方攻擊（cube attack）[1]的密碼分析方法并對(duì)流密碼算法Trivium[2]進(jìn)行了分析，立方攻擊是一種新型的代數(shù)攻擊方法，旨在尋找密碼算法固有的低次方程以恢復(fù)密鑰[3～7]或進(jìn)行區(qū)分攻擊[8～10]。

一般來講，密碼算法模型如圖1所示。對(duì)分組密碼來講，密碼算法可看作mbit明文與nbit密鑰的函數(shù)，經(jīng)過輪函數(shù)的迭代過程，產(chǎn)生密文。對(duì)流密碼來講，密碼算法可看作mbit初始向量IV與nbit密鑰的函數(shù)，流密碼算法設(shè)計(jì)一般分為初始化過程和密鑰流產(chǎn)生過程，很多流密碼算法，如Trivium[2]、Grain v1[11]、Mickey[12]、F-FCSR-H[13]等，其初始化過程均采用低次函數(shù)迭代一定拍數(shù)，使密鑰和初始向量達(dá)到一定程度的混亂與擴(kuò)散。無論是流密碼算法還是分組密碼算法，一般開始隨著迭代拍數(shù)的增加，密碼算法的代數(shù)次數(shù)和代數(shù)標(biāo)準(zhǔn)型(ANF)項(xiàng)數(shù)會(huì)戲劇性地增加，迭代一定拍數(shù)后，密碼算法的代數(shù)次數(shù)和代數(shù)標(biāo)準(zhǔn)型項(xiàng)數(shù)會(huì)達(dá)到一個(gè)相對(duì)穩(wěn)定且不可預(yù)測(cè)的狀態(tài)。

圖1 密碼算法模型

本文就一般隨機(jī)布爾函數(shù)及布爾函數(shù)的代數(shù)次數(shù)或代數(shù)標(biāo)準(zhǔn)型項(xiàng)數(shù)受限情況下，從理論上分析了立方攻擊的成功概率，設(shè) f (v1,v2, … ,vm,k1, k2,… ,kn)為m個(gè)公開變量 ( v1,v2,… ,vm)及n個(gè)密鑰變量(k1, k2,… ,kn)的布爾函數(shù)，證明了以下結(jié)論：1）針對(duì)一般隨機(jī)布爾函數(shù)進(jìn)行討論，立方攻擊的成功概論，設(shè)隨機(jī)布爾函數(shù)的代數(shù)次數(shù)至多為s，若代數(shù)次數(shù)s與極大項(xiàng)(maxterm)[1]的代數(shù)次數(shù)l滿足關(guān)系s - l = 1時(shí)，立方攻擊的成功概率為1；當(dāng) s - l ＞ 1時(shí)，成功概率為3）針對(duì)布爾函數(shù)的代數(shù)標(biāo)準(zhǔn)型項(xiàng)數(shù)進(jìn)行討論，若隨機(jī)布爾函數(shù)可被極大項(xiàng)整除的代數(shù)標(biāo)準(zhǔn)型中，代數(shù)次數(shù)大于等于(l +2)的代數(shù)標(biāo)準(zhǔn)型至多為N項(xiàng)，那么立方攻擊的成功概率為2-N。

2 立方攻擊簡(jiǎn)介

立方攻擊是一種新型的代數(shù)攻擊方法，在選擇IV或選擇明文條件下，尋找關(guān)于密鑰的仿射函數(shù)以恢復(fù)密鑰或進(jìn)行區(qū)分攻擊，它吸收了飽和攻擊[14]及高階差分分析[15]的思想，該攻擊方法主要基于下述定理。

定理 1[1]設(shè) f (x1, x2,… ,xn)為含有n個(gè)變量的布 爾 函 數(shù) ， S = ｛ x1, x2, … , xn｝ , f(?)函 數(shù) 可 表 示 為其中，I為集合S的非空真子集，設(shè)， P (?)和 R (?)均為代數(shù)標(biāo)準(zhǔn)型表示的布爾函數(shù)， P (?)函數(shù)中的變量均取自集合I對(duì)S的余集 S I， R (?)函數(shù)代數(shù)標(biāo)準(zhǔn)型中的每一項(xiàng)均不含I中的全部變量，那么，當(dāng)對(duì)集合I中的變量跑遍所有可能取值并對(duì) f(?)函數(shù)求和，可得：

為了進(jìn)一步說明該定理，舉例如下：

其可以表示為

流密碼算法中，在選擇 IV攻擊條件下，初始向量 IV為公開變量，密鑰為未知變量。分組密碼算法中，在選擇明文攻擊條件下，明文為公開變量，密鑰為未知變量。

定義1[1]定理1中，若集合I中的變量均為公開變量，并且 P (?)的代數(shù)次數(shù)為 1，就得到了關(guān)于未知變量的一個(gè)仿射方程f(x1, x2,… ,xn)，并稱T(I)為極大項(xiàng)(maxterm)，稱P(?)為超級(jí)多項(xiàng)式(superpoly)。

立方攻擊中，攻擊者把密碼算法看作一個(gè)黑盒子，它是關(guān)于公開變量和未知變量的未知多項(xiàng)式，只考慮輸出的一個(gè)比特。對(duì)密碼算法的立方攻擊分為2個(gè)階段：預(yù)處理階段和密鑰恢復(fù)階段。在預(yù)處理階段，攻擊者可以改變公開變量及未知變量的值并可模擬算法的執(zhí)行，目的是通過BLR線性測(cè)試的方法[16]找到盡量多的關(guān)于未知變量的超級(jí)多項(xiàng)式，預(yù)處理過程只進(jìn)行一次。在密鑰恢復(fù)階段，攻擊者只改變公開變量的值，通過在預(yù)處理階段找到的超級(jí)多項(xiàng)式建立仿射方程組來恢復(fù)某些密鑰比特或進(jìn)行區(qū)分攻擊。

在預(yù)處理階段，若找到的多項(xiàng)式P為常量，為方便起見，下面討論中仍視其為攻擊成功。

下面就一般布爾函數(shù)及布爾函數(shù)的代數(shù)次數(shù)或代數(shù)標(biāo)準(zhǔn)型項(xiàng)數(shù)受限情況下對(duì)立方攻擊的成功概率進(jìn)行分析。

3 一般布爾函數(shù)立方攻擊成功概率分析

在一般情況下，分析對(duì)隨機(jī)布爾函數(shù)立方攻擊的成功概率。

設(shè) V = ｛ v1, v2,… ,vm｝ 為m個(gè)公開變量， K ={k1,k2,… ,kn}為n個(gè)密鑰變量，f(v1,v2,… ,vm,k1,k2,… ,kn)為含(m+n)個(gè)變量的布爾函數(shù)，立方攻擊在尋找超級(jí)多項(xiàng)式時(shí)，先選定集合V的一個(gè)非空子集I，不妨設(shè) I = ｛v1, v2,… ,vl｝, 1≤l≤m，并將其他公開變量設(shè)置為常數(shù) 0或 1 ，此時(shí)，f（v1, v2, … ,vm,k1, k2,… ,kn） 函數(shù)就退化為含(l + n)個(gè) 變 量 的 布 爾 函 數(shù) g（v1, … ,vl,k1, … ,kn）=f（v1, … ,vl,c1, … ,cm-l, k1, … ,kn） ，其中，ci∈ ｛ 0,1｝,1≤i≤ m - l 。

證明 根據(jù)以代數(shù)標(biāo)準(zhǔn)型表示的 g (?)函數(shù)中各項(xiàng)所含集合I中變量的個(gè)數(shù)，可將 g (?)函數(shù)表示如下

若將 g (?)函數(shù)表示如下

若使 P(?)為仿射函數(shù)或常量，參數(shù)ai（0≤ i≤n） 可 任 意 取 值 為0或1， 參 數(shù)值為0，因此所有參數(shù)的可能取值共有 S1= 2n+1。

從定理2可以推出如下結(jié)論。

推論1 立方攻擊中，針對(duì)隨機(jī)布爾函數(shù)，P （?）為仿射函數(shù)或常量的概率與選擇的公開變量的子集I的大小l無關(guān)，只與密鑰長(zhǎng)度n有關(guān)。

密碼算法設(shè)計(jì)的目的是使密鑰和初始向量（或明文）達(dá)到充分的混亂與擴(kuò)散，在密碼算法接近于隨機(jī)的情況下，又一般密鑰長(zhǎng)度 n ≥ 8 0，則由定理

4 布爾函數(shù)的代數(shù)次數(shù)受限情況下立方攻擊成功概率分析

本節(jié)針對(duì)布爾函數(shù)的代數(shù)次數(shù)對(duì)立方攻擊的成功概率進(jìn)行分析。

定 理 3 設(shè) g(v1,v2, … ,vl,k1,k2,… ,kn)為 含(l + n )個(gè)變量的隨機(jī)布爾函數(shù)，該布爾函數(shù)的代數(shù)次數(shù)不大于 s( 2 ≤ s ≤ l + n)，設(shè) I ={v1,v2,… ,vl},1 ≤ l≤ s -1， K = { k1,k2,… , kn}，將 g (?)函數(shù)表示如下：其中，P (?)和 R (?)均為代數(shù)標(biāo)準(zhǔn)型表示的布爾函數(shù)， T (I)/| R (?)代數(shù)標(biāo)準(zhǔn)型中的任意一項(xiàng)，那么， P (?)為仿射函數(shù)或常量的概率為

證明 根據(jù)以代數(shù)標(biāo)準(zhǔn)型表示的 g (?)函數(shù)中各項(xiàng)所含集合I中變量的個(gè)數(shù)，可將 g (?)函數(shù)表示如下

其中， f0為關(guān)于變量 （k1, k2,… ,kn） 的以代數(shù)標(biāo)準(zhǔn)型i2＜ … ＜it≤ l, 1 ≤ t≤ l )均為關(guān)于變量 （k1, k2,… ,kn）的以代數(shù)標(biāo)準(zhǔn)型表示的代數(shù)次數(shù)小于等于（s - t ）的布爾函數(shù)， fi1i2…it可表示如下

若將 g (?)函數(shù)表示如下

下面分2種情況進(jìn)行討論。

若使 P (?)為仿射函數(shù)或常量，參數(shù) ai(0 ≤ i≤n)iq≤ n , 2 ≤ q ≤ s - l)必須全部取值為0，因此所有參數(shù)的可能取值共有

從定理3可以看出，設(shè)隨機(jī)布爾函數(shù)的代數(shù)次數(shù)至多為s，若代數(shù)次數(shù)s與極大項(xiàng)的代數(shù)次數(shù)l滿足關(guān)系 s -l=1，立方攻擊的成功概率為1。然而，若選擇的公開變量的個(gè)數(shù)l過小，或算法的代數(shù)次數(shù) s ＞(m +1)，則有s-l＞1，又一般情況下，密鑰長(zhǎng)度 n ≥ 8 0，由定理3可知， P (?)為仿射函數(shù)或常量的概率即 P r幾乎為0。這

2可以解釋為什么密碼算法的代數(shù)次數(shù)較低時(shí)立方攻擊的成功概率較高。

由定理3易得，在立方攻擊中，若布爾函數(shù)的代數(shù)次數(shù)s固定，隨著選擇的公開變量的子集I的大小l的逐漸增加， P (?)為仿射函數(shù)或常量的概率也逐漸增加。因此，在對(duì)密碼算法進(jìn)行立方攻擊時(shí)，若長(zhǎng)時(shí)間找不到超級(jí)多項(xiàng)式，應(yīng)適當(dāng)增加選取的公開變量的個(gè)數(shù)l，這也正是文獻(xiàn)[1]中立方攻擊所采用的手段。然而，立方攻擊至少需要2l次密碼算法運(yùn)算，因此隨著l的增加，尋找超級(jí)多項(xiàng)式也變得越來越困難。

5 布爾函數(shù)的代數(shù)標(biāo)準(zhǔn)型項(xiàng)數(shù)受限情況下立方攻擊成功概率分析

本節(jié)針對(duì)布爾函數(shù)的代數(shù)標(biāo)準(zhǔn)型項(xiàng)數(shù)對(duì)立方攻擊的成功概率進(jìn)行分析。

定理4 設(shè) I = {v1,v2,…,vl}，K ={k1,k2,… ,kn}，g（v1, v2,… ,vl,k1, k2,… , kn） 為含(l + n )個(gè)變量的隨機(jī)布爾函數(shù)，，其中，P(?)和 R (?)均為代數(shù)標(biāo)準(zhǔn)型(A NF ) 表示的布爾函數(shù)，T(I)/| R (?)代數(shù)標(biāo)準(zhǔn)型中的任意一項(xiàng)。若 g (?)函數(shù)可被 T (I)整除的代數(shù)標(biāo)準(zhǔn)型中，代數(shù)次數(shù)大于等于(l + 2 )的代數(shù)標(biāo)準(zhǔn)型至多為N項(xiàng)且均勻出現(xiàn)，那么P(?)為仿射函數(shù)或常量的概率為2-N。

證明 根據(jù)以代數(shù)標(biāo)準(zhǔn)型表示的 g (?)函數(shù)中各項(xiàng)所含集合I中變量的個(gè)數(shù)，可將 g (?)函數(shù)表示如下：為關(guān)于變量（k1, k2,… ,kn）的以代數(shù)標(biāo)準(zhǔn)型表示的布爾函數(shù)。不妨以 f1,2,…,l為例，其可表示如下：∈ { 0,1}，且各參數(shù)取值0或1的概率均為12。

若將 g (?)函數(shù)表示如下

因 g (?)函數(shù)可被 T (I)整除的代數(shù)標(biāo)準(zhǔn)型中，代數(shù)次數(shù)不小于(l + 2 )的代數(shù)標(biāo)準(zhǔn)型至多為N項(xiàng)，因1≤t≤n)的可能取值共有

若使式(9)中 P (?)為仿射函數(shù)或常量，參數(shù)ai(0 ≤ i≤n)可任意取值為0或1，參數(shù)值為0，因此所有參數(shù)的可能取值共有

式(7)中，設(shè)函數(shù) f0及it≤l,1≤t≤ l-1)中各參數(shù)的可能取值共有Δ3，那么 P (?)為仿射函數(shù)或常量的概率為

由定理4可以看出，若布爾函數(shù)可被極大項(xiàng)整除的代數(shù)標(biāo)準(zhǔn)型中，代數(shù)次數(shù)不小于(l + 2 )的項(xiàng)數(shù)至多為N項(xiàng)，那么隨著N的逐漸減小，立方攻擊的成功概率逐漸增大。

6 實(shí)驗(yàn)結(jié)果

上述理論分析結(jié)果與文獻(xiàn)[1]中對(duì)Trivium算法的實(shí)驗(yàn)分析結(jié)果是相吻合的，如表1所示。為了節(jié)省硬件資源，Trivium算法初始化過程采用二次函數(shù)迭代1 152拍，迭代672拍時(shí)，找到63個(gè)超級(jí)多項(xiàng)式，選取的公開變量的個(gè)數(shù)l=12；迭代735拍時(shí)，找到52個(gè)超級(jí)多項(xiàng)式，l =23；迭代770拍時(shí)，找到4個(gè)超級(jí)多項(xiàng)式，l =29，30。再隨著迭代拍數(shù)的增加，密碼函數(shù)的代數(shù)次數(shù)增高，代數(shù)標(biāo)準(zhǔn)型項(xiàng)數(shù)增多，需要選擇的公開變量的個(gè)數(shù)l也隨之增加，理論上立方攻擊的成功概率越來越低，實(shí)際上也超出了計(jì)算機(jī)的運(yùn)算能力，因此并沒有找到更多的超級(jí)多項(xiàng)式。

表1 對(duì)Trivium算法的立方攻擊結(jié)果

應(yīng)用立方攻擊方法，編程對(duì)Grain v1算法進(jìn)行了分析[17]，如表2所示，實(shí)驗(yàn)結(jié)果與上述命題及結(jié)論也是吻合的。Grain v1算法與Trivium算法相比，非線性次數(shù)較高，密鑰擴(kuò)散速度快，Grain v1算法非線性反饋移存器的反饋多項(xiàng)式的非線性次數(shù)為6，過濾函數(shù)的非線性次數(shù)為3，而Trivium算法非線性反饋移存器的反饋多項(xiàng)式的非線性次數(shù)為2，過濾函數(shù)是線性的。Grain v1算法初始化過程共迭代160拍，迭代70拍時(shí)，找到19個(gè)超級(jí)多項(xiàng)式，迭代75拍時(shí)，找到1個(gè)超級(jí)多項(xiàng)式，再隨著迭代拍數(shù)的增加，程序運(yùn)行了數(shù)月仍未找到超級(jí)多項(xiàng)式。

表2 對(duì)Grain v1算法的立方攻擊結(jié)果

7 結(jié)束語

本文就一般布爾函數(shù)及布爾函數(shù)的代數(shù)次數(shù)或代數(shù)標(biāo)準(zhǔn)型項(xiàng)數(shù)受限情況下，從理論上分析了立方攻擊的成功概率，為立方攻擊密碼分析方法提供了理論支持，理論結(jié)果與對(duì)流密碼算法Trivium及Grain v1的實(shí)驗(yàn)結(jié)果是相吻合的。

在實(shí)際密碼算法運(yùn)行過程中，算法的迭代過程也是密鑰的擴(kuò)散過程，若算法迭代一定拍數(shù)后，代數(shù)次數(shù)已經(jīng)比較高，且代數(shù)標(biāo)準(zhǔn)型項(xiàng)數(shù)也比較多，按照上述理論分析結(jié)果，這時(shí)找到超級(jí)多項(xiàng)式的概率幾乎為 0，若在實(shí)際立方攻擊過程中仍能找到超級(jí)多項(xiàng)式，則說明密碼算法設(shè)計(jì)中密鑰的擴(kuò)散能力較差，因此立方攻擊可作為密碼算法設(shè)計(jì)中檢驗(yàn)密鑰擴(kuò)散能力的一種手段。

致謝 在此，我們向?qū)Ρ疚牡墓ぷ鹘o予支持和建議的同行，尤其是馮登國(guó)教授領(lǐng)導(dǎo)的討論班上的同學(xué)和老師表示衷心的感謝。

[1] DINUR I, SHAMIR A. Cube attacks on tweakable black box Polynomials[A]. EUROCRYPT 2009[C]. Cologne, Germany, 2009. 278-299.

[2] CANNIèRE C, PRENEEL B. TRIVIUM - a stream cipher construction inspired by block cipher design principles[EB/OL]. eStream-ECRYPT Stream Cipher Project, Report 2005/030, http:// www.ecrypt.eu. org/stream/trivium.html, 2005.

[3] AUMASSON J, DINUR I, MEIER W, et al. Cube testers and key recovery attacks on reduced-round MD6 and trivium[A]. FSE 2009[C].Leuven, Belgium, 2009. 1-22.

[4] YANG L, WANG M, QIAO S. Side Channel Cube Attack on PRESENT[A]. CANS 2009[C]. Beijing, China, 2009. 379-391.

[5] FISCHER S, KHAZAEI S, MEIER W. Chosen IV statistical analysis for key recovery attacks on stream ciphers[A]. AFRICACRYPT 2008[C]. Casablanca, Morocco, 2008. 236-245.

[6] KHAZAEI S, MEIER W. New directions in cryptanalysis of self-synchronizing stream ciphers[A]. INDOCRYPT 2008[C]. Kharagpur, India, 2008. 15-26.

[7] VIELHABER M. Breaking ONE FIVIUM by AIDA an algebraic IV differential attack[EB/OL]. http://eprint.iacr.org/2007/413, 2007.

[8] ENGLUND H, JOHANSSON T, TURAN M S. A framework for chosen IV statistical analysis of stream ciphers[A]. INDOCRYPT 2007[C]. Chennai, India, 2007. 268-281.

[9] FILIOL E. A new statistical testing for symmetric ciphers and hash functions[A]. ICICS 2002[C]. Singapore, 2002. 342-353.

[10] SAARINEN M. Chosen-IV statistical attacks on eStream ciphers[A].SECRYPT[C]. Setubal Portugal, 2006. 260-266.

[11] HELL M, JOHANSSON T, MAXIMOV A, et al. The Grain family of stream ciphers[A]. LNCS 4986[C]. Setubal, Portugal, 2008. 179-190.

[12] BABBAGE S, DODD M. The stream cipher MICKEY[EB/OL].http://www.ecrypt.eu.org/stream, 2005.

[13] ARNAULT F, BERGER T, LAURADOUX C. Update on F-FCSR stream cipher[EB/OL]. http://www.ecrypt.eu.org/stream, 2006.

[14] LUCKS S. The saturation attack - a bait for Twofish[A]. FSE 2001[C].Yokohama, 2001. 1-15.

[15] KNUDSEN L. Truncated and higher order differentials[A]. FSE 1994[C].Leuven, Belgium, 1995. 196-211.

[16] BLUM M, LUBY M, RUBINFELD R. Self-testing/correcting with applications to numerical problems[A]. Proc 22nd Annual ACM Symp on Theory of Computing[C]. New York, USA, 1990. 73-83.

[17] 宋海欣, 范修斌, 武傳坤等. 流密碼算法 Grain的立方攻擊[J]. 軟件學(xué)報(bào), 2012, 23(1): 171-176.SONG H X, FAN X B, WU C K, et al. Cube a ttack on Grain[J].Journal of Software, 2012, 23(1): 171-176.