對簡化版MORUS算法的改進(jìn)動態(tài)立方攻擊*

李俊志, 關(guān) 杰

(信息工程大學(xué),河南 鄭州 450001)

MORUS 算法[1]是2014 年由Wu 等人提出的認(rèn)證加密算法,該算法提交到了CAESAR 競賽[2]中,并經(jīng)過層層篩選進(jìn)入了競賽的第3 輪.MORUS 算法有MORUS-640-128 和MORUS-1280-256 兩個(gè)版本,前者的內(nèi)部狀態(tài)為640 比特,密鑰規(guī)模為128 比特;后者的內(nèi)部狀態(tài)1 280 比特,密鑰規(guī)模256 比特.本文分析的對象是MORUS-640-128-v1.MORUS 可以完成加密和認(rèn)證兩個(gè)方面的工作,其加密過程類似流密碼,將生成的密鑰流與明文進(jìn)行異或,認(rèn)證過程將消息注入到內(nèi)部狀態(tài)中參與運(yùn)算,生成或驗(yàn)證認(rèn)證碼.算法由循環(huán)移位、與和異或這3 種運(yùn)算組成,適用于硬件實(shí)現(xiàn)同時(shí)具有優(yōu)良的軟件實(shí)現(xiàn)效率.

MORUS 算法提出以后,由于其高效的軟硬件實(shí)現(xiàn)效率和簡潔的結(jié)構(gòu)受到人們的廣泛關(guān)注,但是由于其內(nèi)部狀態(tài)規(guī)模較大(640 比特),初始化迭代輪數(shù)較多(16 輪),并沒有出現(xiàn)比較好的分析結(jié)果.文獻(xiàn)[3]對初始化3 步的簡化版MORUS 算法進(jìn)行了區(qū)分攻擊和密鑰分割攻擊,其中,區(qū)分攻擊的復(fù)雜度可以忽略,密鑰分割攻擊的復(fù)雜度為O(2106.8).此外,作者利用差分自動推演方法給了對初始化4 步的簡化版MORUS 算法的差分-區(qū)分攻擊,所需數(shù)據(jù)量為O(2105).文獻(xiàn)[4]給出了對MORUS 算法在SAT 攻擊下的一些結(jié)果.文獻(xiàn)[5]給出了對4 輪MORUS算法的立方攻擊(cube attack).文獻(xiàn)[6]利用可分性的方法給出了對5 輪MORUS 算法的立方攻擊.

立方攻擊[7]是2009 年由Dinur 和Shamir 提出的,該分析方法將目標(biāo)算法看成黑盒多項(xiàng)式,沒有利用算法的結(jié)構(gòu)信息,可以用于分析內(nèi)部結(jié)構(gòu)未知的算法.目前,該方法已被應(yīng)用于分析序列密碼、分組密碼和雜湊函數(shù)等的安全性,對Trivium、Grain 等算法取得了較好的攻擊結(jié)果[8,9].動態(tài)立方攻擊(dynamic cube attack)[10]由Dinur和Shamir 在2011 年提出,它可以看成是立方攻擊的改進(jìn),其原理如下:猜測一部分和密鑰有關(guān)的信息,并根據(jù)算法在立方測試(cube test)中表現(xiàn)出來的不同性質(zhì)區(qū)分出正確的猜測值,從而恢復(fù)出密鑰信息.由于它利用了算法的結(jié)構(gòu)特點(diǎn),往往可以取得比單純立方攻擊更好的效果.動態(tài)立方攻擊在序列密碼、分組密碼和雜湊函數(shù)的分析中得到應(yīng)用,其中,對滿輪的Grain-128 的2118大小的密鑰子空間,可以低于窮舉攻擊215倍的復(fù)雜度恢復(fù)出所有密鑰[10],對雜湊函數(shù)Keccak 取得了目前最好的分析結(jié)果[11],在分析分組密碼KATAN32 和SIMON32 時(shí)也取得了較好的效果[12].

本文提出一種改進(jìn)的動態(tài)立方攻擊方法,優(yōu)化了動態(tài)立方攻擊的立方集合的選取規(guī)則,提出了優(yōu)先猜測關(guān)鍵值并恢復(fù)相應(yīng)的關(guān)鍵秘密信息的方法,據(jù)此給出了成功率更高的秘密信息恢復(fù)方法.利用該方法分析了初始化5 步的簡化版MORUS 算法,最終以O(shè)(295.05)的復(fù)雜度恢復(fù)所有128 比特密鑰,攻擊的成功率大于92%.

1 基礎(chǔ)知識

1.1 立方攻擊

立方攻擊目前已被應(yīng)用于分析序列密碼、分組密碼和雜湊函數(shù)等的安全性.立方攻擊是一種選擇明文攻擊(對于分組密碼)或選擇IV 攻擊(對于序列密碼),也是一種密鑰恢復(fù)攻擊,可以應(yīng)用于密碼算法的內(nèi)部結(jié)構(gòu)未知的條件下.

立方攻擊可以實(shí)施的條件是密碼算法的輸出比特可以表示成關(guān)于密鑰比特和明文比特(對于分組密碼)或IV 比特(對于序列密碼)的次數(shù)較低的多變量多項(xiàng)式,這個(gè)多項(xiàng)式稱為主多項(xiàng)式.

令p(x1,…,xn,v1…,vm)為主多項(xiàng)式在GF(2)上的代數(shù)正規(guī)型,其中,xi(1

其中,tI是只含有公開變量的單項(xiàng)式,tI中變量下標(biāo)的集合I(I?{1,2,…,n})稱為立方集合,pS(I)稱為I在p中的超級多項(xiàng)式(superpoly).在上述分解中,pS(I)中變量的下標(biāo)都不在立方集合I中,并且q中的任一單項(xiàng)式中都至少缺少下標(biāo)在I中的一個(gè)變量.

下面給出包含立方攻擊主要思想的定理.

定理1[7].如果主多項(xiàng)式有如下分解:

對密碼算法的立方攻擊可以分為預(yù)處理階段和在線攻擊階段兩個(gè)階段:在預(yù)處理階段,攻擊者需要找到合適的立方集合,然后尋找盡可能多的最大項(xiàng)和對應(yīng)的線性超級多項(xiàng)式,并將其組成方程組;在線攻擊階段,攻擊者求出預(yù)處理階段得到的線性超級多項(xiàng)式的值,并解方程組恢復(fù)密鑰.

1.2 立方測試

立方測試的原理也是通過公開變量的值來評估超級多項(xiàng)式,只不過它的目的不是恢復(fù)密鑰,而是通過立方測試將密碼算法和隨機(jī)函數(shù)區(qū)分開,或者是根據(jù)超級多項(xiàng)式的某些代數(shù)性質(zhì)檢測出它的非隨機(jī)性.一種常用的立方測試是平衡性測試,根據(jù)超級多項(xiàng)式的0,1 不平衡性,將其與隨機(jī)函數(shù)區(qū)分開.此外,其他有效的區(qū)分性質(zhì)包括低代數(shù)次數(shù)、線性變量和中性變量等.

1.3 動態(tài)立方攻擊

動態(tài)立方攻擊的原理如下:猜測一部分和密鑰有關(guān)的信息,并根據(jù)算法在立方測試中表現(xiàn)出來的不同性質(zhì)區(qū)分出正確的猜測值,從而恢復(fù)出密鑰信息.在文獻(xiàn)[10]中,作者給出了進(jìn)行動態(tài)立方攻擊的一般步驟,概括如下.

算法1.動態(tài)立方攻擊[10].

· Step 1.選擇需要消去(即使這個(gè)內(nèi)部狀態(tài)取0)的內(nèi)部狀態(tài)比特,并給出該內(nèi)部狀態(tài)比特取0 時(shí)動態(tài)變量的取值或條件;

· Step 2.選擇一個(gè)進(jìn)行立方測試時(shí)區(qū)分效果較好的立方集合,根據(jù)所選的立方集合確定需要猜測的秘密變量的表達(dá)式,以便在立方求和時(shí)可以計(jì)算動態(tài)變量的值;

· Step 3.對每個(gè)秘密變量可能的猜測值,將動態(tài)變量設(shè)置成合適的值,在Step 2 中得到的立方集合的階較大的立方子集上進(jìn)行立方求和,將針對不同立方子集對應(yīng)的立方和構(gòu)成一個(gè)集合,計(jì)算集合中元素取值的重量(其中取值為1 的元素個(gè)數(shù)),根據(jù)重量取值按照由小到大的順序進(jìn)行排序,得到一個(gè)由重量及相應(yīng)猜測值構(gòu)成的有序表;

· Step 4.根據(jù)Step3 中得到的有序表,給出秘密變量可能的候選值(一般選擇表中排序靠前的部分作為秘密變量的候選值),進(jìn)而求出部分或所有秘密變量的值.

其中:前兩步是離線階段,攻擊者具有控制密鑰的能力,其復(fù)雜度為預(yù)計(jì)算的復(fù)雜度;后兩步為在線階段,目的是恢復(fù)密鑰.

1.4 改進(jìn)的動態(tài)立方攻擊

我們在對動態(tài)立方攻擊研究時(shí)發(fā)現(xiàn),算法1 的Step 2 中,立方集合的選取規(guī)則和Step 4 中秘密變量的恢復(fù)方法可以進(jìn)行改進(jìn).我們嘗試優(yōu)化了動態(tài)立方攻擊的立方集合的選取規(guī)則,提出了優(yōu)先猜測關(guān)鍵值并恢復(fù)相應(yīng)的關(guān)鍵秘密信息的方法,據(jù)此提出了一種改進(jìn)的動態(tài)立方攻擊方法,從而提高了原始攻擊的成功率并降低了攻擊的復(fù)雜度.具體改進(jìn)如下.

觀察1.雖然算法1 的Step 2 中選取的立方集合對猜測值的區(qū)分效果較好,但是并不是它的所有階較大的立方子集的區(qū)分效果都很好,有些立方子集對正確和錯(cuò)誤猜測值求和的結(jié)果相差很小,如果將此立方子集列入統(tǒng)計(jì),則會對后面的排序結(jié)果造成干擾.

改進(jìn)1.為了避免這樣的干擾,我們不再選擇大的立方集合,而是直接測試較小的立方集合對猜測值的區(qū)分能力,從中選取所需的區(qū)分能力強(qiáng)的立方集合,進(jìn)而為下一步恢復(fù)秘密信息提供了攻擊基礎(chǔ).

觀察2.當(dāng)需要猜測的表達(dá)式的個(gè)數(shù)較小時(shí),通過對求和表排序得到正確猜測值的方法成功率較低,有時(shí)正確猜測值的排序甚至在表的后半部分中,此時(shí)以可接受的成功率得到正確秘密信息的計(jì)算復(fù)雜度將近似窮舉攻擊.研究發(fā)現(xiàn):當(dāng)選擇合適的立方集合后,待猜測值組成的集合中存在著某些關(guān)鍵猜測值,在固定其他猜測值的情況下,關(guān)鍵猜測值取值正確時(shí)對應(yīng)立方和為0 的概率往往比關(guān)鍵猜測值錯(cuò)誤時(shí)對應(yīng)立方和為0 的概率高,可據(jù)此恢復(fù)關(guān)鍵猜測值.

改進(jìn)2.根據(jù)內(nèi)部狀態(tài)的表達(dá)式選定關(guān)鍵猜測值,離線階段選定合適的立方集合;在線階段,窮舉猜測值進(jìn)行立方求和后,得到一個(gè)由重量及相應(yīng)猜測值構(gòu)成的表,我們按照關(guān)鍵猜測值的取值將表進(jìn)行分類(t個(gè)關(guān)鍵猜測值則分為2t類),將每類表中所有的重量相加,對應(yīng)重量和最小的猜測值即為正確的關(guān)鍵猜測值.

以下我們對5 輪簡化版MORUS 算法進(jìn)行了改進(jìn)的動態(tài)立方攻擊,通過實(shí)驗(yàn)驗(yàn)證,改進(jìn)的方法可以提高正確恢復(fù)關(guān)鍵猜測值的成功率.

2 MORUS 算法

MORUS 算法分為初始化、關(guān)聯(lián)數(shù)據(jù)處理、加密、認(rèn)證碼生成和解密與驗(yàn)證這5 個(gè)階段.由于本文的攻擊條件將關(guān)聯(lián)數(shù)據(jù)設(shè)置為0,只涉及初始化階段和加密階段,下面只對算法的這兩個(gè)階段進(jìn)行描述,詳細(xì)的算法請參考設(shè)計(jì)報(bào)告.

2.1 符號說明

·Si:第i步的內(nèi)部狀態(tài),0≤i≤16;

·:第i步更新第k輪的內(nèi)部狀態(tài),0≤k≤4;

·:第i步第k輪內(nèi)部狀態(tài)的第l塊128 比特分組,0≤l≤4;

·:第i步第k輪內(nèi)部狀態(tài)第l塊分組的第j比特,0≤j≤127;

·Rotl(x,n):將128 比特長的x分成4 塊32 比特字,每塊循環(huán)左移n比特;

· 0n:n長全0 比特串;

· 1n:n長全1 比特串;

· (·)4:16 進(jìn)制表示;

·const0:128 比特常數(shù)(000101020305080d1522375990e97962)4;

·const1:128 比特常數(shù)(db3d18556dc22ff12011314273b528dd)4.

2.2 MORUS算法的狀態(tài)更新函數(shù)

MORUS 算法的狀態(tài)更新函數(shù)為Si+1=StateUpdate(Si,mi),算法初始化過程共有16 步這樣的更新函數(shù),每步更新函數(shù)包含5 輪相似的更新過程,具體過程如下.

·Si+1更新:Fork=0 to 4,

狀態(tài)更新函數(shù)如圖1 所示.

Fig.1 Update function of MORUS圖1 MORUS 算法的狀態(tài)更新函數(shù)

2.3 MORUS算法的初始化階段

MORUS 的初始化階段包括將密鑰K和初始向量IV 注入到內(nèi)部狀態(tài)中,并運(yùn)行16 步狀態(tài)更新函數(shù).密鑰和IV 的加載方式如下:

2.4 MORUS算法的加密階段

在算法的加密階段,128 比特的明文Pi與密鑰流進(jìn)行異或運(yùn)算得到密文Ci,設(shè)明文消息的長度為msglen,令:

3 對5 步MORUS 算法的改進(jìn)動態(tài)立方攻擊

動態(tài)立方攻擊的過程可以分為離線階段和在線階段:離線階段主要是收集必要的信息,為恢復(fù)秘密信息做準(zhǔn)備;在線階段的主要目的是恢復(fù)密鑰.下面對簡化版MORUS 算法的動態(tài)立方攻擊按照這兩個(gè)階段進(jìn)行說明.

由于MORUS 算法密鑰流每次輸出128 比特,相當(dāng)于128 個(gè)關(guān)于密鑰和IV 的多項(xiàng)式,在進(jìn)行立方測試時(shí),可以分別利用每個(gè)比特的信息.下面我們以第0 比特為例進(jìn)行分析,其他比特的分析類似.

3.1 離線攻擊階段

· 步驟1:尋找合適的表達(dá)式化簡方法.

尋找動態(tài)IV、需要窮舉的秘密信息、關(guān)鍵猜測值和對應(yīng)的立方集合中的必選IV 集合,使得動態(tài)IV 滿足動態(tài)立方攻擊條件時(shí)能夠以合適的方式化簡表達(dá)式.

輸出密鑰流的第0 比特為:

故當(dāng)s-3,314=0 且s-3,186⊕s-3,570=0 時(shí),有s-2,251=0.

分別將s-3,314和s-3,186⊕s-3,570表示成關(guān)于密鑰和IV 的表達(dá)式.

將s-3,314和s-3,186⊕s-3,570簡單表示成如下形式:

·s-3,314=v82⊕F1=v82⊕v127·(v111⊕F4)⊕F3;

·s-3,186⊕s-3,570=v97⊕F2.

其中,F1和F2是關(guān)于密鑰和IV 的多項(xiàng)式;而v82只出現(xiàn)在s-3,314的一次項(xiàng)中,且在s-3,186⊕s-3,570中不出現(xiàn);v97只出現(xiàn)在s-3,186⊕s-3,570的一次項(xiàng)中,且在s-3,314中不出現(xiàn);v127和v111均不包含在F3和F4中.

當(dāng)v111=F4,v82=F3,v92=F2時(shí),s-2,251恒為0.根據(jù)觀察2 我們發(fā)現(xiàn):若選取的立方集合能夠以較大概率將s-2,251是否為0 區(qū)分開,則能以較大概率判斷出v111=F4,進(jìn)而根據(jù)v111的取值恢復(fù)出F4.這樣,我們令v111為關(guān)鍵猜測值,F4為關(guān)鍵秘密信息,對應(yīng)的v127為必選IV,同時(shí)將v82和v97列為動態(tài)變量.

需要說明的是:上述化簡方式并不唯一,還可以找到其他的關(guān)鍵猜測值及其對應(yīng)的秘密信息,為攻擊者提供更多的信息.

· 步驟2:尋找合適的立方集合.

此步需要根據(jù)步驟1 中確定的表達(dá)式化簡方法和必選IV 集合,尋找滿足區(qū)分條件的足夠數(shù)量的立方集合.

在對初始化5 步的MORUS 算法進(jìn)行立方測試的過程中我們發(fā)現(xiàn):當(dāng)立方集合大小為9 時(shí),輸出比特的立方和存在明顯的0/1 不平衡性,而且可以保證在可接受的時(shí)間內(nèi)找到足夠數(shù)量符合條件的立方集合,我們將立方階定為9.

立方集合中包含必選IV 和候選IV,其中必選IV 是由步驟1 中關(guān)鍵秘密因素確定的.為了降低復(fù)雜度,候選IV 則從s-3,314和s-3,186⊕s-3,570的表達(dá)式中均不包含的IV 集合中選取,這樣可使需要窮舉的秘密信息盡可能少.經(jīng)統(tǒng)計(jì)可知,s-3,314和s-3,186⊕s-3,570中一共包含了88 個(gè)IV 比特,未包含40 個(gè)IV 比特的序號集合如下:

T={1,3,15,17,18,22,27,28,34,35,40,41,42,47,54,55,56,60,64,65,66,67,73,74,75,79,80,83,93,105,112,113,114,116,117,120,122,123,124,126}.

在立方測試時(shí),為了檢測s-2,251是否為0 時(shí)立方測試時(shí)表現(xiàn)出的差別,在離線階段則賦予攻擊者額外的能力,可以在立方求和時(shí)強(qiáng)制將s-2,251設(shè)置為0.

算法2.尋找MORUS 算法的立方集合.

輸入:立方階d,候選IV 集合A,必選IV 集合B,區(qū)分度δ,立方集合目標(biāo)個(gè)數(shù)n;

輸出:候選立方集合.

初始化:C=?

· Step 1.從A中任選d-|B|個(gè)IV,與B組成立方集合C′;

· Step 2.隨機(jī)選取m組密鑰,遍歷立方集合C′,其他IV 設(shè)置為0,運(yùn)行立方測試算法,在算法運(yùn)行中強(qiáng)制將s-2,251設(shè)置為0,對輸出結(jié)果求和,結(jié)果為sumc;

· Step 3.隨機(jī)選取m組密鑰,遍歷立方集合C′,其他IV 設(shè)置為0,運(yùn)行立方測試算法,對輸出結(jié)果求和,結(jié)果為;

· Step 5.如果|C|=n,或Step 1 中已將A遍歷,則輸出C并終止算法;否則返回Step 1,重新尋找立方集合.如例1,設(shè)置候選IV 集合A={vi|i∈T},必選IV 集合B={v127},n=400,m=1000,δ=0.05.運(yùn)行算法2,找到其中一個(gè)立方集合C′={v3,v18,v27,v42,v65,v73,v114,v126,v127},隨機(jī)選取1 000 組密鑰,分別執(zhí)行Step 2 和Step 3 時(shí)得到:,差值129>50,這個(gè)立方集合將具有較好的區(qū)分效果.

與算法1 中的立方集合選取方式進(jìn)行對比,我們的改進(jìn)在于增加了區(qū)分度的判決篩選過程:1000·δ.如果立方集合不滿足此篩選條件,在線階段使用此立方集合則會對恢復(fù)秘密信息造成干擾,降低成功率.

我們搜索了關(guān)于輸出密鑰流前32 比特的立方集合及其對應(yīng)的秘密信息(具體如表1 所示).本文的實(shí)驗(yàn)環(huán)境為Intel i5,3.2GHzCPU,4GB 內(nèi)存,Windows7 32 位操作系統(tǒng),對表中每個(gè)關(guān)鍵猜測值和必選IV,搜索到足夠數(shù)量的立方集合所需時(shí)間為幾十分鐘到幾天不等.需要指出的是:對其他的96 個(gè)密鑰流輸出比特進(jìn)行考察將得到更多此類信息,能夠進(jìn)一步降低攻擊復(fù)雜度.

Table 1 Dynamic cube attack key information of MORUS reduced to 5 rounds表1 5 步簡化版MORUS 算法動態(tài)立方的重要信息

3.2 在線攻擊階段

· 步驟3:恢復(fù)MORUS 算法的秘密信息

本步驟是在線攻擊階段,此時(shí)密鑰固定,主要目的是利用上一步中得到的秘密信息及其對應(yīng)的立方集合,恢復(fù)其中的關(guān)鍵秘密信息,進(jìn)而恢復(fù)部分(或全部)密鑰.

算法3.恢復(fù)MORUS 算法的關(guān)鍵秘密信息.

輸入:秘密信息及其立方集合、關(guān)鍵秘密信息c;

輸出:c的值.

初始化:令sum0=0,sum1=0.

· Step 1.將關(guān)鍵猜測值設(shè)置為0,窮舉剩下需要猜測的秘密信息,對每個(gè)猜測值,設(shè)置相應(yīng)的動態(tài)IV 取值,運(yùn)行立方測試算法,將輸出結(jié)果加到sum0上;

· Step 2.將關(guān)鍵猜測值設(shè)置為1,窮舉剩下需要猜測的秘密信息,對每個(gè)猜測值,設(shè)置相應(yīng)的動態(tài)IV 取值,運(yùn)行立方測試算法,并將求和的結(jié)果加到sum1上;

· Step 3.若sum0

利用算法3 可以恢復(fù)關(guān)鍵秘密信息,關(guān)鍵秘密信息一般是一個(gè)非線性表達(dá)式,對于一些特殊的非線性表達(dá)式,我們可采取執(zhí)行下述操作從中直接恢復(fù)某些ki的信息:

當(dāng)這個(gè)表達(dá)式中存在密鑰比特ki與IV 比特vj的乘積項(xiàng)kivj時(shí),且vj在表達(dá)式其他部分中不出現(xiàn)時(shí),可分別令vj=0 或1,執(zhí)行算法3,并對兩次求得的關(guān)鍵秘密信息做模2 和,結(jié)果即為ki.

如例1,利用算法3 中的方法恢復(fù)關(guān)鍵秘密信息F4時(shí),隨機(jī)選取了100 組密鑰,實(shí)驗(yàn)所得恢復(fù)的F4與真實(shí)值相等的概率為ps=90%.由于F4的表達(dá)式中含有項(xiàng)v2(k11⊕1),可以按照上述方法,通過改變v2的值直接求出k11的值.表1 中列出了恢復(fù)關(guān)鍵秘密信息的成功率ps和利用該秘密信息能夠直接求出的密鑰比特.為了對比,我們使用算法1 中恢復(fù)秘密信息的方法,實(shí)驗(yàn)發(fā)現(xiàn)成功率約為65%,遠(yuǎn)小于本文恢復(fù)關(guān)鍵秘密信息的成功率.

由表1 可知,表中標(biāo)*的項(xiàng)共23 個(gè),運(yùn)行算法3,可求出23 個(gè)關(guān)鍵秘密信息.其中,能夠直接求出16 個(gè)密鑰比特和12 個(gè)關(guān)于密鑰的線性方程,共28 比特密鑰信息.下面給出恢復(fù)所有密鑰的方法.

算法4.恢復(fù)簡化版MORUS 算法所有密鑰.

· Step 1.對表1 中23 個(gè)關(guān)鍵秘密信息,運(yùn)行算法3,可求出23 個(gè)關(guān)鍵秘密信息的值;

· Step 2.對表1 中28 個(gè)密鑰信息,改變相應(yīng)的IV 比特,運(yùn)行算法3,求出28 個(gè)關(guān)鍵秘密信息的值;

· Step 3.對于上述51 個(gè)關(guān)鍵秘密信息,窮舉其中錯(cuò)誤值小于5 的所有情況,對每一種情況,修正相應(yīng)的關(guān)鍵猜測值,求出16 個(gè)密鑰比特和12 個(gè)關(guān)于密鑰的線性方程,并得到修正的23 個(gè)關(guān)于密鑰的方程;

· Step 4.窮舉剩余112 個(gè)密鑰比特:

? Step 4-1.代入12 個(gè)關(guān)于密鑰的線性方程和23 個(gè)非線性方程進(jìn)行驗(yàn)證:若出現(xiàn)矛盾,則返回Step 3 中窮舉下一個(gè)錯(cuò)誤情況;否則,將此密鑰代入MORUS 算法進(jìn)行進(jìn)一步檢驗(yàn);

? Step4-2.若通過檢驗(yàn),則輸出此密鑰為正確密鑰,算法終止;否則,返回Step 3 中窮舉下一個(gè)錯(cuò)誤情況.

為保證攻擊的成功率,算法4 中采用了試錯(cuò)與窮舉相結(jié)合的方法.Step 1 和Step 2 的復(fù)雜度為(23+28)×400×23×29≈226.32,Step 3 中窮舉所有錯(cuò)誤情況的復(fù)雜度為,Step 4 中密鑰能夠通過每個(gè)線性方程的概率為1/2,而經(jīng)驗(yàn)證,這23 個(gè)非線性式子每個(gè)等于0 的概率均為1/2,且近似兩兩獨(dú)立,可以認(rèn)為密鑰通過這23 個(gè)非線性方程中每個(gè)的概率均為1/2.因此,密鑰通過第1 層檢驗(yàn)的概率為1/235,故恢復(fù)所有128 比特密鑰的計(jì)算復(fù)雜度為O(226.32+218.05×2112-35)≈O(295.05).攻擊的數(shù)據(jù)復(fù)雜度為O(226.32).在計(jì)算成功率時(shí),為簡化計(jì)算,將恢復(fù)單個(gè)關(guān)鍵秘密信息的成功率ps均假設(shè)為最低值96%(實(shí)際的成功率應(yīng)大于計(jì)算值),此時(shí),51 個(gè)值中正確的個(gè)數(shù)x服從二項(xiàng)分布B(51,0.96),近似服從正態(tài)分布N(48.96,1.96),則p(x≥47)≈0.92.因此,算法4 恢復(fù)所有密鑰的成功率大于92%.表2 給出了現(xiàn)有不同攻擊方法的結(jié)果的比較.

Table 2 Results of attacks on MORUS表2 對MORUS 算法的攻擊結(jié)果對比

從攻擊結(jié)果的對比可以發(fā)現(xiàn):目前本文給出的改進(jìn)的動態(tài)立方攻擊是對MORUS-640-128 算法輪數(shù)最多的恢復(fù)密鑰攻擊之一,并且本文的攻擊相比文獻(xiàn)[6]的結(jié)果在計(jì)算復(fù)雜度方面有較大優(yōu)勢.可見,動態(tài)立方攻擊對此類算法是一種比較有效的攻擊方法.另外,文獻(xiàn)[4]中利用SAT 求解器恢復(fù)內(nèi)部狀態(tài)攻擊的計(jì)算復(fù)雜度大大高于窮舉攻擊,僅對該算法抵抗基于SAT 的代數(shù)攻擊能力給出了一個(gè)參考.

4 總結(jié)

MORUS 算法的內(nèi)部狀態(tài)更新函數(shù)與傳統(tǒng)的基于移位寄存器的序列密碼有明顯區(qū)別,基于移存器的序列密碼每次只更新幾個(gè)比特,而MORUS 算法每次更新128 比特,導(dǎo)致其內(nèi)部狀態(tài)各比特的代數(shù)表達(dá)式復(fù)雜程度接近,給動態(tài)立方攻擊帶來了一定的困難.本文改進(jìn)了動態(tài)立方攻擊方法,優(yōu)化了立方子集合的選取規(guī)則,給出了新的秘密信息恢復(fù)方法.對初始化5 輪的MORUS 算法進(jìn)行了動態(tài)立方攻擊,最終以O(shè)(295.05)的復(fù)雜度恢復(fù)了所有128 比特密鑰.結(jié)果表明:動態(tài)立方攻擊針對MORUS 算法的攻擊效果很好,并且有進(jìn)一步提升的空間.下一步擬將改進(jìn)的動態(tài)立方攻擊應(yīng)用于分析其他算法.