改進(jìn)的基于可分屬性的立方攻擊*

穆道光，李 楓，張文政

（保密通信重點(diǎn)實(shí)驗(yàn)室，四川 成都 610041）

0 引言

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

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

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

針對(duì)基于可分屬性的立方攻擊，本文提出了一種改進(jìn)的單項(xiàng)式枚舉算法，該算法相較于之前的算法，能夠?qū)⒏嗟牟淮嬖谟诔?jí)多項(xiàng)式中的單項(xiàng)式排除，從而得到的單項(xiàng)式數(shù)量更少，新的攻擊所需要的時(shí)間復(fù)雜得到降低。

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

1 基本知識(shí)

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

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

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

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

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

基于可分屬性的立方攻擊方法主要依據(jù)以下性質(zhì)1。

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

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

將性質(zhì)1 作一般性推廣，有如下性質(zhì)2。

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

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

根據(jù)性質(zhì)2，王慶菊在文獻(xiàn)[3]中提出了一種單項(xiàng)式枚舉方法，通過(guò)在比特可分屬性傳播的MILP 模型中增加約束，其中0 ≤t≤d，該MILP 模型的一個(gè)可行解即對(duì)應(yīng)了pI中可能存在的一個(gè)次數(shù)為t的單項(xiàng)式，該MILP 模型的所有可行解對(duì)應(yīng)了pI中所有可能存在的次數(shù)為t的單項(xiàng)式，記pI中次數(shù)為t的單項(xiàng)式集合為Jt。

對(duì)選定的一個(gè)立方變量集I，在立方攻擊離線階段需要的時(shí)間復(fù)雜度為；在立方攻擊離線階段需要的時(shí)間復(fù)雜度為，假設(shè)I對(duì)應(yīng)的超級(jí)多項(xiàng)式pI為平衡布爾函數(shù)，該立方變量集I恢復(fù)1 比特密鑰信息的時(shí)間復(fù)雜度為。

1.3 標(biāo)記技術(shù)

考慮比特運(yùn)算：(s1,s2)→(s1,s2,s1·s2)，根據(jù)比特可分屬性傳播規(guī)則，當(dāng)輸入的比特可分屬性為(0,1)時(shí)，輸出的比特可分屬性為{(0,1,0),(0,0,1)}；當(dāng)輸入的比特可分屬性為(1,0)時(shí)，輸出的比特可分屬性為{(1,0,0),(0,0,1)}。

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

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

針對(duì)這種情況，王慶菊等在文獻(xiàn)[3]中提出了標(biāo)記技術(shù)，在每個(gè)比特位置υi，額外增加一個(gè)輔助標(biāo)記符號(hào)υi.F。當(dāng)該位置的比特取值恒為0 時(shí)，其標(biāo)記符號(hào)υi.F設(shè)置為0c，當(dāng)該位置的比特取值恒為1 時(shí)，其標(biāo)記符號(hào)υi.F設(shè)置為1c，當(dāng)該位置的比特取值不固定時(shí)，其標(biāo)記符號(hào)υi.F設(shè)置為δ。

標(biāo)記符號(hào)在比特運(yùn)算中傳遞規(guī)則如下：

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

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

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

通過(guò)設(shè)置標(biāo)記符號(hào)，當(dāng)遇到(s1,s2)→(s1,s2,s1·s2)運(yùn)算時(shí)，如果s1或者s2的標(biāo)記符號(hào)為0c，將排除比特可分屬性傳播路徑(0,1)→(0,0,1)或者(1,0)→(0,0,1)。

2 改進(jìn)的單項(xiàng)式枚舉算法

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

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

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

命題1 令f(X,V) 為關(guān)于n元密鑰比特變量X∈和m元公開(kāi)IV變量V∈的布爾函數(shù)，集合I={i0,i1,…,i|I|-1} ?{0,1,…,m-1}為立方變量集合，pI為I對(duì)應(yīng)的超級(jí)多項(xiàng)式。J為pI中包含的密鑰比特集合，不妨假設(shè)J={x0,x1,…,x|J|-1}，集合T={j0,j1,…,j|T|-1} ?{0,1,2,…,|J|-1}，對(duì)所有的x∈X′=J-T,x=0。如果不存在可分屬性傳播路徑，則pI中不包含單項(xiàng)式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中僅有一項(xiàng)xj0,xj1,…,xj|T|-1g(0)滿足時(shí)，故g(0)=0，表明pI中不包含單項(xiàng)式xj0,xj1,xj2,…,xj|T|-1，即xj0,xj1,xj2,…,xj|T|-1?J|T|。證明完畢。

由命題1，我們?cè)谖墨I(xiàn)[3]中算法5 的基礎(chǔ)上提出了一種改進(jìn)的單項(xiàng)式枚舉算法。

算法：改進(jìn)的單項(xiàng)式枚舉算法

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

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

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

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

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

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

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

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

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

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

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

步驟13：輸出Jt。

改進(jìn)的單項(xiàng)式枚舉算法相較于之前的算法，能夠?qū)⒏嗟牟淮嬖谟趐I中的t次單項(xiàng)式排除，從而改進(jìn)的單項(xiàng)式枚舉算法得到的|Jt|更小。由于立方變量集I恢復(fù)1 比特密鑰信息的時(shí)間復(fù)雜度為，因此，采用改進(jìn)的單項(xiàng)式枚舉算法將使得立方變量集I恢復(fù)1 比特密鑰信息的時(shí)間復(fù)雜度得到降低。

3 對(duì)MORUS-640-128 算法的分析

3.1 MORUS-640-128 算法簡(jiǎn)介

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

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

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

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

初始狀態(tài)載入完畢后進(jìn)行16 拍狀態(tài)更新，每拍包含5 輪運(yùn)算，具體如下（i=-16 至-1）：

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

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

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

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

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

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

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

方法三：采用文獻(xiàn)[3]中的算法5，通過(guò)在比特可分屬性傳播的MILP 模型中增加約束，該MILP 模型的一個(gè)可行解即對(duì)應(yīng)了pI中可能存在的一個(gè)次數(shù)為1 的單項(xiàng)式，該MILP 模型的所有可行解對(duì)應(yīng)了pI中所有可能存在的次數(shù)為1的單項(xiàng)式，記得到的集合為。

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

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

我們采用3 節(jié)中改進(jìn)的單項(xiàng)式枚舉算法，對(duì)這些立方變量集I和它們相應(yīng)輸出比特位置，重新判斷他們對(duì)應(yīng)的超級(jí)多項(xiàng)式中可能包含的單項(xiàng)式及數(shù)量。整個(gè)分析過(guò)程如下：

步驟1：選取文獻(xiàn)[4]中附表9 中的一個(gè)立方變量集I，非立方變量固定為0，運(yùn)行文獻(xiàn)[3]中算法1，得到I對(duì)應(yīng)超級(jí)多項(xiàng)式中包含的密鑰比特集J。

步驟2：立方變量集I，非立方變量固定為0，運(yùn)行文獻(xiàn)[3]中算法2，得到I對(duì)應(yīng)超級(jí)多項(xiàng)式pI的代數(shù)次數(shù)上界d。

步驟3：對(duì)t=0 至d，運(yùn)行第3 節(jié)中改進(jìn)的單項(xiàng)式枚舉算法，得到pI中可能包含的所有t 次單項(xiàng)式集合Jt。

我們的分析結(jié)果見(jiàn)表2。

表1 、、中元素個(gè)數(shù)

表1 、、中元素個(gè)數(shù)

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

其中，單項(xiàng)式數(shù)量num，時(shí)間復(fù)雜度。最后一列為文獻(xiàn)[4]中的攻擊時(shí)間復(fù)雜度。

以立方變量集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對(duì)應(yīng)的超級(jí)多項(xiàng)式pI的代數(shù)次數(shù)上界為14，下表3 給出了pI中t次單項(xiàng)式數(shù)量|Jt|的情況（t=0 至14）。

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

表3 t 次單項(xiàng)式數(shù)量

4 結(jié)語(yǔ)

立方攻擊是一種典型的對(duì)稱密碼算法分析方法。針對(duì)基于可分屬性的立方攻擊，提出了一種改進(jìn)的單項(xiàng)式枚舉算法，該算法相較于之前的算法，能夠?qū)⒏嗟牟淮嬖谟诔?jí)多項(xiàng)式中的單項(xiàng)式排除，從而導(dǎo)致新的攻擊所需要的時(shí)間復(fù)雜得到降低。針對(duì)初始化5 拍MORUS-640-128 算法的分析驗(yàn)證了新的攻擊方法的有效性。針對(duì)初始化6 拍MORUS-640-128 算法的攻擊所需要的時(shí)間復(fù)雜度較之前的分析結(jié)果更低。