对分组密码SKINNY- 64- 64的Biclique攻击
2018-07-25唐鹏袁征，2
唐 鹏 袁 征，2
1(西安电子科技大学 陕西 西安 710071) 2(北京电子科技学院 北京 100071)
0 引 言
Biclique密码分析方法是一种较为新颖的密码分析技术。它由Khovratovich等在文献[1]中被提出，后来在FSE 2012中被收录。Biclique是一种完全二分图，一个集合中的每个元素的初始状态都和另一个集合中的结束状态相联系。在密码分析过程中，在这种二分图中的每一条路径代表一个初始原语在一个唯一密钥下经过若干步骤后加密后的密文状态。如果这些路径不共享活跃的非线性部件，那么一个Biclique结构就允许攻击者可以高效地检测候选密钥的集合。这种Biclique结构可以用来降低中间相遇攻击的时间复杂度。起初Biclique被用于分析哈希函数，后来发现Biclique也适用于分组密码的安全性分析。Bogdanov等在文献[2]中采用Biclique对AES算法进行了攻击。他们的成果得到了高度关注，因为他们利用Biclique攻击首次实现了对AES单密钥模式下的全轮攻击。从那以后，基于Biclique的密钥恢复攻击开始被广泛应用于分组密码的分析中。
分组密码SKINNY由文献[3]提出，它是SP结构的分组密码。SKINNY是一种可调分组密码，分组长度和密钥长度有多种版本。SKINNY- 64- 64是SKINNY分组密码的64比特分组长度、64比特密钥长度的版本。多种分组、密钥长度版本使SKINNY能更好地适应不同的应用环境，它的软硬件实现均有较好的性能。因此，对它的安全性进行分析有着极为重要的实际意义。
本文利用Biclique攻击方法对轻量级分组密码SKINNY- 64- 64进行分析，通过从明文方向寻找两条不相交的差分路径来构建Biclique结构，结合中间相遇攻击的思路对SKINNY- 64- 64进行了全轮攻击。
1 基础知识
1.1 轻量级分组密码SKINNY- 64- 64的描述
轻量级分组密码SKINNY，是在CRYPTO 2016上提出的一种新型分组密码。SKINNY- 64- 64是SKINNY密码中64比特分组长度、64比特密钥长度的版本。本节将介绍SKINNY- 64- 64的加密算法和密钥扩展算法。
1.1.1 SKINNY- 64- 64的初始化
以m表示SKINNY- 64- 64的64比特明文，m=m0‖m1‖…‖m14‖m15，mi为4比特状态单位。以IS表示中间状态，以矩阵形式给出，其中ISi=mi，0≤i≤15。
以tk表示64比特初始密钥，tk=tk0‖tk1‖…‖tk14‖tk15，tki为4比特密钥状态单位。以TK表示轮密钥，以矩阵形式给出，其中TKi=tki，0≤i≤15。
1.1.2 SKINNY- 64- 64的轮函数
SKINNY- 64- 64的加密轮数为32轮，分组长度为64比特，密钥长度为64比特。
SKINNY- 64- 64的轮函数由以下5种操作组成：
1) 状态单位替换(SubCells)：SKINNY- 64- 64使用的S盒，与PICCOLO密码[4]所使用的S盒非常接近。SKINNY- 64- 64的中间状态以4比特为单位通过4×4的S盒进行非线性变换。SKINNY- 64- 64所使用的4×4的S盒见表1。
表1 分组密码SKINNY- 64- 64的S盒
2) 轮常量加(AddConstants)：轮常量与64比特中间状态相加。
3) 轮密钥加(AddRoundTweakey)：经过密钥编排算法得到的轮密钥的前32比特，与64比特的中间状态的前32比特对应相加。
4) 行移位(ShiftRows)：中间状态的每一行依次循环右移0、1、2、3个单位(4比特)。
5) 列混合(MixColumns)：64比特中间状态矩阵与矩阵M相乘。矩阵M如下：
分组密码SKINNY- 64- 64的轮函数如图1所示。
图1 分组密码SKINNY- 64- 64的轮函数
1.1.3 SKINNY- 64- 64的密钥编排算法
图2 SKINNY- 64- 64的密钥编排过程
1.2 Biclique攻击方法的描述
Biclique攻击的基本思路是通过构造Biclique结构来降低中间相遇攻击的复杂度。在所构造的Biclique结构的基础上，通过密钥划分、部分匹配、重新检测候选密钥等步骤来确定密钥恢复的时间复杂度。Biclique结构决定了攻击的数据复杂度，部分匹配过程决定了攻击的时间复杂度。
1.2.1 明文方向的平衡型Biclique结构
Biclique结构可以从明文方向构造，也可以从密文方向构造。这取决于密码算法的结构，以及对降低攻击数据复杂度的综合权衡。Biclique结构分为平衡型和非平衡型(星型)两种，本文使用平衡型Biclique结构进行攻击，非平衡型Biclique结构的详细介绍可以参考文献[5]。本文对SKINNY- 64- 64的攻击将从明文方向构造Biclique结构。从密文方向构建Biclique结构的过程与从明文方向构建的过程类似，在此不再赘述，详情可以参考文献[2]。
明文P在函数f的作用下映射为中间状态S：fK(P)=S。如果对2d个明文Pi、2d个中间状态Sj以及2d个密钥K[i,j]满足关系Sj=fK[i,j](Pi)，则三元组[{Pi},{Sj},{K[i,j]}]称为一个d维的平衡型Biclique结构(见图3 )。密钥集合K[i,j]如下：
图3 d维平衡型Biclique结构
1.2.2 使用相关密钥差分构造的独立型Biclique结构
构造独立型的Biclique结构，需要找到两条不相交的密钥差分路径，通过这两条密钥差分路径再构造两条不相交的差分路径。因为这两条差分路径不相交(不共享任何活跃的非线性部件)，所以它们之间相互独立，这两条路径就可以直接合并起来构成独立的Biclique结构。下面来详细介绍从明文方向用相关密钥差分构造独立型Biclique结构的过程。
1.2.3 部分匹配及密钥检测
最后对密钥集中剩余的密钥再次进行检测，直到正确的密钥找到为止。
1.2.4Biclique攻击的复杂度计算
Biclique攻击的密钥恢复时间复杂度按如下公式计算：
Ctotal=2n-2d[Cbiclique+Cmatch+Crecheck]
式中：n为密钥长度，d为Biclique结构的维度。Cbiclique为构造Biclique结构的复杂度。Cmatch为部分匹配过程的复杂度，Cmatch等于前向匹配与后向匹配的复杂度之和，Cmatch=Cfoward+Cbackward。Crecheck为密钥检测复杂度。Biclique攻击的存储复杂度为2d。由于本文从明文方向构造Biclique结构，所以攻击属于选择明文攻击，攻击的数据复杂度取决于所构造的具体的Biclique结构。
2 对SKINNY- 64- 64的Biclique攻击
本节我们将利用Biclique攻击方法对SKINNY- 64- 64进行攻击。在进行Biclique攻击过程中，SKINNY- 64加密的中间状态和经过密钥编排算法后的子密钥长度都是64比特。64比特的加密中间状态和子密钥均按图4的位置顺序来标记每个半字节，图中的每一格代表一个半字节(4比特)。
图4 中间状态位置标记
2.1.1 密钥划分
对第1轮密钥空间进行划分。将基密钥K[0,0]的第1、第12两个个位置固定为0 ( 如图5所示)，其他位置取遍所有可能的值，这样基密钥K[0,0]有214×4=256种可能的取值，也就是说第1轮密钥被划分为256个密钥集合。{K[i,j]}表示在K[0,0]上取遍所有i和j可能的值(如图6所示)，它有28个可能的取值，也就是说每个密钥集合中有28个密钥。这样第1轮的密钥空间就完成了完备划分。
图5 基密钥K[0,0] 图6 差分i和j
2.1.2 从明文方向构造6轮4维的Biclique结构
图和
图8 由前项差分Δ和后向差分构造的 覆盖1-6轮的Biclique结构
2.1.3 向后匹配26轮
(a) (b) 图9 SKINNY- 64- 64的前向匹配和后向匹配
2.1.4 攻击复杂度的计算
我们将密钥空间分为256个集合，每个集合中有密钥28个，所以攻击的存储复杂度不超过28。
3 结 语
本文首先对轻量级分组密码SKINNY- 64- 64进行了描述，然后介绍了Biclique攻击方法。通过相关密钥差分从明文方向构造了独立型Biclique结构，在此结构的基础上对SKINNY- 64- 64进行了全轮攻击，攻击的时间复杂度为262.908，数据复杂度为248个选择明文，时间复杂度优于文献[3]。这是目前使用平衡型Biclique结构对SKINNY- 64- 64进行全轮攻击的最优攻击结果。本文对SKINNY- 64- 64的攻击结果与文献[3]的攻击结果的比较见表2。
表2 对SKINNY- 64- 64的攻击复杂度比较
