蘇崇茂

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

1 引言

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

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

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

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

近年來(lái)隨著大塊Rijndael在哈希函數(shù)的構(gòu)造和消息認(rèn)證碼（MAC）中的應(yīng)用越來(lái)越廣泛，目前的分析結(jié)果主要從不可能差分攻擊和積分攻擊兩個(gè)角度來(lái)進(jìn)行［5］，如何針對(duì)Rijndael密碼給出新的安全性分析是當(dāng)前的研究熱點(diǎn)。

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

2 Rijndael-160密碼算法

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

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

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

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

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

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

2）行移位（ShiftRow）

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

3）列混淆（MixColumn）

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

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

4）輪密鑰加（AddRoundKey）

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

密鑰擴(kuò)展算法參見(jiàn)參考文獻(xiàn)［1］。

3 中間相遇攻擊基本思想

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

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

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

當(dāng)前中間相遇攻擊已廣泛應(yīng)用于分組密碼分析中，如文獻(xiàn)［7～12］等。

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

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

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

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

具體攻擊步驟如下：

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

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

圖2 6輪相遇攻擊示意圖

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

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

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

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

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

表1 已知的Rijndael-160攻擊結(jié)果對(duì)比

7 比較

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

8 結(jié)語(yǔ)

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

［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］.電子與信息學(xué)報(bào)，2012，34（3）：694-697.