随着物联网技术的不断发展, 人们对其安全性的要求也越来越高, 适用于这些资源受限环境的密码算法即轻量级密码算法成为密码学研究的一个热点, 大量轻量级密码算法被设计出来, 如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的攻击, 但攻击所需的数据量超过算法的分组规模2⁶⁴.2016年, Zheng等人^[19]利用U-method分别给出了Piccolo-80和Piccolo-128算法11轮和17轮的相关密钥-不可能差分区分器, 但未能给出具体的安全性分析结果.

●本文工作

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

●文章结构安排

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

1 相关知识

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

1.1 符号说明

● (P, P'):输入明文状态.

● (C, C'):输出密文状态.

● $X_i^r$:第r轮算法的第i个字节, i∈{0, 1, …, 7}.

● $Y_i^r$:第r轮算法在字节置换变换前的第i个字节, i∈{0, 1, …, 7}.

● $K_i^L$:第i个主密钥的左半部分.

● $K_i^R$:第i个主密钥的右半部分.

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

● (rk_2r, rk_2r+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数据进行作用, 实现算法的混乱和扩散.即有(x₀₍₄₎, x₁₍₄₎, x₂₍₄₎, x₃₍₄₎)^t=M·(x₀₍₄₎, x₁₍₄₎, x₂₍₄₎, x₃₍₄₎)^t, 其中, 列混合矩阵M的运算定义在由不可约多项式x⁴+x+1生成的GF(2⁴)上.

●字节置换RP

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

$({x_{0(8)}},{x_{1(8)}},{x_{2(8)}},{x_{3(8)}},{x_{4(8)}},{x_{5(8)}},{x_{6(8)}},{x_{7(8)}})\xrightarrow{{RP}}({x_{2(8)}},{x_{7(8)}},{x_{4(8)}},{x_{1(8)}},{x_{6(8)}},{x_{3(8)}},{x_{0(8)}},{x_{5(8)}}).$

●密钥扩展算法

Piccolo算法的密钥扩展有80bits和128bits密钥两种.其中, 对于Piccolo-80, 将80bits主密钥划分为5个部

分, 每个部分包括2字节, 即K=K₀||K₁||K₂||K₃||K₄, 其中, ${K_i} = (K_i^L||K_i^R),i \in \{ 0,1,2,3,4\} $.根据F函数中采用的是4bits的S盒, 可对每一字节密钥进行再划分, 即${K_i} = (K_i^{{L_0}}||K_i^{{L_1}}||K_i^{{R_1}}||K_i^{{R_0}})$.

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

${\rm{Piccolo - 80:}}\;W{K_0} = (K_0^L||K_1^R),W{K_1} = (K_1^L||K_0^R),W{K_2} = (K_4^L||K_3^R),W{K_{\rm{3}}} = (K_3^L||K_4^R).$

轮密钥(rk_2r, rk_2r+1)由主密钥与固定常数异或所得, r∈{0, …, 24}.在Piccolo-128中, 增加了6个字节的主密钥, 有K=K₀||K₁||K₂||K₃||K₄||K₅||K₆||K₇, 相应的白化密钥也有所变化, 即

${\rm{Piccolo - 128:}}\;W{K_0} = (K_0^L||K_1^R),W{K_1} = (K_1^L||K_0^R),W{K_2} = (K_4^L||K_7^R),W{K_{\rm{3}}} = (K_7^L||K_4^R).$

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

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

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

2.1 Piccolo算法性质

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

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

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

(3) 对于Piccolo-128算法, 在不考虑轮常数的影响下, 自第0轮开始, 其轮密钥左半部分是按(K₂, K₄, K₆, K₂, K₆, K₀, K₄, K₆, K₄, K₂, K₀, K₄, K₀, K₆, K₂, K₀)排列的一个16轮循环, 右半部分是按(K₃, K₅, K₇, K₁, K₇, K₃, K₅, K₁, K₅, K₇, K₃, K₁)排列的一个12轮循环.

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

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

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

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

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

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

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

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

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

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

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

由于本文攻击中考虑前向白化密钥对算法安全性的影响, 因此密钥差分选取在K₀和K₁中的区分器不适合用于攻击环节.而为了使攻击轮数尽可能长, 且攻击复杂度尽可能低, 考虑选用输入差分活动块较少的区分器, 故在下文的攻击中, 选用的区分器为情形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所示, 其中, 黑色表示差分活动比特块, 灰色标识差分值为γ的比特块, 差分不活动比特块用白色标识.

2.3.1 攻击算法1

● Step 1.数据收集.

基于性质3, 对于密文(C, C'), 选择其在第14轮的输入差分为(α, 0, 0, 0, 0, β, γ, 0), 其中, α, β, γ表示差分活动比特块, 且每一比特块表示一个字节.则显然:对于一个结构, 需要选择2²⁴个选择密文, 则得到2⁴⁷个密文对.当选定γ的一个非零取值时, 因为有2⁸-1种可能, 所以对应的密文对数量2³⁹个.此时选择相应的密钥差分$\Delta K_2^L = \gamma {\rm{,}}$筛选明文差分为(*, 0, *, *, 0, *, *, *)的密文对, 予以保留, 则平均剩余的密文对个数为2³⁹×2^-16=2²³.构造2ⁿ个结构, 当γ选定一个非零值时, 可得到2ⁿ⁺²³个平均剩余密文对.

● Step 2.密钥猜测.

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

➢ Step 2.1.对于选定的一个γ, 根据已得到的密文对, 猜测密钥$(rk_{29}^L,rk_{28}^R)$, 筛选使得$\Delta X_{2,3}^{13} = 0$的密文对, 予以保留, 则平均剩余密文对个数为2ⁿ⁺²³×2^-16=2ⁿ⁺⁷.

➢ Step 2.2.已知密钥$(rk_{29}^L,rk_{28}^R)$, 根据密钥扩展算法, 可计算得到对应的主密钥$(K_1^L,K_0^R)$, 也就是WK₁.再通过已知密文对可得相应的明文对, 进行第0轮的右半部分加密.筛选$\Delta Y_6^0 = \gamma ,\Delta Y_7^0 = 0$的密文对, 予以保留, 则平均剩余密文对的个数为2ⁿ⁺⁷×2^-16=2^n-9.

➢ Step 2.3.猜测密钥WK₀, 也就是$(K_0^L||K_1^R)$, 进行第0轮的左半部分加密, 筛选使得$\Delta Y_2^0 = \gamma ,\Delta Y_3^0 = 0$的密文对, 予以保留, 则平均剩余密文对的个数为2^n-9×2^-16=2^n-25.

➢ Step 2.4.猜测密钥$(rk_1^L,rk_0^R)$, 根据上述步骤剩余密文对, 计算并验证$\Delta Y_{6,7}^1 = 0$是否成立:若成立, 即此时仍有密文对通过验证, 则说明此时的密钥为错误密钥, 将密钥筛去, 存入错误密钥候选密钥集; 否则, 将猜测密钥作为正确密钥候选密钥予以保留.

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

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

定理1.根据攻击算法1, 可恢复出Piccolo-80算法的全部主密钥, 攻击所需数据复杂度为2^58.6, 计算复杂度为2⁷⁸, 存储复杂度为2^60.6.

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

1.由于攻击所需选择密文量为2ⁿ⁺²⁴, 因此构造明密文对所需的计算复杂度为T_N=2ⁿ⁺²⁴×2=2ⁿ⁺²⁵.

2. Step 2.1中, 选定γ的一个值, 猜测密钥$(rk_{29}^L,rk_{28}^R)$共有2¹⁶种可能, 根据已得的密文对, 进行$\frac{1}{2}$轮Piccolo- 80算法解密操作, 筛选$\Delta X_{2,3}^{13} = 0$的密文对, 因此, 攻击所需的计算复杂度为$\frac{1}{2} \times ({2^{n + 23}} \times {2^{16}}) \times 2 = {2^{n + 39}}{\rm{.}}$

3. Step 2.2中, 根据步骤2.1中得到的密钥$(K_1^L,K_0^R)$和剩余2ⁿ⁺⁷个密文对, 进行$\frac{1}{2}$轮加密操作, 筛选$\Delta Y_6^0 = \gamma ,\Delta Y_7^0 = 0$的密文对, 因此, 该步骤所需的计算复杂度为$\frac{1}{2} \times ({2^{n + 7}} \times {2^{16}}) \times 2 = {2^{n + 23}}{\rm{.}}$

4. Step 2.3中, 与前两步类似, 猜测密钥WK₀, 有2¹⁶种取值, 筛选符合条件的密文对, 则该步骤的计算复杂度为$\frac{1}{2} \times ({2^{n - 9}} \times {2^{32}}) \times 2 = {2^{n + 23}}{\rm{.}}$

5. Step 2.4中, 猜测密钥$(rk_1^L,rk_0^R)$, 验证$\Delta Y_{6,7}^1 = 0$是否成立, 则该步骤的计算复杂度为

$\frac{1}{2} \times ({2^{n - 25}} \times {2^{48}}) \times 2 = {2^{n + 23}}{\rm{.}}$

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

${T_G} = ({2^8} - 1) \times \frac{1}{{15}} \times ({2^{n + 39}} + {2^{n + 23}} + {2^{n + 23}} + {2^{n + 23}}) = {2^{n + 43.09}}{\rm{.}}$

在上述攻击中, 错误密钥不通过验证的概率为$P = {({(1 - {2^{ - 16}})^{{2^{n - 25}}}})^{{2^8} - 1}} \approx {(1 - {2^{ - 16}})^{{2^{n - 17}}}}$, 总计对48bits密钥进行了猜测, 因此剩余密钥量为K_R=2⁴⁸×P, 也就是穷举剩余密钥的计算复杂度为T_R≈2³²×K_R.利用文献[20]的方法, 为使得攻击效果更好, 对攻击所需数据复杂度和计算复杂度进行折衷, 选取n=34.6, 则攻击所需的计算复杂度总计为T=T_N+T_G+T_R=2ⁿ⁺²⁵+2^n+43.09+2^75.63≈2⁷⁸次15轮Piccolo-80算法加密.

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

综上, 攻击所需数据复杂度为2^58.6个选择密文, 计算复杂度为2⁷⁸次15轮Piccolo-80算法加密, 存储复杂度为2^60.6个字节.

2.3.2 攻击算法2

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

●攻击条件:选择第14轮的输入差分为(α, 0, 0, 0, 0, β, (γ||0), 0), 密钥差分为$\Delta K_2^L = (\gamma ||0)$.其中, α, β各表示一个差分活动字节, γ表示一个差分活动半字节.

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

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

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

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

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

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

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

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

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

观察表 6可得, 区分器的密钥差分选取均位于轮密钥的左半部分.这是因为每轮轮密钥的右半部分采用的是主密钥(K₁, K₃, K₅, K₇)中的任意一个, 而由性质1, Piccolo-128的轮密钥的右半部分是按(K₃, K₅, K₇, K₁, K₇, K₃, K₅, K₁, K₅, K₇, K₃, K₁)排列的一个12轮循环.其中, K₃, K₅在轮密钥中连续出现5次的相距轮数为18, K₇在轮密钥中的相距轮数为17, 但该三者中间轮均已达到算法达到完全性的轮数要求, 在截断差分条件下不能得到矛盾.K₁在轮密钥中的相距轮数为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基本一致.

3.2 21轮密钥恢复攻击

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

3.2.1 攻击算法3

● Step 1.数据收集.

选择明文(P, P')的输入差分为(0, 0, 0, 0, α, 0, β, γ), 同样, α, β, γ表示差分活动字节.对于一个明文结构, 需要选择2²⁴个明文, 则得到2⁴⁷个明文对.当α选定一个非零的取值时, 因为有2⁸-1种可能, 所以对应的明文对数量2³⁹个.此时选择相应的密钥差分$\Delta K_4^L = \alpha {\rm{,}}$基于性质3轮函数的等效结构, 筛选满足在第20轮的输入差分有$\Delta X_{2,3}^{20} = 0{\rm{,}}$其余字节差分活动的明文对予以保留, 构造2ⁿ个结构, 当α选定一个非零值时, 可得到2ⁿ⁺²³个平均剩余明文对.

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

● Step 2.密钥猜测.

➢ Step 2.1.猜测密钥WK₁, 对于选定的一个α, 根据已得到的明文对, 筛选使得的明文对, 予以保留, 则平均剩余明文对个数为2ⁿ⁺²³×2^-16=2ⁿ⁺⁷.

➢ Step 2.2.猜测密钥$(rk_{41}^L,rk_{40}^R)$, 利用上述剩余明文对, 进行第19轮左半部分解密, 筛选$\Delta X_{2,3}^{19} = 0$的明文对, 予以保留, 则平均剩余明文对个数为2ⁿ⁺⁷×2^-16=2^n-9.

➢ Step 2.3.猜测密钥$(rk_{40}^L,rk_{41}^R)$, 利用上述剩余明文对, 进行第19轮右半部分解密, 筛选$\Delta X_6^{19} = \alpha ,$ $\Delta X_7^{19} = 0$的明文对, 予以保留, 则该步骤后, 平均有2^n-9×2^-16=2^n-25个明文对剩余.

➢ Step 2.4.猜测密钥$rk_{38}^R$, 由步骤2.1已知$K_1^L$, 根据密钥扩展算法的对应关系, 也就是已知$rk_{39}^L$.对剩余明文对进行第18轮的左半部分解密, 验证$\Delta X_{2,3}^{18} = 0$是否成立:若此时仍有明文对通过检验, 则说明此时猜测的密钥错误, 将其放入错误密钥候选密钥集; 否则, 将其看作正确密钥的候选密钥, 予以保留.

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

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

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

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

由于攻击所需选择明文为2ⁿ⁺²⁴, 因此构造明文对所需的计算复杂度为T_N=2ⁿ⁺²⁵.在Step 2.1中, 攻击所需的计算复杂度为$\frac{1}{2} \times ({2^{n + 23}} \times {2^{16}}) \times 2 = {2^{n + 39}}{\rm{;}}$Step 2.2所需的计算复杂度为$\frac{1}{2} \times ({2^{n + 7}} \times {2^{32}}) \times 2 = {2^{n + 39}}{\rm{;}}$Step 2.3所需的计算复杂度为$\frac{1}{2} \times ({2^{n - 9}} \times {2^{48}}) \times 2 = {2^{n + 39}}{\rm{;}}$Step 2.4中, 猜测密钥$rk_{38}^R$, 验证$\Delta X_{2,3}^{18} = 0$是否成立, 进行密钥筛选, 则该步骤的计算复杂度为$\frac{1}{2} \times ({2^{n - 25}} \times {2^{56}}) \times 2 = {2^{n + 31}}{\rm{;}}$Step 3中, 对α所有可能的2⁸-1值进行遍历, 进行密钥筛选.也就是重复上述攻击步骤2.1~步骤2.4, 因此在密钥猜测阶段, 总的计算复杂度约为

${T_G} = ({2^8} - 1) \times \frac{1}{{21}} \times ({2^{n + 39}} + {2^{n + 39}} + {2^{n + 39}} + {2^{n + 31}}) = {2^{n + 44.2}}.$

在上述攻击中, 错误密钥不通过验证的概率为$P = {({(1 - {2^{ - 16}})^{{2^{n - 25}}}})^{{2^{8 - 1}}}}$, 总计对56bits密钥进行了猜测, 因此剩余密钥量为K_R=2⁵⁶×P, 取n=38.3, 也就是穷举剩余密钥的计算复杂度为T_R=K_R×2^72≈2⁷², 则攻击总计所需的计算复杂度为T=T_N+T_G+T_R=2ⁿ⁺²⁵+2^n+44.2+2^72≈2^82.5次21轮Piccolo-128算法加密.

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

综上, 攻击所需数据复杂度为2^62.3个选择明文, 计算复杂度为2^82.5次21轮Piccolo-128算法加密, 存储复杂度为2^64.3个字节.

3.2.2 攻击算法4

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

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

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

定理4.根据攻击算法4, 恢复Piccolo-128算法的全部主密钥所需数据复杂度为2^62.3, 计算复杂度为2^124.45, 存储复杂度为2^64.3.

证明:选取n=42.3, 则该攻击所需的数据复杂度约为2^62.3个选择明文, 计算复杂度为2^124.45次21轮Piccolo- 128算法加密, 存储复杂度为2^64.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
附录B