Midori64 分組密碼算法的積分攻擊

王 超，陳懷鳳

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

0 概述

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

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

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

1 預備知識

1.1 符號說明

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

1.2 Midori64 算法描述

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

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

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

1.2.1 密鑰編排算法

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

1.2.2 S 盒

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

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

1.2.3 置換

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

1.2.4 列混淆

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

1.2.5 密鑰加

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

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

1.2.6 加密流程

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

圖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)進行密鑰加，第16輪使用白化密鑰進行密鑰加。

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

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

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

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

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

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

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

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

取3 個輸入掩碼權(quán)重為7 且輸出掩碼權(quán)重為1的5 輪零相關(guān)區(qū)分器，然后對輸出掩碼部分繼續(xù)擴展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 個6 輪零相關(guān)區(qū)分器的掩碼擴展細節(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)造

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

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

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

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

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

命題2［10］對于函數(shù)h：，定義Tλ：Fs2→Ft2，Tλ(y)=h1(λ，y)。若?a∈，b≠0 且a與b獨立，則函數(shù)h上線性特征（a‖0，b‖0）的相關(guān)度為0 等價于，函數(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個元素，存在228個此類集合。經(jīng)過6 輪加密后，得到對應的輸出集合為Sout=。

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

定理1當輸入為Sin時，加密6輪后，y1是零和的。

證明加密函數(shù)上線性特征(α1，β1)、(α1，β2)和(α1，β3) 的相關(guān)度都是0，由命題2 可知Tλ：是平衡的，得到t0、t1和t2每個取值的原像個數(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ū)分器。對6 輪積分區(qū)分器的輸入Sin中各單元進行逆向輪密鑰異或操作，其中，第0 個、第3 個、第4 個、第6 個、第8 個、第9 個和第12 個單元是固定常數(shù)，其余單元仍然遍歷所有可能取值。因此，在構(gòu)造7 輪積分區(qū)分器的過程中，可忽略此逆向密鑰加操作。記7 輪積分區(qū)分器的明文集合為：

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

4 Midori64 的積分攻擊

4.1 Midori64 的10 輪積分攻擊

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

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

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

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

步驟7使用2 組明密文對進行剩余正確密鑰的窮搜猜測。

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

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

4.1.2 時間復雜度分析

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

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

4.2 Midori64 的11 輪積分攻擊

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

步驟6由上述恢復的等價輪密鑰計算密鑰。

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

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

4.2.2 時間復雜度分析

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

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

4.3 Midori64 的積分攻擊對比

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

表3 Midori64 算法的密鑰恢復攻擊對比Table 3 Comparison of key recovery attacks of Midori64

5 結(jié)束語

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