Rijndael-160的中間相遇攻擊?

蘇崇茂

（1.廣西金投互聯(lián)網(wǎng)金融服務有限公司 南寧 530021）（2.廣西金融投資集團有限公司 南寧 530021）

1 引言

Rijndael-b［1］按分組長度的不同劃分為 Rijn?dael-128， Rijndael-160， Rijndael-192， Rijn?dael-224，Rijndael-256等五種加密算法類型，其中密鑰長度分別為-128 bits，-192 bits，-256bits的Rijndael-128被選為新的高級加密標準（AES），而分組長度超過128 bits的類型稱為大塊Rijndael。本文主要關注Rijndael-160的分析結果：

1）2005年J.Nakahara等給出Rijndael-160的多重集攻擊［2］：6輪多重集攻擊的數(shù)據(jù)復雜度為234.5選擇明文，時間復雜度為243.5次6輪Rijndael-160加密；7輪多重集攻擊的數(shù)據(jù)復雜度為2129選擇明文，時間復雜度為2133.5次7輪Rijndael-160加密。

2）2008年J.Nakahara等對Rijndael-160進行不可能差分攻擊［3］：6輪攻擊數(shù)據(jù)復雜度和時間復雜度分別為 2105.5選擇明文和 2135次6輪Rijn?dael-160加密。

3）2008年L.Zhang等提高了Rijndael-160的不可能差分攻擊［4］：6輪攻擊數(shù)據(jù)復雜度和時間復雜度分別為293.2選擇明文和2114.1次6輪Rijndael-160加密。7輪攻擊數(shù)據(jù)復雜度和時間復雜度分別為2147選擇明文和281.9次7輪Rijndael-160加密。

近年來隨著大塊Rijndael在哈希函數(shù)的構造和消息認證碼（MAC）中的應用越來越廣泛，目前的分析結果主要從不可能差分攻擊和積分攻擊兩個角度來進行［5］，如何針對Rijndael密碼給出新的安全性分析是當前的研究熱點。

本文將側重檢查Rijndael-160抵抗中間相遇攻擊的能力：基于Rijndael-160密碼算法結構，設計了一個3、4輪相遇區(qū)分器，并由此給出6、7輪Ri?jndael-160密碼新的安全性評價。

2 Rijndael-160密碼算法

本小節(jié)簡單描述Rijndael-160密碼算法，更多的細節(jié)參見文獻［1］。

Rijndael-160的數(shù)據(jù)分組長度為160bits，密鑰長度范圍128-256bits，并且以32bits為增量，相應的輪數(shù)為11/11/12/13/14輪。160bits分組數(shù)據(jù)按列存放，可表示為圖1。

圖1 Rijndael-160數(shù)據(jù)表示圖

其輪函數(shù)由四個部件構成：

1）字節(jié)替換（SubBytes）

Rijndael-160中唯一的非線性變換，即把每個狀態(tài)字節(jié)作用于一個相同的S盒。

2）行移位（ShiftRow）

Rijndael-160的字節(jié)行移位類似于AES，第一行循環(huán)左移0個字節(jié)，第二行循環(huán)左移1個字節(jié)，第三行循環(huán)左移2個字節(jié)，第四行循環(huán)左移3個字節(jié)。

3）列混淆（MixColumn）

Rijndael-160的列混淆是用一個可逆矩陣對每列狀態(tài)字節(jié)進行相乘的操作。變換如下：

其中 x0，x1，x2，x3為列混淆前同一列的四個字節(jié)，y0，y1，y2，y3為列混淆后同一列的四個字節(jié)。

4）輪密鑰加（AddRoundKey）

把160bits狀態(tài)字節(jié)與160bits輪子密鑰直接異或。

密鑰擴展算法參見參考文獻［1］。

3 中間相遇攻擊基本思想

1977年W.Diffie和M.Hellman針對DES密碼算法提出中間相遇攻擊方法［6］。其基本思想是把一個密碼算法可以看作兩部分構成：

1）設明文Pi某個位置輸入取遍0～255的所有值（例如第一個字節(jié)，記為x）而余下字節(jié)均固定，計算某個位置的輸出（例如第一個字節(jié)，記為 y）可由函數(shù) f表示：y=f(x)。其中 f由一些固定值和Ka決定。

2）通過明文Pi獲得相應的密文Ci，對所有可能的Kb計算的第一個字節(jié)為 y'，檢查是否有 y'=y成立，淘汰不滿足該式的Kb。對所有的 i=1，2，...，n 重復以上步驟，錯誤的密鑰將被過濾掉，最終獲得正確密鑰。

當前中間相遇攻擊已廣泛應用于分組密碼分析中，如文獻［7～12］等。

4 3輪Rijndael-160相遇區(qū)分器

性質1：考慮一個集合：M(0)={x，a1，a2，...，a19}，x取遍0～255的所有值，ai(1≤i≤19)取值固定。為經(jīng)過3輪Rijndael-160加密M(0)之后的輸出。函數(shù) f:x→由 x 和確定的7個字節(jié)完全決定。差分?Y(j)=f(j)⊕f(0)，1≤j≤17，則由x和確定的6個字節(jié)完全決定。

5 6輪Rijndael-160中間相遇攻擊

6輪Rijndael-160的中間相遇基本攻擊思路為：在上述3輪區(qū)分器的基礎上，前面加1輪，后面加2輪構成6輪攻擊；其中第5輪的輪密鑰加RAK與列混合操作MC交換次序，見圖2所示。其中*為加密過程中所涉及的字節(jié)，C為非考慮字節(jié)

具體攻擊步驟如下：

第1步：對于性質1中的6個常量字節(jié)即26×8=248個可能的參數(shù)值，由性質1計算函數(shù)。進一步，對于每個 f，計算?Y(i)=f(i)⊕f(0)，1≤i≤18，把此序列存儲在一張哈希表H中。

第2步：定義一個明文空間結構：滿足在字節(jié)（0，5，10，15）取遍0～255所有值，其余字節(jié)取固定值。選擇1個上述結構，在選擇明文攻擊下，6輪Rijndael-160加密這一結構，獲取相應的密文。猜測，并做以下處理：

圖2 6輪相遇攻擊示意圖

2）選擇19個明文，其對應第2輪輸出字節(jié)（0）處值x=0，1，…，18，其余字節(jié)均為固定值。存儲這19個明文，記為

新攻擊所需的數(shù)據(jù)復雜度為24×8=232選擇明文。預計算階段的時間復雜度為19×26×8/6≈249.5次6輪Rijndael-160加密。第2步1）的時間復雜度為232×240×/6≈269.4次6輪Rijndael-160加密。第3步1）所需的時間復雜度為19×240+40/6≈281.5次6輪Rijndael-160加密。

6 7輪Rijndael-160中間相遇攻擊

7輪Rijndael-160的中間相遇與6輪攻擊類似，只是在3輪區(qū)分器的基礎上增加一輪。

若直接進行預處理，計算的復雜度將超過窮搜索復雜度，可以利用時空折中的方法，即以增加數(shù)據(jù)復雜度和時間復雜度的代價來降低預處理復雜度 。 記為第n輪第i行第j列加密處理所涉及的常量字節(jié)。令(，概率為 P(，則預處理階段需要猜測15個字節(jié)。新攻擊的數(shù)據(jù)復雜度為248×24×8=280選擇明文，預計算階段的時間復雜度為19×215×8/6≈2121.5次7輪Rijndael-160加密。時間復雜度為19×248×240+40/7≈2129.4次7輪Rijn?dael-160加密。

表1 已知的Rijndael-160攻擊結果對比

7 比較

由表1可以看出：6輪Rijndael-160或者7輪Rijndael-160的攻擊中，中間相遇攻擊的數(shù)據(jù)復雜度最低。

8 結語

本文檢查Rijndael-160算法抵抗中間相遇攻擊的能力：基于Rijndael-160算法設計了一個3、4輪區(qū)分器，并由此給出了6、7輪Rijndael-160的新攻擊。結果表明：6輪Rijndael-160或者7輪Rijn?dael-160的攻擊中，中間相遇攻擊的數(shù)據(jù)復雜度最低。

［1］J.Daemen，V.Rijnmen.The Design of Rijndael AES：The Advanced Encryption Standard［M］.Berlin， Spring?er-Verlag，2002：30-45.

［2］J.Nakahara，D.S.de Freitas，Phan，et al.New Multiset At?tacks on Rijndael with Large Blocks［C］//Mycrypt 2005.Springer-Verlag，2005.LNCS3715：277-295.

［3］J.Nakahara，I C.Pavao.Impossible-differential Attacks on Large-Block Rijndael［C］//ISC 2007.Springer-Verlag，2007.LNCS4779：104-117.

［4］L.Zhang，W.Wu，J.Park，et al.Improved Impossible Dif?ferential Attacks on Large-Block Rijndael［C］//ISC 2008，Springer-Verlag，2008.LNCS5222：298-315.

［5］ Y.Sasaki.Known-Key Attacks on Rijndael with Large Blocks and Strengthening ShiftRow Parameter［C］//IW?SEC 2010.Springer-Verlag，2010.LNCS6434：301-315.

［6］ H.Diffie，M.Hellman：Exhaustive Cryptanalysis of the NBSData Encryption Standard［J］.IEEEComputer.1977，10（6）：74-84.

［7］H.Demirci，H.Selcuk：A Meet in the Middle Attack on 8-Round AES［C］//Fast Software Encryption 2008.Springer-Verlag，2008.LNCS5086：116-126.

［8］ H.Demirci，I.Taskin，M.Coban，et al.Improved Meet-in-the-Middle Attacks on AES［C］//INDOCRYPT 2009，Springer-Verlag，2009，LNCS5922：144-156.

［9］O.Dunkelman，N.Keller，A.Shamir.Improved Single-Key Attacks on 8-Round AES［C］//ASIACRYPT 2010，Springer-Verlag 2010，LNCS6477：158-176.

［10］Y.Wei，J.Lu，Y.Hu.Meet-in-the-Middle Attacks on 8 Rounds of the AES Block Cipher under 192 Key Bits［C］//ISPEC 2011， Springer-Verlag 2011， LNCS 6672：222-232.

［11］ G.Sekar，N.Mouha，V.Velichkov，B.P reneel.Meet-in-the-Middle Attacks on Reduced-Round XTEA［C］//Topics in Cryptology-CT-RSA 2011.Spring?er-Verlag，2011，LNCS6558：250-267.

［12］蘇崇茂，韋永壯，馬春波.10輪3D分組密碼算法的中間相遇攻擊［J］.電子與信息學報，2012，34（3）：694-697.