密鑰泄露下Even-Mansour密碼的滑動(dòng)攻擊

楊 光 張 平 胡紅鋼

(中國科學(xué)技術(shù)大學(xué)信息科學(xué)技術(shù)學(xué)院 合肥 230027) (中國科學(xué)院電磁空間信息重點(diǎn)實(shí)驗(yàn)室 合肥 230027) (yg14@mail.ustc.edu.cn)

近幾年來，網(wǎng)絡(luò)技術(shù)更新速度極快，尤其是在大數(shù)據(jù)處理和云計(jì)算技術(shù)的出現(xiàn)之后，數(shù)據(jù)的使用量每年都較前一年成倍增長.如此海量的數(shù)據(jù)其安全性的保障是非常重要的.一般來說，數(shù)據(jù)的安全性會(huì)通過一些加密方案和認(rèn)證方案實(shí)現(xiàn)，其中前者為數(shù)據(jù)提供保密性保護(hù)，后者為數(shù)據(jù)提供完整性保護(hù).分組密碼在加密方案和認(rèn)證方案的設(shè)計(jì)中是非常重要的基礎(chǔ)模塊，尤其是對(duì)于批量數(shù)據(jù)，其安全性和加解密速度在現(xiàn)有密碼體制中都相當(dāng)優(yōu)秀.

很多分組密碼方案會(huì)迭代使用一種結(jié)構(gòu)(如AES)，該結(jié)構(gòu)首先將輸入和一個(gè)密鑰進(jìn)行異或，然后將結(jié)果通過一個(gè)公共偽隨機(jī)置換(比較典型的如S盒和一些線性變換)，再將置換的結(jié)果與另一個(gè)密鑰進(jìn)行異或，并以輸出結(jié)果作為迭代結(jié)構(gòu)的下次輸入.通常，我們假設(shè)這樣的置換是理想的，即隨機(jī)性足夠好，這樣，攻擊者無法通過置換的弱點(diǎn)對(duì)加密系統(tǒng)進(jìn)行攻擊.這樣的設(shè)計(jì)有3點(diǎn)好處：第一，結(jié)構(gòu)設(shè)計(jì)簡單，安全性理論非常清晰；第二，此類結(jié)構(gòu)可以利用置換的隨機(jī)性，證明對(duì)該結(jié)構(gòu)的破解攻擊和偽造攻擊的攻擊復(fù)雜度下界；第三，任何基于此通用形式的新的分組密碼攻擊都具有廣泛的適用性.

上述結(jié)構(gòu)的一個(gè)最簡單的例子是由Even和Mansour[1-2]在1991年的Asiacrypt上提出的一種分組密碼體制.該密碼的提出是受到由Rivest提出的DESX[3-4]結(jié)構(gòu)的影響，由一個(gè)公共偽隨機(jī)置換F和2個(gè)密鑰K1,K2構(gòu)成，通過將輸入在置換前后分別與2個(gè)密鑰進(jìn)行異或得到輸出，其結(jié)構(gòu)如圖1所示：

圖1 Even-Mansour結(jié)構(gòu)

Even-Mansour密碼體制簡單的設(shè)計(jì)和嚴(yán)格的安全性證明，使其成為分組密碼方向的熱門研究點(diǎn).近幾年的重要密碼會(huì)議中都有與其相關(guān)的論文[5-14].

對(duì)于如此重要的密碼體制，它的攻擊算法也有很多相關(guān)研究.如之前所說，Even-Mansour密碼體制的攻擊下界(攻擊所需要的時(shí)間復(fù)雜度與空間復(fù)雜度乘積)是已被證明的，但是這樣的界并不是緊的[15].該密碼體制最典型的一類攻擊方案研究是滑動(dòng)攻擊分析[16]，如扭式滑動(dòng)攻擊[17](slide with a twist attack).扭式滑動(dòng)攻擊通過搜索給定明文，在給定明文中找到滿足某些條件的明文對(duì)，我們稱其為滑動(dòng)對(duì).根據(jù)滑動(dòng)對(duì)，可以很容易恢復(fù)出對(duì)應(yīng)的密鑰.但是扭式滑動(dòng)攻擊要求給定明文的數(shù)量必須要達(dá)到明文空間的根號(hào)數(shù)量級(jí)，即無法通過少量明文恢復(fù)密鑰.為了解決這一問題，Dunkelman等人[18]在原攻擊基礎(chǔ)之上，提出了Slidex攻擊.新的攻擊可以在任意數(shù)量的給定明文的條件下實(shí)施，通過使用輔助數(shù)據(jù)來彌補(bǔ)明文數(shù)量的不足.

關(guān)于Even-Mansour密碼體制在密鑰泄露情況的攻擊算法，目前沒有相關(guān)的研究.直覺上來說，如果發(fā)生密鑰泄露，那么攻擊算法的下界應(yīng)當(dāng)會(huì)隨密鑰泄露的多少而進(jìn)行變化.本文中，首次提出對(duì)密鑰泄露情況下的Even-Mansour密碼體制選擇明文攻擊算法，同時(shí)給出攻擊算法的復(fù)雜度和實(shí)驗(yàn)時(shí)間與密鑰泄露情況的關(guān)系圖.然后，進(jìn)一步給出幾類變式Even-Mansour密碼體制的密鑰泄露攻擊算法.

1 理論基礎(chǔ)

1.1 Even-Mansour的定義及其模型假設(shè)

設(shè){0,1}n表示長度為n的二元字符串(比特串)，F(xiàn)表示對(duì){0,1}n的公共置換，F(xiàn)-1表示置換F的逆.則對(duì)于任意給定的字符串x∈{0,1}n，我們可以認(rèn)為可通過調(diào)用一個(gè)接口(Oracle)得到F (x)或F-1(x)，這樣的調(diào)用時(shí)間復(fù)雜度為1.密鑰K由2個(gè)子密鑰K1和K2構(gòu)成，每個(gè)子密鑰都是從密鑰空間{0,1}n隨機(jī)選取的n長比特串.另外，本文中用LSBm(x)表示比特串x的低位m比特(比特串右邊有效位)，MSBm(x)表示比特串x的高位m比特(比特串左邊有效位).

Even-Mansour體制由置換F和密鑰K=〈K1,K2〉構(gòu)成，設(shè)其明文輸入P∈{0,1}n，則其加密算法可以寫作：

其中⊕表示比特異或運(yùn)算.

其對(duì)應(yīng)的以密文為輸入的解密算法，可以寫作：

同時(shí)，設(shè)計(jì)者考慮2類攻擊.1)破解攻擊：攻擊者嘗試在不知道密鑰K的條件下給出密文C的對(duì)應(yīng)明文；2)偽造攻擊：攻擊者偽造出一個(gè)未被查詢過的明密文對(duì)(P,C)，使其滿足E(P)=C.

對(duì)于攻擊的復(fù)雜度我們需要從2方面考慮，其一為時(shí)間復(fù)雜度，即攻擊中訪問F -接口的次數(shù)，用T表示；其二為空間(數(shù)據(jù))復(fù)雜度，即攻擊中訪問E-接口的次數(shù)(因?yàn)樯傻拿髅芪膶?duì)會(huì)被保存)，用D表示.另外，攻擊的成功率定義為一次攻擊中輸出為正確結(jié)果的概率.

1.2 Even-Mansour密碼體制的攻擊下界

在文獻(xiàn)[2]中，Even和Mansour給出了對(duì)于Even-Mansour密碼體制的攻擊成功概率上界的嚴(yán)格證明.正如1.1節(jié)中假設(shè)，T次攻擊中訪問F -接口的次數(shù)，D為攻擊中訪問E-接口的次數(shù)，則攻擊的成功率應(yīng)為O (DT2n).則如果攻擊者希望攻擊成功的概率為一個(gè)不可忽略的常數(shù)，需要的時(shí)間空間復(fù)雜度需要滿足條件：DT=Ω(2n).

為了說明Even-Mansour密碼體制的安全性，我們需要證明對(duì)該密碼的破解攻擊和偽造攻擊都無法在多項(xiàng)式時(shí)間內(nèi)以不可忽略概率輸出結(jié)果.假設(shè)攻擊者構(gòu)造了破解攻擊算法A，其運(yùn)行時(shí)間為t(n)，攻擊成功率為ε(n)，其中t:N→N，且ε:N →[0,1].則攻擊者可以通過A的結(jié)果構(gòu)造偽造攻擊算法B.B的攻擊成功率為ε(n)t(n)，攻擊時(shí)間為t(n).這說明，若可以證明對(duì)Even-Mansour密碼體制的偽造攻擊無法在多項(xiàng)式時(shí)間內(nèi)完成，則對(duì)該體制的破解攻擊也無法在多項(xiàng)式時(shí)間內(nèi)完成[2].

引理1. 假設(shè)置換F和密鑰K都是隨機(jī)且均勻選取的，則Even-Mansour密碼體制的偽造攻擊成功概率的界為

其中,T為攻擊中訪問F -接口的次數(shù)，D為攻擊中訪問E-接口的次數(shù).

引理1的證明細(xì)節(jié)可以參考文獻(xiàn)[2].由引理1可知，如果攻擊者希望攻擊成功的概率為一個(gè)不可忽略的常數(shù)，時(shí)間空間復(fù)雜度需要滿足條件：DT=Ω(2n)，從而說明了該體制的安全性.

注意到，原始的證明中其實(shí)并未考慮到密鑰泄露的情況，但是從直覺上來看，當(dāng)Even-Mansour的密鑰空間為2n時(shí)，其對(duì)應(yīng)攻擊時(shí)間空間復(fù)雜度需滿足條件DT=Ω(2n)，那么如果密鑰泄露了m比特，此時(shí)其攻擊的時(shí)間空間復(fù)雜度應(yīng)當(dāng)滿足條件DT=Ω(2n-m)，因?yàn)槠涿荑€的實(shí)際長度只剩下了n-m比特.在之后的幾節(jié)中，我們給出對(duì)此類情況下的Even-Mansour密碼體制的攻擊算法，并且其理論時(shí)間空間復(fù)雜度與我們猜想的界正好吻合.

2 Slidex攻擊

2.1 攻擊過程說明

Slidex攻擊[18]為扭式滑動(dòng)攻擊[17]的改進(jìn)版本.扭式滑動(dòng)攻擊只能對(duì)數(shù)量級(jí)為2{(n+1)2}的給定明密文對(duì)進(jìn)行攻擊，一旦給定明密文數(shù)量未達(dá)到該數(shù)量級(jí)，則由于未能達(dá)到生日界，原先的攻擊無法成功恢復(fù)密鑰[19-21].Slidex攻擊在原先的攻擊基礎(chǔ)上添加了輔助數(shù)據(jù) ，其目的是通過輔助數(shù)據(jù)來增加置換的次數(shù)，以減少使用明密文對(duì)的個(gè)數(shù).

Slidex攻擊的攻擊思想為：假設(shè)攻擊者可以得到1對(duì)明文對(duì)，滿足

P⊕P*=K1⊕Δ，

此時(shí)，由Even-Mansour體制定義可以得到：

E(P)=F (P⊕K1)⊕K2=F (P*⊕Δ)⊕K2,

類似地，

E(P*)=F (P*⊕K1)⊕K2=F (P⊕Δ)⊕K2，

則有

E(P)⊕E(P*)=F (P⊕Δ)⊕F (P*⊕Δ),

此時(shí)有

E(P)⊕F (P⊕Δ)=E(P*)⊕F (P*⊕Δ).

由該關(guān)系，我們可以按如下步驟實(shí)現(xiàn)攻擊，對(duì)任意d≤n：

1) 對(duì)2(d+1)2條已知n比特明文P1,P2,…分別進(jìn)行2{(n+1)2}次加密操作；

2) 選擇任意2n-d個(gè)n比特?cái)?shù)Δ1,Δ2,…,Δn.對(duì)每個(gè)Δl以{Pi⊕Δl}i=1,2,…,2(d+1)2作為輸入，進(jìn)行置換操作，將計(jì)算結(jié)果(E(Pi)⊕F (Pi⊕Δl),i)存到Hash表，并以橫坐標(biāo)進(jìn)行排序；

3) 對(duì)Hash表中的每個(gè)碰撞，即滿足E(Pi)⊕F (Pi⊕Δl)=E(Pj)⊕F (Pj⊕Δl)的明文對(duì)(Pi,Pj)，驗(yàn)證K1=Pi⊕Pj⊕Δl，K2=E(Pi)⊕F (Pj⊕Δl)是否為所求密鑰.

2.2 攻擊有效性證明與復(fù)雜度分析式

由生日攻擊的擴(kuò)展情況[22-23]可知，在數(shù)據(jù)集中找到三元對(duì)(Pi,Pj,Δl) 滿足Pi⊕Pj⊕Δl=K1的概率為一個(gè)不可忽略的常數(shù).同時(shí)，對(duì)于任一明文碰撞對(duì)(Pi,Pj) 滿足E(Pi)⊕F (Pi⊕Δ)=E(Pj)⊕F (Pj⊕Δ)的概率為2-n，每一個(gè)Hash表共出現(xiàn)2d次碰撞，同時(shí)共有Hash表2n-d個(gè)，因此可以期望得到少量碰撞.由上文推導(dǎo)的關(guān)系可知，用來恢復(fù)密鑰的滑動(dòng)對(duì)就出現(xiàn)在這些碰撞里，對(duì)于得到的少量碰撞進(jìn)行密鑰驗(yàn)證K1=Pi⊕Pj⊕Δl,K2=E(Pi)⊕F (P⊕Δl)，如果驗(yàn)證成功就表示恢復(fù)密鑰成功.

考察攻擊的復(fù)雜度，我們從時(shí)間空間2方面分析.首先在時(shí)間復(fù)雜度方面，共使用置換操作T=2n-d·2(d+1)2次，其次在空間復(fù)雜度方面，共使用數(shù)據(jù)D=2(d+1)2條，因此有DT=2n+1.

3 Even-Mansour密碼體制的密鑰泄露攻擊

3.1 攻擊方案

假設(shè)在Even-Mansour加密模式中，密鑰K1高位k比特，即MSBk(K1)被泄露，從直覺上看，攻擊者掌握了更多的信息，對(duì)于原加密體制的攻擊，攻擊者需要利用已經(jīng)掌握的信息來減少攻擊的時(shí)間和空間復(fù)雜度.

為了方便說明，我們將比特串X∈{0,1}n寫作X=x‖y，其中x=MSBk(X)，y=LSBn-k(X).例如取n=8，k=4，X=11110000，則X=1111‖0000，其中x=1111，y=0000.

假設(shè)K1=δ‖ω，攻擊者預(yù)先知道δ，則具體攻擊方案如下：

1) 隨機(jī)選取2(n-k)2條n比特明文P1,P2,…,P2(n-k)2∈{0,1,…,2n-k-1}，并對(duì)所有明文進(jìn)行加密，得到C1,C2,…,C2(n-k)2；

2) 取Δ=δ‖0，對(duì){Pi⊕Δ}i=1,2,…,2(n-k)2進(jìn)行置換操作，將計(jì)算結(jié)果(E(Pi)⊕F (Pi⊕Δ),i)存到Hash表，并以橫坐標(biāo)進(jìn)行排序；

3) 對(duì)Hash表中的每個(gè)碰撞，即找到滿足E(Pi)⊕F (Pi⊕Δ)=E(Pj)⊕F (Pj⊕Δ)的明文對(duì)(Pi,Pj)，并對(duì)每個(gè)這樣的明文對(duì)驗(yàn)證K1=Pi⊕Pj⊕Δ，K2=E(Pi)⊕F (Pj⊕Δ)是否為所求密鑰.

3.2 攻擊有效性證明與復(fù)雜度分析

與第2節(jié)情況相同，攻擊需要找到滿足K1=Pi⊕Pj⊕Δ的明文對(duì)(Pi,Pj).考慮無重復(fù)元素集合A={Pi⊕Pj⊕Δ|1≤i

考察攻擊的復(fù)雜度，我們從時(shí)間空間2方面分析.首先在時(shí)間復(fù)雜度方面，共使用置換操作T=2(n-k)2次，其次在空間復(fù)雜度方面，共使用數(shù)據(jù)D=2(n-k)2條，因此有DT=2n-k.這一結(jié)果說明本算法將泄露密鑰后的Even-Mansour密碼體制的密鑰有效長度降低到n-k比特，這一結(jié)果也正好和密鑰泄露的長度造成的影響相吻合.

3.3 實(shí)驗(yàn)結(jié)果

圖3 32 b級(jí)Even-Mansour密碼攻擊時(shí)間比較

為了比較改進(jìn)攻擊和原攻擊之間的性能差異，我們分別針對(duì)16 b輸入和32 b輸入的Even-Mansour密碼體制進(jìn)行攻擊時(shí)間對(duì)比.實(shí)驗(yàn)中使用的計(jì)算機(jī)CPU為Intel?CoreTMi5-4590, 3.30 GHz，內(nèi)存為8 GB，代碼語言為C++.實(shí)驗(yàn)結(jié)果如圖2、圖3所示：

圖2 16 b級(jí)Even-Mansour密碼攻擊時(shí)間比較

圖2、圖3中，橫坐標(biāo)表示密鑰泄露的長度(單位：b)，縱坐標(biāo)表示攻擊實(shí)例所用的時(shí)間(單位：s).其中，圖2攻擊隨機(jī)實(shí)例個(gè)數(shù)為10萬個(gè)，圖3為1 000個(gè).由圖2、圖3可知，改進(jìn)后的攻擊在密鑰泄露時(shí)攻擊時(shí)間較原始攻擊大大縮短.同時(shí)，改進(jìn)攻擊的攻擊時(shí)間隨密鑰泄露長度增加呈指數(shù)級(jí)衰減.可以看出，實(shí)際實(shí)驗(yàn)結(jié)果并沒有理論結(jié)果率減速度快.理論結(jié)果中，每泄露1 b，攻擊時(shí)間折半，但在實(shí)驗(yàn)中需要2 b，攻擊時(shí)間達(dá)到原先一半.這一結(jié)果是由于攻擊中的時(shí)間不止是由置換的使用次數(shù)決定，還有一些代碼運(yùn)行中的轉(zhuǎn)化工作消耗時(shí)間，雖然置換次數(shù)減半，但是有些固定時(shí)間無法縮減.

4 模加Even-Mansour密碼體制的密鑰泄露攻擊

4.1 模加Even-Manosur密碼及其對(duì)應(yīng)攻擊

模加Even-Mansour密碼體制的形式為

其對(duì)應(yīng)的解密形式為

其中,F為n比特偽隨機(jī)置換，“+”表示模加運(yùn)算.在Biryukov等人[17]的論文中提到了對(duì)該體制的滑動(dòng)攻擊，該攻擊的攻擊思路如下：

假設(shè)攻擊者可以得到1對(duì)明文對(duì)(P,P*),滿足

P+P*=-K1+Δ，

此時(shí)，由Even-Mansour體制定義可以得到

AEM(P)=F (P+K1)+K2=

F (-P*+Δ)+K2.

類似地，

AEM(P*)=F (P*+K1)+K2=

F (-P+Δ)+K2，

則有

AEM(P)-AEM(P*)=

F (-P*+Δ)-F (-P+Δ),

此時(shí)有

AEM(P)+F (-P+Δ)=

AEM(P*)+F (-P*+Δ).

這種攻擊形式是和Slidex攻擊相似，唯一的不同之處在于攻擊中使用的明文之間的關(guān)系式不同.事實(shí)上，我們只需將Slidex攻擊Hash表中的元素由(E(Pi)⊕F (Pi⊕Δl),i)替換為(AEM(Pi)⊕F (-Pi⊕Δl),i)即可.但是對(duì)于該體制下的密鑰泄露攻擊，和第3節(jié)中的改進(jìn)Slidex攻擊卻有所不同.

4.2 模加Even-Mansour加密體制的密鑰泄露攻擊

如上文所說，對(duì)2種Even-Mansour加密體制的密鑰泄露攻擊，其不同之處來自于加密體制中采取的基本運(yùn)算的不同.原始體制中使用的異或運(yùn)算不會(huì)產(chǎn)生多余的進(jìn)位，因此考慮Δ的取值直接選擇泄露的密鑰部分和0的異或即可；而本節(jié)中的模加Even-Mansour加密體制使用模加運(yùn)算，因此難以避免計(jì)算中進(jìn)位的出現(xiàn)，針對(duì)這一點(diǎn)，我們需要對(duì)原有的方法進(jìn)行一些調(diào)整.

假設(shè)K1=δ‖ω，攻擊者預(yù)先知道δ，則具體攻擊方案如下：

1) 隨機(jī)選取2(n-k)2條n比特明文P1,P2,…,P2(n-k)2∈{0,1,…,2n-k-1}，并對(duì)所有明文進(jìn)行加密，得到C1,C2,…,C2(n-k)2；

2) 取Δ=(δ+1)‖0，對(duì){Pi⊕Δ}i=1,2,…,2(n-k)2進(jìn)行置換操作，將計(jì)算結(jié)果(E(Pi)⊕F (Pi⊕Δ),i)存到Hash表，并以橫坐標(biāo)進(jìn)行排序；

3) 對(duì)于Hash表中的每個(gè)碰撞，即滿足E(Pi)⊕F (Pi⊕Δ)=E(Pj)⊕F (Pj⊕Δ)的明文對(duì)(Pi,Pj)，驗(yàn)證K1=Pi⊕Pj⊕Δ，K2=E(Pi)⊕F (Pj⊕Δ)是否為所求密鑰.

4.3 攻擊有效性證明和復(fù)雜度分析

攻擊需要找到滿足K1=Δ-(Pi+Pj)的明文對(duì)(Pi,Pj).考慮無重復(fù)元素集合A={Δ-(Pi+Pj)|1≤i

該攻擊復(fù)雜度與4.2節(jié)中攻擊復(fù)雜度分析相同，因此這里省略.

4.4 實(shí)驗(yàn)結(jié)果

圖4，圖5結(jié)果與圖2，圖3類似.圖4攻擊實(shí)例有1萬個(gè)，圖5攻擊實(shí)例有1 000個(gè)，改進(jìn)攻擊時(shí)間隨密鑰泄露比特增加呈指數(shù)級(jí)衰減.由于計(jì)算機(jī)上模加時(shí)間明顯長于異或，因此圖4，圖5時(shí)間較圖3，圖4大幅增加.

圖4 16 b級(jí)模加Even-Mansour密碼攻擊時(shí)間比較

圖5 32 b級(jí)模加Even-Mansour密碼攻擊時(shí)間比較

5 對(duì)合Even-Mansour密碼體制的密鑰泄露攻擊

5.1 對(duì)合Even-Mansour密碼體制及其對(duì)應(yīng)攻擊

對(duì)合Even-Mansour密碼體制的形式為

其對(duì)應(yīng)的解密形式為

其中I為在長度為n的比特串上的對(duì)合運(yùn)算，它滿足條件：對(duì)x∈{0,1}n，I(I(x))=x.對(duì)該體制的原始攻擊在Dunkelman等人[17]的論文中已論述，該攻擊思路如下：

假設(shè)攻擊者可以得到1對(duì)明文對(duì)(P,P*),滿足

P⊕C*=K1⊕K2，

此時(shí)，

P⊕K1=C*⊕K2,

則由對(duì)合定義，可知

I (P⊕K1)=I-1(C*⊕K2).

由IEM定義，有

C=IEM(P)=I (P⊕K1)⊕K2，

P*=DI(C*)=I-1(C*⊕K2)⊕K1，

由此可得

C⊕K2=P*⊕K1，

即

P*⊕C=K1⊕K2=P⊕C*.

該攻擊的目標(biāo)是為了恢復(fù)K1⊕K2的值，攻擊者需要找到1對(duì)明文對(duì)(P,P*),滿足P⊕C*=K1⊕K2.這樣的明文對(duì)由上文的推導(dǎo)關(guān)系，需要滿足條件P⊕C=P*⊕C*.由于隨機(jī)選擇明文P對(duì)應(yīng)的密文C可以近似看作隨機(jī)比特串，因此其異或結(jié)果P⊕C也可以看作一個(gè)隨機(jī)比特串.因此由生日攻擊原理[22-23]，攻擊者通過使用2n2對(duì)明密文對(duì)(Pi,Ci)，可以找到極少量Pi⊕Ci的碰撞，然后從碰撞中通過驗(yàn)證P*⊕C=K1⊕K2，可以確定碰撞明文對(duì)是否為所求的滑動(dòng)對(duì).同時(shí)，考慮由擴(kuò)展的生日攻擊原理[24]，存在明文對(duì)(P,P*)滿足P*⊕C=K1⊕K2的概率是一個(gè)不可忽略的常數(shù).因此，該攻擊可以以不可忽略常數(shù)的概率恢復(fù)出K1⊕K2的值.

考察攻擊的復(fù)雜度，我們從時(shí)間空間2方面分析.首先在時(shí)間復(fù)雜度方面，共使用置換操作T=2n2次，其次在空間復(fù)雜度方面，共使用數(shù)據(jù)D=2n2條，因此有DT=2n.

5.2 對(duì)合Even-Mansour加密體制的密鑰泄露攻擊

假設(shè)K1⊕K2=δ‖ω，攻擊者預(yù)先知道δ，則具體攻擊方案如下：

1) 隨機(jī)選取2(n-k)2-1條n比特長明文P1,P2,…,P2(n-k)2∈{0,1,…,2n-k-1}，對(duì)所有明文進(jìn)行加密，得到C1,C2,…,C2(n-k)2；隨機(jī)選取2(n-k)2-1條n比特長密文C2(n-k)2+1,C2(n-k)2+2， …,C2(n-k)2+1∈{δ‖0,δ‖1,…,δ‖2n-k-1}，對(duì)所有密文進(jìn)行解密，得到P2(n-k)2+1,P2(n-k)2+2,…,P2(n-k)2+1.綜上，獲得明密文對(duì)(Pi,Ci)i=1,…,2(n-k)2+1.

2) 對(duì)i=1,…,2(n-k)2+1，計(jì)算(Pi⊕Ci,i)存到Hash表，并以橫坐標(biāo)進(jìn)行排序.

3) 對(duì)于Hash表中的每個(gè)碰撞，即滿足Pi⊕Ci=Pj⊕Cj的明文對(duì)(Pi,Pj)，驗(yàn)證Pi⊕Cj=K1⊕K2是否成立.

5.3 攻擊有效性證明和復(fù)雜度分析

攻擊需要找到滿足Pi⊕Cj=K1⊕K2的明文對(duì)(Pi,Pj).考慮無重復(fù)元素集合A={Pi⊕Cj|1≤i≤2(n-k)2

考察攻擊的復(fù)雜度，我們從時(shí)間空間2方面分析.首先在時(shí)間復(fù)雜度方面，共使用對(duì)合操作T=2(n-k)2+1次，其次在空間復(fù)雜度方面，共使用數(shù)據(jù)D=2(n-k)2+1條，因此有DT=2n-k+2.

5.4 實(shí)驗(yàn)結(jié)果

由于對(duì)合Even-Mansour密碼的攻擊與前述攻擊的攻擊方式大不相同，同時(shí)模擬的對(duì)合置換是通過大量隨機(jī)對(duì)換進(jìn)行模擬，因此時(shí)間較前4個(gè)實(shí)驗(yàn)大大縮短.其中，圖6的攻擊實(shí)例有10萬個(gè)，圖7攻擊實(shí)例有1 000個(gè)，可以看到，改進(jìn)攻擊性能在密鑰泄漏情況下優(yōu)于原始攻擊，同時(shí)攻擊時(shí)間隨密鑰泄露比特增加以指數(shù)級(jí)衰減.

圖6 16 b級(jí)對(duì)合Even-Mansour加密攻擊時(shí)間比較

圖7 32 b級(jí)對(duì)合Even-Mansour加密攻擊時(shí)間比較

6 結(jié)束語

分組密碼作為密碼學(xué)中重要的組成部分，在當(dāng)今網(wǎng)絡(luò)數(shù)據(jù)快速增長的時(shí)代背景中，為數(shù)據(jù)的安全性保護(hù)提供了堅(jiān)實(shí)的保障.Even-Mansour密碼體制是分組密碼中一個(gè)非常具有代表性的密碼結(jié)構(gòu).在對(duì)于其攻擊的研究中，考慮其由于密鑰結(jié)構(gòu)而產(chǎn)生的對(duì)應(yīng)攻擊很有意義.本文中介紹的攻擊技巧：在已知部分密鑰的選擇明文攻擊情況下，通過構(gòu)造明文來減少使用明文的個(gè)數(shù).這一方法其實(shí)也可以用到其他的滑動(dòng)攻擊或分組密碼的攻擊中.我們也非常期待文中介紹的攻擊技巧可以給其他密碼分析工作者提供一些密碼攻擊的思路.

[1]Even S, Mansour Y. A construction of a cipher from a single pseudorandom permutation[C]Proc of Int Conf on the Theory and Application of Cryptology. Berlin: Springer, 1991: 210-224

[2]Even S, Mansour Y. A construction of a cipher from a single pseudorandom permutation[J]. Journal of Cryptology, 1997, 10(3): 151-161

[3]Kilian J, Rogaway P. How to protect DES against exhaustive key search (an analysis of DESX)[G]LNCS 1109: CRYPT0 1996. Berlin: Springer, 2003: 252-267

[4]Kilian J, Rogaway P. How to protect DES against exhaustive key search (an analysis of DESX)[J]. Journal of Cryptology, 2001, 14(1): 17-35

[5]Andreeva E, Bogdanov A, Dodis Y, et al. On the Indifferentiability of Key-alternating Ciphers[M]Advances in Cryptology-CRYPTO 2013. Berlin: Springer, 2013: 531-550

[6]Barbosa M, Farshim P. The related-key analysis of feistel constructions[C]Proc of Int Workshop on Fast Software Encryption. Berlin: Springer, 2014: 265-284

[7]Bogdanov A, Knudsen L R, Leander G, et al. Key-alternating ciphers in a provable setting: Encryption using a small number of public permutations[C]Proc of Annual International Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2012: 45-62

[8]Cogliati B, Lampe R, Seurin Y. Tweaking even-mansour ciphers[C]Proc of Annual Cryptology Conf. Berlin: Springer, 2015: 189-208

[9]Dai Y, Seurin Y, Steinberger J, et al. Indifferentiability of iterated Even-Mansour ciphers with non-idealized key-schedules: Five rounds are necessary and sufficient[C]Proc of Annual International Cryptology Conf. Berlin: Springer, 2017: 524-555

[10]Dinur I, Dunkelman O, Keller N, et al. Key recovery attacks on 3-round Even-Mansour, 8-step LED-128, and full AES 2[C]Proc of Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2013: 337-356

[11]Dinur I, Dunkelman O, Keller N, et al. Key recovery attacks on iterated Even-Mansour encryption schemes[J]. Journal of Cryptology, 2016, 29(4): 697-728

[12]Dunkelman O, Keller N, Shamir A. Slidex attacks on the Even-Mansour encryption scheme[J]. Journal of Cryptology, 2015, 28(1): 1-28

[13]Lampe R, Patarin J, Seurin Y. An asymptotically tight security analysis of the iterated even-mansour cipher[C]Proc of Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2012: 278-295

[14]Mouha N, Luykx A. Multi-key security: The Even-Mansour construction revisited[C]Proc of Annual Cryptology Conf. Berlin: Springer, 2015: 209-223

[15]Biham E, Shamir A. Differential Cryptanalysis of the Data Encryption Standard[M]. Berlin: Springer, 2012

[16]Biryukov A, Wagner D. Slide attacks[C]Proc of Int Workshop on Fast Software Encryption. Berlin: Springer, 1999: 245-259

[17]Biryukov A, Wagner D. Advanced slide attacks[C]Proc of Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2000: 589-606

[18]Dunkelman O, Keller N, Shamir A. Minimalism in cryptography: The Even-Mansour scheme revisited[C]Proc of Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2012: 336-354

[19]Biham E. New types of cryptanalytic attacks using related keys[J]. Journal of Cryptology, 1994, 7(4): 229-246

[20]Biham E, Dunkelman O, Keller N. Improved slide attacks[C]Proc of Int Workshop on Fast Software Encryption. Berlin: Springer, 2007: 153-166

[21]Furuya S. Slide attacks with a known-plaintext cryptanalysis[C]Proc of Int Conf on Information Security and Cryptology. Berlin: Springer, 2001: 214-225

[22]Mathis F H. A generalized birthday problem[J]. SIAM Review, 1991, 33(2): 265-270

[23]Suzuki K, Tonien D, Kurosawa K, et al. Birthday paradox for multi-collisions[C]Proc of Int Conf on Information Security and Cryptology. Berlin: Springer, 2006: 29-40

[24]Wagner D. A generalized birthday problem[C]Proc of Annual Int Cryptology Conf. Berlin: Springer, 2002: 288-304