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

連 闖 毛 明 李艷俊

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

0 引 言

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

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

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

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

1 Midori64算法描述

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

1.1 符號說明

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

A:活躍字節,遍歷多有可能值。

B:平衡字節,該字節和為0。

U:未知,字節性質不可知。

1.2 SubCell(s)

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

表1 Midori64的S盒

1.3 ShuffleCell(SC)

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

1.4 MixCloumn(MC)

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

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

1.5 KeyAdd(AK)

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

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的積分區分器

2.1 Midori64的4輪積分區分器

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

證明: 設輸入的第一個字節為活躍字節,其他字節均為常數字節,經過S盒以及SC后第一個字節仍為活躍字節,其余字節為常數字節,經過列混淆MC后,第一列的第2,3,4字節為活躍字節,其余字節為常數字節,接下來的密鑰加AK操作不會改變字節性質。第二輪經過S盒后活躍字節位置不變,經過單元置換SC后,活躍字節的位置變為第8,10,15這三個字節,其余字節為常數字節,經過列混淆MC后,活躍字節位置為第5,6,7,9,11,12,13,14,16這9個字節。又由于密鑰加AK操作不改變字節性質,因此第二輪輸出后5,6,7,9,11,12,13,14,16這9個字節為活躍字節,其余為常數字節。第三輪經過S盒后活躍字節性質不變。經過單元置換SC后活躍字節位置為第2,3,4,6,7,11,12,14,16這9個字節,經過列混淆MC操作后字節性質發生改變,第1,2,3,4,5,8,9,13,15這9個字節為平衡字節,其余字節為活躍字節,最后AK操作不改變字節性質。這些字節在進入第四輪后,經過S盒后平衡字節性質發生破壞,變為未知狀態,活躍字節性質不變。經過單元置換SC及列混淆MC操作后,第1個字節為平衡字節,其余字節均為未知狀態,又由于密鑰加AK操作不改變字節性質,因此第4輪的輸出在進入第5輪后,平衡字節性質通過S盒發生破壞,即得到了Midori64的4輪積分區分器。如圖1所示。

圖1 Midori64的4輪積分區分器

2.2 Midori64的5輪積分區分器

由Midori的密碼結構,可以將上述4輪積分區分器向前擴展一輪得到5輪高階積分區分器。

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

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

(1)

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

(2)

(3)

其余字節為常數字節,再利用4輪積分區分器經過4輪加密后第5輪輸出的首字節為平衡字節。即得到Midori64的5輪積分區分器。如圖2所示。

圖2 Midori64的5輪積分區分器

3 Midori64的積分攻擊

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

3.1 Midori64的6輪積分攻擊

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

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

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

(4)

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

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

復雜度計算如下:

若密鑰K(6,0)為錯誤密鑰,則錯誤密鑰值使得P=0的概率為2-4,經過一組明文驗證后,剩余的錯誤密鑰個數為1-2-4<1,因此,需要兩組明文就可以確定正確密鑰。從而攻擊的數據復雜度為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輪區分器的后面加2輪可以進行7輪攻擊。

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

(1) 選擇包含216個不同明文組滿足結構：

進行7輪加密。

經過AK、MC-1、SC-1、S-1操作后：

(5)

(6)

3.3 Midori64的8輪積分攻擊

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

(7)

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

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

因此表達式為:

(8)

式中：

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

3.4 3種積分攻擊復雜度

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

表2 Midori64積分分析復雜度結果

4 結 語

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

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