輕量級分組密碼Midori64的積分攻擊

連 闖 毛 明 李艷俊

1(西安電子科技大學通信工程學院 陜西 西安 710071)2(北京電子科技學院 北京100070)3(北京電子科技學院信息安全系 北京 100070 )

0 引 言

物聯(lián)網(wǎng)技術(shù)的快速發(fā)展已經(jīng)使其成為新時代信息技術(shù)的重要組成部分。物聯(lián)網(wǎng)最初是通過射頻識別、紅外感應和定位系統(tǒng)等信息傳感設備把物品與互聯(lián)網(wǎng)連接起來。因此設備體積變小成為行業(yè)內(nèi)追逐的趨勢,這使輕量級密碼算法成為了研究的熱點。這些年研究人員設計了許多輕量級分組密碼如：MIBS[1]、PRESENT[2]、Lblock[3]、Piccolo[4]、GOST[5]等。這些算法大都可以在保證足夠的安全性下實現(xiàn)良好的效率,為物聯(lián)網(wǎng)信息傳遞過程中的信息加密提供了保障。Midori[6]是在2015年ASIACRYPT會議上提出的一種輕量級分組密碼,其分組長度為64和128 bit,分別記為Midori64和Midori128。Midori算法的密鑰長度為128 bit,可以提供較好的安全性。

積分分析起源于Square攻擊。在Square攻擊的基礎上，Lucks[7]攻擊了Feistel結(jié)構(gòu)型分組密碼Twofish算法，并因此提出了Satuation攻擊。Biryukov等[8]通過分析SPN結(jié)構(gòu)安全性,提出了Multiset攻擊。Knudsen總結(jié)了Square攻擊、Saturation攻擊和Multiset攻擊,并在此基礎上提出了積分攻擊。

目前,密碼學者利用積分攻擊分析了Rijndael[9]、ARIA[10]、Camellia等[11]著名算法的安全性。積分攻擊對AES、MISTY等算法的攻擊結(jié)果優(yōu)于已有的差分分析和線性分析結(jié)果。

對Midori的攻擊主要有不可能差分分析[12]、基于輪密鑰猜測的不可能差分分析[13]、抗故障攻擊[14]等。還沒有針對Midori算法的積分攻擊,在對算法模塊進行深入分析后,本文首先提出了Midori64算法的4輪積分區(qū)分器,并向解密方向擴展1輪,得到了5輪高階積分區(qū)分器。使用5輪積分區(qū)分器對Midori64進行了6輪、7輪和8輪的攻擊,并給出了攻擊的數(shù)據(jù)和時間復雜度。

1 Midori64算法描述

Midori算法是一種SPN結(jié)構(gòu)的輕量級加密算法。算法明文分組長度64 bit,輪數(shù)為16輪,種子密鑰長度為128 bit,其運算單元為半字節(jié)。以下所稱字節(jié)均表示半字節(jié)。明文被分成了16個4 bit的明文組,用一個的矩陣表示：

1.1 符號說明

K(j,i):第j輪的輪密鑰的第i個字節(jié)。

A:活躍字節(jié),遍歷多有可能值。

B:平衡字節(jié),該字節(jié)和為0。

U:未知,字節(jié)性質(zhì)不可知。

1.2 SubCell(s)

Midori64采用的S盒如表1所示。明文矩陣中每個單元需通過S盒。

表1 Midori64的S盒

1.3 ShuffleCell(SC)

對明文矩陣中各個單元的進行位置重新排列,如下所示:

1.4 MixCloumn(MC)

用MDS矩陣M左乘ShuffleCell計算結(jié)果,執(zhí)行列混淆變換,由于M具有自逆特性,其逆矩陣與其相同。

t(Si,Si+1,Si+2,Si+3)←M·t(Si,Si+1,Si+2,Si+3)

1.5 KeyAdd(AK)

將MixCloumn結(jié)果與輪密鑰進行“異或”計算。

1.6 密鑰編排

Midori的密鑰編排將128 bit的主密鑰取高64 bit記為K0,取低64 bit為K1,K=K0‖K1,定義白化密鑰WK=K0⊕K1,輪密鑰RKi=Ki mod2⊕ai(0≤i≤14)，ai為輪常量。

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

2.1 Midori64的4輪積分區(qū)分器

命題1經(jīng)過對Midori加密算法分析,選取輸入的第一個字節(jié)為活躍字節(jié),其余字節(jié)均為常數(shù)字節(jié),則第4輪的輸出中第一個字節(jié)為平衡字節(jié)。

證明: 設輸入的第一個字節(jié)為活躍字節(jié),其他字節(jié)均為常數(shù)字節(jié),經(jīng)過S盒以及SC后第一個字節(jié)仍為活躍字節(jié),其余字節(jié)為常數(shù)字節(jié),經(jīng)過列混淆MC后,第一列的第2,3,4字節(jié)為活躍字節(jié),其余字節(jié)為常數(shù)字節(jié),接下來的密鑰加AK操作不會改變字節(jié)性質(zhì)。第二輪經(jīng)過S盒后活躍字節(jié)位置不變,經(jīng)過單元置換SC后,活躍字節(jié)的位置變?yōu)榈?,10,15這三個字節(jié),其余字節(jié)為常數(shù)字節(jié),經(jīng)過列混淆MC后,活躍字節(jié)位置為第5,6,7,9,11,12,13,14,16這9個字節(jié)。又由于密鑰加AK操作不改變字節(jié)性質(zhì),因此第二輪輸出后5,6,7,9,11,12,13,14,16這9個字節(jié)為活躍字節(jié),其余為常數(shù)字節(jié)。第三輪經(jīng)過S盒后活躍字節(jié)性質(zhì)不變。經(jīng)過單元置換SC后活躍字節(jié)位置為第2,3,4,6,7,11,12,14,16這9個字節(jié),經(jīng)過列混淆MC操作后字節(jié)性質(zhì)發(fā)生改變,第1,2,3,4,5,8,9,13,15這9個字節(jié)為平衡字節(jié),其余字節(jié)為活躍字節(jié),最后AK操作不改變字節(jié)性質(zhì)。這些字節(jié)在進入第四輪后,經(jīng)過S盒后平衡字節(jié)性質(zhì)發(fā)生破壞,變?yōu)槲粗獱顟B(tài),活躍字節(jié)性質(zhì)不變。經(jīng)過單元置換SC及列混淆MC操作后,第1個字節(jié)為平衡字節(jié),其余字節(jié)均為未知狀態(tài),又由于密鑰加AK操作不改變字節(jié)性質(zhì),因此第4輪的輸出在進入第5輪后,平衡字節(jié)性質(zhì)通過S盒發(fā)生破壞,即得到了Midori64的4輪積分區(qū)分器。如圖1所示。

圖1 Midori64的4輪積分區(qū)分器

2.2 Midori64的5輪積分區(qū)分器

由Midori的密碼結(jié)構(gòu),可以將上述4輪積分區(qū)分器向前擴展一輪得到5輪高階積分區(qū)分器。

命題2選取輸入明文中4個字節(jié)(S0,S5,S10,S15)為活躍字節(jié),其他字節(jié)為常數(shù)字節(jié),則第5輪輸出的首個字節(jié)為平衡字節(jié)。

證明:(S0,S5,S10,S15)這4個字節(jié)遍歷所有216種取值,設輸入的明文形式為:

(1)

式中：(A0,A5,A10,A15)為活躍字節(jié),其余均為常數(shù)字節(jié)。經(jīng)過一輪加密我們可以得到第一輪的輸出為:

(2)

(3)

其余字節(jié)為常數(shù)字節(jié),再利用4輪積分區(qū)分器經(jīng)過4輪加密后第5輪輸出的首字節(jié)為平衡字節(jié)。即得到Midori64的5輪積分區(qū)分器。如圖2所示。

圖2 Midori64的5輪積分區(qū)分器

3 Midori64的積分攻擊

運用積分攻擊的方法,我們對Midori64算法進行了6輪、7輪、8輪的攻擊。

3.1 Midori64的6輪積分攻擊

利用5輪區(qū)分器進行6輪攻擊,過程如下:

(1) 選擇如式(1)的一組明文,對其進行6輪加密,記密文為c0,c1,…,c216-1。

(2) 猜測第6輪首字節(jié)密鑰K(6,0)的值,計算:

(4)

(3) 檢驗P=0是否成立,若成立,相應的K(6,0)作為一個正確密鑰的候選值,否則淘汰。

(4) 重新選擇一組明文,重復上述步驟,直到K(6,0)的值唯一確定。

復雜度計算如下:

若密鑰K(6,0)為錯誤密鑰,則錯誤密鑰值使得P=0的概率為2-4,經(jīng)過一組明文驗證后,剩余的錯誤密鑰個數(shù)為1-2-4<1,因此,需要兩組明文就可以確定正確密鑰。從而攻擊的數(shù)據(jù)復雜度為2×216=217個選擇明文。第一組明文需要進行216次6輪加密,需要進行24×24=28次S盒運算。一次6輪Midori64加密需要查詢S盒96次,因此第一組明文需要進行(24×24)/96=21.41次6輪加密;處理完第一組明文后錯誤密鑰最多還剩1個,因此對于第二組明文其共需要24次6輪加密,因此上述攻擊的時間復雜度為216+21.41≈216次6輪加密運算。

3.2 Midori64的7輪攻擊

在5輪區(qū)分器的后面加2輪可以進行7輪攻擊。

將表3和5進行比較發(fā)現(xiàn),各要素標注出的缺省指代數(shù)與各要素的缺省量不一致,那是因為缺省要素的標注只能根據(jù)篇章中已經(jīng)存在的要素進行缺省要素補全,而一些事件的缺省要素在文中是沒有描述的,這時是不能進行補全的,也就是說缺省指代只能根據(jù)已存在要素在一定程度上補全缺省要素.

(1) 選擇包含216個不同明文組滿足結(jié)構(gòu)：

進行7輪加密。

經(jīng)過AK、MC-1、SC-1、S-1操作后：

(5)

(6)

3.3 Midori64的8輪積分攻擊

在上述7輪之后再加一輪,進行8輪攻擊,根據(jù)加密算法結(jié)構(gòu)得第5輪首字節(jié)輸出與第6輪輸出的表達式:

(7)

第6輪的輸出第一列3個字節(jié)與第7輪輸出的表達式:

第7輪輸出與第8輪密文的表達式:

因此表達式為:

(8)

式中：

利用部分和技術(shù)優(yōu)化其時間復雜度的計算,過程同上述7輪復雜度的計算過程,經(jīng)過計算得到的數(shù)據(jù)復雜度為216×14=219.80個選擇明文,時間復雜度為265次8輪加密。

3.4 3種積分攻擊復雜度

整理文中對Midori64加密算法的6輪、7輪和8輪攻擊的復雜度如表2所示。

表2 Midori64積分分析復雜度結(jié)果

4 結(jié) 語

本文對Midori64加密算法構(gòu)造出了4輪積分區(qū)分器,并向解密方向擴展1輪,得到了5輪區(qū)分器。利用5輪區(qū)分器對Midori64進行了6輪、7輪和8輪的積分攻擊。這是首次運用積分攻擊來評估Midori64算法的安全性,從表2中可以看到,隨著攻擊輪數(shù)的增加,所需要恢復的密鑰個數(shù)也在相應增加,在復雜度方面,6輪與7輪攻擊的數(shù)據(jù)復雜度均為217個選擇明文,但在時間復雜度上面,7輪大于6輪。8輪攻擊一共需要恢復52 bit密鑰,數(shù)據(jù)復雜度為3×216個選擇明文,時間復雜度為258.43次8輪加密,相比于窮舉搜索復雜度有所增加。

通過猜測相關輪密鑰與密文的關系,可以進一步學習到積分攻擊過程中平衡字節(jié)與密文的對應關系,進而得到每一輪中所用到的相關字節(jié)密鑰,進而可以采用部分和技術(shù)來降低恢復密鑰的時間復雜度。