改進的縮減輪Crypton-256 分組密碼算法的中間相遇攻擊*

郝泳霖, 田呈亮, 袁 祺

1.密碼科學技術國家重點實驗室, 北京100878

2.青島大學計算機科學技術學院, 青島266071

3.中國科學院信息工程研究所信息安全國家重點實驗室, 北京100093

1 引言

分組密碼算法Crypton[1]于1998年被Lim 提出, 它也是高級加密標準(Advanced Encryption Standard, AES)的候選算法之一.分組長度128 比特, 密鑰長度可變, 最短64 比特, 最長256 比特.在FSE 1999 會議上, Lim 又提出了Crypton 的加強版[2], 對原版的S 盒和密鑰擴展方案進行了改進, 命名為Crypton v1.0 (由于本文的攻擊方法對Crypton 和Crypton v1.0 都有效, 在沒有特別說明的情況下, 我們將兩個版本統稱為Crypton).雖然Crypton 最終不敵Rijindael[3], 落選AES 標準算法, 但是Crypton 與最終的AES 標準算法有很多相似之處, 學術界對它在單密鑰和相關密鑰模型下的安全強度進行了相當多的研究.

在相關密鑰模型下, Wei 等人給出了9 輪Crypton 的相關密鑰不可能差分攻擊[4].在單密鑰模型下,早在1999年, D’Halluin 就給出了6 輪Crypton 的積分攻擊[5]; 2001年又出現了同樣輪數的不可能差分結果[6]; 2010年出現了7 輪不可能差分結果[7]; 2013年, Lin 等人給出了7 輪Crypton 的中間相遇攻擊[8]; Liu 等人改進了7 輪的攻擊結果并將輪數擴展到了8 輪、9 輪[9]; 最近, Li 和Jin 又給出了復雜度更低的8 輪攻擊[10].此外, Derbez 等人聲稱用自動化方法找到了11 輪中間相遇攻擊, 但并未提供攻擊過程和詳細參數[11]; Shakiba 等人還給出了Crypton-256 的Biclique 攻擊[12], 可以攻擊到全12 輪, 但這種方法需要窮搜全部密鑰空間, 并不是一個真正意義上威脅安全強度的密鑰恢復攻擊.根據以往的攻擊結果可見: 中間相遇攻擊是對Crypton 最行之有效的攻擊方法.

本文關注的是Crypton 在單密鑰模型下的中間相遇攻擊,詳細分析了Crypton 和Crypton v1.0 的算法結構和密鑰編排特征.通過構建性質優良的截斷差分特征、定制巧妙的密鑰猜測方案, 改進了Crypton的中間相遇攻擊結果.分析結果表明: 就抵抗中間相遇攻擊的能力而言, Crypton v1.0 并不優于Crypton.

中間相遇攻擊.中間相遇攻擊于1977年被Diffie 和Hellman 提出[13].在過去的十余年中, 中間相遇攻擊被廣泛運用于對分組密碼算法的安全性分析中, 并取得了很好的成果(如文獻[14–17]等).特別是對高級加密標準AES, 中間相遇攻擊的效率非常高: Demirci 和Sel?uk 在FSE 2008 上首次將中間相遇攻擊的思想運用于對AES 的安全性分析[18], 給出了對7 輪AES 的攻擊結果, 之后經過一系列的改進[19–24], 提出了多重集(multiset)、超級S 盒匹配(super-box)等新思想新技術, 使得攻擊輪數逐漸增加, 攻擊復雜度逐漸降低.目前, 對AES 最優的密鑰恢復攻擊結果是由Li 等人給出的[24], 他們構造出了6 輪區分器, 并利用了之前已有的密鑰分割技術[23]降低復雜度, 給出了對10 輪AES-256 的中間相遇攻擊, 數據/時間/存儲復雜度為2111/2253/2211.2.

本文貢獻.給出了3 個對Crypton-256 的中間相遇攻擊結果.借鑒Li 等人對10 輪AES 的中間相遇攻擊[24]的思想, 我們構造了一個6 輪截斷差分區分器, 給出了9 輪攻擊, 與之前的9 輪攻擊結果相比具有更低的時間和存儲復雜度; 用同樣的6 輪區分器, 我們給出了第一個10 輪中間相遇攻擊結果, 數據/時間/存儲復雜度為2113/2240.01/2241.59.接著, 利用Crypton 密鑰編排性質, 通過巧妙構建密鑰過濾方法[23], 提出了10 輪攻擊的改進版, 降低了存儲復雜度, 改進后的復雜度為2113/2245.05/2209.59.我們將本文的結果與之前所有單密鑰模型下的攻擊結果進行對比(表1)可見: 我們的10 輪中間相遇攻擊是目前對Crypton 可驗證的最好的密鑰恢復攻擊結果(考慮到Derbez 等人[11]聲稱的11 輪攻擊并未給出具體的攻擊過程和詳細參數, 其正確性不可驗證).

表1 單密鑰模型下對Crypton 的密鑰恢復攻擊Table 1 Key-recovery attacks on Crypton under single-key model

文章結構安排.第2 節簡要介紹了Crypton-256 的算法流程和攻擊中所需要用到的一些性質.在第3 節構造了Crypton-256 的6 輪區分器, 基于這一區分器, 我們在第4、5 節分別詳細描述了針對9 輪、10 輪Crypton-256 的中間相遇攻擊, 其中第5 節包含基本攻擊和改進攻擊兩個版本.最后, 我們在第6 節總結全文.

2 預備知識

本節第一部分簡要介紹Crypton-256 的算法基本流程, 更多細節請參考原始文獻[1,2]; 第二部分介紹中間相遇攻擊中需要用到的概念和性質.首先, 對常用的運算的符號做一說明: 按位與(AND)運算用“∧” 表示1在不會引起誤會的情況下, 為了使公式簡潔, 有時會省略, 如xy 等價于x ∧y.; 按位異或符號為“⊕”; 字符串的級聯運算用“∥”.

2.1 Crypton-256 簡介

與AES 相同, Crypton 的分組長度為128 比特, 采用SPN 結構進行設計.每個128 比特分組可以看成16 個字節組成的4×4 矩陣, 每個字節的編號如下:完整的Crypton 共有12 輪, 每輪由以下四種變換構成:

非線性代換γ.使用2 個8 比特S 盒S0,S1, 對式(1)的每一個字節進行替換, 其中S0,S1滿足關系S0=且具有與AES 的S 盒相同的性質.

性質1 [1]任意給定非零的輸入輸出差分?in,?out∈F28{0}, 則平均只有一個解x ∈F28滿足方程Si(x)⊕S(x ⊕?in)=?out.

比特置換 π.對式(1)中矩陣A 的每一列進行線性變換, 共有四種可能的線性列變換, 記作π0,···,π3.將A 的第i 列記作Ai= (a4i,a4i+1,a4i+2,a4i+3)T.在偶數輪(2,4,··· ,12)中, π(A)=(π3(A3),π2(A2),π1(A1),π0(A0)), 奇數輪(1,3,··· ,11)中, π(A)=(π0(A3),π3(A2),π2(A1),π1(A0)).由于我們只需要用到列變換 π0的性質, 將 π0的具體運算介紹如下: 令 (b0,b1,b2,b3)T=π0((a0,a1,a2,a3)T), 則

其中m0=0xfc, m0=0xf3, m0=0xcf, m3=0x3f 為常數.通過簡單的計算可以得到π0具有性質2.

性質2[24]設(b0,b1,b2,b3)T= π0((a0,a1,a2,a3)T)并令a2= a3= b3= 0, 則a0∥a1共有28個可能值.

π0,··· ,π3的分支數均為4, 具有如下性質3.

性質3[24]在πi的8 個輸入/輸出字節中, 如果已知其中的5 個, 那么剩下的3 個也可以唯一地確定出來.

置換τ.類似于矩陣轉置, 將矩陣中的元素位置做如下變換

密鑰加σ.σK即為令中間狀態的16 個字節與密鑰K 進行按位異或(XOR)操作, 這與AES 的輪密鑰加(AddRoundKey, ARK)是完全一樣的.

在加密流程開始之前, Crypton-256 密鑰擴展方案會將256 比特的主密鑰K 擴展為13 個128 比特的子密鑰k0,··· ,k12.

對于輪數r = 1,··· ,12, 我們定義相應的輪函數ρr(·)= σkr?τ ?π ?γ(·), 進一步定義線性變換Φ(·)=τ ?π ?τ(·).從而, 由明文P 開始, 通過r 輪Crypton-256 加密得到密文C 的完整流程可以表示為

在加密過程中, 所有的128 比特中間狀態(P,C 除外)我們都用小寫字母來表示, 我們約定σkr輸出的128 比特狀態為xr, 而ρr中γ 的輸出為yr?1, τ 的輸出為wr?1(r =1,··· ,12), 即

任一狀態x 的第i(i ∈[0,15])個字節用x[i]表示, 第i 到j 字節用x[i,··· ,j]表示, 編號與式(1)一致.

密鑰擴展方案.對于256 比特主密鑰K, Crypton-256 首先對其進行非線性變換, 得到一個新的256比特密鑰, 由于這個非線性變換是1-1 映射, 所以我們依然用K 來表示.子密鑰k0和k1分別對應K的高位128 比特及低位128 比特, 即K = k0∥k1.然后, 對于i = 1,··· ,6, 子密鑰k2i(k2i+1)可以由k2i?2(k2i?1)通過循環移位和與輪常數異或這兩種簡單的操作而完全確定, 即

性質4[1,2]Crypton-256 的子密鑰k0,··· ,k12滿足: 對于任意i ∈[0,6](i ∈[0,5]), 知道k2i(k2i+1)就完全可以推出全部的k0,k2,··· ,k12(k1,k3,··· ,k11).而且, 知道k2i(k2i+1)的一個字節, 一定可以唯一確定出k0,k2,··· ,k12(k1,k3,··· ,k11)的一個字節.

性質4 對于Crypton 和Crypton v1.0 都是成立的, 但具體到密鑰字節的位置, 二者略有差異, 我們的中間相遇攻擊需要利用Crypton 和Crypton v1.0 的子密鑰之間的一些具體關系, 分別表述為性質5 和性質6, 這些性質可以幫助我們降低中間相遇攻擊的復雜度.

性質 5[1]在 Crypton 中, 已知 k5[0,··· ,7]可以推出 k1[0,7,9,10,11,12,13,14]; 已知k4[4,7,10,13], 可以推出k0[0,··· ,3].

性質6[2]在Crypton v1.0 中,已知k5[0,··· ,7]可以推出k1[2,3,5,7,8,9,12,14];已知k4[2,4,9,15]可以推出k0[0,··· ,3].

2.2 中間相遇攻擊相關概念

定義1 (σ 集)[18]一個σ 集是由256 個128 比特中間狀態所構成的集合.中間狀態的1 個字節取遍全部256 個可能值(稱為“活躍字節”), 其余15 個字節取相同的常值(稱為“非活躍字節”).

定義2 (超級S 盒)[24]考慮Crypton 加密中的如下流程:

整個過程等價于并行如下4 個超級S 盒SSB0,··· ,SSB3:

其中超級S 盒SSBi需要知道4 個密鑰字節kr[i,i+4,i+8,i+12]才能進行, 它可以看作是32 比特到32 比特的S 盒運算.根據性質1, Crypton 的超級S 盒具也有如下性質7.

性質7[24]給定非零的輸入盒輸出差分?in,?out∈F232{0}, 平均只有一個解滿足方程SSBi(x)⊕SSB(x ⊕?in)=?out.

3 Crypton-256 的六輪區分器

借鑒之前AES-256 的6 輪區分器構造方法[24], 我們構造了Crypton-256 的6 輪截斷差分區分器.根據性質3, 我們可以證明第6 輪中間狀態字節滿足如下關系

定義字節ein,eout如下

則ein,eout滿足關系

根據性質5 和性質6, 已知k5[0,··· ,7]可以推出k1[12], 因此我們可以構造圖1 所示的截斷差分區分器, 該區分器對于Crypton 和Crypton v1.0 都有效.(注: 本文所有圖中, 黑色表示差分非零的字節, 陰影部分表示需要通過猜測或計算得到的密鑰字節).為了證明構造該區分器的存儲復雜度上界, 我們證明了如下定理1, 該定理的證明綜合運用了高效差分枚舉技術[22]和密鑰過濾技術[23].

定理1令為w0[12]位置活躍的σ 集且其中的元素滿足: 對t ∈[0,255], 有考慮對σ 集的前33 個元素(w0,··· ,w32)進行6 輪加密得到一個256 比特序列如果該σ 集中存在一對元素滿足圖1 所示的截斷差分, 那么對應的256比特序列只有2240個可能的取值.

圖1 本文的中間相遇攻擊中所使用的6 輪區分器Figure 1 6-round distinguisher used in proposed MITM attacks

證明:首先, 我們要證明: 知道如下46 個字節的信息就可以計算出序列

對于固定的i,我們將任意中間狀態的差分xm⊕xi表示為?xm(m ∈[0,255]).在第1 輪,可以在已知的情況下通過等式顯式地計算出來.由于已知, 我們可以根據計算由于可以進一步通過線性變換σk2?τ ?π 得到差分[3,7,11,15].類似地, 我們可以在已知[3,7,11,15]的情況下得到由于和都是已知的, 我們可以推出狀態值和再通過密鑰k4進行1輪加密得到和已知和k5[0,··· ,7], 我們就能得到[0,··· ,7]和[0,··· ,7].又因為k6[0,1]可以通過k4得到(性質4), 我們又可以進一步進行部分加密得到[0,1]和[0,1]最終獲得根據式(3), 我們知道對m ∈[1,32]恒成立, 這就證明了式(4).

如果對固定的i 做一限制: wi屬于某狀態對(wi,wj)滿足圖1 的截斷差分特征.可以進一步證明:只需知道如下式(5)中的33 個字節的信息, 我們就可以確定式(4)的全部信息

我們從加密方向推導.由于(wi,wj)滿足圖1 的截斷差分傳播, 因此知道就足以求解出差分再知道了式(5)的我們就可以計算出并進一步得到差分

4 9 輪Crypton-256 的中間相遇攻擊

我們將第3 節的6 輪區分器上擴1 輪, 下擴2 輪, 給出了9 輪Crypton-256 的中間相遇攻擊.擴展之后的截斷差分特征見圖2, 明文對(P,P′)符合該截斷差分特征的概率為2?144.攻擊過程分為預計算和線上兩個階段, 具體步驟如下.

預計算階段.在預計算階段, 我們構建2 個查找表T0,T1.其中T0存儲著2240序列及能提高攻擊成功率的其他信息; 表格T1可以進一步降低線上階段的時間復雜度.具體步驟如下:

(1)將T0初始化為空.對全部2128個k4可能值, 我們做如下步驟:

(a)根據k4, 推出k6.

(b)通過以下步驟構建臨時查找表T2:

i.對于y5[0,··· ,7]的所有可能值, 根據k6向前計算得到y6[0,1];

ii.根據性質2, 確定出28個?y6[0,1]值滿足:

iii.根據已知信息向后計算得到x5[0,··· ,7]和?x5[0,··· ,7];

iv.將得到的x5[0,··· ,7]存儲在T2(?x5[0,··· ,7])中; 對于每個?x5[0,··· ,7](共264個),平均有28可能的x5[0,··· ,7]被保存下來.

(c)再通過以下步驟構建臨時查找表T3:

i.對?y2[3,7,11,15]∥?x5[0,··· ,7]的全部296個可能值, 推出對應的差分?x3∥?y4;

ii.根據性質7 和密鑰k4, 我們平均可以得到一個解x3∥y4滿足差分條件?x3∥?y4;

iii.將x3∥?x5[0,··· ,7]存儲在T3(?y2[3,7,11,15])分量中, 每個?y2[3,7,11,15](共232個)對應264個x3∥?x5[0,··· ,7].

(d)對每個?y1[12]∥x2[3,7,11,15](共240個), 我們通過查找表T2和T3逐步構建出T0:

i.通過k2推出k4(性質5)并進一步通過部分解密y1[12]∥x1[12];

ii.根據已知的y1[12]和?y1[12]推出?x2[3,7,11,15]并進一步根據已知的x2[3,7,11,15]得到?y2[3,7,11,15];

iii.查詢T3(?y2[3,7,11,15]), 可以平均得到264個對應的x3∥?x5[0,··· ,7];

iv.對每一個x3∥?x5[0,··· ,7], 通過查詢T2找到對應的28個x5[0,··· ,7].由于k4是已知的, 我們可以從x3加密到w4, 再根據k5[0,··· ,7]得到x5[0,··· ,7];

v.在通過k5[0,··· ,7]推出k1[12]之后, 我們可以通過對y1[12]進行部分解密得到w0[0]從而構建出序列

vi.通過k4推出k0并將字符串存儲在表格T0中.

(2)將T1初始化為空, 定義集合λ 如式(6)

進行如下步驟:

(a)對密鑰u9[λ]||u8[0,4,8]全部2120個可能值和的296個可能值, 我們計算相應的eout;

(b)將eout存儲在中.

線上階段.首先要找到滿足圖2 差分特征的明文對, 從而構造出相應的σ 集, 再進一步通過密鑰猜測和部分加解密得到對應的序列最后通過預計算階段構建的查找表T0確定取遍所有可能值, 其余12 個字節取相同的常值.這樣每個結構體中都有個明文對滿足截斷差分特征的起始部分, 共有281+63= 2144.由于整個截斷差分的概率為2?144, 平均有1個明文對滿足圖2 的要求.

(2)在每個結構體內部選擇滿足?C[12,··· ,15]= 0 的明文對, 這是一個32 比特的過濾器, 共有2112個明文對(P,P′)被保留了下來.

(3)對每個保留下來的(P,P′)進行如下操作:

(a)猜測?w0[12]并假定?w0[0,4,8]= 0, 從而推出差分?y0[0,··· ,3], 再結合已知的差分?x0[0,··· ,3]= ?P[0,··· ,3], 我們平均可以得到1 個符合上述差分條件的x0[0,··· ,3]∥y0[0,··· ,3](性質1).根據已知的P[0,··· ,3]∥x0[0,··· ,3], 我們進一步推出k0[0,··· ,3];

(b)猜測?y7[0,1,2]并假定?y7[3,··· ,15]= 0, 然后線性求出差分?x8.再根據密文的差分得到?y8.對于?x8[λ]∥?y8[λ], 我們平均可以得到1 個符合差分條件的x8[λ]∥y8[λ](性質1, λ 定義見式(6)); 又根據x9= τ ?π ?τ(C)可以線性推出以及密鑰

(c)猜測密鑰u8[0,1,2], 由于已知k0[0,··· ,3], 我們可以從P 出發得到w0[0,4,8,12].將w0[0]賦值為0,··· ,32, 通過部分解密確定出對應的P0,··· ,P32以及密文C0,··· ,C32; 再通過已知的u9[λ]||u8[0,4,8]和(由密文得到, t = 0,··· ,32), 我們可以獲得以及對應的序列

(d)查詢T0, 看是不是在T0中, 如果存在, 則u9[λ]∥u8[0,4,8]為正確的密鑰; 否則,返回步驟(a); 如果窮舉?w0[0]∥?y7[0,1,2]∥u8[0,1,2]的全部256個可能值仍未找到正確密鑰, 則換一個新的明文對重新開始步驟(a).

(4)在獲取了u9[λ]∥u8[0,1,2]之后, 我們窮搜剩余的136 比特密鑰u9[3,7,11,15]∥u8[3,··· ,15]從而恢復出256 比特的主密鑰K.

復雜度分析.預計算階段, 構造T2需要28×(8+2)=280次加密; T2包含264+8=272條記錄.構造出正確的序列和密鑰.具體步驟如下:

(1)構造281個明文結構體并獲得它們對應的密文.每個結構體中含有232個明文使得P[0,··· ,3]T3需要296次加密操作, 最終的規模也是296條記錄.步驟(d)需要240×28×264×33 ≈2117.05次加密.因此, 預計算階段的時間復雜度為2128×(280+296+2117.05)≈2245.05; 查找表T0包含2240條記錄,每條記錄占36 個字節的存儲空間, 相當于2240×36/16 ≈2241.17個128 比特分組, 這也是整個攻擊的存儲復雜度.攻擊的時間復雜度由線上階段的步驟3.(c)決定, 具體值為2112×28×224×224×33 ≈2173.05.數據復雜度為281×232=2113.錯誤的密鑰通過3.(d)的概率僅為2240×2?8×36=2?48, 故該攻擊的成功概率為1 ?2?48.

圖2 攻擊9 輪Crypton-256 所用到的截斷差分特征Figure 2 Truncated differential characteristics for attacking 9-round Crypton-256

5 10 輪Crypton-256 的中間相遇攻擊

將第4 節的攻擊向下擴展1 輪就可以得到10 輪Crypton-256 的中間相遇攻擊.我們首先在第5.1 節介紹10 輪基本攻擊, 然后在第5.2 節介紹10 輪改進攻擊.改進攻擊通過將基本攻擊拆分成多個“弱密鑰” 攻擊, 從而降低了攻擊的存儲復雜度, 這一方法之前曾在部分文獻中被應用于對AES 的中間相遇攻擊[23,24].10 輪攻擊的截斷差分特征見于圖3.

5.1 基本攻擊

預計算階段.10 輪攻擊的預計算階段和9 輪基本是一樣的, 只是將9 輪預計算階段的步驟1.(c).vii替換為如下形式:

? 通過k4推出k10并將存儲于T0中;這一變化使得10 輪攻擊的成功概率大幅度提升.

線上階段.10 輪攻擊中找到符合圖3 截斷差分特征的消息對的過程比較復雜, 具體步驟如下:

圖3 攻擊10 輪Crypton-256 所使用的差分特征Figure 3 Truncated differential characteristics for attacking 10-round Crypton-256

(1)首先構造與9 輪攻擊相同的281個明文結構體并獲取相應密文, 共得到了2144滿足截斷差分特征的明文對(P,P′).

(2)對全部2144個明文對(P,P′)進行如下操作:

(a)猜測差分?y8[λ]并求出?x9; 通過密文差分?C 推出?y9, 對接差分(?x9,?x9), 根據S 盒的性質1 平均可以確定出1 個x9∥y9滿足差分條件.由于知道了y9和C, 我們可以得到整個k10也就知道了k0(性質4).用k0對明文對部分加密得到?w0, 如果差分?w0[0,4,8]0, 則說明之前猜測的?y8[λ]是錯誤的, 這是一個24 比特的過濾器.由于?y8[λ]有96 比特, 所以通過這一步我們共得到了296?24=272個候選的k10及與之相應的k0;

(b)對性質2 中的28個可能的?y6[0,1]進行部分加密得到?x7; 再通過已知的k10推出k8.由于?x7∥k8∥?y8[λ]都是已知的, 所以根據性質7, 平均可以得到一個解x7[λ]∥y8[λ], 又x9也是已知的, 我們可以恢復出密鑰u9[λ]; 用k0對明文P 進行部分加密得到w0, 依次令w0[12]=0,··· ,32, 再部分解密得到σ 集前33 個元素對應的明文P0,··· ,P32和相應的密文C0,··· ,C32;

(c)對(a)中得到的272個k10, 推出相應的k8和等價密鑰u8, 根據已知的對密文進行部分解密得到圖3 的查詢預計算表獲得相應的并最終得到序列檢測是否在T0中, 如果在, 則繼續進行到步驟3.

(3)對于已經得到的密鑰u9[λ]∥k10, 窮搜剩余的u9[3,7,11,15]確定出全部256 比特主密鑰K.

復雜度分析.預計算階段的時間復雜度仍為2245.05, T0的中仍然是含有2240條記錄, 但每條記錄的大小由36 字節增加到48 字節, 因此存儲復雜度相應增加到了2240×48/16 ≈2241.59.線上階段的步驟1 復雜度為232+81= 2113.對于全部2144個明文對中的每一個, 執行步驟2.(a)的復雜度為296; 步驟2.(b)和2.(c)分別為272+8= 280和272+8×33 ≈285.04.因此線上階段步驟2 的復雜度為2144×(296+280+285.04)≈2240.01.步驟3 的復雜度僅為232.所以, 線上階段的整體時間復雜度由步驟2 決定, 為2240.01.整個攻擊需要232+81= 2113個明文, 所以數據復雜度仍為2113.對于成功概率, 正確的明文對和正確的密鑰通過步驟2 的概率為1; 錯誤密鑰通過步驟2.(a)的概率為2?24, 通過2.(c)的概率為2240×2?8×(32+16)= 2?264.因此, 整個攻擊的成功概率為1 ?2?288.綜上, 10 輪Crypton-256 的基本中間相遇攻擊的數據/時間/空間復雜度為2113/2240.01/2241.59/, 成功概率高達1 ?2?288.

5.2 改進攻擊

借鑒之前AES 攻擊的方法[23,24], 可以將基本攻擊密鑰猜測空間劃分成若干子空間, 對每個子空間分別進行攻擊, 從而降低整個攻擊的存儲復雜度.而Crypton-256 的密鑰擴展方案是線性的, 比AES 更加簡單, 更便于我們劃分密鑰空間, 實現時間和存儲的折中.

改進攻擊中, 預計算階段不再構建T0, 只構建T1, 詳細步驟見第4 節.線上階段步驟如下:

(1)與基本攻擊(第5.1 節)相同, 通過281個明文結構體獲取2144個明文對(P,P′)滿足圖3 的差分特征.

(2)對232個可能的k4[i0,··· ,i3]分別進行如下步驟:

注:對Crypton[1], 取(i0,··· ,i3)= (4,7,10,13)(性質5); 而對于Crypton v1.0[2], 則取(i0,··· ,i3)=(2,4,9,15)(性質6).

(a)猜測k4的其余12 個字節, 根據已知的k4用第4 節預計算步驟1 的方法構建查找表其中包含了2208個

(b)通過k4求出k0(性質4), 再對281個明文結構體進行部分加密得到w0[0,4,8,12], 并確定出滿足?w0[0,4,8]= 0 的明文對.這是一個24 比特的過濾器, 平均每個結構體有263?24=239個消息對被保留下來, 總共剩余2120個;

(c)通過k4求出k10及等價密鑰u10, 對每個結構體中剩余的239個明文對所對應的密文進行部分解密得到并確定出其中符合差分條件的明文對.這是一個32比特過濾器, 平均每個結構體剩余239?32=27個明文對, 共剩余288個;

(d)對全部的288個剩余明文對(P,P′)進行如下操作:

i.通過k4求出k8和k10, 對密文進行部分解密得到x9和?y8[λ].對?y6[0,1]的28個可能值(性質2)計算?x7.由于k8是已知的, 對每個?x7∥k8∥?y8[λ]平均可以求得一個x7[λ]∥y8[λ](性質7), 進而可以根據已知的y8[λ]和x9求解出密鑰u9[λ];

ii.用k0對明文進行部分加密得到w0, 再通過改變w0[12]的值和部分解密, 獲取σ 集前33 個元素對應的明文P0,··· ,P32及其密文C1,··· ,C32;

iii.對t = 0,··· ,32, 我們通過k10∥u9[λ]對密文進行部分解密得到通過查詢得到相應的及序列再并進一步計算出差分查詢看是否存在, 存在則說明密鑰k4∥u9[λ]是正確的.

(3)完成上述步驟之后, 平均只能得到1 個正確的密鑰候選k4∥u9[λ], 只需要窮舉剩余的232個u9[3,7,11,15]即可恢復全部256 比特主密鑰K.

復雜度分析.改進攻擊的存儲復雜度由決定, 為2208×48/16=2209.59.而構建的時間復雜度是構建T0的2?32,而構建T0的時間復雜度為2245.05,所以構建一個的復雜度2245.05?32=2213.05,所以步驟2.(a)的時間復雜度為232×2213.05= 2245.05, 這也是整個改進攻擊的時間復雜度.錯誤密鑰通過步驟2.(e).iii 的概率為2208×2?8×(32+16)= 2?276, 所以攻擊的成功概率為1 ?2?276.數據復雜度保持不變, 仍為2113.

6 結論

本文借鑒了之前AES 中間相遇攻擊的技術[23,24], 通過構造6 輪截斷差分區分器, 給出了對9 輪Crypton-256 的中間相遇攻擊.與之前的9 輪攻擊相比, 我們的結果具有更低的時間和存儲復雜度.我們還首次給出了10 輪Crypton-256 的中間相遇攻擊結果, 這是目前對Crypton-256 可驗證的最好的攻擊結果.特別地, 10 輪Cypton-256 的從攻擊的時間和存儲復雜度上看都略低于10 輪AES-256 的同類攻擊, 從一定程度上反映出AES-256 在安全強度上可能略優于Crypton-256.我們的攻擊方法對原版Crypton[1]和改進版Crypton v1.0[2]同樣有效.