Crypton算法的不可能差分分析

崔競一 郭建勝 劉翼鵬

(解放軍信息工程大學(xué) 鄭州 450001)

?

Crypton算法的不可能差分分析

崔競一 郭建勝 劉翼鵬

(解放軍信息工程大學(xué) 鄭州 450001)

(xd_cjy@126.com)

Crypton算法是基于Square算法設(shè)計(jì)的SPN結(jié)構(gòu)類密碼算法，由于其具備良好的軟硬件性能而引起了廣泛的關(guān)注.對Crypton分組密碼算法在不可能差分分析下的安全性進(jìn)行了研究.通過分析Crypton算法擴(kuò)散層的性質(zhì)，指出了現(xiàn)有7輪Crypton算法不可能差分分析中存在的問題，結(jié)合快速排序、分割攻擊與早夭技術(shù)對7輪Crypton算法的不可能差分分析進(jìn)行了改進(jìn)，降低了其數(shù)據(jù)復(fù)雜度與時(shí)間復(fù)雜度；同時(shí)，通過并行使用4條不可能差分區(qū)分器，結(jié)合密鑰擴(kuò)展算法的性質(zhì)給出了7輪Crypton算法的多重不可能差分分析結(jié)果，恢復(fù)了算法的主密鑰；最后，在7輪Crypton算法的不可能差分分析的基礎(chǔ)上向后拓展1輪，給出了8輪Crypton-256算法的不可能差分分析，恢復(fù)了其主密鑰，其數(shù)據(jù)復(fù)雜度為2103個(gè)選擇明文，時(shí)間復(fù)雜度為2214次8輪Crypton加密，存儲(chǔ)復(fù)雜度為2154.4B.研究結(jié)果表明:結(jié)合算法的性質(zhì)及多種技術(shù)給出了Crypton算法目前最優(yōu)的不可能差分分析結(jié)果.

分組密碼；密碼分析；Crypton；不可能差分分析；早夭技術(shù)

AES加密標(biāo)準(zhǔn)面向全球征集了15個(gè)候選算法[1]，Crypton分組密碼算法[2]就是其中之一.Crypton算法是基于Square算法[3]設(shè)計(jì)的，由于其具有很多優(yōu)點(diǎn)：使用SPN結(jié)構(gòu)滿足加脫密結(jié)構(gòu)相似，具有良好的可證明安全性，同時(shí)具有良好的并行能力，能夠廣泛適用于各類軟硬件環(huán)境，從而受到廣大學(xué)者的關(guān)注.Crypton算法共有2個(gè)版本，通常稱作Crypton v0.5[4]與Crypton v1.0[2].設(shè)計(jì)者對Crypton v0.5的密鑰擴(kuò)展算法與S盒的設(shè)計(jì)中存在的缺陷進(jìn)行改進(jìn)后提出了Crypton v1.0.隨著物聯(lián)網(wǎng)技術(shù)與RFID技術(shù)的發(fā)展，對輕量級密碼算法的需求日益增加，Lim等人[5]于2006年參照Crypton算法的設(shè)計(jì)思路，設(shè)計(jì)提出了輕量級分組密碼算法mCrypton.人們針對Crypton算法與mCrypton算法給出了許多分析結(jié)果.1999年Seki等人[6]給出了Crypton算法的不可能差分分析結(jié)果；2000年Minier等人[7]給出了Crypton算法的猜測攻擊；2001年Cheon等人[8]給出了改進(jìn)不可能差分分析結(jié)果；2003年Kim等人[9]給出了8輪Crypton算法截?cái)嗖罘址治鼋Y(jié)果；2010年Mala等人[10]利用不可能差分給出了7輪Crypton算法的分析結(jié)果；2011年Wei等人[11]給出了Crypton算法的相關(guān)密鑰不可能差分分析結(jié)果；2013年Kang等人[12]給出了Crypton-192256算法與mCrypton-96128算法的碰撞攻擊；2014年Song等人[13]給出了全輪Crypton-256算法與mCrypton-128算法的Biclique攻擊結(jié)果，同時(shí)Hao等人[14]給出了mCrypton算法在中間相遇攻擊下的安全性研究結(jié)果；2015年Shakiba等人[15]進(jìn)一步完善了全輪Crypton算法的Biclique攻擊結(jié)果，同時(shí)，Shakiba等人[16]與Jeong等人[17]分別對全輪mCrypton算法在Biclique下的安全性進(jìn)行了討論；2016年Hao等人[18]給出了10輪Crypton-256算法的中間相遇攻擊結(jié)果，王高麗等人[19]給出了8輪mCrypton-96算法的中間相遇攻擊結(jié)果.

不可能差分分析是由Knudsen[20]和Biham等人[21]獨(dú)立提出的1種單密鑰條件下的攻擊方法.Knudsen在分析AES候選算法DEAL的安全性時(shí)，提出輪函數(shù)是雙射的Feistel結(jié)構(gòu)存在5輪不可能差分；Biham等人在FSE 1999上介紹了利用中間相遇思想來構(gòu)造不可能差分的方法.隨后，不可能差分成為了研究熱門并在許多算法的分析中得到應(yīng)用.近年來，不可能差分的思想逐漸演化出了多種分析方法，如零相關(guān)線性分析[22]、相關(guān)密鑰不可能差分分析[23].

本文對Crypton算法在不可能差分分析下的安全性進(jìn)行了研究.結(jié)合擴(kuò)散層性質(zhì)、早夭技術(shù)[24]、分割攻擊、快速排序算法[25]，改進(jìn)7輪Crypton算法的不可能差分分析；同時(shí)并行利用4個(gè)區(qū)分器[26]，給出7輪Crypton算法的多重不可能差分分析結(jié)果；最后，給出首個(gè)8輪Crypton-256算法不可能差分分析結(jié)果.

1 Crypton算法介紹

1.1 符號(hào)說明

xi: 第i輪經(jīng)過密鑰異或σ后的狀態(tài)；

yi: 第i輪經(jīng)過非線性變換γ后的狀態(tài)；

zi：第i輪經(jīng)過比特置換π后的狀態(tài)；

wi: 第i輪經(jīng)過字節(jié)移位τ后的狀態(tài)；

xi,c ol(j):xi狀態(tài)的第j列；

xi,r ow(j):xi狀態(tài)的第j行；

ke i: 第i輪加密密鑰；

xi[j]: 狀態(tài)xi的第j個(gè)字節(jié)；

<

1.2 Crypton算法

Crypton v0.5與Crypton v1.0算法僅在S盒與密鑰擴(kuò)展算法處不同，本節(jié)以Crypton v1.0為例進(jìn)行介紹.Crypton算法采用SPN結(jié)構(gòu)，分組規(guī)模為128 b，密鑰規(guī)模為64+32k(0≤k≤6)位，迭代輪數(shù)為12輪，本文對算法迭代輪數(shù)的標(biāo)號(hào)從1開始記，分別標(biāo)記為第1輪至第12輪.128 b的分組狀態(tài)可表示為16 B的形式，如圖1所示，其中aij表示第i行第j列的元素.

Fig. 1 The state of Crypton圖1 Crypton狀態(tài)表示

Crypton算法的輪函數(shù)ρ由非線性變換γ、比特置換π、字節(jié)移位τ、密鑰異或σ共4個(gè)變換組成.下面分別對4個(gè)變換進(jìn)行說明.

Fig. 2 The S layers of Crypton圖2 Crypton算法的S層

2) 比特置換π.對狀態(tài)的每1列使用4個(gè)字節(jié)掩碼mi進(jìn)行置亂，分支數(shù)為4，其中m0=0xfc,m1=0xfc,m2=0xcf,m3=0x3f.定義4個(gè)列置換πi(0≤i≤3)：

算法中包含2個(gè)不同的擴(kuò)散層，奇數(shù)輪使用πo，偶數(shù)輪使用πe：

πo(A)=(π3(A3),π2(A2),π1(A1),π0(A0))；

πe(A)=(π1(A3),π0(A2),π3(A1),π2(A0)).

3) 字節(jié)移位τ.將位于第i行、第j列的字節(jié)移位至第j行、第i列，滿足B=τ(A)?bij=aji.

4) 密鑰異或σ.將密鑰字節(jié)與狀態(tài)字節(jié)進(jìn)行異或.

完整的加密流程需要在算法的初始位置異或1個(gè)白化密鑰，在算法的末尾增加1個(gè)出口變換φe=τ°πe°τ確保加脫密算法結(jié)構(gòu)相似性，同理可以定義φo=τ°πo°τ.

Crypton v1.0的密鑰擴(kuò)展算法利用主密鑰生成52個(gè)32位字節(jié)，構(gòu)成13個(gè)圈子密鑰.密鑰擴(kuò)展算法分為利用主密鑰生成8個(gè)擴(kuò)展密鑰和利用擴(kuò)展密鑰生成圈子密鑰2個(gè)過程.

1) 生成擴(kuò)展密鑰.在主密鑰左側(cè)填充0，將規(guī)模為64+32k(0≤k≤6)位的主密鑰擴(kuò)充至256 b.令K=k31…k1k0為256 b擴(kuò)展密鑰，將K分為8個(gè)32位字節(jié)：

U[0]=k6k4k2k0,V[0]=k7k5k3k1；

U[1]=k14k12k10k8,V[1]=k15k13k11k9；

U[2]=k22k20k18k16,V[2]=k23k21k19k17；

U[3]=k30k28k26k24,V[3]=k31k29k27k25.

利用U,V按步驟生成擴(kuò)展密鑰Ee：

步驟1.U′=τ°πo°γ(U),V′=τ°πe°γ(V)；

步驟2. fori=0 to 3

生成圈子密鑰：利用擴(kuò)展密鑰Ee(k)與13個(gè)輪常數(shù)Ce[i]、4個(gè)掩碼常數(shù)MCj共同生成13個(gè)圈子密鑰.其中輪常數(shù)Ce[i]與掩碼常數(shù)MCj的具體形式為

Ce[0]=0xa54ff53a，

Ce[i]=Ce[i-1]+0x3c6ef372 mod 232,

(i=1,2,…,12)；

MC0=0xacacacac,

(j=1,2,3).

2) 按照2個(gè)步驟生成13個(gè)圈子密鑰.

步驟1. 計(jì)算前2輪的圈子密鑰Ke[0,1,…,7].對于i=0,1,2,3，計(jì)算:

Ke[i]=Ee[i]⊕Ce[0]⊕MCi；

Ke[i+4]=Ee[i+4]⊕Ce[1]⊕MCi.

步驟2. 計(jì)算2～12輪的圈子密鑰，對于奇數(shù)輪與偶數(shù)輪分別使用不同的步驟.

步驟2.1. IFr為偶數(shù)*對于偶數(shù)輪*

{Ee[3],Ee[2],Ee[1],Ee[0]}←

Ke[4r+i]←Ee[i]⊕Ce[r]⊕MCi,

(i=0,1,2,3)；

步驟2.2. IFr為奇數(shù)*對于奇數(shù)輪*

{Ee[7],Ee[6],Ee[5],Ee[4]}←

Ke[4r+i]←Ee[4+i]⊕Ce[r]⊕MCi,

(i=0,1,2,3).

2 Crypton算法的不可能差分性質(zhì)

首先對Crypton算法的差分性質(zhì)進(jìn)行研究，其次構(gòu)造Crypton算法的2類4輪不可能差分區(qū)分器.

2.1 相關(guān)性質(zhì)

性質(zhì)1. 在Crypton算法中，所有奇數(shù)輪(偶數(shù)輪)圈子密鑰的對應(yīng)字節(jié)之間存在一一映射關(guān)系，已知奇數(shù)輪(偶數(shù)輪)圈子密鑰的1 B，可以求出其他奇數(shù)輪(偶數(shù)輪)圈子密鑰的對應(yīng)字節(jié).

證明. 在奇數(shù)輪(偶數(shù)輪)圈子密鑰的生成算法中，獨(dú)立使用4個(gè)擴(kuò)展密鑰生成圈子密鑰，且在生成圈子密鑰時(shí)，32 b塊的循環(huán)移位是以8 b16 b24 b進(jìn)行的，1個(gè)輸出字節(jié)僅與對應(yīng)的1個(gè)輸入字節(jié)有關(guān).因此，各奇數(shù)輪(偶數(shù)輪)圈子密鑰字節(jié)與字節(jié)之間存在一一映射關(guān)系.

證畢.

性質(zhì)2. 在Crypton算法中，當(dāng)已知任意1個(gè)奇數(shù)輪圈子密鑰與任意1個(gè)偶數(shù)輪圈子密鑰時(shí)，可以恢復(fù)主密鑰.

證畢.

類比文獻(xiàn)[10]中的結(jié)論，可以給出Crypton算法最后1輪復(fù)合輸出變換的差分特性.

性質(zhì)3. 當(dāng)僅考慮截?cái)嗖罘謧鬟f規(guī)律時(shí)，Crypton算法的最后1輪的τ°π變換與輸出變換φ=τ°π°τ可合并為1個(gè)字節(jié)移位變換，同時(shí)滿足πe°πo=πo°πe.

證明. 僅考慮差分傳遞時(shí)，當(dāng)減輪Crypton算法為奇數(shù)輪時(shí)，最后1輪τ°πo與輸出變換φe=τ°πe°τ可以合并為1個(gè)字節(jié)移位變換；當(dāng)減輪Crypton算法為偶數(shù)輪時(shí)，最后1輪τ°πe與輸出變換φo=τ°πo°τ也可以合并為1個(gè)字節(jié)移位變換.下面以奇數(shù)輪的Crypton算法為例進(jìn)行證明，偶數(shù)輪的Crypton算法可以同理證明得到.

由于密鑰模加變換相對于異或操作是線性的，因此在考慮字節(jié)的異或差分傳遞時(shí)可以忽略密鑰模加操作，則最后1輪與輸出變換復(fù)合后得τ°πe°πo.令a為非線性變換層的輸出且滿足τ°πe°πo(a)=c，若c′=τ(c)，b=πo(a)則有πe°πo(a)=c′.

b3=m3a3⊕m0a7⊕m1a11⊕m2a15；

b7=m0a3⊕m1a7⊕m2a11⊕m3a15；

b11=m1a3⊕m2a7⊕m3a11⊕m0a15；

b15=m2a3⊕m3a7⊕m0a11⊕m1a15.

證畢.

性質(zhì)4. 當(dāng)Crypton算法的π變換滿足輸入2 B差分活動(dòng)，輸出2 B差分活動(dòng)時(shí)，必滿足輸入2 B的差分值與輸出2 B的差分值相同且取特定差分值，共有4組差分對應(yīng):

1) 第1組.其中x=0x1,0x2,0x3，

(x,x,0,0)→(x,0,0,x),

(0,x,x,0)→(0,0,x,x)，

(x,0,x,0)→(x,0,x,0),

(0,x,0,x)→(0,x,0,x)，

(x,0,0,x)→(x,x,0,0),

(0,0,x,x)→(0,x,x,0).

2) 第2組.其中x=0x4,0x8,0xc，

(x,x,0,0)→(x,x,0,0),

(0,x,x,0)→(x,0,0,x)，

(x,0,x,0)→(0,x,0,x),

(0,x,0,x)→(x,0,x,0)，

(x,0,0,x)→(0,x,x,0),

(0,0,x,x)→(0,0,x,x).

3) 第3組.其中x1=0x10,0x20,0x30，

x2=0x10,0x11,0x12,0x13,0x20,0x21，0x22,0x23,0x30,0x31,0x32,0x33，

(x1,x1,0,0)→(0,x1,x1,0),

(0,x1,x1,0)→(x1,x1,0,0),

(0,0,x1,x1)→(x1,0,0,x1),

(0,x2,0,x2)→(0,x2,0,x2),

(x1,0,0,x1)→(0,0,x1,x1),

(x2,0,x2,0)→(x2,0,x2,0).

4) 第4組.其中x1=0x40,0x80,0xc0，

x2=0x40,0x44,0x48,0x4c,0x80,0x84,0x88,0x8c,0xc0,0xc4,0xc8,0xcc，

(x1,x1,0,0)→(0,0,x1,x1),

(0,x1,x1,0)→(0,x1,x1,0),

(0,0,x1,x1)→(x1,x1,0,0),

(0,x2,0,x2)→(x2,0,x2,0),

(x1,0,0,x1)→(x1,0,0,x1),

(x2,0,x2,0)→(0,x2,0,x2).

其中,x代表非0差分字節(jié)，0代表字節(jié)差分為0.

性質(zhì)5[14]. 隨機(jī)給定Crypton算法S盒的1對輸入差分與輸出差分對應(yīng)，平均可以確定1對S盒的輸入與輸出.

2.2 2類4輪不可能差分區(qū)分器

定理1. 區(qū)分器I.當(dāng)τ變換輸入狀態(tài)中僅有1 B為差分活動(dòng)字節(jié)時(shí)，經(jīng)過4輪Crypton算法加密后，γ變換輸出狀態(tài)僅在1列中有2個(gè)差分活動(dòng)字節(jié)是不可能的.

證明. 當(dāng)輸入狀態(tài)中僅有1 B為差分活動(dòng)時(shí)，經(jīng)過1輪Crypton算法加密后，π變換的輸出至少有3個(gè)差分活動(dòng)字節(jié).經(jīng)過1.5輪Crypton算法加密后，輸出一定至少存在9個(gè)差分活動(dòng)字節(jié)，至多有1列不含差分活動(dòng)字節(jié).

當(dāng)輸出狀態(tài)中僅有1列中含有2個(gè)差分活動(dòng)字節(jié)時(shí)，經(jīng)過1.5輪Crypton算法解密后，必存在2列不含有差分活動(dòng)字節(jié)，因此產(chǎn)生矛盾.

證畢.

當(dāng)取輸入狀態(tài)中第3個(gè)字節(jié)為差分活動(dòng)時(shí)，經(jīng)過4輪Crypton算法加密后，輸入狀態(tài)中不可能僅在第8個(gè)字節(jié)與第12個(gè)字節(jié)處為差分活動(dòng).具體形式圖3所示，灰色表示差分活動(dòng)字節(jié)，斜線表示該字節(jié)可能存在差分，白色表示該字節(jié)非差分活動(dòng).

Fig. 3 4-round impossible differential distinguisher圖3 4輪不可能差分區(qū)分器

定理2. 區(qū)分器I的對偶形式.當(dāng)τ變換輸入狀態(tài)同一列任意2 B為差分活動(dòng)字節(jié)時(shí)，經(jīng)過4輪Crypton算法加密后，γ變換的輸出狀態(tài)不可能僅有1個(gè)差分活動(dòng)字節(jié).

證明. 當(dāng)τ變換輸入狀態(tài)同一列中存在2個(gè)差分活動(dòng)字節(jié)，則經(jīng)過γ°τ變換后，下一輪π變換的輸入必有1行中含有2個(gè)差分活動(dòng)字節(jié)，經(jīng)過π變換后必有2列為非差分活動(dòng)的.

若最后1輪γ變換后的輸出狀態(tài)中僅有1個(gè)差分活動(dòng)字節(jié)，則向上推導(dǎo)可知在π-1變換的輸入中僅有1個(gè)差分活動(dòng)字節(jié)，經(jīng)過π-1變換后該行必至少存在3個(gè)差分活動(dòng)字節(jié).經(jīng)過τ-1變換與π-1變換后，必存在3列有差分活動(dòng)字節(jié)，從而產(chǎn)生矛盾，形成了1個(gè)不可能差分對應(yīng).

證畢.

3 7輪Crypton算法不可能差分分析

利用定理1中構(gòu)造的區(qū)分器I，改進(jìn)7輪Crypton算法的不可能差分分析，恢復(fù)最后1輪圈子密鑰；同時(shí)通過并行利用4條定理2給出的不可能差分區(qū)分器，恢復(fù)7輪Crypton算法的主密鑰.

3.1 改進(jìn)的7輪Crypton算法不可能差分分析

文獻(xiàn)[10]使用定理1中所給出的區(qū)分器，對7輪Crypton算法進(jìn)行了攻擊，恢復(fù)了第7輪的圈子密鑰.通過進(jìn)一步研究發(fā)現(xiàn)，上述攻擊存在2個(gè)問題：

1) 根據(jù)性質(zhì)4，當(dāng)輸出差分模式滿足(0,0,1,1)時(shí)，輸入差分模式不存在(0,0,1,1)的形式；

2) 根據(jù)性質(zhì)4，當(dāng)輸出差分第11,15 B差分活動(dòng)，而輸入差分為任意2 B差分活動(dòng)時(shí)，僅存在15個(gè)可能的差分對應(yīng)，因此其概率應(yīng)為2-12.4而非2-11.8.

基于定理1中的4輪不可能差分區(qū)分器，結(jié)合擴(kuò)散層性質(zhì)、快速排序算法、分割攻擊與早夭技術(shù)[27]改進(jìn)7輪Crypton算法的不可能差分分析.攻擊過程分為預(yù)計(jì)算與在線攻擊2個(gè)階段.

1) 在預(yù)計(jì)算階段需要預(yù)計(jì)算并存儲(chǔ)3個(gè)表

① 表T1.滿足第3列中僅有1 B差分活動(dòng)，其余字節(jié)為非差分活動(dòng)的差分狀態(tài)Δz1,c ol(3)共有210種取值.因此，S盒輸出差分Δy1,c ol(3)共有210種取值，根據(jù)性質(zhì)5，給定S盒輸入差分Δx1,col(3)，平均能夠確定出210個(gè)y1,c ol(3).同時(shí)，由于Δx1,col(3)=ΔPc ol(3)，表T1以232個(gè)明文差分ΔPc ol(3)為索引，存儲(chǔ)對應(yīng)的210個(gè)x1,col(3).

② 表T2.對于僅在第0個(gè)字節(jié)處差分活動(dòng)的狀態(tài)對Δz6,c ol(0)′，共有28種可能取值.根據(jù)性質(zhì)5，表T2以232個(gè)密文差分ΔCc ol(2)為索引，存儲(chǔ)28個(gè)(z6′[0],z6″[0])和對應(yīng)的y7,row(0).

③ 表T3.類似表T2，對于僅在第2個(gè)字節(jié)處為差分活動(dòng)的狀態(tài)對Δz6,col(2)′，共有28種可能取值.因此以232個(gè)ΔCc ol(0)為索引，存儲(chǔ)28個(gè)(z6′[2],z6″[2])和y7,row(2).

2) 在線攻擊階段包含6個(gè)步驟：

步驟1. 選擇2n1個(gè)明文結(jié)構(gòu)，其中明文滿足在第3,7,11,15字節(jié)上取所有的值，在其余字節(jié)上取固定值，1個(gè)明文結(jié)構(gòu)包含232個(gè)明文，可以構(gòu)造263個(gè)明文對.因此攻擊的選擇明文量為2n1+32，其中包含2n1+63個(gè)明文對.

步驟2. 運(yùn)用快速排序算法篩選明文對.根據(jù)性質(zhì)3，篩選出密文在第0,2,4,6,8,10,12,14字節(jié)差分活動(dòng)，其余字節(jié)差分不活動(dòng)的明文對，剩余2n1-1個(gè)明文對.以明文對序號(hào)作索引，將篩選得到的明文對存儲(chǔ)在表Ω中，存儲(chǔ)明文的第3,7,11,15字節(jié)與密文的第0,2,4,6,8,10,12,14字節(jié).

具體的攻擊路徑如圖4所示，其中黑色表示差分活動(dòng)字節(jié)，白色表示差分為0的字節(jié)，斜線表示可能存在差分的字節(jié)，網(wǎng)狀表示猜測的密鑰字節(jié).定理3給出上述7輪Crypton算法不可能差分分析的復(fù)雜度分析結(jié)果.

Fig. 4 Impossible differential attack on 7-round Crypton圖4 7輪Crypton算法不可能差分分析

定理3. 利用4輪不可能差分區(qū)分器能夠?qū)?輪Crypton算法進(jìn)行不可能差分分析，恢復(fù)第7輪的圈子密鑰，其時(shí)間復(fù)雜度為2112.6，數(shù)據(jù)復(fù)雜度為2120.4，存儲(chǔ)復(fù)雜度為299.1.

證明. 預(yù)計(jì)算階段與在線攻擊階段的復(fù)雜度相差較大，在線攻擊階段的復(fù)雜度占主要部分，可以忽略預(yù)計(jì)算階段的復(fù)雜度.

在線攻擊階段各步驟的復(fù)雜度如下：

步驟2快速排序篩選明文對的時(shí)間復(fù)雜度為2n1×232lb 232=2n1+37次比較，表Ω順序存儲(chǔ)2n1-1個(gè)明密文對，其中包含明文4B，密文8B，存儲(chǔ)復(fù)雜度為2n1-1×2×(4+8)=2n1+2×3B.

步驟3對2n1-1個(gè)明文對查找表T2并存儲(chǔ)的時(shí)間復(fù)雜度為2n1-1×28=2n1+7次查表，表Ω1需要存儲(chǔ)2B與明文對序號(hào)，其存儲(chǔ)復(fù)雜度為2n1-25×232×(2+(n1-1)8)B.

證畢.

上述7輪不可能差分分析沒有利用密鑰擴(kuò)展算法的信息泄漏規(guī)律，而且復(fù)雜度較低，因此適用于128 b192 b256 b共3種密鑰規(guī)模的算法.

3.2 7輪Crypton算法多重不可能差分分析

使用定理2中的區(qū)分器，僅改變區(qū)分器輸出的差分活動(dòng)字節(jié)分別為第0,1,2,3 字節(jié)，則4條區(qū)分器具有相同輸入，通過選取相同的明文結(jié)構(gòu)，并行利用4條不可能差分路徑，結(jié)合密鑰擴(kuò)展算法性質(zhì)可以給出7輪Crypton算法多重不可能差分分析，恢復(fù)算法主密鑰.攻擊過程分為預(yù)計(jì)算階段與在線攻擊階段.

在預(yù)計(jì)算階段，需要預(yù)計(jì)算并存儲(chǔ)6個(gè)表.

表T4：僅在第15 B差分非0的差分Δz1,c ol(3)共有28種可能取值，可以得到S盒的輸出差分Δy1,c ol(3).由明文對可以得到S盒的輸入差分Δx1,col(3)，根據(jù)性質(zhì)5可以求出28個(gè)x1,col(3)，將x1,col(3)和(z1[15],

在線攻擊階段共包含8個(gè)步驟：

步驟1. 選擇2n2個(gè)明文結(jié)構(gòu)，其中的明文滿足在第1,3,5,7,9,11,13,15字節(jié)取所有值，在其余字節(jié)上固定.1個(gè)明文結(jié)構(gòu)包含264個(gè)明文，可構(gòu)造2127個(gè)明文對，因此選擇明文量為2n2+64，明文對2n2+127個(gè).

步驟2. 對i=0,1,2,3，分別運(yùn)用快速排序算法篩選明文對.若i=3，保留密文在第1,5,9,13字節(jié)的差分活動(dòng)，其余字節(jié)差分為0的明文對，篩選后剩余2n2+31個(gè)明文對.以明文對序號(hào)為索引，將剩余明文對存儲(chǔ)在表Γi中，存儲(chǔ)明文的第1,3,5,7,9,11,13,15字節(jié)與密文的第1,5,9,13字節(jié).

步驟5. 由密鑰ke 0,c ol(1,3)的當(dāng)前值求解ke 1[7,15].由表Ω2中2n2-17個(gè)明文對，可以得到S盒的輸入差分Δx2[7,15].根據(jù)性質(zhì)4，S盒的輸出差分滿足Δy2[7]=Δy2[15].對Δy2[7]的取值進(jìn)行窮舉，由性質(zhì)5可以求出(x2[7,15],y2[7,15])，從而可以確定密鑰ke 1[7,15].以密鑰ke 1[7,15]的216個(gè)可能的取值為索引，將滿足區(qū)分器的明文序號(hào)存儲(chǔ)在表Ω3中.1個(gè)ke 1[7,15]平均剩余明文對個(gè)數(shù)2n2-17×30216=2n2-28.1.

步驟7. 對密鑰(ke 0,c ol(1,3),ke 1[7,15])，在i=0,1,2時(shí)，分別進(jìn)行下面2步檢測：

步驟7.1. 對Γi中的明文對，加密1輪后，若輸出在第1行與第3行中差分活動(dòng)字節(jié)多于1個(gè)或者2個(gè)差分活動(dòng)字節(jié)不在同一列，則丟棄該明文對；否則加密至第2輪π變換后，若僅有1列包含2個(gè)差分活動(dòng)字節(jié)，其余字節(jié)均非差分活動(dòng)，則保留該明文對.平均剩余明文對個(gè)數(shù)為2n2+31×2-48×3065 025=2n2-28.1.

攻擊路徑如圖5所示，定理4給出7輪Crypton算法多重不可能差分分析的復(fù)雜度分析結(jié)果.

Fig. 5 Multiple impossible differential attack on 7-round Crypton圖5 7輪Crypton算法多重不可能差分分析

定理4. 并行利用4條不可能差分區(qū)分器可以恢復(fù)7輪Crypton算法的主密鑰，其時(shí)間復(fù)雜度為2115.2，數(shù)據(jù)復(fù)雜度為2120.9，存儲(chǔ)復(fù)雜度為2101.8.

證明. 步驟2分別對4組2n2+64個(gè)明文進(jìn)行快速排序篩選的時(shí)間復(fù)雜度為4×2n2×264lb 264=2n2+72次比較，對4組2n2+31個(gè)明密文進(jìn)行存儲(chǔ)，存儲(chǔ)復(fù)雜度為4×2n2+31×2×(4+8)=2n2+36×3 B.

步驟3對2n2+31個(gè)明文對查表T5并存儲(chǔ)的時(shí)間復(fù)雜度為2n2+31×28=2n2+39次查表，表Ω1的存儲(chǔ)復(fù)雜度為232×2n2+7×(2+(n2+31)8)B.

步驟4在ke 0,c ol(1)下，對2n2+7個(gè)明文對查表T4的時(shí)間復(fù)雜度為2n2+7×232×28=2n2+47次查表，表Ω2的存儲(chǔ)復(fù)雜度為232×2n2-17×(4+(n2+31)8)B.

步驟5的時(shí)間復(fù)雜度為264×2n2-17×28=2n2+55次查表，存儲(chǔ)復(fù)雜度為216×2n2-28.1×(n2+31)8B.

步驟6利用類似3.1節(jié)中的早夭技術(shù)，時(shí)間復(fù)雜度為280×225.6×210=2115.6次查表.

錯(cuò)誤密鑰(ke 0,c ol(1,3),ke 1[7,15])通過步驟6檢測概率為q=1-[1-(1-2-22)2n2-28.1]232≈1-[1-e-222×2n2-28.1]232≈1-e-232×e-222×2n2-28.1≈1-e-232-1.4425×2n2-50.1,因此能夠通過步驟6檢測的密鑰個(gè)數(shù)為280×q≈280(1-e-232-1.4425×2n2-50.1).

步驟7分2個(gè)子步驟，對于i=0,1,2，步驟7.1的時(shí)間復(fù)雜度可以忽略不計(jì)，通過步驟7.2中檢測的概率為q′=1-e-232-1.4425×2n2-50.1,則步驟7.2的時(shí)間復(fù)雜度為280×225.6×210×q×(q′)i次查表.步驟6與步驟7的時(shí)間復(fù)雜度之和不超過2115.6×4次查表.

步驟8的候選密鑰量為280+4×32×[(1-2-22)2n2-28.1]4≈2208-1.4425×2n2-50.1，對剩余的候選密鑰依次窮舉8 B，總的計(jì)算復(fù)雜度為2208-1.442 5×2n2-50.1×264次加密.取n2=56.9時(shí)，時(shí)間復(fù)雜度主要由步驟2所決定2115.2，數(shù)據(jù)復(fù)雜度為2120.9，存儲(chǔ)復(fù)雜度為2101.8.

證畢.

7輪Crypton算法多重不可能差分分析沒有利用密鑰擴(kuò)展算法的信息泄漏規(guī)律，而且復(fù)雜度較低，因此適用于128 b192 b256 b共3種密鑰規(guī)模的算法.

4 8輪Crypton-256算法不可能差分分析

本節(jié)在3.1節(jié)中7輪Crypton算法不可能差分分析的基礎(chǔ)上向后拓展1輪，結(jié)合密鑰擴(kuò)展算法與擴(kuò)散層的性質(zhì)，利用分割攻擊思想給出8輪Crypton-256算法的不可能差分分析過程及復(fù)雜度分析結(jié)果.攻擊分為預(yù)計(jì)算階段與在線攻擊階段.

預(yù)計(jì)算階段需要預(yù)計(jì)算并存儲(chǔ)5個(gè)表.

表T5：窮舉210個(gè)差分Δz1,c ol(3)，以232個(gè)明文差分ΔPc ol(3)為索引，存儲(chǔ)對應(yīng)的210個(gè)x1,col(3).

在線攻擊階段包含8個(gè)步驟:

步驟1. 選擇2n個(gè)明文結(jié)構(gòu)，其中的明文滿足在第3,7,11,15 B上取所有的值，在其余字節(jié)上取固定值，1個(gè)明文結(jié)構(gòu)包含232個(gè)明文，可以構(gòu)造263個(gè)明文對.因此攻擊的選擇明文量為2n+32，將2n+63個(gè)明文對以明文序號(hào)為索引存儲(chǔ)在表Ω1中.

Fig. 6 Impossible differential attack on 8-round Crypton-256圖6 8輪Crypton-256算法不可能差分分析

圖6給出了8輪Crypton算法的不可能差分分析的具體路徑，定理5給出其復(fù)雜度分析結(jié)果.

定理5. 8輪Crypton-256算法的不可能差分分析能夠恢復(fù)最后1輪圈子密鑰，其時(shí)間復(fù)雜度為2213，數(shù)據(jù)復(fù)雜度為2103，存儲(chǔ)復(fù)雜度為2154.4.

證明. 以表1的形式給出8輪Crypton-256算法不可能差分分析中各步的時(shí)間復(fù)雜度與存儲(chǔ)復(fù)雜度.

Table 1 Complexity of Impossible Differential Attack on 8-round Crypton-256表1 8輪Crypton-256算法不可能差分分析復(fù)雜度

E: One round encryption.

控制經(jīng)過步驟8后剩余的候選密鑰量2192×(1-2-14.9)2n-49=1時(shí)，得到n=71.時(shí)間復(fù)雜度為2213次8輪Crypton-256算法加密，存儲(chǔ)復(fù)雜度為2154.4B，數(shù)據(jù)復(fù)雜度為2103個(gè)選擇明文.

證畢.

定理6. 8輪Crypton-256算法的不可能差分分析能夠恢復(fù)256 b主密鑰，其時(shí)間復(fù)雜度為2214，數(shù)據(jù)復(fù)雜度為2103，存儲(chǔ)復(fù)雜度為2154.4.

5 結(jié)束語

本文對Crypton算法在不可能差分分析下的安全性進(jìn)行了研究.指出了文獻(xiàn)[10]中對Crypton算法不可能差分分析中差分傳遞概率估計(jì)與攻擊路徑表示中的錯(cuò)誤，并運(yùn)用π變換性質(zhì)、分割攻擊、早夭技術(shù)、快速排序算法改進(jìn)了7輪Crypton算法不可能差分分析結(jié)果；同時(shí)并行使用4條不可能差分區(qū)分器，結(jié)合密鑰擴(kuò)展算法的性質(zhì)恢復(fù)了7輪Crypton算法的主密鑰；向后拓展1輪后給出了8輪Crypton算法的不可能差分分析并對其復(fù)雜度進(jìn)行了分析.本文結(jié)果與現(xiàn)有Crypton算法的不可能差分分析結(jié)果對比如表2所示：

Table 2 Comparison of Impossible Differential Attacks on Crypton表2 Crypton算法不可能差分分析結(jié)果對比

目前，針對Crypton算法的研究多集中于中間相遇攻擊、不可能差分分析和Biclique攻擊等單密鑰情況下的分析，而Crypton算法的密鑰擴(kuò)展算法較弱，能否進(jìn)一步結(jié)合密鑰擴(kuò)展算法中的弱點(diǎn)，給出更高輪數(shù)的攻擊或者復(fù)雜度更低的相關(guān)密鑰條件下的攻擊結(jié)果是下一步研究的重點(diǎn).

[1]Biham E. A note on comparing the AES candidates[EBOL]. 1998 [2016-06-02]. http:csrc.nist.govarchiveaesround1conf2papersbiham2.pdf

[2]Lim C. A revised version of Crypton-Crypton V1.0[G]LNCS 1636: Proc of Fast Software Encrypton. Berlin: Springer, 1999: 31-45

[3]Daemen J, Knudsen L, Rijmen V. The block cipher Square[G]LNCS 1267: Proc of Fast Software Encryption. Berlin: Springer, 1997: 149-165

[4]Lim C. Crypton: A new 128-bit block cipher[EBOL]. 1998 [2016-06-01]. http:citeseerx.ist.psu.eduviewdocdownload?doi=10.1.1.52.5771&rep=rep1&type=pdf

[5]Lim C, Korkishko T. mCrypton—A lightweight block cipher for security of low-cost RFID tags and sensors[G]LNCS 3786: Proc of Information Security Applications. Berlin: Springer, 2006: 243-258

[6]Seki H, Kaneko T. Cryptanalysis of five rounds of Crypton using impossible differentials[G]LNCS 1716: Proc of ASIACRYPT. Berlin: Springer, 1999: 43-51

[7]Minier M, Gilbert H. Stochastic cryptanalysis of Crypton[G]LNCS 1978: Proc of Fast Software Encryption. Berlin: Springer, 2000: 121-133

[8]Cheon J H, Kim M J, Kim K, et al. Improved impossible differential cryptanalysis of Rijndael and Crypton[G]LNCS 2288: Proc of Information Security and Cryptology. Berlin: Springer, 2001: 39-49

[9]Kim J, Hong S, Lee S, et al. Truncated differential attacks on 8-round Crypton[G]LNCS 2971: Proc of Information Security and Cryptology. Berlin: Springer, 2003: 446-456

[10]Mala H, Shakiba M, Dakhilalian M. New impossible differential attacks on reduced-round Crypton[J]. Computer Standards & Interfaces, 2010, 32(4): 222-227

[11]Wei Yuechuan, Li Chao, Sun Bing. Related-key impossible differential cryptanalysis on Crypton and Crypton v1.0[G]Proc of World Congress on Internet Security. Piscataway, NJ: IEEE, 2011: 227-232

[12]Kang J, Jeong K, Sung J, et al. Collision attacks on AES-192256, Crypton-192256, mCrypton-96128, and Anubis[JOL]. Journal of Applied Mathematics, 2013: Article ID 713673 [2016-08-22]. http:www.hindawi.comjournalsjam2013713673

[13]Song J, Lee K, Lee H. Biclique cryptanalysis on the full Crypton-256 and mCrypton-128[JOL]. Journal of Applied Mathematics, 2014: Article ID 529736 [2016-08-22]. http:www.hindawi.comjournalsjam2014529736citations

[14]Hao Yonglin, Bai Dongxia, Li Leibo. A meet-in-the-middle attack on round-reduced mCrypton using the differential enumeration techniques[G]LNCS 8792: Proc of Network and System Security. Berlin: Springer, 2014: 166-183

[15]Shakiba M, Dakhilalian M, Mala H. Cryptanalysis of mCrypton-64[J]. International Journal of Communication Systems, 2015, 28(8): 1401-1418

[16]Shakiba M, Dakhilalian M, Mala H. Non-isomorphic biclique cryptanalysis of full-round Crypton[J]. Computer Standards & Interfaces, 2015, 41: 72-78

[17]Jeong K, Kang H, Lee C, et al. Weakness of lightweight block ciphers mCrypton and LED against biclique cryptanalysis[J]. Peer-to-Peer Networking and Applications, 2015, 8(4): 716-732

[18]Hao Yonglin. Improved meet-in-the-middle on round-reduced Crypton-256[EBOL]. [2016-05-21]. https:eprint.iacr.org2016267.pdf

[19]Wang Gaoli, Gan Nan. A meet-in-the-middle attack on 8-round mCrypton-96[J]. Journal of Computer Research and Development, 2016, 53(3): 666-673 (in Chinese)(王高麗, 甘楠. mCrypton-96算法的改進(jìn)中間相遇攻擊[J]. 計(jì)算機(jī)研究與發(fā)展, 2016, 53(3): 666-673)

[20]Knudsen L R. DEAL-A 128-bit block cipher[EBOL]. 1998 [2016-06-02]. http:repo.hackerzvoice.netdepot_madchatcryptohash-lib-algodealdeal.pdf

[21]Biham E, Bivyukov A, Shamir A. Miss in the middle on IDEA and Khufu[G]LNCS 1636: Proc of Fast Software Encryption. Berlin: Springer, 1999: 124-138

[22]Sun Bing, Liu Zhiqiang, Rijmen V, et al. Links among impossible differential, integral and zero correlation linear cryptanalysis[G]LNCS 9215: Proc of CRYPTO. Berlin: Springer, 2005: 95-115

[23]Wei Hongru, Yin Guangli. Related-key impossible differential cryptanalysis on LBlock[J]. Journal of Computer Research and Development, 2014, 51 (7): 1520-1526 (in Chinese)(衛(wèi)宏儒, 殷廣麗. LBlock算法的相關(guān)密鑰不可能差分分析[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(7): 1520-1526)

[24]Lu Jiqiang, Kim J, Keller N, et al. Improving the efficiency of impossible differential cryptanalysis of reduced Camellia and MISTY1[G]LNCS 4964: Proc of Topics in Cryptology. Berlin: Springer, 2008: 370-386

[25]Zhang Qinggui. Plaintext pair sieve methods in impossible differential attack[J]. Computer Engineering, 2010, 36(2): 127-129 (in Chinese)(張慶貴. 不可能差分攻擊中的明文對篩選方法[J]. 計(jì)算機(jī)工程, 2010, 36(2): 127-129)

[26]Li Rongjia, Jin Chenhui. Meet-in-the-middle attacks on 10-round AES[J]. Designs, Codes and Cryptography, 2016, 80(3): 459-471

[27]Hu Hongjian, Jin Chenhui, Li Xinran. Improved impossible differential attack on 7-round AES -128[J]. Journal of Cryptologic Research, 2015, 2(1): 92-100 (in Chinese)(胡弘堅(jiān), 金晨輝, 李信然. 改進(jìn)的7輪AES -128的不可能差分攻擊[J]. 密碼學(xué)報(bào), 2015, 2(1): 92-100)

Cui Jingyi, born in 1992. Master candidate. His main research interests include design and cryptanalysis of symmetric cipher.

Guo Jiansheng, born in 1972. Professor and PhD supervisor. His main research interests include information security and cryptology theory.

Liu Yipeng, born in 1992. Master candidate. His main research interests include information security and quantum cryptology (lyp_31@126.com).

Impossible Differential Attack on Crypton

Cui Jingyi, Guo Jiansheng, and Liu Yipeng

(ThePLAInformationEngineeringUniversity,Zhengzhou450001)

Crypton is one of the candidates of AES that designed based on Square which is a SP-network block cipher. Crypton attracts much attention of the world because of its excellent performance on hardware. The security of Crypton block cipher under impossible differential attack was studied in this paper. The properties of the diffusion layer and nonlinear layer of Crypton are analyzed and combined with the quick sort technique, the divide-and-conquer strategy, the early abort technique, the impossible differential attack on 7-round Crypton is improved with a lower data complexity and time complexity. By using 4 impossible differential distinguishers in parallel, combined with the property of key schedule, the master key of 7-round Crypton is recovered. Based on the impossible differential attack on 7-round Crypton, one more round is extended to maintain the attack on 8-round Crypton-256 to recover the 256-bit key with a data complexity of 2103chosen plaintexts, a time complexity of 22148-round encryptions, a memory complexity of 2154.4B. The results show that with the usage of several techniques and the properties of Crypton, the best impossible differential attacks on Crypton are proposed in this paper known before. These techniques can also be used to analyze the other SP-network block ciphers.

block cipher; cryptanalysis; Crypton; impossible differential attack; early abort technique

2016-06-12；

2016-08-31

中國博士后科學(xué)基金項(xiàng)目(2014M562582) This work was supported by the China Postdoctoral Science Foundation (2014M562582).

郭建勝(tsg_31@126.com)

TP309