Crypton算法的不可能差分分析

崔竞一 郭建胜 刘翼鹏

(解放军信息工程大学 郑州 450001)

(xd_cjy@126.com)

摘 要:Crypton算法是基于Square算法设计的SPN结构类密码算法,由于其具备良好的软硬件性能而引起了广泛的关注.对Crypton分组密码算法在不可能差分分析下的安全性进行了研究.通过分析Crypton算法扩散层的性质,指出了现有7轮Crypton算法不可能差分分析中存在的问题,结合快速排序、分割攻击与早夭技术对7轮Crypton算法的不可能差分分析进行了改进,降低了其数据复杂度与时间复杂度;同时,通过并行使用4条不可能差分区分器,结合密钥扩展算法的性质给出了7轮Crypton算法的多重不可能差分分析结果,恢复了算法的主密钥;最后,在7轮Crypton算法的不可能差分分析的基础上向后拓展1轮,给出了8轮Crypton-256算法的不可能差分分析,恢复了其主密钥,其数据复杂度为2103个选择明文,时间复杂度为2214次8轮Crypton加密,存储复杂度为2154.4 B.研究结果表明:结合算法的性质及多种技术给出了Crypton算法目前最优的不可能差分分析结果.

关键词:分组密码;密码分析;Crypton;不可能差分分析;早夭技术

AES加密标准面向全球征集了15个候选算法[1],Crypton分组密码算法[2]就是其中之一.Crypton算法是基于Square算法[3]设计的,由于其具有很多优点:使用SPN结构满足加脱密结构相似,具有良好的可证明安全性,同时具有良好的并行能力,能够广泛适用于各类软硬件环境,从而受到广大学者的关注.Crypton算法共有2个版本,通常称作Crypton v0.5[4]与Crypton v1.0[2].设计者对Crypton v0.5的密钥扩展算法与S盒的设计中存在的缺陷进行改进后提出了Crypton v1.0.随着物联网技术与RFID技术的发展,对轻量级密码算法的需求日益增加,Lim等人[5]于2006年参照Crypton算法的设计思路,设计提出了轻量级分组密码算法mCrypton.人们针对Crypton算法与mCrypton算法给出了许多分析结果.1999年Seki等人[6]给出了Crypton算法的不可能差分分析结果;2000年Minier等人[7]给出了Crypton算法的猜测攻击;2001年Cheon等人[8]给出了改进不可能差分分析结果;2003年Kim等人[9]给出了8轮Crypton算法截断差分分析结果;2010年Mala等人[10]利用不可能差分给出了7轮Crypton算法的分析结果;2011年Wei等人[11]给出了Crypton算法的相关密钥不可能差分分析结果;2013年Kang等人[12]给出了Crypton-192256算法与mCrypton-96128算法的碰撞攻击;2014年Song等人[13]给出了全轮Crypton-256算法与mCrypton-128算法的Biclique攻击结果,同时Hao等人[14]给出了mCrypton算法在中间相遇攻击下的安全性研究结果;2015年Shakiba等人[15]进一步完善了全轮Crypton算法的Biclique攻击结果,同时,Shakiba等人[16]与Jeong等人[17]分别对全轮mCrypton算法在Biclique下的安全性进行了讨论;2016年Hao等人[18]给出了10轮Crypton-256算法的中间相遇攻击结果,王高丽等人[19]给出了8轮mCrypton-96算法的中间相遇攻击结果.

不可能差分分析是由Knudsen[20]和Biham等人[21]独立提出的1种单密钥条件下的攻击方法.Knudsen在分析AES候选算法DEAL的安全性时,提出轮函数是双射的Feistel结构存在5轮不可能差分;Biham等人在FSE 1999上介绍了利用中间相遇思想来构造不可能差分的方法.随后,不可能差分成为了研究热门并在许多算法的分析中得到应用.近年来,不可能差分的思想逐渐演化出了多种分析方法,如零相关线性分析[22]、相关密钥不可能差分分析[23].

本文对Crypton算法在不可能差分分析下的安全性进行了研究.结合扩散层性质、早夭技术[24]、分割攻击、快速排序算法[25],改进7轮Crypton算法的不可能差分分析;同时并行利用4个区分器[26],给出7轮Crypton算法的多重不可能差分分析结果;最后,给出首个8轮Crypton-256算法不可能差分分析结果.

1 Crypton算法介绍

1.1 符号说明

xi: 第i轮经过密钥异或σ后的状态;

yi: 第i轮经过非线性变换γ后的状态;

zi:第i轮经过比特置换π后的状态;

wi: 第i轮经过字节移位τ后的状态;

xi,c ol(j): xi状态的第j列;

xi,r ow(j): xi状态的第j行;

ke i: 第i轮加密密钥;

: 第i轮加密密钥经过π-1τ-1变换后状态,满足

xi[j]: 状态xi的第j个字节;

<<a: 32位字节循环左移a位;

: 32位字节中的每个字节循环左移i位.

1.2 Crypton算法

Crypton v0.5与Crypton v1.0算法仅在S盒与密钥扩展算法处不同,本节以Crypton v1.0为例进行介绍.Crypton算法采用SPN结构,分组规模为128 b,密钥规模为64+32k(0≤k≤6)位,迭代轮数为12轮,本文对算法迭代轮数的标号从1开始记,分别标记为第1轮至第12轮.128 b的分组状态可表示为16 B的形式,如图1所示,其中aij表示第i行第j列的元素.

Fig. 1 The state of Crypton
图1 Crypton状态表示

Crypton算法的轮函数ρ由非线性变换γ、比特置换π、字节移位τ、密钥异或σ共4个变换组成.下面分别对4个变换进行说明.

1) 非线性变换γ.在Crypton算法中共有4个8b的S盒Si(0≤i≤3),其中1.算法中包括2个非线性变换层γeγo,连续2轮的非线性变换层不同,奇数轮使用γo,偶数轮使用γe,具体形式如图2所示:

Fig. 2 The S layers of Crypton
图2 Crypton算法的S层

2) 比特置换π.对状态的每1列使用4个字节掩码mi进行置乱,分支数为4,其中m0=0xfc,m1=0xfc,m2=0xcf,m3=0x3f.定义4个列置换πi(0≤i≤3):

).

算法中包含2个不同的扩散层,奇数轮使用πo,偶数轮使用πe:

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

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

3) 字节移位τ.将位于第i行、第j列的字节移位至第j行、第i列,满足B=τ(A)⟺bij=aji.

4) 密钥异或σ.将密钥字节与状态字节进行异或.

完整的加密流程需要在算法的初始位置异或1个白化密钥,在算法的末尾增加1个出口变换φe=τπe∘τ确保加脱密算法结构相似性,同理可以定义φo=τπo∘τ.

Crypton v1.0的密钥扩展算法利用主密钥生成52个32位字节,构成13个圈子密钥.密钥扩展算法分为利用主密钥生成8个扩展密钥和利用扩展密钥生成圈子密钥2个过程.

1) 生成扩展密钥.在主密钥左侧填充0,将规模为64+32k(0≤k≤6)位的主密钥扩充至256 b.令K=k31k1k0为256 b扩展密钥,将K分为8个32位字节:

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按步骤生成扩展密钥Ee

步骤1. U′=τπo∘γ(U),V′=τπe∘γ(V);

步骤2. for i=0 to 3

Ee[i]=U′[i]⊕

Ee[i+4]=V′[i]⊕).

生成圈子密钥:利用扩展密钥Ee(k)与13个轮常数Ce[i]、4个掩码常数MCj共同生成13个圈子密钥.其中轮常数Ce[i]与掩码常数MCj的具体形式为

Ce[0]=0xa54ff53a,

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

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

MC0=0xacacacac,

,

(j=1,2,3).

2) 按照2个步骤生成13个圈子密钥.

步骤1. 计算前2轮的圈子密钥Ke[0,1,…,7].对于i=0,1,2,3,计算:

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

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

步骤2. 计算2~12轮的圈子密钥,对于奇数轮与偶数轮分别使用不同的步骤.

步骤2.1. IF r为偶数 *对于偶数轮*

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

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

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

步骤2.2. IF r为奇数 *对于奇数轮*

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

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

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

2 Crypton算法的不可能差分性质

首先对Crypton算法的差分性质进行研究,其次构造Crypton算法的2类4轮不可能差分区分器.

2.1 相关性质

性质1. 在Crypton算法中,所有奇数轮(偶数轮)圈子密钥的对应字节之间存在一一映射关系,已知奇数轮(偶数轮)圈子密钥的1 B,可以求出其他奇数轮(偶数轮)圈子密钥的对应字节.

证明. 在奇数轮(偶数轮)圈子密钥的生成算法中,独立使用4个扩展密钥生成圈子密钥,且在生成圈子密钥时,32 b块的循环移位是以8 b16 b24 b进行的,1个输出字节仅与对应的1个输入字节有关.因此,各奇数轮(偶数轮)圈子密钥字节与字节之间存在一一映射关系.

证毕.

性质2. 在Crypton算法中,当已知任意1个奇数轮圈子密钥与任意1个偶数轮圈子密钥时,可以恢复主密钥.

证明. 奇数轮圈子密钥与偶数轮圈子密钥是由8个32 b扩展密钥Ee[0,1,2,…,7]通过字节内循环移位、字节间循环移位与异或常数生成的.根据性质1,利用任意奇数轮与偶数轮2轮的圈子密钥可以求出完整的扩展密钥Ee[0,1,2,…,7].根据密钥扩展算法,可得Ee[i]=U′[i]⊕T1,Ee[4+i]=V′[i]⊕T0,(i=0,1,2,3),同时根据密钥扩展算法,Ee[i]=V′[i]=T1,因此当已知扩展密钥Ee时,可以恢复U′,V′,进而可以恢复原始256 b主密钥.

证毕.

类比文献[10]中的结论,可以给出Crypton算法最后1轮复合输出变换的差分特性.

性质3. 当仅考虑截断差分传递规律时,Crypton算法的最后1轮的τπ变换与输出变换φ=τπτ可合并为1个字节移位变换,同时满足πe∘πo=πo∘πe.

证明. 仅考虑差分传递时,当减轮Crypton算法为奇数轮时,最后1轮τπo与输出变换φe=τπe∘τ可以合并为1个字节移位变换;当减轮Crypton算法为偶数轮时,最后1轮τπe与输出变换φo=τπo∘τ也可以合并为1个字节移位变换.下面以奇数轮的Crypton算法为例进行证明,偶数轮的Crypton算法可以同理证明得到.

由于密钥模加变换相对于异或操作是线性的,因此在考虑字节的异或差分传递时可以忽略密钥模加操作,则最后1轮与输出变换复合后得τπ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.

m2b7⊕m3b11⊕m0b15;

m3b7⊕m0b11⊕m1b15;

m0b7⊕m1b11⊕m2b15;

m1b7⊕m2b11⊕m3b15.

可以得到15=a7,同理可以得到其余3列均为1个列内字节移位变换,同时可以将最后1轮非线性变换的输出差分字节与密文的差分字节对应起来,具体字节对应关系为

.

证毕.

性质4. 当Crypton算法的π变换满足输入2 B差分活动,输出2 B差分活动时,必满足输入2 B的差分值与输出2 B的差分值相同且取特定差分值,共有4组差分对应:

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差分字节,0代表字节差分为0.

性质5[14]. 随机给定Crypton算法S盒的1对输入差分与输出差分对应,平均可以确定1对S盒的输入与输出.

2.2 2类4轮不可能差分区分器

定理1. 区分器I.当τ变换输入状态中仅有1 B为差分活动字节时,经过4轮Crypton算法加密后,γ变换输出状态仅在1列中有2个差分活动字节是不可能的.

证明. 当输入状态中仅有1 B为差分活动时,经过1轮Crypton算法加密后,π变换的输出至少有3个差分活动字节.经过1.5轮Crypton算法加密后,输出一定至少存在9个差分活动字节,至多有1列不含差分活动字节.

当输出状态中仅有1列中含有2个差分活动字节时,经过1.5轮Crypton算法解密后,必存在2列不含有差分活动字节,因此产生矛盾.

证毕.

当取输入状态中第3个字节为差分活动时,经过4轮Crypton算法加密后,输入状态中不可能仅在第8个字节与第12个字节处为差分活动.具体形式图3所示,灰色表示差分活动字节,斜线表示该字节可能存在差分,白色表示该字节非差分活动.

Fig. 3 4-round impossible differential distinguisher
图3 4轮不可能差分区分器

定理2. 区分器I的对偶形式.当τ变换输入状态同一列任意2 B为差分活动字节时,经过4轮Crypton算法加密后,γ变换的输出状态不可能仅有1个差分活动字节.

证明. 当τ变换输入状态同一列中存在2个差分活动字节,则经过γτ变换后,下一轮π变换的输入必有1行中含有2个差分活动字节,经过π变换后必有2列为非差分活动的.

若最后1轮γ变换后的输出状态中仅有1个差分活动字节,则向上推导可知在π-1变换的输入中仅有1个差分活动字节,经过π-1变换后该行必至少存在3个差分活动字节.经过τ-1变换与π-1变换后,必存在3列有差分活动字节,从而产生矛盾,形成了1个不可能差分对应.

证毕.

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

利用定理1中构造的区分器I,改进7轮Crypton算法的不可能差分分析,恢复最后1轮圈子密钥;同时通过并行利用4条定理2给出的不可能差分区分器,恢复7轮Crypton算法的主密钥.

3.1 改进的7轮Crypton算法不可能差分分析

文献[10]使用定理1中所给出的区分器,对7轮Crypton算法进行了攻击,恢复了第7轮的圈子密钥.通过进一步研究发现,上述攻击存在2个问题:

1) 根据性质4,当输出差分模式满足(0,0,1,1)时,输入差分模式不存在(0,0,1,1)的形式;

2) 根据性质4,当输出差分第11,15 B差分活动,而输入差分为任意2 B差分活动时,仅存在15个可能的差分对应,因此其概率应为2-12.4而非2-11.8.

基于定理1中的4轮不可能差分区分器,结合扩散层性质、快速排序算法、分割攻击与早夭技术[27]改进7轮Crypton算法的不可能差分分析.攻击过程分为预计算与在线攻击2个阶段.

1) 在预计算阶段需要预计算并存储3个表

① 表T1.满足第3列中仅有1 B差分活动,其余字节为非差分活动的差分状态Δz1,c ol(3)共有210种取值.因此,S盒输出差分Δy1,c ol(3)共有210种取值,根据性质5,给定S盒输入差分Δx1,c ol(3),平均能够确定出210y1,c ol(3).同时,由于Δx1,c ol(3)=ΔPc ol(3),表T1以232个明文差分ΔPc ol(3)为索引,存储对应的210x1,c ol(3).

② 表T2.对于仅在第0个字节处差分活动的状态对Δz6,c ol(0)′,共有28种可能取值.根据性质5,表T2以232个密文差分ΔCc ol(2)为索引,存储28个(z6′[0],z6″[0])和对应的y7,r ow(0).

③ 表T3.类似表T2,对于仅在第2个字节处为差分活动的状态对Δz6,c ol(2)′,共有28种可能取值.因此以232个ΔCc ol(0)为索引,存储28个(z6′[2],z6″[2])和y7,r ow(2).

2) 在线攻击阶段包含6个步骤:

步骤1. 选择2n1个明文结构,其中明文满足在第3,7,11,15字节上取所有的值,在其余字节上取固定值,1个明文结构包含232个明文,可以构造263个明文对.因此攻击的选择明文量为2n1+32,其中包含2n1+63个明文对.

步骤2. 运用快速排序算法筛选明文对.根据性质3,筛选出密文在第0,2,4,6,8,10,12,14字节差分活动,其余字节差分不活动的明文对,剩余2n1-1个明文对.以明文对序号作索引,将筛选得到的明文对存储在表Ω中,存储明文的第3,7,11,15字节与密文的第0,2,4,6,8,10,12,14字节.

步骤3. 求解.对于表Ω剩余的2n1-1个明文对,利用对应的密文差分查表T2,得到对应的28个密钥6[0],z″6[0]).以232的可能值为索引,将6[0],z″6[0])与明文对序号存入表Ω1中.对于每一个密钥,平均剩余明文对个数为2n1-1×28232=2n1-25.

步骤4. 求解.对于当前值所对应表Ω1中的2n1-25个明文对,利用密文差分查表T3得到对应的28个密钥6[2],z″6[2]).以232的可能值为索引,将6[0,2],z″6[0,2])与明文对的序号存入表Ω2中.对于每一个密钥,平均剩余明文对的个数为2n1-25×28232=2n1-49.

步骤5. 求解[0,2].对于当前值所对应表Ω2中的2n1-49个明文对,根据性质4,满足输入第0B与第8B为差分活动,输出任意2B差分活动的对应有30个,且差分满足5[0].穷举5[0]的取值,根据性质5,可以确定出密钥[0,2],其中仅有30个满足区分器的输出.以216[0,2]的可能值为索引,将明文对序号存储在表Ω3中.对1个[0,2],平均剩余的明文对个数为2n1-49×30216=2n1-60.1.

步骤6. 对每一个)的取值建立1个表T,表T以232个密钥ke 0,c ol(3)可能的取值为索引,每个地址存储1 b.令表T中所有地址上均存放0,并初始化计数器flag=0.利用表Ω3中剩余的2n1-60.1个明文对差分,查表T1获得对应的210个密钥ke 0,c ol(3);查找表T中地址ke 0,c ol(3)所对应的比特值,若对应值为0则将其置1,同时计数器加1,否则不做任何操作并检测下一个明文对.若在检测过程中有flag=232,则可以判定当前所检测的10 B密钥)为错误密钥,提前终止本次检测,并取)的下一个取值进行检测;若遍历表Ω3中2n1-60.1个明文对后,计数器满足flag<232,则判定)为候选密钥.进一步搜索表T中比特值为0处所对应的地址ke 0,c ol(3),并将)列为候选密钥.

具体的攻击路径如图4所示,其中黑色表示差分活动字节,白色表示差分为0的字节,斜线表示可能存在差分的字节,网状表示猜测的密钥字节.定理3给出上述7轮Crypton算法不可能差分分析的复杂度分析结果.

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

定理3. 利用4轮不可能差分区分器能够对7轮Crypton算法进行不可能差分分析,恢复第7轮的圈子密钥,其时间复杂度为2112.6,数据复杂度为2120.4,存储复杂度为299.1.

证明. 预计算阶段与在线攻击阶段的复杂度相差较大,在线攻击阶段的复杂度占主要部分,可以忽略预计算阶段的复杂度.

在线攻击阶段各步骤的复杂度如下:

步骤2快速排序筛选明文对的时间复杂度为2n1×232lb 232=2n1+37次比较,表Ω顺序存储2n1-1个明密文对,其中包含明文4B,密文8B,存储复杂度为2n1-1×2×(4+8)=2n1+2×3B.

步骤3对2n1-1个明文对查找表T2并存储的时间复杂度为2n1-1×28=2n1+7次查表,表Ω1需要存储2B与明文对序号,其存储复杂度为2n1-25×232×(2+(n1-1)8)B.

步骤4对剩余的2n1-25在232下查表T3并存储的时间复杂度为2n1-25×232×28=2n1+15次查表,表Ω2需要存储4B及对应的明文对序号,对应的存储复杂度为2n1-49×232×(4+(n1-1)8)B.

步骤5对剩余2n1-49个明文对在给定264下,穷举可能差分的时间复杂度为2n1-49×264×28=2n1+23次查表,表Ω3存储对应明文对序号的复杂度为2n1-60.1×216×(n1-1)8B.

步骤6中1组错误密钥通过1次检测的概率为1-210232=1-1222,因此232N次检测中均不通过的概率为[1-(1-2-22)N]232,即N次检测中都不通过的概率.那么能够通过222t次检测,不能通过222(t+1)次检测的概率为pt=[1-(1-2-22)222t]232-[1-(1-2-22)222(t+1)]232,t的期望是

利用早夭技术,平均需要检测222×23.6=225.6个明文对能够得到1个候选密钥,因此步骤7需要在1组80 b密钥)下,对225.6个明文对查表T1T,对应的时间复杂度为280×225.6×210=2115.6次查表,存储复杂度为232b.

候选密钥集的规模为ε=2112×(1-2-22)2n-60.1,控制候选密钥集规模为1时,得到n1=88.4.改变区分器的输出差分活动字节为6[1,3]并重复进行如上攻击,可以得到.攻击的数据复杂度为2120.4个选择明文,时间复杂度主要由步骤2确定,利用文献[10]中的方法将查表操作转换为Crypton算法加密操作,共需要2125.4×2-14×76×2=2112.6次7轮Crypton算法加密,存储复杂度主要步骤3确定,共需要263.4×232×(2+(88.4-1)8)=299.1B.

证毕.

上述7轮不可能差分分析没有利用密钥扩展算法的信息泄漏规律,而且复杂度较低,因此适用于128 b192 b256 b共3种密钥规模的算法.

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

使用定理2中的区分器,仅改变区分器输出的差分活动字节分别为第0,1,2,3 字节,则4条区分器具有相同输入,通过选取相同的明文结构,并行利用4条不可能差分路径,结合密钥扩展算法性质可以给出7轮Crypton算法多重不可能差分分析,恢复算法主密钥.攻击过程分为预计算阶段与在线攻击阶段.

在预计算阶段,需要预计算并存储6个表.

Ti:仅在第i列(i=0,1,2,3)有1 B差分活动,其余字节非差分活动的6,c ol(i)共有210种可能值,则得到第7轮S盒的输入差分Δx7,r ow(i)有210种可能取值,S盒的输出差分Δy7,r ow(i)是已知的,则性质5平均可以得到210y7,r ow(i).因此表Ti以232个Δy7,r ow(i)为索引,存储210y7,r ow(i).同时,注意到S盒的输出差分可由密文对差分ΔC移位得到,因此可以利用密文对的差分直接查表.

T4:仅在第15 B差分非0的差分Δz1,c ol(3)共有28种可能取值,可以得到S盒的输出差分Δy1,c ol(3).由明文对可以得到S盒的输入差分Δx1,c ol(3),根据性质5可以求出28x1,c ol(3),将x1,c ol(3)和(z1[15],

存储在表T4中,以4 B明文差分ΔPc ol(3)为索引.

T5:类似表T4,当仅有第13 B为差分活动时,其所对应的状态对差分Δz1,c ol(1)共有28种可能取值.利用232个4 B明文差分ΔPc ol(1)索引,存储x1,c ol(1)和).

在线攻击阶段共包含8个步骤:

步骤1. 选择2n2个明文结构,其中的明文满足在第1,3,5,7,9,11,13,15字节取所有值,在其余字节上固定.1个明文结构包含264个明文,可构造2127个明文对,因此选择明文量为2n2+64,明文对2n2+127个.

步骤2. 对i=0,1,2,3,分别运用快速排序算法筛选明文对.若i=3,保留密文在第1,5,9,13字节的差分活动,其余字节差分为0的明文对,筛选后剩余2n2+31个明文对.以明文对序号为索引,将剩余明文对存储在表Γi中,存储明文的第1,3,5,7,9,11,13,15字节与密文的第1,5,9,13字节.

步骤3. 求解ke 0,c ol(1).对表Γ3中2n+31个明文对,利用明文差分ΔPc ol(1)查找表T5,可以得到28个状态对[13])和密钥ke 0,c ol(1).以232个密钥ke 0,c ol(1)的可能值为索引,将对应的与明文对序号存入表Ω1中.1个ke 0,c ol(1)平均剩余的明文对个数为2n2+31×28232=2n2+7.

步骤4. 求解ke 0,c ol(3).对Ω1中2n2+7个明文对,利用明文差分ΔPc ol(3)查找表T4,可以得到28个状态对和密钥ke 0,c ol(3).以232个密钥ke 0,c ol(3)的可能值为索引,将28与明文对序号存储在表Ω2中.1个ke 0,co l(3)平均剩余明文对个数为2n2+7×28232=2n2-17.

步骤5. 由密钥ke 0,c ol(1,3)的当前值求解ke 1[7,15].由表Ω2中2n2-17个明文对,可以得到S盒的输入差分Δx2[7,15].根据性质4,S盒的输出差分满足Δy2[7]=Δy2[15].对Δy2[7]的取值进行穷举,由性质5可以求出(x2[7,15],y2[7,15]),从而可以确定密钥ke 1[7,15].以密钥ke 1[7,15]的216个可能的取值为索引,将满足区分器的明文序号存储在表Ω3中.1个ke 1[7,15]平均剩余明文对个数2n2-17×30216=2n2-28.1.

步骤6. 对10 B密钥(ke 0,c ol(1,3),ke 1[7,15])建立表T,以232的可能值为索引,每个索引存放1 b.将表T每个地址对应的位置0,初始化计数器flag为0.遍历表Ω3中2n2-28.1个明文对,由密文差分,查表T3获得对应的210个密钥;查表T对应的值,若值为0则将其修改为1,并将flag+1,否则,取下一个明文对进行检测.若flag=232,则可判定当前使用的10 B密钥(ke 0,c ol(1,3),ke 1[7,15])为错误密钥,选取密钥的下一个取值进行检测;若遍历表Ω3后,存在flag<232,则执行步骤7.

步骤7. 对密钥(ke 0,c ol(1,3),ke 1[7,15]),在i=0,1,2时,分别进行下面2步检测:

步骤7.1. 对Γi中的明文对,加密1轮后,若输出在第1行与第3行中差分活动字节多于1个或者2个差分活动字节不在同一列,则丢弃该明文对;否则加密至第2轮π变换后,若仅有1列包含2个差分活动字节,其余字节均非差分活动,则保留该明文对.平均剩余明文对个数为2n2+31×2-48×3065 025=2n2-28.1.

步骤7.2. 建立1个表Λi,以232可能值为索引,每个位置存放1 b.将所有位置置0,并初始化计数器flag=0.根据表Γi中剩余的明文对查表Ti得到,然后按地址查找表Λi对应位置的比特值,若为0则将其修改为1,并将计数器加1;否则,对下一个明文对进行检测.若flag=232,则判断当前的(ke 0,c ol(1,3),ke 1[7,15])为错误密钥,终止本次检测,取密钥的下一个取值进行检测.若遍历表Γi后仍有flag<232,当i<2时,将i增加1后再次执行步骤7;在i=2时,判定(ke 0,c ol(1,3),ke 1[7,15])为候选密钥,并找出使]=0成立的,并将)判定为正确密钥的候选密钥.

步骤8. 由按照密钥扩展算法求出ke 1[7,15],若与已知的值一致,则判定为正确密钥;否则返回步骤7.对剩余8 B密钥ke 0,c ol(0,2)进行穷举,进行7轮Crypton算法加密检测,恢复得到原始主密钥.

攻击路径如图5所示,定理4给出7轮Crypton算法多重不可能差分分析的复杂度分析结果.

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

定理4. 并行利用4条不可能差分区分器可以恢复7轮Crypton算法的主密钥,其时间复杂度为2115.2,数据复杂度为2120.9,存储复杂度为2101.8.

证明. 步骤2分别对4组2n2+64个明文进行快速排序筛选的时间复杂度为4×2n2×264lb 264=2n2+72次比较,对4组2n2+31个明密文进行存储,存储复杂度为4×2n2+31×2×(4+8)=2n2+36×3 B.

步骤3对2n2+31个明文对查表T5并存储的时间复杂度为2n2+31×28=2n2+39次查表,表Ω1的存储复杂度为232×2n2+7×(2+(n2+31)8)B.

步骤4在ke 0,c ol(1)下,对2n2+7个明文对查表T4的时间复杂度为2n2+7×232×28=2n2+47次查表,表Ω2的存储复杂度为232×2n2-17×(4+(n2+31)8)B.

步骤5的时间复杂度为264×2n2-17×28=2n2+55次查表,存储复杂度为216×2n2-28.1×(n2+31)8B.

步骤6利用类似3.1节中的早夭技术,时间复杂度为280×225.6×210=2115.6次查表.

错误密钥(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检测的密钥个数为280×q≈280(1-e-232-1.4425×2n2-50.1).

步骤7分2个子步骤,对于i=0,1,2,步骤7.1的时间复杂度可以忽略不计,通过步骤7.2中检测的概率为q′=1-e-232-1.4425×2n2-50.1,则步骤7.2的时间复杂度为280×225.6×210×q×(q′)i次查表.步骤6与步骤7的时间复杂度之和不超过2115.6×4次查表.

步骤8的候选密钥量为280+4×32×[(1-2-22)2n2-28.1]4≈2208-1.4425×2n2-50.1,对剩余的候选密钥依次穷举8 B,总的计算复杂度为2208-1.442 5×2n2-50.1×264次加密.取n2=56.9时,时间复杂度主要由步骤2所决定2115.2,数据复杂度为2120.9,存储复杂度为2101.8.

证毕.

7轮Crypton算法多重不可能差分分析没有利用密钥扩展算法的信息泄漏规律,而且复杂度较低,因此适用于128 b192 b256 b共3种密钥规模的算法.

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

本节在3.1节中7轮Crypton算法不可能差分分析的基础上向后拓展1轮,结合密钥扩展算法与扩散层的性质,利用分割攻击思想给出8轮Crypton-256算法的不可能差分分析过程及复杂度分析结果.攻击分为预计算阶段与在线攻击阶段.

预计算阶段需要预计算并存储5个表.

T1:穷举216个差分,可以得到Δx8,r ow(0).根据性质3可以得到ΔCc ol(2)y8,r ow(0),以232个ΔCc ol(2)的可能值为索引,存储对应的216y8,r ow(0)).

T2:类似表T1,穷举216个差分7,c ol(1),以232个ΔCc ol(3)的可能值为索引,存储对应的216y8,r ow(1)).

T3:类似表T1,穷举216个差分7,c ol(2),以232个ΔCc ol(0)的可能值为索引,存储对应的216y8,r ow(2)).

T4:类似表T1,穷举216个差分7,c ol(3),以232个ΔCc ol(1)的可能值为索引,存储对应的216y8,r ow(3)).

T5:穷举210个差分Δz1,c ol(3),以232个明文差分ΔPc ol(3)为索引,存储对应的210x1,c ol(3).

在线攻击阶段包含8个步骤:

步骤1. 选择2n个明文结构,其中的明文满足在第3,7,11,15 B上取所有的值,在其余字节上取固定值,1个明文结构包含232个明文,可以构造263个明文对.因此攻击的选择明文量为2n+32,将2n+63个明文对以明文序号为索引存储在表Ω1中.

步骤2. 对表Ω1中的2n+63个明文对,每1个密文差分ΔCc ol(2)通过查表T1可以得到216y8,r ow(0),结合密文可以得到对应的2167[0,8],z″7[0,8]).以的取值为索引,平均剩余2n+63×216232=2n+47,将其与明文对序号存储在表Ω2中.

步骤3. 在下,对表Ω2中剩余的2n+47个明文对,类似步骤2对密文差分ΔCc ol(3)查表T2得到y8,r ow(1),求出对应的7[1,9],z″7[1,9]).以的取值为索引,剩余2n+31,将其与明文对序号存储在表Ω3中.

步骤4. 在下,对表Ω3中剩余的2n+31个明文对,密文差分ΔCc ol(0)查表T3求出对应的).以的取值为索引,平均剩余2n+15,z″7[0,1,2,8,9,10]),将其与明文对序号存储在表Ω4中.

步骤5. 在下,对表Ω4中剩余的2n+15个明文对,密文差分ΔCc ol(1)查表T4求出对应的7[3,11],z″7[3,11]).以的取值为索引,剩余2n-1,将其也明文对序号存储在表Ω5中.

步骤6. 在下,对表Ω5中剩余的2n-1个明文对穷举28个Δz6[0],已知,根据性质5平均可以得到28).以的取值为索引,剩余2n-25,将,z″7[8,9,10,11])与明文对序号存储在表Ω6中.

步骤7. 在)下,对表Ω6中剩余的2n-25个明文对穷举28个Δz6[2],可以得到).以的取值为索引,剩余2n-49,将其及明文对序号存储表Ω7中.

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

步骤8. 对每1个),根据性质1可以得到[0,2])的1个取值,遍历表Ω7中的明文对,对明文对加密0.5轮,6[0,2],z″6[0,2])解密0.5轮后检测是否符合不可能差分区分器的输入与输出.若遍历表Ω7中明文对后,均能够满足区分器的输入与输出则为错误密钥;否则将其列为正确密钥的候选密钥.

图6给出了8轮Crypton算法的不可能差分分析的具体路径,定理5给出其复杂度分析结果.

定理5. 8轮Crypton-256算法的不可能差分分析能够恢复最后1轮圈子密钥,其时间复杂度为2213,数据复杂度为2103,存储复杂度为2154.4.

证明. 以表1的形式给出8轮Crypton-256算法不可能差分分析中各步的时间复杂度与存储复杂度.

Table 1 Complexity of Impossible Differential Attack on 8-round Crypton-256
表1 8轮Crypton-256算法不可能差分分析复杂度

StepTimeComplexityMemoryComplexity12n+64×322n+792n+79×(4+(n+63)∕8)32n+952n+63×(8+(n+63)∕8)42n+1112n+47×(12+(n+63)∕8)52n+1272n+31×(16+(n+63)∕8)62n+1352n+7×(10+(n+63)∕8)72n+1432n-17×(4+(n+63)∕8)82n+144E

E: One round encryption.

控制经过步骤8后剩余的候选密钥量2192×(1-2-14.9)2n-49=1时,得到n=71.时间复杂度为2213次8轮Crypton-256算法加密,存储复杂度为2154.4B,数据复杂度为2103个选择明文.

证毕.

当改变区分器的输出形式时,令Δz6[1,3]为区分器输出的差分活动字节,重复上述攻击过程可以得到,利用性质2可以恢复8轮Crypton-256算法的256 b主密钥,复杂度分析结果由定理6给出.

定理6. 8轮Crypton-256算法的不可能差分分析能够恢复256 b主密钥,其时间复杂度为2214,数据复杂度为2103,存储复杂度为2154.4.

5 结束语

本文对Crypton算法在不可能差分分析下的安全性进行了研究.指出了文献[10]中对Crypton算法不可能差分分析中差分传递概率估计与攻击路径表示中的错误,并运用π变换性质、分割攻击、早夭技术、快速排序算法改进了7轮Crypton算法不可能差分分析结果;同时并行使用4条不可能差分区分器,结合密钥扩展算法的性质恢复了7轮Crypton算法的主密钥;向后拓展1轮后给出了8轮Crypton算法的不可能差分分析并对其复杂度进行了分析.本文结果与现有Crypton算法的不可能差分分析结果对比如表2所示:

Table 2 Comparison of Impossible Differential Attacks on Crypton
表2 Crypton算法不可能差分分析结果对比

Key|K|RoundRecoveredKeyDataComplexityTimeComplexityMemoryComplexityReference128b∕192b∕256b5|K|283.4243Ref[6]128b∕192b∕256b6|K|2912124Ref[8]128b∕192b∕256b6|K|293.52110.5Ref[8]128b∕192b∕256b7|K|∕221212125.2Ref[10]128b∕192b∕256b7|K|∕221212116.2Ref[10]128b∕192b∕256b7|K|∕22120.42112.6299.1Section3.1128b∕192b∕256b7|K|2120.92115.22101.8Section3.2256b8|K|∕2210322132154.4Section4256b8|K|210322142154.4Section4

目前,针对Crypton算法的研究多集中于中间相遇攻击、不可能差分分析和Biclique攻击等单密钥情况下的分析,而Crypton算法的密钥扩展算法较弱,能否进一步结合密钥扩展算法中的弱点,给出更高轮数的攻击或者复杂度更低的相关密钥条件下的攻击结果是下一步研究的重点.

参考文献:

[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]. 计算机研究与发展, 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)(卫宏儒, 殷广丽. LBlock算法的相关密钥不可能差分分析[J]. 计算机研究与发展, 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]. 计算机工程, 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)(胡弘坚, 金晨辉, 李信然. 改进的7轮AES -128的不可能差分攻击[J]. 密码学报, 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

(The PLA Information Engineering University, Zhengzhou 450001)

Abstract: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 2103 chosen plaintexts, a time complexity of 2214 8-round encryptions, a memory complexity of 2154.4 B. 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.

Key words:block cipher; cryptanalysis; Crypton; impossible differential attack; early abort technique

收稿日期:2016-06-12;

修回日期:2016-08-31

基金项目:中国博士后科学基金项目(2014M562582) This work was supported by the China Postdoctoral Science Foundation (2014M562582).

通信作者:郭建胜(tsg_31@126.com)

中图法分类号:TP309