Piccolo 算法的相关密钥-不可能差分攻击∗

2019-10-28徐林宏郭建胜崔竞一李明明

软件学报 2019年8期

徐林宏, 郭建胜, 崔竞一, 李明明

(信息工程大学,河南郑州 450001)

随着物联网技术的不断发展,人们对其安全性的要求也越来越高,适用于这些资源受限环境的密码算法即轻量级密码算法成为密码学研究的一个热点,大量轻量级密码算法被设计出来,如 PRESENT[1],LBlock[2],PRINCE[3],SIMON[4]等算法.

Piccolo 算法是由日本密码学家Shibutani 等人[5]于CHES 2011 上提出的一种适用于资源受限环境的轻量级分组密码算法,其算法结构为广义Feistel 结构,硬件实现效率较高.该算法一经提出,就受到学界的广泛关注.

不可能差分分析是由Knudsen[6]和Biham[7]两人独自提出的单密钥条件下的密码分析方法,Knudsen 在分析高级加密标准的候选算法DEAL 的安全性时,提出了轮函数为双射的Feistel 结构存在5 轮的不可能差分路径;Biham 等人在FSE’99 上介绍了基于中间相错的思想构造不可能差分的方法.此后,不可能差分在研究很多标准密码算法的安全性时得到了广泛应用,如AES[8],CLEFIA[9]等.

相关密钥攻击同样是由Biham[10]和Knudsen[11]各自独立提出的,其主要思想是:基于密码算法密钥扩展方式对算法安全性的影响,利用密钥扩展算法的一些弱点,通过分析相关密钥与原有密钥之间的关系对加密结果造成的影响恢复出原有密钥.该攻击方法对于具有简单密钥扩展方式的密码算法尤其有效.当前,主流应用是在此攻击方法假设条件下,与其他密码分析方法相结合,如差分分析、不可能差分分析、矩阵攻击等,对算法进行安全性分析.因此,本文结合上述两种攻击方法,对Piccolo 算法进行了相关密钥-不可能差分分析.

· 相关工作

现有的对于Piccolo 算法的安全性分析结果较多,这里主要介绍差分类分析结果.其中,利用Biclique 分析方法可得到对于全轮Piccolo-80 和Piccolo-128 算法低于穷举复杂度的攻击结果[12−14].在单密钥条件下,Azimi 等人[15]于2014 年利用不可能差分分析方法,对含前向白化密钥12 轮Piccolo-80 算法、不含白化密钥的13 轮Piccolo-80 算法和含后向白化密钥的15 轮Piccolo-128 算法进行了安全性分析;2015 年,Tolba 等人[16]给出了14轮Piccolo-80 不含白化密钥和17 轮Piccolo-128 含后向白化密钥的中间相遇攻击结果;2017 年,Liu 等人[17]在文献[16]基础上进行改进,利用中间相遇攻击方法,给出了不含白化密钥的14 轮Piccolo-80 和含后向白化密钥的的18 轮Piccolo-128 的安全性分析结果.在相关密钥条件下,Minier[18]在2013 年结合相关密钥攻击和不可能差分分析,实现了对均不含白化密钥的14 轮Piccolo-80 和21 轮Piccolo-128 的攻击,但攻击所需的数据量超过算法的分组规模264.2016 年,Zheng 等人[19]利用U-method 分别给出了Piccolo-80 和Piccolo-128 算法11 轮和17轮的相关密钥-不可能差分区分器,但未能给出具体的安全性分析结果.

· 本文工作

本文主要使用相关密钥-不可能差分分析方法评估了Piccolo 算法的安全性:首先,基于中间相错思想和密钥扩展的性质,寻找到所有可能的最长相关密钥-不可能差分区分器;而后,利用轮函数等效结构减少攻击所需选择明(密)文量,给出了15 轮Piccolo-80 和21 轮Piccolo-128 算法的攻击结果,所需数据复杂度和计算复杂度均低于穷举分析.在不考虑Biclique 分析结果的情况下,均优于现有分析结果.本文攻击结果见表1.

Table 1 Comparison of attack results on Piccolo表1 Piccolo 算法的攻击结果对比

· 文章结构安排

本文首先介绍研究背景.第1 节主要介绍Piccolo 算法的相关知识.第2 节给出Piccolo-80 的相关密钥-不可能差分分析结果.Piccolo-128 算法的相关密钥-不可能差分分析主要在第3 节中给出.最后对全文进行总结.

1 相关知识

本节中,首先给出下文中一些常用符号说明,而后给出Piccolo 算法具体描述.

1.1 符号说明

· (P,P′):输入明文状态.

· (C,C′):输出密文状态.

·WKt:第t个白化密钥,t∈{0,1,2,3}.

· (rk2r,rk2r+1):第r轮轮密钥.

1.2 Piccolo算法简介

Piccolo 算法的分组规模为64bits,根据密钥规模不同,可分为Piccolo-80 和Piccolo-128 两种,对应轮数分别为25(0～24)轮和31(0～30)轮.其加密环节主要由密钥白化、F函数和字节置换操作组成.密钥白化操作仅在第1轮和最后一轮存在,保证加脱密结构的一致性.轮变换包括F函数和字节置换,具体的Piccolo 算法轮函数各环节的结构示意图详见文献[5]的图1～图4.轮函数各个环节和密钥扩展算法的介绍如下给出.

·F函数

每一个F函数包含了8 个相同的4bits 双射S盒和一个列混合矩阵M,通过对16bits 数据进行作用,实现算法的混乱和扩散.即有(x0(4),x1(4),x2(4),x3(4))t=M⋅(x0(4),x1(4),x2(4),x3(4))t,其中,列混合矩阵M的运算定义在由不可约多项式x4+x+1 生成的GF(24)上.

· 字节置换RP

该环节主要实现各字节的移位替换,即

· 密钥扩展算法

Piccolo 算法的密钥扩展有80bits 和128bits 密钥两种.其中,对于Piccolo-80,将80bits 主密钥划分为5 个部分,每个部分包括2 字节,即K=K0||K1||K2||K3||K4,其中,根据F函数中采用的是4bits的S盒,可对每一字节密钥进行再划分,即

白化密钥WKj(j∈{0,1,2,3})由主密钥直接生成,其中,

轮密钥(rk2r,rk2r+1)由主密钥与固定常数异或所得,r∈{0,…,24}.在Piccolo-128 中,增加了6 个字节的主密钥,有K=K0||K1||K2||K3||K4||K5||K6||K7,相应的白化密钥也有所变化,即

表2 和表3 分别给出了两个版本Piccolo 算法轮子密钥和主密钥的对应关系.

Table 2 Correspondence between the master key and the round keys of Piccolo-80表2 Piccolo-80 算法的主密钥与轮密钥之间的对应关系

Table 3 Correspondence between the master key and the round keys of Piccolo-128表3 Piccolo-128 算法的主密钥与轮密钥之间的对应关系

2 15 轮Piccolo-80 算法的相关密钥-不可能差分攻击

本节中首先介绍了Piccolo 算法具有的3 点性质,而后基于中间相错思想,分析了Piccolo-80 算法在状态值和主密钥值均仅有单比特块差分活动的情况下,其能够具有的所有最长11 轮相关密钥-不可能差分区分器.通过选择合适的区分器,向上向下各拓展两轮,得到了15 轮Piccolo-80 含前向白化密钥的安全性分析结果.

2.1 Piccolo算法性质

性质1(密钥扩展算法性质).主要有以下3 个方面.

(1) 对于Piccolo 两种密钥规模的算法,除白化密钥外,其每一主密钥字Ki在各轮密钥中分布的位置均与其第1 次出现的位置相同.具体来说,若主密钥Ki第1 次出现在轮密钥的左(右)半部分,则后续的均出现在轮密钥的左(右)半部分.

(2) 在不考虑轮常数的影响时,对于Piccolo-80,其轮密钥(除白化密钥外)是由主密钥构成的一个周期为5的循环.

(3) 对于Piccolo-128 算法,在不考虑轮常数的影响下,自第0 轮开始,其轮密钥左半部分是按(K2,K4,K6,K2,K6,K0,K4,K6,K4,K2,K0,K4,K0,K6,K2,K0)排列的一个16 轮循环,右半部分是按(K3,K5,K7,K1,K7,K3,K5,K1,K5,K7,K3,K1)排列的一个12 轮循环.

证明:分别观察表2、表3 中Piccolo-80 和Piccolo-128 主密钥与轮密钥间的对应关系,可得上述结论.□

性质2.根据算法结构中的F函数采用的是4bits 的S盒,且在字节置换操作中,实现的是对字节整体的移位操作,未改变各个字节内部每一比特的状态,因此在引入明文差分时,可在与密钥进行差分抵消的位置选取4bits 或8bits 差分,相应地选择4bits 或8bits 的相关密钥差分实现差分抵消.当选取明文差分为4bits 时,攻击所需的相关密钥量约为24,较差分选为8bits 时有所减少,具体应用见第2.3 节和第3.2 节.

性质3(轮函数等效结构)[12].改变Piccolo 算法中轮密钥加的顺序,不影响算法加解密效果,且根据轮密钥加变换顺序的不同有两种算法轮函数的等效结构,具体结构如图1 所示.

Fig.1 Equivalent structure of round function图1 轮函数等效结构

在下文给出的攻击过程中,利用性质3,通过在数据收集阶段采用算法等效结构,可以有助于减少攻击过程中的选择明(密)文量,降低攻击所需数据复杂度.这里仅以Piccolo-80 算法为例进行具体说明,对于Piccolo-128算法具有同样的效果.

例1:对于Piccolo-80 算法,由图2 的攻击路径可得:在数据收集阶段使用算法等效结构,使得第14 轮不含密钥加运算的作用,进而可由预计算直接得到满足第14 轮的输入状态差分为(α,0,0,0,0,β,γ,0)的密文对.也就是说,对于2n个明文结构,所需的选择密文量为2n+24.而若未使用算法等效结构,则根据密文差分中有6 个活动差分字节,攻击所需的选择密文量2n+48.进一步的,在攻击计算复杂度相同的条件下,显然,未使用等效结构所需的数据复杂度更高.

2.2 11轮相关密钥-不可能差分区分器

根据算法轮函数结构,在不含相关密钥差分,输入状态仅存在1 个差分活动比特块时,算法达到完全性有两种情况.

(1) 活动比特块位于F函数的输入,经过3 轮变换后,算法达到完全.

(2) 活动比特块位于密钥加操作的输入,经过4 轮变换后,算法达到完全.

引入相关密钥差分,一般用于实现与输入状态差分的相互抵消,得到更长的区分器,提升密钥恢复攻击时的轮数,所以说,密钥差分选取的位置也十分关键.一般情况下,针对Piccolo 算法,所能构造区分器的最长轮数由同一主密钥字在轮密钥中连续出现5 次的相距轮数决定.但并不是说,所能构造的区分器轮数就一定达到相距轮数,还需受到算法达到完全性的轮数限制.此外,直观地可以发现:若引入的密钥差分和输入状态差分活动比特块越多,算法达到完全所需的轮数越少.

综合上述考虑,利用中间相错思想,在主密钥差分和输入状态差分均仅有1 个活动比特块时构造区分器.特别地,当轮密钥为(K4,K4)时,若在K4中引入一个差分活动块,则为了实现差分抵消,需要在状态差分中有2 个差分活动比特块,此种情况的区分器也在本节考虑范围内.由此,利用性质1,尤其是Piccolo-80 密钥扩展中轮密钥具有的5 轮循环性,能够构造得到的Piccolo-80 的最长11 轮相关密钥-不可能差分区分器主要有3 种情形,见表4.其中,密钥差分选取在K0中与选取在K1中,所得的区分器情形基本一致,且根据差分选取的左右位置不同,共有12 种情况;密钥差分选取在K2中与选取在K3中,所得的区分器情形一致,且与情形1 类似,也有12 种情况;密钥差分选取在K4中时,根据差分选取的左右位置不同,共有6 种情况.综上,能够找到30 条11 轮Piccolo-80 的相关密钥-不可能差分区分器.附录A、附录B 给出了3 种情形区分器的示例.

Table 4 11-round related-key impossible differential distinguishers of Piccolo-80表4 11 轮Piccolo-80 算法的相关密钥-不可能差分区分器

由于本文攻击中考虑前向白化密钥对算法安全性的影响,因此密钥差分选取在K0和K1中的区分器不适合用于攻击环节.而为了使攻击轮数尽可能长,且攻击复杂度尽可能低,考虑选用输入差分活动块较少的区分器,故在下文的攻击中,选用的区分器为情形2 中的区分器,且区分器的位置取为第2 轮～第12 轮,具体路径见附录A 中表A 的左半部分.特别指出:文献[19]给出的Piccolo-80 区分器也是情形2 中的一种,且情形2 中的位于第12 轮～第22 轮的区分器也可用来分析15 轮Piccolo-80 算法仅含后向白化密钥的安全性,具体攻击过程和复杂度估计与下文给出的攻击算法1、算法2 类似.

2.3 15轮密钥恢复攻击

根据上述构造所得区分器,向上解密2 轮,向下加密2 轮,基于分割攻击思想,可对15 轮Piccolo-80 算法进行密钥恢复,攻击总共分为两个阶段:一为数据收集阶段,二为密钥猜测阶段.本小节中根据选取密钥差分的比特块规模不同,给出了两种攻击算法,可以恢复出Piccolo-80 算法的全部80bits 主密钥,具体的攻击步骤基本类似,但在所需复杂度方面有一定差异,下面具体介绍这两种攻击算法.具体攻击路径如图2 所示,其中,黑色表示差分活动比特块,灰色标识差分值为γ的比特块,差分不活动比特块用白色标识.

Fig.2 15-round related-key impossible differential cryptanalysis of Piccolo-80图2 15 轮Piccolo-80 算法相关密钥-不可能差分分析

2.3.1 攻击算法1

· Step 1.数据收集.

基于性质3,对于密文(C,C′),选择其在第14 轮的输入差分为(α,0,0,0,0,β,γ,0),其中,α,β,γ表示差分活动比特块,且每一比特块表示一个字节.则显然:对于一个结构,需要选择224个选择密文,则得到247个密文对.当选定γ的一个非零取值时,因为有28−1 种可能,所以对应的密文对数量239个.此时选择相应的密钥差分筛选明文差分为(*,0,*,*,0,*,*,*)的密文对,予以保留,则平均剩余的密文对个数为239×2−16=223.构造2n个结构,当γ选定一个非零值时,可得到2n+23个平均剩余密文对.

· Step 2.密钥猜测.

第2 步中具体介绍密钥猜测阶段的攻击步骤,其中,Step 2.1～Step 2.4 是基于γ取定的情况,γ≠0.

➢ Step 2.1.对于选定的一个γ,根据已得到的密文对,猜测密钥,筛选使得的密文对,予以保留,则平均剩余密文对个数为2n+23×2−16=2n+7.

➢ Step 2.3.猜测密钥WK0,也就是,进行第0 轮的左半部分加密,筛选使得的密文对,予以保留,则平均剩余密文对的个数为2n−9×2−16=2n−25.

➢ Step 2.5.遍历所有可能的γ值,重复进行上述步骤2.1～步骤2.4,将均不满足第2.4 步验证条件的密钥可作为最终正确密钥的候选密钥.对于任一γ值,存在满足验证条件的密钥作为错误密钥筛除.上述攻击步骤已对48bits 密钥进行了猜测,将筛选后得到的候选密钥与未猜测32bits 密钥进行穷举,得到最终正确密钥.

攻击所需的各项复杂度由定理1 给出.

定理1.根据攻击算法1,可恢复出Piccolo-80 算法的全部主密钥,攻击所需数据复杂度为258.6,计算复杂度为278,存储复杂度为260.6.

证明:攻击所需数据复杂度主要由选择密文量决定.由攻击步骤1 可知,对于每一个结构,选择密文的数目为224,选取2n个这样的结构,得到攻击所需的选择密文量为2n+24,也就是数据复杂度为2n+24个选择密文.本文中所有攻击所需计算复杂度均采用的是文献[20]中的方法进行估计,即总的计算复杂度由构造明文结构、密钥猜测筛选阶段以及穷举剩余密钥这3 部分的计算复杂度组成.由于Piccolo 算法中F函数采用的是SDS 结构,在一轮运算中,与计算其他环节操作相比,计算F函数所需的复杂度要高出很多,因此攻击的计算复杂度可依所需计算的F函数的个数进行近似估计,下面进行具体分析.

1.由于攻击所需选择密文量为2n+24,因此构造明密文对所需的计算复杂度为TN=2n+24×2=2n+25.

2.Step 2.1 中,选定γ的一个值,猜测密钥共有216种可能,根据已得的密文对,进行轮Piccolo-80 算法解密操作,筛选的密文对,因此,攻击所需的计算复杂度为

4.Step 2.3 中,与前两步类似,猜测密钥WK0,有216种取值,筛选符合条件的密文对,则该步骤的计算复杂度为

6.Step 2.5 中,对γ所有可能的28−1 值进行遍历,进行密钥筛选.也就是重复上述攻击步骤2.1～步骤2.4,所以密钥猜测阶段总的计算复杂度体现在该步骤中,也就是需要再进行约28−2 次步骤2.1～步骤2.4,因此密钥猜测阶段总的计算复杂度为

存储复杂度主要用于存储密文结构以及错误密钥,共需约为260.6个字节.

综上,攻击所需数据复杂度为258.6个选择密文,计算复杂度为278次15 轮Piccolo-80 算法加密,存储复杂度为260.6个字节.□

2.3.2 攻击算法2

根据Piccolo 算法F函数组成部分中的S盒为4bits,我们可以将算法每一轮的输入按半字节进行划分,密钥同样如此,为简化表示,每一轮的一个输入状态将每一个主密钥定义为Ki=相应的轮密钥也依此表示.通过简化密钥选取的条件,给出如下具体攻击算法.

· 攻击条件:选择第14 轮的输入差分为(α,0,0,0,0,β,(γ||0),0),密钥差分为.其中,α,β各表示一个差分活动字节,γ表示一个差分活动半字节.

· 攻击步骤:除数据收集阶段采用上述攻击条件,使得与算法1 的步骤1 略有不同外,其余步骤与攻击算法1 基本类似.

定理2 给出了攻击算法2 的各项复杂度分析结果.

定理2.根据攻击算法2,可恢复出Piccolo-80 算法的全部主密钥,攻击所需数据复杂度为262.6,计算复杂度为277.93,存储复杂度为264.6.

证明:显然对于2n个结构,需要2n+20个选择密文,相应的密钥猜测阶段所需的计算复杂度与攻击算法1 也有所不同,具体各个环节所需的计算复杂度见表5.

Table 5 Computation complexity analysis of attack Algorithm 2表5 攻击算法2 的计算复杂度分析

经过验证可得,选取n=42.6,此攻击所需的数据复杂度约为262.6个选择密文,计算复杂度为277.93次15 轮Piccolo-80 算法加密,存储复杂度为264.6个字节.□

3 21 轮Piccolo-128 算法的相关密钥-不可能差分攻击

与第2 节类似,本节首先分析Piccolo-128 算法在输入状态差分和主密钥差分均仅有1 个活动比特块的限制条件下能够具有的最长17 轮相关密钥-不可能差分区分器,在此基础上,得到适用于攻击21 轮含前向白化密钥的Piccolo-28 算法的16 轮相关密钥-不可能差分区分器,并给出相应的安全性分析结果.

3.1 17轮相关密钥-不可能差分区分器

结合性质1,考虑Piccolo-28 主密钥的各个部分在各轮密钥中出现的分布情况,通过选取合适位置的密钥差分,实现与输入输出差分状态的抵消,能够构造得到的最长相关密钥-不可能差分区分器主要有4 种情形,见表6.

Table 6 17-round related-key impossible differential distinguishers of Piccolo-128表6 17 轮Piccolo-128 算法的相关密钥-不可能差分区分器

观察表6 可得,区分器的密钥差分选取均位于轮密钥的左半部分.这是因为每轮轮密钥的右半部分采用的是主密钥(K1,K3,K5,K7)中的任意一个,而由性质1,Piccolo-128 的轮密钥的右半部分是按(K3,K5,K7,K1,K7,K3,K5,K1,K5,K7,K3,K1)排列的一个12 轮循环.其中,K3,K5在轮密钥中连续出现5 次的相距轮数为18,K7在轮密钥中的相距轮数为17,但该三者中间轮均已达到算法达到完全性的轮数要求,在截断差分条件下不能得到矛盾.K1在轮密钥中的相距轮数为15<17,因此当密钥差分位于轮密钥的右半部分时,所能构造的区分器轮数定不超过17 轮,所以未予考虑.

由此,我们可得Piccolo-128 算法的8 条17 轮相关密钥-不可能差分区分器,且需要强调,情形1 中包含了文献[19]给出的Piccolo-128 算法的相关密钥-不可能差分区分器.

由于本文的攻击考虑前向白化密钥对算法安全性的影响,因此我们仅选取情形1 中的区分器用于实施攻击.为了能够利用多相关密钥以及轮函数的等效结构实现攻击,我们对所得区分器进行改进,将区分器的第一轮置于密钥恢复攻击环节,也就是说改进后的区分器仅为第2 轮～第17 轮,表7 给出了此16 轮区分器的具体构造.而后,借助所得区分器向上向下分别拓展2 轮和3 轮,给出了21 轮含前向白化密钥Piccolo-128 算法的安全性分析结果.此外,情形4 中的区分器也可用来分析21 轮Piccolo-128 算法仅含后向白化密钥的安全性,具体攻击过程和复杂度估计与下文给出的攻击算法3、算法4 基本一致.

Table 7 16-round related-key impossible differential distinguisher of Piccolo-128 with ΔK4=(α||0)表7 Piccolo-128 在密钥差分分别选为ΔK4=(α||0)时的16 轮区分器

3.2 21轮密钥恢复攻击

根据第3.1 节所得的16 轮区分器,向上解密2 轮,向下加密3 轮,得到对于Piccolo-128 的21 轮攻击路径,且与对Piccolo-80 算法的攻击相同,对于Piccolo-128 的攻击过程也由两个阶段组成:一为数据收集阶段,二为密钥猜测阶段.下文中给出两个攻击算法,其中,攻击算法3 选取的密钥差分规模为8bits,攻击算法4 中密钥差分规模为4bits.下面对算法3 进行详细介绍,算法4 由于步骤基本与算法3 相似,在本节仅进行简单介绍.图3 给出具体攻击路径,其中,黑色和白色标识与图2 相同,灰色表示差分值为α的比特块.

Fig.3 21-round related-key impossible differential cryptanalysis of Piccolo-128图3 21 轮Piccolo-128 算法的相关密钥-不可能差分分析

3.2.1 攻击算法3

· Step 1.数据收集.

选择明文(P,P′)的输入差分为(0,0,0,0,α,0,β,γ),同样,α,β,γ表示差分活动字节.对于一个明文结构,需要选择224个明文,则得到247个明文对.当α选定一个非零的取值时,因为有28−1 种可能,所以对应的明文对数量239个.此时选择相应的密钥差分基于性质3 轮函数的等效结构,筛选满足在第20 轮的输入差分有其余字节差分活动的明文对予以保留,构造2n个结构,当α选定一个非零值时,可得到2n+23个平均剩余明文对.第2 步中具体介绍密钥猜测阶段的攻击步骤,其中,步骤2.1～步骤2.4 是基于α的值取定的情况,α≠0.

· Step 2.密钥猜测.

➢ Step 2.1.猜测密钥WK1,对于选定的一个α,根据已得到的明文对,筛选使得的明文对,予以保留,则平均剩余明文对个数为2n+23×2−16=2n+7.

➢ Step 2.5.遍历所有可能的α值,重复进行上述Step 2.1～Step 2.4,则对于所有可能的α值,均不通过Step 2.4 检验的密钥可作为最终正确密钥的候选密钥.对于任一非零α值,存在满足第2.4 步验证条件的密钥作为错误密钥筛除.上述攻击步骤已对56bits 密钥进行了猜测,将筛选后得到的候选密钥与未猜测72bits 密钥进行穷举,得到最终正确密钥.

攻击所需的复杂度由定理3 给出.

定理3.根据攻击算法3,可恢复出Piccolo-128 算法的全部主密钥,攻击所需数据复杂度为262.3,计算复杂度为282.5,存储复杂度为264.3.

证明:攻击所需数据复杂度主要由选择明文量决定.由步骤1 可得:对于每一个结构,选择明文数量为224,选取2n个这样的结构,得到攻击所需的选择明文量为2n+24,也就是数据复杂度为2n+24个选择明文.各步骤具体的计算复杂度情况如下.

由于攻击所需选择明文为2n+24,因此构造明文对所需的计算复杂度为TN=2n+25.在Step 2.1 中,攻击所需的计算复杂度为Step 2.2 所需的计算复杂度为Step 2.3 所需的计算复杂度为Step 2.4 中,猜测密钥,验证是否成立,进行密钥筛选,则该步骤的计算复杂度为Step 3 中,对α所有可能的28−1 值进行遍历,进行密钥筛选.也就是重复上述攻击步骤2.1～步骤2.4,因此在密钥猜测阶段,总的计算复杂度约为

存储复杂度主要用于存储明文结构以及错误密钥,共需约为264.3个字节.

综上,攻击所需数据复杂度为262.3个选择明文,计算复杂度为282.5次21 轮Piccolo-128 算法加密,存储复杂度为264.3个字节.□

3.2.2 攻击算法4

· 攻击条件:与攻击算法2 类似,对各轮输入输出状态和密钥比特块按半字节进行划分.选择明文差分为(0,0,0,0,(α||0),0,β,γ),密钥差分为其中,α表示一个差分活动半字节,β,γ各表示一个差分活动字节.

· 攻击步骤:除数据收集阶段略异于攻击算法3,其余步骤基本类似.

攻击算法4 的复杂度分析结果由定理4 给出.

定理4.根据攻击算法4,恢复Piccolo-128 算法的全部主密钥所需数据复杂度为262.3,计算复杂度为2124.45,存储复杂度为264.3.

证明:选取n=42.3,则该攻击所需的数据复杂度约为262.3个选择明文,计算复杂度为2124.45次21 轮Piccolo-128 算法加密,存储复杂度为264.3个字节.主要证明过程与定理2.3 类似,此处不再赘述.□

4 结束语

本文中利用相关密钥-不可能差分分析方法,结合算法密钥扩展方面的弱点,基于算法的等效结构,给出了除Biclique 分析外,攻击轮数最长的缩减轮Piccolo 算法的差分类分析结果.其中,对于Piccolo-80 算法,找到所有30 条11 轮相关密钥-不可能差分区分器,并基于情形1 的区分器,得到了15 轮含前向白化密钥的攻击结果;对于Piccolo-128 算法,找到所有8 条17 轮区分器,并基于改进后的16 轮区分器,攻击了21 轮含前向白化密钥的Piccolo-128 算法.且根据所选取的密钥差分规模不同,对Piccolo-80 和Piccolo-128 分别给出了两个不同的攻击算法,攻击所需的复杂度均低于穷举分析,优于已有攻击结果.分析结果表明,15 轮Piccolo-80 算法和21 轮Piccolo-128 算法在不含后向密钥的条件下均不能抵抗相关密钥-不可能差分攻击.能否在不增加算法实现代价的前提下,通过改进Piccolo 算法的密钥扩展方式使得算法的安全性进一步提高,是下一步研究的方向.

作者注本文于2018 年5 月22 日投稿至《软件学报》“面向自主安全可控的可信计算”专题,并于2018 年12月13 日被录用,于2019 年正式发表.本文第一作者徐林宏的硕士学位论文于2018 年12 月底完成答辩,后提交至学位论文库.该硕士学位论文的部分章节内容基于本文工作成果,特此说明.

附录A