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

郝泳霖, 田呈亮, 袁 祺

1.密碼科學(xué)技術(shù)國家重點實驗室, 北京100878

2.青島大學(xué)計算機(jī)科學(xué)技術(shù)學(xué)院, 青島266071

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

1 引言

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

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

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

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

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

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

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

2 預(yù)備知識

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

2.1 Crypton-256 簡介

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

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

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

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

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

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

π0,··· ,π3的分支數(shù)均為4, 具有如下性質(zhì)3.

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

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

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

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

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

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

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

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

性質(zhì)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)的一個字節(jié), 一定可以唯一確定出k0,k2,··· ,k12(k1,k3,··· ,k11)的一個字節(jié).

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

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

性質(zhì)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 中間相遇攻擊相關(guān)概念

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

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

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

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

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

3 Crypton-256 的六輪區(qū)分器

借鑒之前AES-256 的6 輪區(qū)分器構(gòu)造方法[24], 我們構(gòu)造了Crypton-256 的6 輪截斷差分區(qū)分器.根據(jù)性質(zhì)3, 我們可以證明第6 輪中間狀態(tài)字節(jié)滿足如下關(guān)系

定義字節(jié)ein,eout如下

則ein,eout滿足關(guān)系

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

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

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

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

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

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

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

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

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

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

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

(a)根據(jù)k4, 推出k6.

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

i.對于y5[0,··· ,7]的所有可能值, 根據(jù)k6向前計算得到y(tǒng)6[0,1];

ii.根據(jù)性質(zhì)2, 確定出28個?y6[0,1]值滿足:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

進(jìn)行如下步驟:

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

(b)將eout存儲在中.

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

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

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

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

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

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

(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]從而恢復(fù)出256 比特的主密鑰K.

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

(1)構(gòu)造281個明文結(jié)構(gòu)體并獲得它們對應(yīng)的密文.每個結(jié)構(gòu)體中含有232個明文使得P[0,··· ,3]T3需要296次加密操作, 最終的規(guī)模也是296條記錄.步驟(d)需要240×28×264×33 ≈2117.05次加密.因此, 預(yù)計算階段的時間復(fù)雜度為2128×(280+296+2117.05)≈2245.05; 查找表T0包含2240條記錄,每條記錄占36 個字節(jié)的存儲空間, 相當(dāng)于2240×36/16 ≈2241.17個128 比特分組, 這也是整個攻擊的存儲復(fù)雜度.攻擊的時間復(fù)雜度由線上階段的步驟3.(c)決定, 具體值為2112×28×224×224×33 ≈2173.05.數(shù)據(jù)復(fù)雜度為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 節(jié)的攻擊向下擴(kuò)展1 輪就可以得到10 輪Crypton-256 的中間相遇攻擊.我們首先在第5.1 節(jié)介紹10 輪基本攻擊, 然后在第5.2 節(jié)介紹10 輪改進(jìn)攻擊.改進(jìn)攻擊通過將基本攻擊拆分成多個“弱密鑰” 攻擊, 從而降低了攻擊的存儲復(fù)雜度, 這一方法之前曾在部分文獻(xiàn)中被應(yīng)用于對AES 的中間相遇攻擊[23,24].10 輪攻擊的截斷差分特征見于圖3.

5.1 基本攻擊

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

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

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

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

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

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

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

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

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

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

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

5.2 改進(jìn)攻擊

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

改進(jìn)攻擊中, 預(yù)計算階段不再構(gòu)建T0, 只構(gòu)建T1, 詳細(xì)步驟見第4 節(jié).線上階段步驟如下:

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)論

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