立方攻擊研究進(jìn)展

王明興 ，朱玉倩 ，苗三立

(1.中國電子信息產(chǎn)業(yè)集團有限公司第六研究所，北京102209；2.密碼科學(xué)技術(shù)國家重點實驗室，北京100878)

0 引言

DINUR I 和 SHAMIR A 在 2009 年的歐密會上提出了一種新型的攻擊手段[1]，稱為立方攻擊(Cube Attack)。 立方攻擊是一種選擇明文攻擊，其攻擊思想是：密碼算法被看成是一個未知的復(fù)雜的多元多項式，輸入變量(明文或者初始向量)稱為公開變量，密鑰變量稱為秘密變量；輸出變量可以表示為公開變量和秘密變量的某種多項式的形式。只要至少有一位輸出變量可以表示為秘密變量和公開變量的低次多項式，通過賦值一些公開變量，即可訪問密碼算法獲取輸出結(jié)果，得到秘密變量的簡單的方程式，恢復(fù)密鑰比特。

TODO Y 等人[2]在 2015 年提出了多重集合的可分性(Division Property)的概念，它是分析分組密碼積分特征的有力工具。 在之后的一年，TODO Y 等人[3]又提出了基于比特的多重集合的可分性。 向澤軍等人[4]在2016 年的亞密會上提出了可分路徑的概念，將可分路徑的計算轉(zhuǎn)化為求解混合整數(shù)線性規(guī) 劃 (Mixed Integer Linear Programming，MILP)問 題 ，提高了積分攻擊的準(zhǔn)確性和運算效率。 在 2017 年的美密會上，TODO Y 等人[5]提出了可分性的可分路徑和立方攻擊的超級多項式之間的聯(lián)系，給出了求解超級多項式中的變量的算法。

王慶菊等人[6]進(jìn)一步提升了MILP 模型的計算準(zhǔn)確性，提出了超級多項式的最高次項的求解算法，降低了立方攻擊的復(fù)雜度。 王森鵬等人[7]采用了三子集可分性的概念，發(fā)展了求超級多項式的算法，降低了算法的時間復(fù)雜度。HAO Y L 等人[8]提出了基于完善的三子集的多重集合的可分性的定義，更進(jìn)一步提升了MILP 模型計算超級多項式的準(zhǔn)確性。

本文的主要目的是全面回顧立方攻擊的技術(shù)演進(jìn)歷程，介紹最新的立方攻擊技術(shù)，展望未來立方攻擊的發(fā)展方向和應(yīng)用價值。

1 立方攻擊的原理和過程

1.1 立方攻擊的定義

立方攻擊利用了多元布爾多項式的高階差分的性質(zhì)，即布爾多項式都可以表示成一種帶余除法的形式，其中余式是不能包含除式的全部變量的多項式。

定義 1[1]設(shè)布爾多項式 f(x1，x2，…，xn-1)的代數(shù)正規(guī)型表示為：

設(shè) I={i1，i2，…，i|I|}是 集合{1，2，…，n}的一個子集，I 中元素的個數(shù)記為|I|，I 被稱為是一個立方指數(shù)，稱為一個立方(cube)，設(shè)于是：

其中PS(I)是與tI沒有相同變量的多項式，被稱為立方 I 的超 級 多項 式(Superpoly)；r(x1，x2，…，xn-1)中的每一項至少缺失tI中的一個變量。 當(dāng) CI中的變量取遍所有的可能值，對式(2)的左端取連加和，得到PS(I)，即∑CIf=PS(I)。

對攻擊者而言，密碼算法是一個關(guān)于秘密變量和公開變量的復(fù)雜的多元多項式，表示為 f(v1，v2，…，vm-1，x1，x2，…，xn-1)，其中 xi是秘密變量 ，vi是公開變量。 立方攻擊是把多元布爾多項式表示成一種類似于式(2)的分解式，除式是某些公開變量的乘積，超級多項式是秘密變量的簡單的多項式，然后通過下面的攻擊過程恢復(fù)密鑰。

1.2 立方攻擊的攻擊過程

攻擊過程分為兩個階段：離線階段和在線階段。

離線階段：攻擊者可以選擇秘密變量和公開變量，隨機選擇立方變量，執(zhí)行密碼算法，計算PS(I)，使用一次或者二次超級多項式的判定準(zhǔn)則(見第2 節(jié))，得到很多立方變量和相應(yīng)的簡單超級多項式，為在線階段做準(zhǔn)備。

在線階段：秘密變量是固定的且是未知的，不允許選擇，敵手利用離線階段獲得的立方變量，對其進(jìn)行0/1 賦值，去訪問加密算法，得到輸出比特；對所有輸出比特進(jìn)行連加求和，獲得超級多項式的值，最后求解得到的代數(shù)方程組，可以恢復(fù)某些密鑰比特；猜測剩余的密鑰變量，完成密鑰恢復(fù)攻擊。

2 低次超級多項式的判別方法

文獻(xiàn)[1，9-10]中的超級多項式的次數(shù)是一次或二次的，判別方法也較為簡單，下面分別敘述。

2.1 一次超級多項式判別方法

獨立均勻隨機地選擇 x，y∈{0，1}n，驗證 PS(I)[0]+PS(I)[x]+PS(I)[y]=PS(I)[x+y]是否成立。如果PS(I)是 線性的，則測試總是成功的；如果 PS(I)不是線性的，則測試以很高的概率失敗，測試進(jìn)行足夠多次，敵手就可以確定PS(I)是非常接近線性的了。

2.2 二次超級多項式的判別方法

隨機選擇 x1，x2，x3∈{0，1}n，驗證 PS(I)[0]+PS(I)[x1]+PS(I)[x2]+PS(I)[x3]+PS(I)[x1+x2]+PS(I)[x1+x3]+PS(I)[x2+x3]+PS(I)[x1+x2+x3]=0 是否成立。如果 PS(I)是 二 次 的 ，則測試總是成功的；如果PS(I)不是二次的(是更高次的)，則測試以很高的概率失敗，測試多次就可以排除非二次的PS(I)。

2.3 非線性超級多項式的判別方法

在非線性超級多項式情形下，為確定超級多項式的項和系數(shù)，引入一種擴展的立方攻擊理論(Extended Cube Attack)。

定義2(擴展立方體)[10]在立方攻擊中，對任意立方 CI，如果存在另一個立方 CH，且 I∩H=φ，則CI與 CH可以得到一個擴展的立方 CI∪H。

下面的引理 1 和引理 2，判斷哪些密鑰變量存在于PS(I)中以及以怎樣的單項式形式存在。

引理 1[10]設(shè) f(x1，x2，…，xn)是一個多項式 ，設(shè)I={i0，…，il} 是集合 {1 ，2 ，…，n}的一個子集，則 tI以子項式或子項的一部分存在于 f 中， 當(dāng)且僅當(dāng)至少存在一個向量 x ∈{0，1}n-|I|，使得。

引理2[10]單項式是 PS(I)中的一個子項，當(dāng)且僅當(dāng)令所有xi=0(xi?I∪H)，有

3 立方攻擊的前沿研究及主要結(jié)論

上節(jié)介紹了求解低次超級多項式的判別方法，求解更高次的超級多項式的方法是本節(jié)要介紹的內(nèi)容。

3.1 基于比特的多重集合的可分性

基于比特的可分性定義如下：

定義3[2]設(shè)是一個多重集合是一個n 維向量的集合，稱多重集 X 有可分性，如果滿足下面的條件：

這里 u≥K 是指如果對于任意的 i，都有 ui≥ki，其中。

定義4[4](可分路徑) 假設(shè)可分性質(zhì)的傳播為{K}?Y0→Y1→…→Yr，進(jìn)一步地，對任何向量Yi+1必然存在一個向量可由可分性的傳播規(guī)則傳播到，更進(jìn)一步地，(K0，K1，…，Kr)∈(Y0×Y1×…×Yr)， 如 果 Ki可以傳播到Ki+1，i ∈{0，1，…，r-1}，就把(K0，K1，…，Kr)稱為一條 r 輪的可分路徑。

為了計算出所有的可分路徑，需要先把密碼算法中的復(fù)制運算(Copy)、異或運算(XOR)和且運算(AND)轉(zhuǎn)化成MILP 模型，再把整個密碼算法建模成MILP 模型，這樣就可以使用最優(yōu)化數(shù)學(xué)軟件Gurobi來計算所有的可分路徑。

3.2 基于可分路徑尋找超級多項式

由第2 節(jié)可知，立方攻擊成功的關(guān)鍵在于找到簡單的超級多項式，例如超級多項式中的變量的個數(shù)少，同時次數(shù)又是一次的或者二次的。 下面的性質(zhì)是利用可分路徑求出超級多項式中所有的變量的依據(jù)。

性質(zhì) 1[5]設(shè) f(X，V)是一個多元多項式，X=(x0，x1，…，xn-1)是秘密變量，V=(v0，v1，…，vm-1)是 公 開變量，設(shè)一個立方索引 I={i0，i1，…，i|I|-1}，KI是一個m 維的向量，使得即 如 果 i∈I，則 ki=1，否則 ki=0；n 維向量 ej=(0，…，0，1，0，…，0)，即在第 j 分量上取值為 1，而其他分量是 0；假設(shè)沒有可分路徑(ej，KI)→f1，那么 xj不是超級多項式中的變量。

性質(zhì) 1 說明，存在可分路徑(ej，KI)→f1，則 xj是超級多項式中的變量，那么可以得到超級多項式中的所有的變量，進(jìn)而求出超級多項式的表達(dá)式。

離線階段：設(shè)J 是超級多項式中的變量下標(biāo)的集合，集合J 遍歷所有可能的值組成的集合記為 CJ， 集合 J 之外的變量賦值為 0， 對于給定的值Xs=(xs，0，0，…，0)，xs∈CJ，敵 手 可 以 設(shè)定 公開 變 量中除了立方變量之外的變量為某些常數(shù)， 計算∑CIf(Xs，V)=PS(I)，得到超級多項式 的真值表。 值得注意的是，敵手可以多次選擇除了立方變量以外的公開變量的值使得超級多項式是一次的。

這里時間復(fù)雜度為 2|I|+|J|，如果|I|+|J|小于密鑰長度，那么立方攻擊就是有效的。

在文獻(xiàn)[6]中，王慶菊等人注意到常數(shù)值0 在運算中會消去多項式這一現(xiàn)象， 提出了Flag 技術(shù)，即定義了初始向量的常數(shù)值與變量的運算法則，修正了復(fù)制、異或、且運算的 MILP 模型，提高了可分路徑的計算準(zhǔn)確性，提出了超級多項式的最高次項的判斷方法，使得立方攻擊可以求出更高次數(shù)的超級多項式。

性質(zhì) 2設(shè) f(X，V)是一個多元多項式，X=(x0，x1，…，xn-1)是秘密變量 ，V=(v0，v1，…，vm-1)是 公 開變量，設(shè)一個立方索引 I={i0，i1，…，i|I|-1}，KI是一個m 維向量 ， 使得即如果i ∈I，則ki=1， 否則 ki=0；KΛ是一個 n 維向量， 假設(shè)沒有可分路徑(KΛ，KI)→1，那么 XKΛ不在超級多項式中。

性質(zhì) 2 說明，如果存在可分路徑(KΛ，KI)→1，那么XKΛ在超級多項式中，于是，在線性整數(shù)規(guī)劃模型中可以求得超級多項式中的最高次項；再由性質(zhì)1，得到超級多項式中的所有的變量，就可以降低恢復(fù)超級多項式的復(fù)雜度。

3.3 基于三子集可分性

定義 5[7](基于三子集可分性) 設(shè) X 是一個多重集合是由 n 維比特向量組成的集合，當(dāng)多重集 X 具有可分性是指下列的條件成立：

基于三子集可分性修改了復(fù)制運算、異或運算、與運算的 MILP 建模，王森鵬等人[7]提出了該可分性的修剪性質(zhì)(Pruning Properties)，去掉無用的可分路徑， 并提出了可分路徑的加速傳播和停止準(zhǔn)則，來提高可分路徑的計算效率；最后提出了相似多項式(Similar Polynomial)的概念來計算超級多項式。 但是這一概念與文獻(xiàn)[10]中的引理2 本質(zhì)上是一致的。對密碼算法 Trivium[11]的立方攻擊的輪數(shù)是 839 輪，但時間復(fù)雜度為常數(shù)，攻擊實際可行。

3.4 完善的三子集可分性

HAO Y L 等人[8]發(fā)現(xiàn)王森鵬等人的立方攻擊的計算方法并非總是有效的，在求841 輪的Trivium的超級多項式時，由于 L 的規(guī)模過大，在合理的時間內(nèi)是無法求解的。 于是，提出了完善三子集可分性的概念。

定義 6[8](完善三子集可分性) 設(shè) X 是一個多重集合，其元素，設(shè) L 也是一個多重集合，其元素有完善的三子集可分性是指滿足下面的條件：

HAO Y L 等人進(jìn)一步完善了復(fù)制運算、異或運算、與運算的MILP 建模，提出了更有效的計算超級多項式的算法，對輪數(shù)是 841 輪的 Trivium，完全確定了其超級多項式的表達(dá)式，展示了立方攻擊的強大的分析能力。

4 立方攻擊技術(shù)比較

密碼算法Trivium 是基于非線性反饋移位寄存器的序列密碼，迭代關(guān)系式是兩次的，密鑰長度是80 bit，初始化向量是80 bit，初始化輪數(shù)是1 152 輪。表1 以立方攻擊分析 Trivium 算法為例， 清晰地展示了立方攻擊技術(shù)的分析能力。

通過表1 可以發(fā)現(xiàn)，基于一次或者二次超級多項式判定方法的立方攻擊，求得的超級多項式表達(dá)式簡單，攻擊輪數(shù)低，時間復(fù)雜度也低；而基于多重集合可分性的立方攻擊，可以求得的超級多項式表達(dá)式復(fù)雜，攻擊輪數(shù)高，但是時間復(fù)雜度不一定高。

究其原因， 密碼算法 Trivium 的迭代關(guān)系式是二次的，在初始化輪數(shù)較低時(小于 767 輪)，局部出現(xiàn)線性多項式的可能性較大，但是隨著初始化輪數(shù)的增加(大于 832 輪)，輸出比特的關(guān)系式的非線性程度將急劇增加，無論是代數(shù)次數(shù)還是項數(shù)都會增加很快，局部出現(xiàn)線性多項式的可能性較小，輸出比特的關(guān)系式會非常復(fù)雜。 這是兩種立方攻擊的分析效果截然不同的根本原因。 這就是說，基于一次或者二次超級多項式的判定方法的立方攻擊不可能分析到更高的輪數(shù)，即基于一次或者二次超級多項式的判定方法的立方攻擊，不可能取得大的突破性進(jìn)展，這是由密碼算法自身的迭代關(guān)系式和輪數(shù)決定的。 但是基于可分性，立方攻擊可能分析到更高的輪數(shù)。 這是因為后者有清晰的數(shù)學(xué)模型、扎實的數(shù)學(xué)理論支撐，而且計算過程使用了數(shù)學(xué)軟件工具，能夠求解的超級多項式從理論上講是不限制次數(shù)和項數(shù)的，能否計算出超級多項式只取決于計算機的計算能力，所以后者方法可以求出更高輪數(shù)的超級多項式的表達(dá)式。

由此可知，未來的研究方向主要是要完善基于可分性的立方攻擊的技術(shù)，提升其計算能力。 亟待解決的研究問題有兩個：一是進(jìn)一步提高數(shù)學(xué)模型計算的準(zhǔn)確性，因為有研究指出，針對 Trivium 的某些輪數(shù)， 立方攻擊不是密鑰恢復(fù)攻擊而是區(qū)分攻擊；二是優(yōu)化實現(xiàn)立方攻擊的算法，降低其時間復(fù)雜度，提高其計算效率，因為目前的攻擊算法在普通計算機上的運行時間需要幾天或者時間復(fù)雜度更大，還有進(jìn)一步優(yōu)化的必要。

表1 Trivium 算法的立方攻擊結(jié)果比較

5 結(jié)論

本文詳細(xì)介紹了立方攻擊的最新發(fā)展，展示了求超級多項式技術(shù)的進(jìn)步，能夠恢復(fù)超級多項式的次數(shù)從一次、二次到更高次。 其中 TODO Y 等人的研究工作具有里程碑意義，打開了建立數(shù)學(xué)模型、利用數(shù)學(xué)軟件計算超級多項式的大門，顯著提高了立方攻擊的分析能力。

從立方攻擊的技術(shù)發(fā)展來看，立方攻擊對反饋關(guān)系式為二次的序列密碼的分析效果非常好。 這說明在設(shè)計序列密碼時，反饋關(guān)系式的代數(shù)次數(shù)應(yīng)適當(dāng)提高，使得輸出比特的表達(dá)式隨著輪數(shù)增加快速復(fù)雜化以抵抗立方攻擊；未來密碼算法能夠抵抗立方攻擊將成為必要的安全準(zhǔn)則。

由于立方攻擊技術(shù)的進(jìn)步，將來可以分析分組密碼和哈希函數(shù)抵抗立方攻擊的能力，雖然這兩類密碼算法設(shè)計復(fù)雜，但也可能得到較理想的分析結(jié)果。