王 超，陳懷鳳

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

0 概述

為了驗(yàn)證Midori 算法［1］的安全性，研究人員對(duì)Midori 算法進(jìn)行了許多密碼分析。文獻(xiàn)［2］提出對(duì)Midori64 算法的14 輪相關(guān)密鑰不可能差分分析，共猜測(cè)了84 bit 密鑰。文獻(xiàn)［3］提出對(duì)Midori64 算法的12 輪中間相遇攻擊，該攻擊的時(shí)間復(fù)雜度為2125.5次12 輪加密，數(shù)據(jù)復(fù)雜度為255.5個(gè)64 bit 分組。文獻(xiàn)［4］提出對(duì)Midori64 算法的11 輪不可能差分分析，該攻擊的時(shí)間復(fù)雜度為2121.6次11 輪加密，數(shù)據(jù)復(fù)雜度為262.3個(gè)64 bit 分組。文獻(xiàn)［5］對(duì)文獻(xiàn)［4］的不可能差分分析進(jìn)行優(yōu)化，時(shí)間復(fù)雜度為2121.42次11 輪加密，數(shù)據(jù)復(fù)雜度為260.82個(gè)64 bit 分組。文獻(xiàn)［6］提出對(duì)Midori64 算法的10 輪多維零相關(guān)線性分析，其時(shí)間復(fù)雜度為279.35次10 輪加密，數(shù)據(jù)復(fù)雜度為262.4個(gè)64 bit 分組。文獻(xiàn)［7］提出對(duì)Midori64 算法的8 輪積分分析，其時(shí)間復(fù)雜度為265次8 輪加密，數(shù)據(jù)復(fù)雜度為219.80個(gè)64 bit 分組。文獻(xiàn)［8-9］分別提出對(duì)Midori64 算法的不變子空間攻擊和非線性不變量攻擊，并給出了算法的全輪弱密鑰攻擊。

文獻(xiàn)［10］建立零相關(guān)區(qū)分器與積分區(qū)分器之間的等價(jià)關(guān)系［11-12］，證明從零相關(guān)路線(a1，0)，b=(b1，0)，a1≠0，b1≠0 可以直接推導(dǎo)出一條積分路線，其中，輸入掩碼部分值a1與輸出掩碼部分值b1相互獨(dú)立。利用該性質(zhì)，可以借助已找到的零相關(guān)線性路線構(gòu)造更優(yōu)的積分路線。為了消除零相關(guān)路線向積分路線轉(zhuǎn)化的條件限制，文獻(xiàn)［13］提出一種新方法，無(wú)論a1和b1是否獨(dú)立，都可以將零相關(guān)路線轉(zhuǎn)為積分路線。分離特性（Division Property）［14］是一種新型積分路線搜索方法，該方法充分考慮非線性組件的代數(shù)次數(shù)，對(duì)積分性質(zhì)的刻畫更加精細(xì)。此后，基于混合整數(shù)線性規(guī)劃MILP 技術(shù)的分離特性搜索方法也相繼被提出，且文獻(xiàn)［15］利用該方法構(gòu)造了7 輪積分路線。

本文對(duì)Midori64 算法的積分攻擊問(wèn)題進(jìn)行研究，給出算法的6 輪零相關(guān)區(qū)分器，得到相應(yīng)的6 輪積分區(qū)分器，向前擴(kuò)展1 輪得到7 輪積分區(qū)分器，在此基礎(chǔ)上，分別研究針對(duì)10 輪、11 輪Midori64 算法的積分攻擊。

1 預(yù)備知識(shí)

1.1 符號(hào)說(shuō)明

本文的符號(hào)說(shuō)明如下：⊕表示按位異或，∥表示字符串級(jí)聯(lián)，?表示函數(shù)復(fù)合，F(xiàn)n2表示F2上的n維向量空間，+表示有限域內(nèi)的模加運(yùn)算，LSB 表示最低有效位，Kji表示第j輪等價(jià)輪密鑰的第i個(gè)單元，U 表示單元性質(zhì)不可知，Z 表示單元具有零和性。

1.2 Midori64 算法描述

Midori算法于2015年由BANIK 等人在ASIACRYPT會(huì)議上提出［1］，其采用SPN(Substitution Permutation Network)結(jié)構(gòu)，具有低功耗的特點(diǎn)，是一種輕量級(jí)分組密碼算法。Midori 算法的密鑰長(zhǎng)度為128 bit，分組長(zhǎng)度為64 bit 或128 bit，相應(yīng)的迭代輪數(shù)為16 輪或20 輪，分別記作Midori64 和Midori128。Midori64算法的明文分組長(zhǎng)度為64 bit，每個(gè)明文分組被分成16 個(gè)4 bit，矩陣表示如下：

其中，Si(i=0，1，…，15)表示單元(Cell)。式（1）又稱狀態(tài)矩陣。

Midori64 算法輪變換作用在狀態(tài)矩陣上，由S 盒(SubCell，簡(jiǎn)記為SB)、置換(ShuffleCell，簡(jiǎn)記為SC)、列混淆(MixColumn，簡(jiǎn)記為MC)和密鑰加(KeyAdd，簡(jiǎn)記為KA)復(fù)合組成。

1.2.1 密鑰編排算法

Midori64 算法的密鑰長(zhǎng)度為128 bit，將密鑰的高64 bit 記為Key0，低64 bit 記為Key1。定義白化密鑰WK=Key0⊕Key1，輪密鑰 RKi=Keyimod2⊕qi(i=0，1，…，14)，其中，qi為4×4 矩陣形式的輪密鑰常數(shù)，其定義參考文獻(xiàn)［1］。將Key0與Key1以4×4 矩陣形式表示，qi按位異或在每個(gè)4 bit 單元的LSB 位。

1.2.2 S 盒

Midori64 算法使用的非線性S 盒取值如表1 所示，S 盒具有對(duì)合性質(zhì)，即SB-1=SB。

表1 Midori64 算法的S 盒Table 1 S-box of Midori64

1.2.3 置換

重新排列狀態(tài)矩陣中16 個(gè)單元的位置稱為置換，置換及逆置換分別如式（2）和式（3）所示：

1.2.4 列混淆

以almost MDS［1］矩陣M左乘更新?tīng)顟B(tài)矩陣稱為列混淆，如式（4）所示，其中，矩陣M如式（5）所示，矩陣M滿足M-1=M。

1.2.5 密鑰加

Midori64 算法在加密過(guò)程中使用64 bit 白化密鑰WK 和輪密鑰RKi(i=0，1，…，14)對(duì)狀態(tài)矩陣進(jìn)行異或更新。

Midori64 算法在解密過(guò)程中使用64 bit 白化密鑰WK 和SC-1(MC(RKi))(i=14，13，…，0)對(duì)狀態(tài)矩陣進(jìn)行異或更新。

1.2.6 加密流程

Midori64 算法的加密流程如圖1 所示，在第1 輪之前添加使用白化密鑰的密鑰加，第1 輪～第15 輪使用輪密鑰RKi(i=0，1，…，14)進(jìn)行密鑰加，第16 輪使用白化密鑰進(jìn)行密鑰加。

圖1 Midori64 算法的加密流程Fig.1 The encryption procedure of Midori64

1.2.7 解密流程

Midori64 算法的解密流程如圖2 所示，在第1 輪之前添加使用白化密鑰的密鑰加，第1 輪～第15 輪使用SC-1(MC(RKi))(i=14，13，…，0)進(jìn)行密鑰加，第16輪使用白化密鑰進(jìn)行密鑰加。

圖2 Midori64 算法的解密流程Fig.2 The decryption procedure of Midori64

2 Midori64 的6 輪零相關(guān)區(qū)分器

零相關(guān)線性分析由BOGDANOV 和RIJMEN［16］于2012 年提出，攻擊使用分組密碼算法中以概率成立的線性逼近，即相關(guān)度為零的線性逼近，由此區(qū)分分組密碼算法與隨機(jī)置換，進(jìn)而恢復(fù)密鑰。文獻(xiàn)［17］建立了多重零相關(guān)分析模型，其克服了經(jīng)典零相關(guān)線性分析在數(shù)據(jù)復(fù)雜度方面的缺陷。文獻(xiàn)［18］建立了卡方多維零相關(guān)線性模型，其消除了對(duì)零相關(guān)數(shù)量的限制條件。

函數(shù)h：上線性逼近(α，β)的相關(guān)度定義為：

其中，α為輸入掩碼，β為輸出掩碼，·表示向量?jī)?nèi)積。當(dāng)Ch(α，β)=0 時(shí)，稱(α，β)為零相關(guān)線性逼近［17］。

命題1（線性映射的相關(guān)度）［17］對(duì)于線性映射h(x)=Mx，若α=MTβ，則Ch(α，β)=1；否則，Ch(α，β)=0。

零相關(guān)區(qū)分器是指在輸入掩碼與輸出掩碼作用下，目標(biāo)輸入與輸出比特的線性相關(guān)度為0 的一類線性區(qū)分器。根據(jù)命題1 進(jìn)行自動(dòng)化搜索，可以得到大量Midori64 算法的5 輪零相關(guān)區(qū)分器，按輸入掩碼權(quán)重與輸出掩碼權(quán)重進(jìn)行分類，零相關(guān)區(qū)分器的個(gè)數(shù)統(tǒng)計(jì)結(jié)果如表2 所示。

表2 Midori64 算法的5 輪零相關(guān)區(qū)分器個(gè)數(shù)統(tǒng)計(jì)Table 2 Number statistics of Midori64 5-round zero-correlation discriminator

取3 個(gè)輸入掩碼權(quán)重為7 且輸出掩碼權(quán)重為1的5 輪零相關(guān)區(qū)分器，然后對(duì)輸出掩碼部分繼續(xù)擴(kuò)展1 輪，得到6 輪零相關(guān)區(qū)分器。令：

其中，a0、a3、a4、a6、a8、a9、a12、d0、d5、d15均為4 bit 向量，0 為4 bit 零向量。和都是Midori64 算法的6 輪零相關(guān)區(qū)分器。第1 個(gè)6 輪零相關(guān)區(qū)分器的掩碼擴(kuò)展細(xì)節(jié)如圖3所示。

圖3 Midori64 算法的6 輪零相關(guān)區(qū)分器Fig.3 6-round zero-correlation discriminator of Midori64

3 Midori64 的積分區(qū)分器

3.1 積分區(qū)分器構(gòu)造

積分攻擊是一種選擇明文攻擊，最先應(yīng)用于Square 分組密碼分析，其基本思想是通過(guò)分析一系列中間狀態(tài)的和具有概率為1 的性質(zhì)，得出不能通過(guò)檢測(cè)的密鑰都是錯(cuò)誤密鑰，從而利用淘汰法直接恢復(fù)出正確密鑰。積分攻擊的主要環(huán)節(jié)是尋找積分區(qū)分器，積分區(qū)分器可以分為如下2 類：

1）一系列中間狀態(tài)的和遍歷所有可能取值，且每個(gè)可能取值的出現(xiàn)次數(shù)相同，該類積分區(qū)分器稱為平衡積分區(qū)分器。

2）一系列中間狀態(tài)的異或和為零，該類積分區(qū)分器稱為零和積分區(qū)分器。

當(dāng)選擇特定的輸入集合（輸入的部分比特固定為常數(shù)，其余比特遍歷所有可能）時(shí)，經(jīng)過(guò)幾輪算法加密后，輸出的某些比特存在概率為1 的分布特性，輸出目標(biāo)值異或和為0 時(shí)，為零和積分區(qū)分器；輸出目標(biāo)值均勻遍歷所有可能時(shí)，為平衡積分區(qū)分器。實(shí)際上，平衡積分區(qū)分器與零相關(guān)區(qū)分器之間存在一定的等價(jià)關(guān)系［10］，任意的零相關(guān)區(qū)分器都可以轉(zhuǎn)化成一個(gè)平衡積分區(qū)分器，本文利用文獻(xiàn)［10］中給出的兩區(qū)分器等價(jià)性進(jìn)行積分區(qū)分器構(gòu)造。

若所有原像集的勢(shì)都相同，則函數(shù)h：是平衡的［10］，即集合的大小與y無(wú)關(guān)。

命題2［10］對(duì)于函數(shù)h：，定義Tλ：Fs2→Ft2，Tλ(y)=h1(λ，y)。若?a∈，b≠0 且a與b獨(dú)立，則函數(shù)h上線性特征（a‖0，b‖0）的相關(guān)度為0 等價(jià)于，函數(shù)Tλ是平衡的。

3.2 Midori64 的6 輪積分區(qū)分器

記集合Sin={x=(c0，b1，b2，c3，c4，b5，c6，b7，c8，c9，b10，b11，c12，b13，b14，b15)}，其中，c0‖c3‖c4‖c6‖c8‖c9‖c12取常數(shù)，b1‖b2‖b5‖b7‖b10‖b11‖b13‖b14‖b15遍歷所有可能取值。Sin中存在236個(gè)元素，存在228個(gè)此類集合。經(jīng)過(guò)6 輪加密后，得到對(duì)應(yīng)的輸出集合為Sout=。

令t0=y1⊕y2⊕y3、t1=y0⊕y1⊕y3和t2=y0⊕y1⊕y2，則加密函數(shù)被分割為：

定理1當(dāng)輸入為Sin時(shí)，加密6輪后，y1是零和的。

證明加密函數(shù)上線性特征(α1，β1)、(α1，β2)和(α1，β3) 的相關(guān)度都是0，由命題2 可知Tλ：是平衡的，得到t0、t1和t2每個(gè)取值的原像個(gè)數(shù)相同，于是∑t0=0，∑t1=0，∑t2=0，從而∑y1=∑t0⊕∑t1⊕∑t2=0，證畢。

6 輪零和積分區(qū)分器如圖4 所示。

圖4 Midori64 算法的6 輪零和積分區(qū)分器Fig.4 6-round zero-sum integral discriminator of Midori64

3.3 Midori64 的7 輪積分區(qū)分器

在6 輪積分區(qū)分器的前面解密1 輪可以得到7 輪積分區(qū)分器。對(duì)6 輪積分區(qū)分器的輸入Sin中各單元進(jìn)行逆向輪密鑰異或操作，其中，第0 個(gè)、第3 個(gè)、第4 個(gè)、第6 個(gè)、第8 個(gè)、第9 個(gè)和第12 個(gè)單元是固定常數(shù)，其余單元仍然遍歷所有可能取值。因此，在構(gòu)造7 輪積分區(qū)分器的過(guò)程中，可忽略此逆向密鑰加操作。記7 輪積分區(qū)分器的明文集合為：

其中，列混淆、置換和S 盒都是可逆變換，復(fù)合變換y=SB-1(SC-1(MC-1(x)))是雙射。對(duì)由236個(gè)明文構(gòu)成的進(jìn)行1 輪加密，其結(jié)果滿足6 輪零和積分區(qū)分器的輸入條件，因此，當(dāng)輸入為時(shí)，加密7 輪后y1是零和的。存在一系列7 輪積分路線，令(c0，b1，b2，c3，c4，b5，c6，b7，b8，b9，c10，c11，c12，b13，c14，c15)}。的定義與類似，當(dāng)輸入為時(shí)，加密7 輪后y13是零和的。

4 Midori64 的積分攻擊

4.1 Midori64 的10 輪積分攻擊

在7 輪積分區(qū)分器的后面加密3 輪可以得到10 輪積分區(qū)分器，如圖5 所示。

圖5 Midori64 算法的10 輪密鑰恢復(fù)攻擊Fig.5 10-round key recovery attack of Midori64

為降低密鑰的猜測(cè)量，本文利用等價(jià)密鑰技術(shù)［19］，該技術(shù)結(jié)合Midori64 算法，將列混淆MC 與密鑰加KA 進(jìn)行位置交換，其中，線性等價(jià)的輪密鑰加記為KA*，從而在攻擊中減少密鑰的猜測(cè)量。具體地，將圖5 中Sout[1]標(biāo)注為Z[1]，以*標(biāo)注每個(gè)從計(jì)算至Z[1]時(shí)需要明確值的單元。設(shè)輪密鑰經(jīng)過(guò)線性變換后的等價(jià)輪密鑰為Ki，即Ki=MC(RKi)。

利用部分和技術(shù)［17］，Midori64 算法的128 bit 密鑰恢復(fù)過(guò)程具體如下：

步驟7使用2 組明密文對(duì)進(jìn)行剩余正確密鑰的窮搜猜測(cè)。

4.1.1 數(shù)據(jù)復(fù)雜度分析

為了平衡總時(shí)間復(fù)雜度與數(shù)據(jù)復(fù)雜度，取m=12，n=4。10 輪積分攻擊的數(shù)據(jù)復(fù)雜度為236×12+236×4=240個(gè)64 bit 長(zhǎng)明密文對(duì)。

4.1.2 時(shí)間復(fù)雜度分析

10 輪積分攻擊的步驟1 復(fù)雜度為選擇明文的復(fù)雜度，計(jì)算時(shí)，需要查SB-1表共236次，由于10 輪算法共查表16×10 次，因此，在忽略其他運(yùn)算耗時(shí)的假設(shè)下，相當(dāng)于236/(16×10)≈228.68次10 輪加密。收集S*out時(shí)進(jìn)行236次10 輪加密。步驟2 進(jìn)行9×236×236次查表，相當(dāng)于9×236×236/(16×10)≈267.85次10 輪加密。步驟3 進(jìn)行3×236×212×212次查表，相當(dāng)于3×236×212×212/(16×10)≈254.26次10 輪加密。步驟4 進(jìn)行236×212×24次查表，相當(dāng)于236×212×24/(16×10)≈244.68次10 輪加密。步驟5 與步驟6 的時(shí)間復(fù)雜度可以忽略。步驟7 進(jìn)行窮搜驗(yàn)證時(shí)，需要265+3 次10 輪加密。

綜上，10 輪積分攻擊的總時(shí)間復(fù)雜度為228.68+236+267.85+254.26+244.68+265+3≈267.85次10 輪加密。

4.2 Midori64 的11 輪積分攻擊

利用快速Walsh-Hadamard 變換技術(shù)［20-21］對(duì)Midori64 進(jìn)行11 輪積分攻擊，具體步驟如下：

步驟6由上述恢復(fù)的等價(jià)輪密鑰計(jì)算密鑰。

4.2.1 數(shù)據(jù)復(fù)雜度分析

為了平衡總時(shí)間復(fù)雜度與數(shù)據(jù)復(fù)雜度，取m=17，11 輪積分攻擊的數(shù)據(jù)復(fù)雜度為236×17 ≈240.09個(gè)64 bit 長(zhǎng)明密文對(duì)。

4.2.2 時(shí)間復(fù)雜度分析

11 輪積分攻擊的步驟1 復(fù)雜度為選擇明文的復(fù)雜度，平均重復(fù)17 次，時(shí)間復(fù)雜度為17×(228.54+236)≈240.09次11 輪加密。步驟3 進(jìn)行簡(jiǎn)單運(yùn)算，相當(dāng)于4×248×(212×(17×2×52×252+52×252)+212) ≈2117.37次11 輪加密。步驟5 進(jìn)行窮搜驗(yàn)證時(shí)，需要(232+1)×228≈260次11 輪加密。

綜上，11 輪積分攻擊的時(shí)間復(fù)雜度為240.09+2117.37+260≈2117.37次11 輪加密。

4.3 Midori64 的積分攻擊對(duì)比

將本文積分攻擊與已有Midori64 算法的積分攻擊進(jìn)行性能對(duì)比，結(jié)果如表3 所示，從表3 可以看出，本文積分攻擊的輪數(shù)相比文獻(xiàn)［7］積分攻擊提高2 輪。與文獻(xiàn)［15］相比，本文找到的路線輸入集合大小為236，而文獻(xiàn)［15］中算法分析需要的數(shù)據(jù)量為263，為整個(gè)明文空間的一半。與已有Midori64 算法其他攻擊相比，在不考慮弱密鑰情況下，本文積分攻擊的數(shù)據(jù)復(fù)雜度和時(shí)間復(fù)雜度具有較大優(yōu)勢(shì)。

表3 Midori64 算法的密鑰恢復(fù)攻擊對(duì)比Table 3 Comparison of key recovery attacks of Midori64

5 結(jié)束語(yǔ)

本文構(gòu)建6 輪零相關(guān)區(qū)分器，利用零相關(guān)區(qū)分器與平衡積分區(qū)分器之間的等價(jià)關(guān)系，將6 輪零相關(guān)區(qū)分器轉(zhuǎn)換為6 輪平衡積分區(qū)分器，然后將3 個(gè)6 輪平衡積分區(qū)分器合成為一個(gè)性能優(yōu)良的6 輪零和積分區(qū)分器，向前擴(kuò)展1 輪得到一個(gè)7 輪零和積分區(qū)分器。將該7 輪零和積分區(qū)分器向后擴(kuò)展3 輪，對(duì)10 輪Midori64 算法實(shí)施密鑰恢復(fù)攻擊，攻擊的數(shù)據(jù)復(fù)雜度約為240個(gè)明密文對(duì)，時(shí)間復(fù)雜度約為267.85次10 輪加密運(yùn)算。將該7 輪零和積分區(qū)分器向后擴(kuò)展4 輪，對(duì)11 輪Midori64 算法實(shí)施密鑰恢復(fù)攻擊，攻擊的數(shù)據(jù)復(fù)雜度約為240.09個(gè)明密文對(duì)，時(shí)間復(fù)雜度約為2117.37次11 輪加密運(yùn)算。10 輪積分攻擊中采用部分和技術(shù)，11 輪積分攻擊中采用快速Walsh-Hadamard 變換技術(shù)。下一步將利用基于MILP 技術(shù)的分離特性搜索方法攻擊Midori64 算法。