6輪Square密碼算法的中間相遇攻擊

李蒙福，蘇凡軍

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093)

1 概 述

隨著信息技術(shù)的高速發(fā)展，數(shù)據(jù)安全的問題愈加凸顯。無(wú)論是在理論上還是技術(shù)上，密碼學(xué)在信息安全領(lǐng)域都是不可或缺的。分組密碼具有速度快、易于標(biāo)準(zhǔn)化和便于軟硬件實(shí)現(xiàn)等特點(diǎn)，通常是信息和網(wǎng)絡(luò)安全中實(shí)現(xiàn)數(shù)據(jù)加密、數(shù)字簽名、認(rèn)證及密鑰管理的核心體制，也是對(duì)稱密碼學(xué)的一個(gè)重要分支。分組密碼已經(jīng)在信息安全領(lǐng)域得到了非常廣泛的應(yīng)用，如數(shù)字通信安全、工業(yè)網(wǎng)絡(luò)控制安全、無(wú)線傳感器網(wǎng)絡(luò)感知安全、無(wú)線射頻識(shí)別安全以及電子商務(wù)支付安全等領(lǐng)域。分組密碼的研究?jī)?nèi)容主要包括分組密碼的設(shè)計(jì)和分析，兩者相互作用，共同推動(dòng)著分組密碼理論的發(fā)展。一方面，在對(duì)密碼進(jìn)行安全性分析的同時(shí)，可以為設(shè)計(jì)出更加安全的密碼積累更多的經(jīng)驗(yàn)，另一方面，在密碼算法的設(shè)計(jì)中也會(huì)涉及到很多具有現(xiàn)實(shí)意義的信息安全技術(shù)和一些具有實(shí)際應(yīng)用價(jià)值的理論知識(shí)。

Square算法是由Joan Daemen和Vincent Rijmen提出的分組密碼[1]，發(fā)表于1997年，是Rijndael的先驅(qū)。Square也是一個(gè)具有8輪代換-置換網(wǎng)絡(luò)[2](SPN)結(jié)構(gòu)的分組密碼，可以在各種處理器上實(shí)現(xiàn)非常高效的操作。該算法采用了2維4×4的字節(jié)矩陣，分組長(zhǎng)度和密鑰長(zhǎng)度都是128 bit。通常，實(shí)施對(duì)整輪密碼算法攻擊的難度是非常大的，但是可以利用一些攻擊方法減少迭代次數(shù)并對(duì)密碼算法進(jìn)行分析以衡量其安全性，這樣不僅能夠促進(jìn)密碼的發(fā)展，而且對(duì)信息安全也具有重要意義。

當(dāng)前，分組密碼的安全性研究也是一個(gè)熱點(diǎn)問題。很多密碼學(xué)研究者在多篇文獻(xiàn)中對(duì)多種密碼算法的安全性進(jìn)行分析和研究，另外，許多高效的分析方法也被陸續(xù)提出，如差分密碼分析、截?cái)嗖罘址治觥⒅虚g相遇攻擊等[3-6]。

截?cái)嗖罘置艽a分析是由Knudsen等提出的差分密碼分析的一個(gè)變形，與經(jīng)典的差分分析考慮的具體差分值不同，截?cái)嗖罘种豢紤]差分的一部分性質(zhì)。利用截?cái)嗖罘值乃枷?，可以?duì)某些抵抗經(jīng)典差分密碼分析的算法進(jìn)行攻擊。截?cái)嗖罘址治龅囊话懔鞒淌牵菏紫?，尋找一條高概率且有效的r-1輪截?cái)嗖罘致窂?；然后，加密符合要求的明文進(jìn)而獲得密文，從得到的密文對(duì)中篩選除差分對(duì)符合要求的密文對(duì)；最后，對(duì)上一步中的密文對(duì)進(jìn)行部分解密，通過(guò)計(jì)數(shù)的方法確定正確的密鑰。文獻(xiàn)[7]給出了Crypton算法的不可能差分分析。

中間相遇攻擊是在文獻(xiàn)[8]中提出，最早是用來(lái)對(duì)分組密碼的一種嘗試性擴(kuò)展進(jìn)行攻擊，之后廣泛應(yīng)用于分組密碼和Hash函數(shù)的安全性分析中。它通過(guò)存儲(chǔ)加密或解密的中間值，并使用這些中間值來(lái)改善強(qiáng)制解密密鑰所需的時(shí)間，從而削弱了使用多重加密的安全性好處。這使得中間相遇攻擊(MITM)成為通用的時(shí)空權(quán)衡密碼分析方法。該種攻擊方法的攻擊原理是：首先構(gòu)造出一個(gè)合適的區(qū)分器，然后將區(qū)分器前面的明文從前向后進(jìn)行加密，后面的密文從后向前進(jìn)行解密，接著和前面構(gòu)造出的區(qū)分器連接，最后形成一條連貫的攻擊路線。其中可能會(huì)出現(xiàn)兩種結(jié)果，假設(shè)加密和解密的部分能夠順利連接上區(qū)分器，那么猜出的密鑰值是無(wú)誤的，不然為錯(cuò)誤的，最后獲取符合的密鑰值。通過(guò)以上步驟，多數(shù)的不對(duì)密鑰會(huì)被排除掉。盡管在構(gòu)造區(qū)分器的過(guò)程中預(yù)計(jì)算的復(fù)雜度和存儲(chǔ)復(fù)雜度可能有點(diǎn)大，不過(guò)由于僅僅只進(jìn)行一次的預(yù)計(jì)算過(guò)程，從而在很大程度上也能降低攻擊的時(shí)間復(fù)雜度，所以中間相遇攻擊還是一種比較有效的攻擊方法。

近年來(lái)，中間相遇攻擊已成為比較成熟和富有成效的密碼分析方法之一，廣泛應(yīng)用于多種分組密碼的安全性分析中。文獻(xiàn)[9]給出了8輪AES的中間相遇攻擊，文獻(xiàn)[10]給出了利用多重集和差分枚舉技術(shù)進(jìn)行8輪AES中間相遇攻擊，文獻(xiàn)[11]給出了利用差分枚舉技術(shù)和有序差分集合進(jìn)行11輪3D中間相遇攻擊，文獻(xiàn)[12]給出了縮減輪Crypton的中間相遇攻擊分析，文獻(xiàn)[13]使用中間相遇攻擊對(duì)Kalyna算法進(jìn)行安全性分析。

Square密碼算法的安全性分析最早是文獻(xiàn)[1]中提出的Square攻擊，其成功給出了6輪Square密碼的攻擊結(jié)果，時(shí)間復(fù)雜度為272。文獻(xiàn)[14]對(duì)Square進(jìn)行了Boomerang攻擊，運(yùn)用了7輪Boomerang區(qū)分器，實(shí)現(xiàn)了全輪的攻擊，這也是目前最好的攻擊結(jié)果。但是，限于計(jì)算機(jī)的計(jì)算能力，其可行性還有待驗(yàn)證。2011年，文獻(xiàn)[15]給出了5輪Square的中間相遇攻擊分析，預(yù)計(jì)算時(shí)間復(fù)雜度為234，空間復(fù)雜度為272。

Dunkelman等在分析AES時(shí)提出了中間相遇攻擊“多重集”的概念。主要思想為：在構(gòu)造區(qū)分器的過(guò)程中，完整的輸出序列不需要進(jìn)行存儲(chǔ)，只將符合要求的無(wú)序的差分篩選集合進(jìn)行存儲(chǔ)，同時(shí)再結(jié)合有關(guān)截?cái)嗖罘值男再|(zhì)，進(jìn)一步減少?zèng)Q定區(qū)分器的參數(shù)個(gè)數(shù)，達(dá)到降低存儲(chǔ)復(fù)雜度的目的。

在分析Square算法的結(jié)構(gòu)特征和一類截?cái)嗖罘值男再|(zhì)的基礎(chǔ)上，文中利用差分枚舉技術(shù)和反彈式思想構(gòu)造出Square算法的4輪中間相遇區(qū)分器，該區(qū)分器由11個(gè)參數(shù)決定。在4輪區(qū)分器的基礎(chǔ)上前后各擴(kuò)展一輪，首次實(shí)現(xiàn)了對(duì)6輪Square算法的中間相遇攻擊。在6輪Square密碼的攻擊過(guò)程中，文中通過(guò)減少明文數(shù)量以降低數(shù)據(jù)復(fù)雜度，又通過(guò)使用了多重集進(jìn)而將決定區(qū)分器的參數(shù)個(gè)數(shù)減少為10個(gè)，從而進(jìn)一步降低了預(yù)計(jì)算的存儲(chǔ)復(fù)雜度。

2 預(yù)備知識(shí)

2.1 Square算法描述

Square是一個(gè)分組長(zhǎng)為128 bit，密鑰長(zhǎng)為128 bit的SPN型迭代分組密碼。Square的輪變換由四個(gè)不同的變換組成。128 bit的分組可以用4×4的2維字節(jié)矩陣表示。16個(gè)字節(jié)分組A={a0,a1,…,a15}可表示為如下形式：

(1)M：列混合，對(duì)一個(gè)狀態(tài)的每一列進(jìn)行操作。

M∶b=M(a)?bi,j=cjai，0⊕cj-1ai，1⊕cj-2ai，2⊕cj-3ai，3

(2)S：非線性變換，S是一個(gè)可逆的8位替換表或S盒。

S∶b=S(a)?bi,j=S(ai,j)

(3)T：轉(zhuǎn)置，狀態(tài)的行列交換。

T∶b=T(a)?bi,j=ai,j，T-1=T

(4)σ：輪密鑰加。

σ[kt]∶b=σ[kt](a)?b=a⊕kt

每一輪進(jìn)行以上4個(gè)操作后，迭代8輪即可得到相關(guān)密文，解密操作基本上和加密操作一樣，只是調(diào)換了密鑰的順序，Square的密鑰編排詳見文獻(xiàn)[15]。

在某些情況下，在兩個(gè)連續(xù)的輪次中交換M和ki的順序。由于這些操作是線性的，所以可以互換[2]。具體操作是：首先用相等的密鑰M-1(ki)排除數(shù)據(jù)，然后再應(yīng)用操作M。例如，k0⊕M(x)=M(M-1(k0)⊕x)。

2.2 符號(hào)說(shuō)明

xi：第i輪經(jīng)過(guò)密鑰加ki的狀態(tài)；

yi：第i輪經(jīng)過(guò)M變換的狀態(tài)；

zi：第i輪經(jīng)過(guò)S的狀態(tài)；

wi：第i輪經(jīng)過(guò)T的狀態(tài)；

Δx：狀態(tài)x的差分；

x[i]：狀態(tài)x的第i個(gè)字節(jié)；

x[i,…,j]：狀態(tài)x從第i個(gè)字節(jié)到第j個(gè)字節(jié)；

ui=M-1(ki)；

x‖y：x與y連接；

⊕：異或；

Δxm：=xm⊕xi。

3 6輪Square算法的中間相遇攻擊

這一節(jié)中，將描述在6輪Square上的MITM攻擊。首先，給出需要的定義、引理和推論。然后，提出4輪MITM區(qū)分器，并在6輪Square上進(jìn)行MITM攻擊。最后，通過(guò)改進(jìn)4輪區(qū)分器，以實(shí)現(xiàn)相應(yīng)攻擊復(fù)雜度的降低。

3.1 4輪中間相遇區(qū)分器

引理1：給定Δi和Δo兩個(gè)非零差分元素，方程S(x)⊕S(x⊕Δi)=Δo，平均有一個(gè)解。這個(gè)屬性也適用于s-1。

推論1：選擇δ集

圖1 6輪Square攻擊的截?cái)嗖罘痔匦詧D

然而，以上給出的25個(gè)字節(jié)其實(shí)可以由以下11個(gè)字節(jié)決定：

3.2 6輪中間相遇攻擊

6輪Square算法中間相遇攻擊由兩個(gè)階段組成：預(yù)計(jì)算階段和在線攻擊階段。攻擊過(guò)程如圖2所示。

1.預(yù)計(jì)算階段。

2.在線攻擊階段。

首先找到滿足圖1中截?cái)嗖罘痔卣鞯拿魑膶?duì)(pi,pj)，并確定δ集，然后計(jì)算差分序列并檢測(cè)它是否在預(yù)計(jì)算階段建立的預(yù)計(jì)算表中，在線階段的攻擊過(guò)程描述如下：

(1)定義一個(gè)232個(gè)明文結(jié)構(gòu)P[0,4,8,12]，其余12個(gè)字節(jié)固定為常數(shù)。使用這一結(jié)構(gòu)可構(gòu)成232×(232-1)/2≈263個(gè)明文對(duì)，并且每個(gè)明文對(duì)都滿足明文差分特性。攻擊過(guò)程中還需對(duì)281個(gè)明文結(jié)構(gòu)進(jìn)行加密以找到281×263×2-12×8=248個(gè)對(duì)應(yīng)的密文對(duì)以驗(yàn)證密文差分。因此，對(duì)于正確的密鑰，248對(duì)中有248×2-2×3×8=1對(duì)遵循整個(gè)截?cái)嗖罘痔卣?。因?yàn)樵诘?輪和第5輪的M操作中有兩個(gè)4→1的轉(zhuǎn)換。注意，不必檢查每一對(duì)去找到248個(gè)密文對(duì)，可以將結(jié)構(gòu)存儲(chǔ)在由密文中的12個(gè)非活動(dòng)字節(jié)索引的散列表中，以獲得正確的對(duì)。

(2)對(duì)248對(duì)中的每一對(duì)，假設(shè)它遵循圖1中的整個(gè)截?cái)嗖罘痔卣?，進(jìn)行如下操作：

(a)猜測(cè)Δw0[0]，推導(dǎo)出Δz0[0]，根據(jù)明文差分推導(dǎo)出Δy0[0]，根據(jù)引理1得到y(tǒng)0[0]，然后推出u0[0]。

(b)猜測(cè)值Δx5[0]，推導(dǎo)出Δy5[0,4,8,12]，根據(jù)密文差分，推導(dǎo)出Δz5[0,4,8,12]，根據(jù)引理2可得出z5[0,4,8,12]，z5[0,4,8,12]經(jīng)過(guò)T操作后得到w5[0,1,2,3]，最后推出k6[0,1,2,3]。

(3)最后只剩下1+248×216×2-936≈1個(gè)子密鑰。根據(jù)得到的部分密鑰，通過(guò)窮舉搜索剩余未知字節(jié)以恢復(fù)全部密鑰。

圖2 6輪中間相遇攻擊圖

3.3 對(duì)6輪Square攻擊的改進(jìn)

通常，為了降低存儲(chǔ)復(fù)雜度，可利用多重集把對(duì)6輪Square中間相遇攻擊決定區(qū)分器的參數(shù)減少一個(gè)(w0[0]可不要)。

根據(jù)6輪Square的中間相遇攻擊過(guò)程可以看出，主要的時(shí)間復(fù)雜度是對(duì)選擇的明文進(jìn)行加密，所以還可以通過(guò)減少選擇明文的數(shù)量以降低時(shí)間復(fù)雜度。在圖1對(duì)6輪Square攻擊的截?cái)嗖罘痔匦灾校驗(yàn)閷?duì)w0活動(dòng)字節(jié)的差分位置有0、1、2、3這4個(gè)位置，每個(gè)選擇可構(gòu)造22個(gè)對(duì)應(yīng)差分表，而x5處的活動(dòng)字節(jié)也會(huì)有0、1、2、3這四個(gè)位置，所以就可以構(gòu)造出4×4=16條不同的區(qū)分器鏈，從而可將數(shù)據(jù)復(fù)雜度減少24，但需要額外的預(yù)計(jì)算表，即存儲(chǔ)復(fù)雜度則會(huì)增加24。

綜上，整個(gè)攻擊的時(shí)間復(fù)雜度為2109，數(shù)據(jù)復(fù)雜度降為2109，存儲(chǔ)復(fù)雜度為284。

4 結(jié)束語(yǔ)

利用差分枚舉技術(shù)和反彈式思想，文中構(gòu)造了Square算法的4輪區(qū)分器，又通過(guò)多重集降低了預(yù)計(jì)算的存儲(chǔ)復(fù)雜度以及通過(guò)減少明文數(shù)量降低了數(shù)據(jù)復(fù)雜度。研究了Square密碼算法的中間相遇攻擊技術(shù)，首次給出了6輪Square算法的中間相遇攻擊，整個(gè)攻擊的數(shù)據(jù)復(fù)雜度為2109，時(shí)間復(fù)雜度2109，存儲(chǔ)復(fù)雜度為284。