改進的基于可分屬性的立方攻擊*

穆道光，李 楓，張文政

（保密通信重點實驗室，四川 成都 610041）

0 引言

立方分析是2009 年歐密會上以色列密碼學者Dinur 和Shamir 提出的一種密碼算法分析方法[1]，目前已成為對稱密碼算法中一種常見的分析方法，針對許多典型的流密碼算法、哈希算法、認證加密算法等，采用立方分析能得到很好的分析效果。

傳統的立方分析是在選定立方變量集后，通過概率測試方法判斷其超級多項式（superpoly）是否是關于密鑰比特之間的線性或者二次關系式，最后使用代數方法求解關于密鑰比特之間的線性或者二次關系式，恢復出密鑰比特。攻擊者能夠選取的立方變量集的大小取決于其實際計算能力，當前一般不超過40。

2017 年美密會上，日本密碼學者Todo 等人提出了基于可分屬性的立方分析方法[2]。借助于混合整數線性規劃（Mixed Integer Linear Programming，MILP）求解工具，該方法可以判斷出較大規模立方變量集（如≥70）對應的超級多項式中包含的密鑰比特變量。2018 年美密會上，王慶菊等對Todo 等的基于可分屬性的立方分析方法作了改進[3]，提出了標記技術（flag technique）、單項式枚舉（term enumeration）、代數次數評估（degree evaluation）等方法，能夠進一步判斷出立方變量集對應的超級多項式的代數式次數、可能包含的單項式及數量。2019 年，葉等人改進了王慶菊等提出的單項式枚舉方法[4]，使得在更短的時間內可以得到立方變量集對應的超級多項式可能包含的單項式及數量，但是判斷的超級多項式中可能包含的單項式及數量并沒有減少，因此攻擊所需要的時間復雜的并沒有降低。

針對基于可分屬性的立方攻擊，本文提出了一種改進的單項式枚舉算法，該算法相較于之前的算法，能夠將更多的不存在于超級多項式中的單項式排除，從而得到的單項式數量更少，新的攻擊所需要的時間復雜得到降低。

在第2 節介紹相關的基本知識，在第3 節中給出改進的單項式枚舉算法，在第4 節中通過對初始化5 拍MORUS-640-128 算法的分析，驗證了改進的單項式枚舉算法的有效性，并將改進的單項式枚舉算法用于初始化6 拍MORUS-640-128 算法的分析，得到的攻擊時間復雜較文獻[4]的分析結果有明顯地降低。在第5 節中對本文進行了總結。

1 基本知識

1.1 比特可分屬性及其傳播路徑

可分屬性的概念由日本學者Todo 等在2015 年的歐密會上提出[5]，它是對積分區分器的一種推廣。隨后Todo 等針對比特向量集又提出了比特可分屬性[6]，2016 年向澤軍等建立了比特可分屬性傳播的混合整數規模（MILP）模型[7]。

定義1： 比特可分屬性，令X為上的一個多重向量集；對x，記u[i]，x[i]、u[i]表 示x、u的 第i個 分 量；集 合K={k0,k1,k2,…}，其中，i=0,1,2,…。當πu(x)=xu滿足下面的關系式(1)時，稱X具有可分屬性。

定義2：可分屬性傳播路徑，假設一個迭代密碼算法的輪函數為f(X,V)，輸入的多重集X具有起始可分屬性，經過i輪作用后得到的輸出集具備可分屬性，r輪可分屬性傳播如下：

1.2 基于可分屬性的立方攻擊

基于可分屬性的立方攻擊方法主要依據以下性質1。

性質1：令f(X,V)為關于n元密鑰比特變量和m元公開IV 變量的布爾函數，集合I={i0,i1,…,i|I|-1} ?{0,1,…,m-1}為立方變量集合，pI為I對應的超級多項式。xj為第j個密鑰比特變量。如果不存在可分屬性傳播路徑，則pI中不包含密鑰比特xj。

運用性質1，攻擊者可以找出pI中包含的所有密鑰比特，我們用集合J表pI示中包含的所有密鑰比特。

將性質1 作一般性推廣，有如下性質2。

性質2：令f(X,V)為關于n元密鑰比特變量和m元公開IV變量的布爾函數，集合I={i0,i1,…,i|I|-1} ?{0,1,…,m-1}為立方變量集合，pI為I對應的超級多項式。集合T={j0,j1,…,j|T|-1} ?{0,1,2,…,n-1}，如果不存在可分屬性傳播路徑，則pI中不包含單項式xj0,xj1,xj2,…,xj|T|-1。

根據性質2，王慶菊等在文獻[3]中提出了pI的代數式次數上界判斷方法，通過在比特可分屬性傳播的MILP 模型中設置目標函數為，求解MILP 模型，目標函數返回值即為pI的代數式次數上界d,d≥deg(pI)。

根據性質2，王慶菊在文獻[3]中提出了一種單項式枚舉方法，通過在比特可分屬性傳播的MILP 模型中增加約束，其中0 ≤t≤d，該MILP 模型的一個可行解即對應了pI中可能存在的一個次數為t的單項式，該MILP 模型的所有可行解對應了pI中所有可能存在的次數為t的單項式，記pI中次數為t的單項式集合為Jt。

對選定的一個立方變量集I，在立方攻擊離線階段需要的時間復雜度為；在立方攻擊離線階段需要的時間復雜度為，假設I對應的超級多項式pI為平衡布爾函數，該立方變量集I恢復1 比特密鑰信息的時間復雜度為。

1.3 標記技術

考慮比特運算：(s1,s2)→(s1,s2,s1·s2)，根據比特可分屬性傳播規則，當輸入的比特可分屬性為(0,1)時，輸出的比特可分屬性為{(0,1,0),(0,0,1)}；當輸入的比特可分屬性為(1,0)時，輸出的比特可分屬性為{(1,0,0),(0,0,1)}。

當s1取固定值0 時，s1·s2恒為0。因此，s1取固定值0，輸入比特可分屬性(0,1)時，輸出的比特可分屬性為(0,1,0)，即這時候不存在可分屬性傳播路徑(0,1)→(0,0,1)。

類似地，當s2取固定值0 時，s1·s2恒為0。因此，s2取固定值0，輸入比特可分屬性(1,0)時，輸出的比特可分屬性為(1,0,0)，即這時候不存在可分屬性傳播路徑(1,0)→(0,0,1)。

針對這種情況，王慶菊等在文獻[3]中提出了標記技術，在每個比特位置υi，額外增加一個輔助標記符號υi.F。當該位置的比特取值恒為0 時，其標記符號υi.F設置為0c，當該位置的比特取值恒為1 時，其標記符號υi.F設置為1c，當該位置的比特取值不固定時，其標記符號υi.F設置為δ。

標記符號在比特運算中傳遞規則如下：

（1）比特復制運算x→(x,x)：0c→(0c,0c)，1c→(1c,1c)，δ→(δ,δ)；

（2）比特異或運算x·y→z：(1c,1c)→0c，(0c,α)→α，(α,0c)→α，(δ,α)→δ，(α,δ)→δ，這里α∈{0c,1c,δ}。

（3）比特與運算x·y→z：(δ,δ) →δ，(1c,α)→α，(α,1c)→α，(0c,α)→0c，(α,0c)→0c，這里α∈{0c,1c,δ}。

通過設置標記符號，當遇到(s1,s2)→(s1,s2,s1·s2)運算時，如果s1或者s2的標記符號為0c，將排除比特可分屬性傳播路徑(0,1)→(0,0,1)或者(1,0)→(0,0,1)。

2 改進的單項式枚舉算法

性質2 給出了判斷立方變量集I對應的超級多項式pI中不包含單項式xj0,xj1,xj2,…,xj|T|-1的理論依據。但反過來，對于一個集合T={j0,j1,…,j|T|-1}?{0,1,2,…,n-1}，如果存在可分屬性傳播路徑，pI中不一定包含單項式xj0,xj1,xj2,…,xj|T|-1。例如假設超級多項式pI=x1x2x3+x1x4，對T∈{{1,2},{1,3},{2,3},{1,4}}，都存在可分屬性傳播路徑(WTn||WIm)→1，但pI中不包含單項式x1x2、x1x3、x2x3。

集 合T={j0,j1,…,j|T|-1} ?{0,1,2,…,|J|-1}。記J為pI中包含的密鑰比特集合，假設J={x0,x1,…,x|J|-1}，則超級多項式pI可以分解為pI=xj0,xj1,…,xj|T|-1g(X′)+h(x0,x1,…,x|J|-1)，其中g(X′)為變量取自X′=J-T上的布爾函數，h(x0,x1,…,x|J|-1)中的項均不包含因子xj0,xj1,…,xj|T|-1。

只有當固定所有的x∈X′為0 時，g(0)=1，即pI中仍然包含單項式xj0,xj1,…,xj|T|-1，則說明xj0,xj1,…,xj|T|-1∈Jt。因此，我們有下面的命題1。

命題1 令f(X,V) 為關于n元密鑰比特變量X∈和m元公開IV變量V∈的布爾函數，集合I={i0,i1,…,i|I|-1} ?{0,1,…,m-1}為立方變量集合，pI為I對應的超級多項式。J為pI中包含的密鑰比特集合，不妨假設J={x0,x1,…,x|J|-1}，集合T={j0,j1,…,j|T|-1} ?{0,1,2,…,|J|-1}，對所有的x∈X′=J-T,x=0。如果不存在可分屬性傳播路徑，則pI中不包含單項式xj0,xj1,xj2,…,xj|T|-1。

由于所有的x∈X′=J-T,x=0，故pI=g(0)xj0,xj1,…,xj|T|-1+h(x0,x1,…,x|J|-1)。pI中僅有一項xj0,xj1,…,xj|T|-1g(0)滿足時，故g(0)=0，表明pI中不包含單項式xj0,xj1,xj2,…,xj|T|-1，即xj0,xj1,xj2,…,xj|T|-1?J|T|。證明完畢。

由命題1，我們在文獻[3]中算法5 的基礎上提出了一種改進的單項式枚舉算法。

算法：改進的單項式枚舉算法

輸入：立方變量集I，非立方變量集賦值IV，次數t，pI中包含的密鑰比特集J，輸出比特位置output。

步驟1：新建MILP 模型 M，一個空集合Jt；

步驟2： 聲明m個MILP 變量vi，其中i=0,1,2,…,m-1，代表公開變量；聲明n個MILP 變量xi，其中i=0,1,2,…,n-1，代表密鑰變量；

步驟3：對所有的vi，i∈I，在 M中增加約束條件vi=1，并將vi的標記符號賦值為vi.F=δ；

步驟4：對所有的vi，i?I，在 M中增加約束條件vi=0，并將vi的標記符號賦值為vi.F=IV[i]；

步驟6：根據算法輪函數、輸出比特位置output，按照可分屬性傳播規則，更新 M；

步驟7：求解 M模型，如果模型無可行解，跳至步驟13；

步驟8：記可行解中集合{xi|xi=1}為T，新建MILP 模型*M，并對*M 模型運行步驟2 至步驟4，對xi∈J-T，xi.F=0c；

步驟9：對xi∈T，在*M 中增加約束條件xi=1；對xi?T，在*M 中增加約束條件xi=0；

步驟10：根據算法輪函數、輸出比特位置output，按照可分屬性傳播規則，更新*M ；

步驟11：求解*M，如果模型有可行解，將單項式納入Jt；

步驟13：輸出Jt。

改進的單項式枚舉算法相較于之前的算法，能夠將更多的不存在于pI中的t次單項式排除，從而改進的單項式枚舉算法得到的|Jt|更小。由于立方變量集I恢復1 比特密鑰信息的時間復雜度為，因此，采用改進的單項式枚舉算法將使得立方變量集I恢復1 比特密鑰信息的時間復雜度得到降低。

3 對MORUS-640-128 算法的分析

3.1 MORUS-640-128 算法簡介

MORUS 算法是CAESAR 競賽末輪7 個候選認證加密算法之一，由新加坡南洋理工大學伍宏軍等提交。MORUS-640-128 算法是MORUS 算法其中一個版本，使用128 比特密鑰和128 比特初始向量IV，內部狀態寄存器大小為640 比特。MORUS-640-128算法加密與認證過程包括初始化階段、關聯數據處理階段、加密階段、標簽生成階段四個階段。我們的分析只涉及到MORUS-640-128 算法的初始化階段，因此只對該階段進行介紹。

記MORUS-640-128 算法的128 比特密鑰為K，128 比特初始向量為IV，640 比特的內部狀態寄存器初始狀態為，其 中均為128 比特。

MORUS-640-128 算法的初始化階段分為初始狀態載入和16拍狀態更新。初始狀態載入過程如下：

這里1128表示128 比特全1 向量，const0、const1均為128 比特常數。

初始狀態載入完畢后進行16 拍狀態更新，每拍包含5 輪運算，具體如下（i=-16 至-1）：

其中，b0=5，b1=31，b2=7，b3=22，b4=13；w0=32，w1=64，w2=96，w3=64，w4=32；函數Rotl(X,b)表示將X分為4 個32 比特數，每個32 比特數循環左移b位。

3.2 初始化5 拍MORUS-640-128 算法的分析

對初始化5 拍的MORUS-640-128 算法，我們選取一個3 維立方變量集I={5,8,97}，非立方變量均固定為0，輸出比特位置為，i從0 到127 變化，分別通過三種不同的方法計算I對應的超級多項式pI中1 次單項式集合J1。

方法一：直接計算，記輸出比特關于密鑰K和初始向量IV的布爾函數為f(K,IV)，用CI表示非立方變量均固定為0，立方變量集I中的元素遍歷所有可能值所組成的向量集合。

首先，取K為全0，即K=0128，計算⊕IV∈CI f(K,IV)，得到pI中常數項值c=⊕IV∈CI f(0128,IV)；

其次，對j=0,1,2,…,127，依次取K為kj，其中kj表示128 比特向量在第j比特位置取1，其他位置取0，計算⊕IV∈CI f(kj,IV)，得到pI中1 次單項式xj的系數aj=c⊕(⊕IV∈CI f(kj,IV))；所有滿足系數aj=1 的xj構成了pI中1 次單項式集合，記得到的集合為。

方法二：采用第3 節中改進的單項式枚舉算法，輸入立方變量集I，次數為1，pI中包含的密鑰比特集J={xj|j=0,1,2,…,127}，非立方變量固定為全0，輸出比特位置；得到的集合記為。

方法三：采用文獻[3]中的算法5，通過在比特可分屬性傳播的MILP 模型中增加約束，該MILP 模型的一個可行解即對應了pI中可能存在的一個次數為1 的單項式，該MILP 模型的所有可行解對應了pI中所有可能存在的次數為1的單項式，記得到的集合為。

3.3 初始化6 拍MORUS-640-128 算法的分析

文獻[4]中葉等人采用基于可分屬性的立方攻擊對初始化為6 輪MORUS-640-128 算法進行了分析，選取了24 個立方變量集I和輸出比特位置，非立方變量固定取0，給出了它們超級多項式中可能包含的單項式和數量，其結果見文獻[4]中附表9。

我們采用3 節中改進的單項式枚舉算法，對這些立方變量集I和它們相應輸出比特位置，重新判斷他們對應的超級多項式中可能包含的單項式及數量。整個分析過程如下：

步驟1：選取文獻[4]中附表9 中的一個立方變量集I，非立方變量固定為0，運行文獻[3]中算法1，得到I對應超級多項式中包含的密鑰比特集J。

步驟2：立方變量集I，非立方變量固定為0，運行文獻[3]中算法2，得到I對應超級多項式pI的代數次數上界d。

步驟3：對t=0 至d，運行第3 節中改進的單項式枚舉算法，得到pI中可能包含的所有t 次單項式集合Jt。

我們的分析結果見表2。

表1 、、中元素個數

表1 、、中元素個數

表2 初始化6 拍MORUS-640-128 的分析結果

其中，單項式數量num，時間復雜度。最后一列為文獻[4]中的攻擊時間復雜度。

以立方變量集I={3,4,7,15,20,24,30,31,40,43,50,60,70,79,86,89,95,96,97,102,103,106,111,116}，輸出比特位置取為例，該立方變量集I對應的超級多項式pI的代數次數上界為14，下表3 給出了pI中t次單項式數量|Jt|的情況（t=0 至14）。

由表3 可知，我們得到pI中單項式數量為=800，假設I對應的超級多項式pI為平衡布爾函數下，則該立方變量集I恢復1比特密鑰信息所需要的時間復雜度為。相比較而言，文獻[4]得到的pI中單項式數量為60928，所需要的時間復雜度約為239.9。

表3 t 次單項式數量

4 結語

立方攻擊是一種典型的對稱密碼算法分析方法。針對基于可分屬性的立方攻擊，提出了一種改進的單項式枚舉算法，該算法相較于之前的算法，能夠將更多的不存在于超級多項式中的單項式排除，從而導致新的攻擊所需要的時間復雜得到降低。針對初始化5 拍MORUS-640-128 算法的分析驗證了新的攻擊方法的有效性。針對初始化6 拍MORUS-640-128 算法的攻擊所需要的時間復雜度較之前的分析結果更低。