立方攻擊研究進展

王明興 ，朱玉倩 ，苗三立

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

0 引言

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

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

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

本文的主要目的是全面回顧立方攻擊的技術演進歷程，介紹最新的立方攻擊技術，展望未來立方攻擊的發展方向和應用價值。

1 立方攻擊的原理和過程

1.1 立方攻擊的定義

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

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

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

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

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

1.2 立方攻擊的攻擊過程

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

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

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

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

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

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

獨立均勻隨機地選擇 x，y∈{0，1}n，驗證 PS(I)[0]+PS(I)[x]+PS(I)[y]=PS(I)[x+y]是否成立。如果PS(I)是 線性的，則測試總是成功的；如果 PS(I)不是線性的，則測試以很高的概率失敗，測試進行足夠多次，敵手就可以確定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 非線性超級多項式的判別方法

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

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

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

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

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

3 立方攻擊的前沿研究及主要結論

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 基于三子集可分性

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

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

3.4 完善的三子集可分性

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

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

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

4 立方攻擊技術比較

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

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

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

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

表1 Trivium 算法的立方攻擊結果比較

5 結論

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

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

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