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

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

不可能差分分析,由Knudsen[1]和Biham[2]两人分别独立提出,是目前最常用的密码分析方法之一.Kim 等人[3]提出了μ方法.该方法通过计算机搜索找出各种算法结构中所固有的不可能差分形式,这些固有的不可能差分只与算法的结构有关,而与算法所采用的S盒无关,这也就是所谓的截断不可能差分.后来,Luo 等人[4]在μ方法的基础上改进,提出了UID 方法.不同于μ方法,UID 方法利用中间相错的思想将密码算法结构分解成两部分进行处理.此外,孙兵等人[5]基于整环上的矩阵论证明了SPN 结构及嵌套SPN 的Feistel 结构的截断不可能差分区分器的上界取决于线性层的本原指数,并以AES 算法、ARIA 算法和Camellia 算法为实例,分别证明了AES 算法和ARIA 算法的截断不可能差分区分器都至多4 轮、Camellia 算法(不考虑FL/FL−1层)不可能差分区分器至多8 轮.

随着物联网的不断发展,物联网的安全问题日益严峻.由于物联网上的加密器件大多存储空间小、计算能力弱,因此,传统的密码算法不适合用来保护物联网上的信息安全.在这种情况下,大量轻量级密码算法应运而生,典型的算法有PRESENT[6],MIBS[7],GOST[8],KLEIN[9],LED[10],Piccolo[11],LBlock[12],PRINCE[13]等.

这些轻量级密码算法大部分关注的是硬件实现电路的面积,但Banik 等人[14]认为,制约轻量级算法应用的因素是算法的功耗,低功耗的密码算法能够更为广泛地应用于多种设备中,并在Asiacrypt 2015 会议上提出专注于低功耗的Midori 算法.由于Midori 算法受限于轻量级使用环境,故通常不对其在已知密钥、相关密钥、选择密钥条件下的安全性进行分析,更多考察算法在单密钥条件下的安全性.

目前,对于Midori 算法在单密钥条件下有多个安全性分析结果.2017 年,Lin 等人[15]利用中间相遇攻击方法,通过构造5 轮与6 轮区分器,分别给出了10 轮～12 轮Midori-64 算法的安全性分析结果.2015 年,Guo 等人[16]对Midori-64 算法的弱密钥集进行了分析,利用Subspace 攻击给出了全轮Midori-64 算法的分析结果;2017 年,Chen等人[17]构造了第一个6 轮截断不可能差分区分器,并给出首个不含入口白化密钥的10 轮Midori-64 算法不可能差分分析.

Midori 算法的设计者曾估计:在单密钥条件下,该算法不可能差分区分器的最大轮数是7 轮,其7 轮或7 轮以上截断不可能差分区分器是否存在,是尚未解决的问题.若存在,可以利用该不可能差分区分器分析更高轮数Midori 算法;若不存在,如何将Midori 算法6 轮截断不可能差分区分器都找出来并进行分类,及是否存在更优的区分器使得对Midori-64 算法分析结果更好.这些问题就是本文研究的重点.

本文首先证明了在单密钥条件下,Midori 算法截断不可能差分区分器的轮数至多6 轮,并根据该证明过程,对6 轮截断不可能差分区分器进行了分类;其次,根据Midori 算法6 轮截断不可能差分区分器的分类,构造了一个6 轮区分器,并给出了11 轮Midori-64 算法的不可能差分分析,恢复了128 比特主密钥.本文得到的结果与在单密钥条件下现有分析结果对比见表1.

Table 1 Comparison of attacks on Midori-64表1 Midori-64 算法分析结果对比

本文第1 节主要介绍Midori 算法及其相关性质.第2 节证明Midori 算法截断不可能差分区分器至多6 轮.第3 节对Midori 算法的6 轮截断不可能差分区分器进行分类.第4 节给出11 轮Midori-64 算法的不可能差分分析.第5 节总结全文.

1 Midori 算法介绍

1.1 符号说明

·P:明文.

· ΔC:输出密文差分.

·xi:第i轮经过密钥异或后的状态.

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

·zi:第i轮经过移位变换后的状态.

·wi:第i轮经过列混合变换后的状态.

·kei:第i轮加密密钥.

·kei[j]:第i轮加密密钥第j个字节.

1.2 Midori算法

Midori 算法分为Midori-64 与Midori-128 两种,密钥规模都是128 比特,分组规模分别为64 比特与128 比特,对应的迭代轮数为16 轮与20 轮.分组状态表示为16 个比特块的形式,分组规模为64 比特时,每个比特块为半字节;分组规模为128 比特时,每个比特块为字节,如图1 所示.

Fig.1 State of Midori图1 Midori 分组状态

Midori 算法采用SPN 结构,其轮函数依次由非线性变换SubCell、移位变换ShuffleCell、列混合变换MixColumn、密钥异或KeyAdd 这4 个变换组成.这4 个变换及密钥扩展算法的具体介绍如下.

· 非线性变换SubCell:在Midori 算法中共有2 个不同的对合4 比特S盒Sb0,Sb1,即Sb0,Sb1:{0,1}4→{0,1}4.在Midori-64 中使用一个S盒Sb0.在Midori-128 中使用由两个Sb1与4 个不同的置换生成4 个8 比特的S盒Sb0,Sb1,Sb2,Sb3.Sb0,Sb1以16 进制表示形式给出,见表2.

Table 2 S-boxes Sb0,Sb1 of Midori表2 Midori 中使用的S 盒Sb0,Sb1

· 移位变换:将16 个比特块的顺序进行重新排列,其变换及逆变换具体如下:

· 列混合变换:使用对合二元阵M对状态中每一列进行如下操作,即M⋅(si,si+1,si+2,si+3)′→(si,si+1,si+2,si+3)′,

其中,i=0,4,8,12,M及其逆矩阵M−1如下:

· 密钥异或:将状态字节与密钥字节对应位置进行模2 加运算.

密钥扩展算法:Midori 算法使用128 比特主密钥,其密钥扩展算法较为简单.其中,Midori-64 算法将128 比特主密钥分为两部分K=k0||k1,算法的入口与出口白化密钥均为WK=k0⊕k1,圈子密钥kei=k(i+1)mod2⊕αi,1≤i≤15,其中,αi是轮常数.而Midori-128 算法的入口与出口白化密钥均为WK=K,圈子密钥kei=K⊕βi,1≤i≤19,其中,βi为轮常数.且当1≤i≤15 时,满足αi=βi.

Midori 算法的加密需要在算法的初始位置异或一个白化密钥WK,为确保Midori 算法加解密算法结构相似性,算法在最后一轮省略移位变换与列混合变换.16 轮Midori-64 算法的加密流程如图2 所示.

Fig.2 Encryption process of Midori-64图2 Midori-64 算法加密流程

1.3 Midori算法相关性质

性质1.1.在Midori-64 算法中,若已知白化密钥,当再得到任意一个奇数轮圈子密钥或者任意一个偶数轮圈子密钥时,即可恢复主密钥;在Midori-128 算法中,若已知任意一个圈子密钥,则可以恢复主密钥.

性质1.2[15].给定Midori 算法S盒的一对对应的输入、输出差分,平均可以确定一对S盒的输入与输出.

性质1.3[18].对于Midori 算法列混合变换,当输入状态的某列仅有1 个比特块差分活动时,输出状态必在相同列的其余3 个比特块有差分活动,且差分值相等;当输入状态的某列有两个比特块差分活动且两个差分值相同,则输出状态必定与输入状态相同;当输入状态的某列有3 个比特块差分活动且差分值相同,则输出状态仅在相同列的另一个比特块上差分活动.

性质1.4.原在同一列的半字节,经两次Midori 算法移位变换后,必定在同一行:

性质1.5.设yi仅在某一列有3 个比特块差分活动(差分值可能不同),则yi经一轮Midori 算法加密,再经一次移位变换后输出状态zi+1必定其中3 列有两个比特块差分活动,一列有3 个比特块差分活动.

证明:yi经移位变换输出状态zi在不同的3 列各有一个比特块差分活动.再经列混合变化输出状态wi.其中,3列有3 个比特块差分活动,其余一列没有差分活动比特块.由于经密钥异或变换及非线性变换不改变原状态截断差分活动位置,故yi+1的差分状态与wi一致.对于yi+1经移位变换的输出状态zi+1,不妨先考虑yi+1+zi经移位变换后的输出状态.因为yi+1+zi满足其中3 列每比特块都有差分活动,其余一列没有差分活动比特块,故经SC变化输出状态必定每一列都有3 个比特块差分活动.又因为由性质1.4 可知,zi再经一次移位变换后输出状态有差分活动的比特块必定在同一行,所以zi+1必定其中3 列有两个比特块差分活动,一列有3 个比特块差分活动.□

性质1.6.设yi仅在某一列有2 个比特块差分活动(差分值可能不同),其余列没有差分活动比特块,则yi经一轮Midori 算法加密,再经一次移位变换后输出状态zi+1必定其中两列各有两个比特块差分活动,其余两列各有一个比特块差分活动.

证明过程与性质1.5 的证明类似,故略.

2 Midori 算法截断不可能差分区分器最大轮数的分析

2016 年,Chen 等人在单密钥条件下构造了第一个6 轮截断不可能差分区分器.对于7 轮及7 轮以上截断不可能差分区分器是否存在,是本文研究的重点内容之一.

对于Midori 算法截断不可能差分区分器至多6 轮的证明的基本思想:证明任意(非零)初始差分状态经过3.5 轮Midori 算法加密或者3.5 轮Midori 解密算法后的输出状态的每个比特块都可能差分活动,这样就不可能构造出7 轮或者7 轮以上的截断不可能差分区分器.当然,7 轮截断不可能差分区分器不仅仅只能由向下加密3.5 轮、向上解密3.5 轮的差分路径组成,也可以由加密(解密)4.5 轮和解密(加密)2.5 轮的差分路径构成,但由于若某个状态其每个比特块都可能存在差分活动,该状态再经1 轮加密或解密Midori-64 算法,输出状态必定不存在确定差分活动或差分不活动的比特块,这样就不能构成一条截断不可能差分区分器.所以,只需证明任意初始差分状态经过3.5 轮Midori 算法加密或者3.5 轮Midori 解密算法后的输出状态的每个比特块都可能差分活动即可.

为便于区分器的分类,不妨以状态z1为初始输入状态,按加密过程和解密过程,证明分为第2.1 节与第2.2节两部分.

2.1 Midori算法加密过程差分路径

引理2.1.初始输入状态z1只在某一列存在差分活动的比特块时,经过3.5 轮Midori 算法加密后,输出状态w4的每个比特块都可能差分活动.

为证明该引理,分别讨论初始输入状态z1只在某一列存在1 个差分活动、2 个差分活动、3 个差分活动、4个差分活动比特块这4 种情况.本文中如不加特殊说明,我们考虑的初始状态z1其差分活动比特块的差分值都是相同的,这是因为差分值不同先于差分值相同的情况输出每个比特块都可能差分活动的状态.由于KeyAdd不改变原状态截断差分活动位置,为表述简洁,性质2.1～性质2.4 中都省去了最后1/4 轮.

性质2.1.初始输入状态z1只存在1 个差分活动比特块时,经过2.5 轮Midori 算法加密后,输出状态w3的每个比特块都可能差分活动.

证明:设z1唯一的差分活动比特块在第i列,其中,0≤i≤3.z1经3/4 轮Midori 算法加密后,非线性变换SB输出状态y2必定仅在第i列有3 个比特块差分活动.以z1仅在第6 个比特块有差分活动为例,给出其2.5 轮Midori算法加密过程,如图3 所示,其中,白色表示差分为0 的半字节,黑色表示差分活动的半字节,斜线表示可能存在差分的半字节.

由性质1.5 可知,y2经一轮Midori 算法加密后,再经SC,输出状态z3必定其中3 列有两个比特块差分活动,一列有3 个比特块差分活动.z3再经MC,输出状态w3的每个比特块都可能差分活动.证毕.□

性质2.2.初始输入状态z1只在某一列存在2 个比特块差分活动时,经过3.5 轮Midori 算法加密后,输出状态w4的每个比特块都可能差分活动.

证明:z1经3/4 轮Midori 算法加密后,输出状态y2必定仅在某一列有2 个比特块差分活动,其余列没有比特块差分活动.以z1仅在第5、第6 个比特块有差分活动为例,给出其3.5 轮Midori 算法加密过程,如图4 所示.

由性质1.6 可知,y2经一轮Midori 算法加密后,再经一次SC,输出状态z3必定其中两列各有两个比特块差分活动,其余两列各有一个比特块差分活动.故易知:再经1.5 轮,输出状态w4不存在确定有无差分活动的比特块.证毕.□

Fig.3 2.5-round differential path of Midori in encryption direction I图3 2.5 轮Midori 算法加密方向差分路径I

Fig.4 3.5-round differential path of Midori in encryption direction I图4 3.5 轮Midori 算法加密方向差分路径I

性质2.3.初始输入状态z1只在某一列存在3 个比特块差分活动时,经过3.5 轮Midori 算法加密后,输出状态w4的每个比特块都可能差分活动.

证明:z1经一轮Midori 算法加密后,输出状态z2必定只有1 个比特块差分活动,由性质2.2 可知,z2再经2.5轮Midori 算法加密,输出状态w4的每个比特块都可能存在差分活动.以z1仅在第5～第7 个比特块差分活动为例,给出其3.5 轮Midori 算法加密过程,如图5 所示. □

性质2.4.初始输入状态z1只在某一列存在4 个比特块差分活动,经过3.5 轮Midori 算法加密后,输出状态w3的每个比特块都可能差分活动.

证明:z1经一轮Midori 算法加密后,输出状态z2必定每一列各有一个比特块差分活动.易知:再经1.5 轮算法加密,输出状态w3不存在确定有无差分活动的比特块.以z1仅在第4～第7 个比特块有差分活动为例,给出其3.5轮Midori 算法加密过程,如图6 所示.□

Fig.5 3.5-round differential path of Midori in encryption direction II图5 3.5 轮Midori 算法加密方向差分路径II

Fig.6 2.5-round differential path of Midori in encryption direction II图6 2.5 轮Midori 算法加密方向差分路径II

引理2.2.假设初始输入状态z1只在某一列存在比特块差分活动时,若经过n+1/2 轮Midori 算法后,输出状态wn+1的每个比特块都可能差分活动,则任意增加z1中其他差分为零列的差分活动得到状态经过n+1/2轮Midori 算法后的输出状态也必定每个比特块都可能差分活动.

证明:由SC,SB,KeyAdd,MC的性质可知,任意状态,其列与列之间的这4 种变换是相互独立的.故z1和经相同的变换,经变换后,输出状态有差分活动的比特块集合必定包含z1的输出状态有差分活动的比特块集合,所以该结论是显然的. □

由引理2.1 和引理2.2 可得出如下定理.

定理2.1.任一初始输入状态z1经过3.5 轮Midori 算法加密后,输出状态w4的每个比特块都可能差分活动.

2.2 Midori算法解密过程差分路径

引理2.3.状态zm只存在1 个比特块差分活动时,经过3.5 轮Midori 解密算法后,输出状态xm−3的每个比特块都可能差分活动.

证明:zm经一轮Midori 算法解密后,输出状态zm−1必定其中一列有3 个比特块差分活动,其余列无差分活动比特块.依据性质1.5,同理可证:再经过1.5 轮,输出状态xm−2必定其中3 列有两个比特块差分活动,一列有3 个比特块差分活动.故xm−2再经一轮解密算法,输出状态xm−3每个比特块都可能差分活动.以zm仅在第5 个比特块有差分活动为例,给出其3.5 轮Midori 算法解密方向差分路径,如图7 所示.□

引理2.4.假设状态zm只存在1 个比特块差分活动时,若经过n+1/2 轮Midori 解密算法后,输出状态xm−n的每个比特块都可能差分活动,则任意增加zm上其他比特块的差分得到的状态,经过n+1/2 轮Midori 解密算法后,输出状态每个比特块也必定都可能差分活动.

证明:不妨将状态上可能有差分活动的所有比特块用集合H表示,例如zm上可能有差分活动的所有个比特块集合用表示,状态上可能有差分活动的所有个比特块用集合表示,显然有.由SC,SB,KeyAdd,MC的性质可知,.故zm和经相同的变换,经变换后输出状态有差分活动的比特块集合,必定包含zm经变换后的输出状态有差分活动的比特块集合,所以该结论是成立的.□

由引理2.3 和引理2.4 可得出如下定理.

定理2.2.任一状态zn经过3.5 轮Midori 解密算法后,输出状态xn−3的每个比特块都可能差分活动.

再由定理2.1 和定理2.2 可得出本文一个重要的结论,如定理2.3 所示.

定理2.3.Midori 算法在单密钥条件下的截断不可能差分区分器至多6 轮.

Fig.7 3.5-round differential path of Midori in decryption direction图7 3.5 轮Midori 算法解密方向差分路径

3 Midori 算法6 轮截断不可能差分区分器的分类

在接下来分类过程中将用到一个概念——列最小差分活动比特块数,其定义如下.

定义3.1.设状态z各列的差分活动比特块数分别为tcol(0),tcol(1),tcol(2),tcol(3),该状态的列最小差分活动比特块数,是指非零差分列中最小差分活动的比特块数,即min{tcol(i)|tcol(i)>0,i=0,1,2,3}.

接下来,我们以输入状态z1的列最小差分活动比特块数进行分类讨论如下.

性质3.1.输入状态z1的列最小差分活动比特块数为1 时,不可能构造出6 轮截断不可能差分区分器.

证明:由性质2.1 和引理2.2 可知,此时,输入状态z1经过2.5 轮Midori 算法加密后,输出状态w3的每个比特块都可能差分活动;再由定理2.2 可知,任意状态经3.5 轮解密算法后,输出状态的每个比特块都可能差分活动,故不可能构造出一条6 轮截断不可能差分路径.□

性质3.2.输入状态z1的列最小差分活动比特块数为2 时,若要构造一条6 轮不可能差分路径,输出状态z7必定仅有1 个比特块差分活动.

证明:要想构造出一条不可能差分路径,由性质2.2 可知,输入状态z1只能向下加密2.5 轮,所以输出状态z7要向上解密3.5 轮,且满足存在确定有无差分活动的比特块,故z7必定仅有1 个比特块差分活动.□

性质3.3.输入状态z1的列最小差分活动比特块数为3 时,要构造一条6 轮不可能差分路径,若z1经过2.5轮Midori 算法加密,则输出状态z7必定仅有1 个比特块差分活动.若输入状态z1经过3.5 轮Midori 算法加密,则z7经一次SC−1输出状态y7有如下4 种情形:(1)y7只有1 列有比特块差分活动;(2)y7有两列有比特块差分活动,且其中一列差分活动比特块数必定为1;(3)y7有3 列有比特块差分活动,且其中两列差分活动比特块数必定为1;(4)y7每一列都有比特块差分活动时,且必定有3 列其差分活动比特块数为1.

证明:若输入状态z1经过2.5 轮Midori 算法加密,输出状态z7必定仅有1 个比特块差分活动.若输入状态z1经过3.5 轮Midori 算法加密,则加密后输出状态w4的每个比特块都可能存在差分活动,则z7必定满足解密2.5轮后存在一定没有差分活动的比特块.对于输出状态z7经一次SC−1的输出状态y7分如下4 种情形讨论.

· 情形1:当y7只有1 列有比特块差分活动时,显然是满足要求的.

· 情形2:当y7仅有2 列有比特块差分活动时,若这两列都有两个以上比特块差分活动,容易推导出x5每个比特块都可能存在差分活动,故不符合要求,所以此时y7必须有一列差分活动比特块数为1.

· 情形3:当y7仅在3 列有比特块差分活动时,若有两列差分活动比特块数超过一个,由情形2 可知不符合要求,所以y7其中两列差分活动比特块数必定为1.

· 情形4:当y7在每一列都有比特块差分活动时,同样由情形2 可知,有3 列差分活动比特块数必定为1.综上所述,性质3.3 得证.□

性质3.4.输入状态z1列最小差分活动半字节数为4 时,不可能构造出6 轮截断不可能差分区分器.

该证明过程同性质3.1.

综上所述,Midori 算法6 轮截断不可能差分区分器可分为性质3.2 与性质3.3 两大类.由引理2.2 和引理2.4可知,z1,z7仅有1 列有比特块差分活动的情况下,区分器能向下加密及向上解密更多轮数.故简单考虑z1,z7仅有1 列有比特块差分活动的情况,此时按输入状态z1存在的差分活动比特块数将Midori 算法6 轮截断不可能差分区分器分为如下两大类.

1) 输入状态z1仅在某一列存在2 个比特块差分活动时,输出状态z7必定仅有1 个比特块差分活动.具体不可能差分差分路径为输入状态z1向下加密2.5 轮,输出状态z7向上解密3.5 轮.

2) 输入状态z1仅在某一列存在3 个比特块差分活动时:(1) 若输入状态z1经过2.5 轮Midori 算法加密,则输出状态z7必定仅有1 个比特块差分活动;(2) 若输入状态z1经过3.5 轮Midori 算法加密,则输出状态z7必定仅有1 个或者2 个比特块差分活动(证明略).

4 Midori-64 算法的不可能差分分析

根据Midori 算法6 轮截断不可能差分区分器的分类结果,可构造相应的6 轮不可能差分区分器.第4.1 节将给出一个6 轮不可能差分区分器;第4.2 节进一步给出Midori-64 算法的11 轮不可能差分分析.

4.1 Midori算法的6轮不可能差分区分器

定理4.1.当初始输入状态z1仅在第0～第2 这3 个比特块差分活动,且满足Δz1[0]=Δz1[1]=Δz1[2]时,经过6轮Midori 算法加密后,输出状态z7仅在第6、第7 比特块处差分活动,且满足Δz1[6]=Δz1[7]是不可能的.具体形式如图8 所示.

Fig.8 6-round impossible differential distinguisher of Midori图8 Midori 算法的6 轮不可能差分区分器

证明:当输入状态z1仅在第0～第2 这3 个比特块差分活动,且满足Δz1[0]=Δz1[1]=Δz1[2]时,经3.5 轮Midori算法加密后,输出状态w4的第4 比特块必定差分活动;当输出状态z7仅在第6、第7 比特块处差分活动,且满足Δz1[6]=Δz1[7]时,经2.5 轮Midori 算法解密后,输出状态x5的第4 比特块差分为0,故产生矛盾,所以结论成立.证毕.□

4.2 11轮Midori-64算法的不可能差分分析

利用定理4.1 中给出的Midori 算法6 轮不可能差分区分器,向上解密1.5 轮,向下加密3.5 轮,给出11 轮Midori-64 算法的不可能差分分析结果.攻击过程分为预计算与在线攻击两个阶段.

(一) 在预计算阶段,共需要预计算并存储4 个表.

(二) 在线攻击阶段.

1.选择2n个明文结构,其中的明文满足在第1、第3、第5、第6、第9～第11、第14、第15 半字节上取所有的值,其余半字节取固定值.故一个明文结构包含236个明文,可以构造271个明文对.因此,攻击的选择明文量为2n+36,其中包含2n+71个明文对.

2.运用快速排序算法筛选明文对.筛选出密文在第4、第8 半字节差分不活动,在第1、第3、第5～第7、第9～第11、第13、第15 半字节差分活动的明文对,剩余2n+63个明文对.以明文对序号作索引,将筛选得到的明文对存储在表Ω中,只需要存储明文第1、第3、第5、第6、第9～第11、第14、第15半字节与密文第1～第3、第5～第7、第9～第15 半字节.

3.猜测出口白化密钥ke11[0,1,2,3].对于表Ω中的2n+63个明文对,利用明文对序号可以得到其对应的密文差分ΔCcol(0).利用ΔCcol(0)查表T1,得到28个y10,col(0)和,可以确定密钥ke11[0,1,2,3]=Ccol(0)⊕y10,col(0).以216个ke11[0,1,2,3]的可能值为索引,平均存储2n+63×28/216=2n+55个明文对序号和在表Ω1中.

4.猜测出口白化密钥ke11[5,6,7].已知ke11[0,1,2,3],对表Ω1中的2n+55个明文对,利用明文对序号可得其对应的密文差分ΔCcol(1).利用ΔCcol(1)查表T2,得到24个y10[5,6,7]和,可确定密钥ke11[5,6,7].以ke11[5,6,7]为索引,平均存储2n+55×24/212=2n+47个明文对序号和在表Ω2中.

5.猜测出口白化密钥ke11[9,10,11].已知ke11[0,1,2,3,5,6,7],对于表Ω2中的2n+47个明文对,利用明文对序号可以得到其对应的密文差分ΔCcol(2).利用ΔCcol(2)查表T3,得到28个y10[9,10,11]和可以确定密钥ke11[9,10,11];以ke11[9,10,11]为索引,平均存储2n+47×24/212=2n+39个明文对和10,14,15])存储在表Ω3中.

6.猜测出口白化密钥ke11[12,13,14,15].已知ke11[0,1,2,3,5,6,7,9,10,11],对于表Ω3中的2n+39个明文对,可以得到其对应的密文差分ΔCcol(3).利用ΔCcol(3)查表T4,得到28个y10,col(3)和,可以确定密钥ke11[12,13,14,15];以ke11[12,13,14,15]为索引,平均存储2n+39×28/216=2n+31个明文对序号和13,14,15],存储在表Ω4中.

9.已知ke11[0,1,2,3,5,6,7,9,10,11,12,13,14,15]与取值,根据密钥扩展算法,由出口白化密钥ke11[0,1,2,3,5,6,7,9,10,11,12,13,14,15]可以直接得到入口白化密钥ke0[1,3,5,6,9,10,11,14,15],利用上述密钥对Ω6中2n+11个明文对加密1 轮,筛选出满足使得仅在Δw0[0,5,10]处活动的明文对.以为索引,表Ω7中存储2n+11×2−24=2n−13个明文对序号.

10.已知密钥ke11[0,1,2,3,5,6,7,9,10,11,12,13,14,15]与取值,穷举212个密钥ke1[0,5,15].利用上述密钥对Ω7中2n−13个明文对加密1/2 轮,以2−8的概率得到不可能差分区分器的输入.将通过检测的密钥列为候选密钥,最后对候选密钥穷举10 个半字节密钥及ke11[4,8],进行11 轮Midori 算法加密检测得到的128 比特密钥是否正确.具体的攻击路径如图9 所示,其中,网状表示猜解的密钥半字节.

Fig.9 11-round impossible differential cryptanalysis of Midori-64图9 11 轮Midori-64 算法不可能差分分析

由定理4.2 给出上述11 轮Midori-64 算法不可能差分分析的复杂度分析结果.

定理4.2.利用6 轮不可能差分区分器对11 轮Midori-64 算法进行不可能差分分析,恢复128 比特主密钥,其时间复杂度为2121.4次11 轮Midori-64 算法加密,数据复杂度为260.8个选择明文,存储复杂度为296.5个Midori-64 状态.

证明:下面给出11 轮Midori-64 算法不可能差分分析中步骤1～步骤9 各步骤的复杂度,见表3.证毕.□

Table 3 Complexity of 11-round impossible differential cryptanalysis on Midori-64表3 11 轮Midori-64 算法不可能差分分析复杂度

由表3 可知,前9 个分析步骤,其时间复杂度大约为2n+96.6次11 轮Midori-64 算法加密.对于第10 步,在88比特已知密钥下,对2n−13个明文对加密0.5 轮的时间复杂度为288×212×2n−13×0.5×2/11≈2n+83.5次11 轮Midori-64算法加密;经过检测后候选密钥集规模,对剩余40 比特密钥进行穷举恢复主密钥的时间复杂度为ε×240.当n=24.8 时,11 轮Midori-64 算法不可能差分分析总时间复杂度为296.6+24.8+283.5+24.8+2100×次11 轮Midori-64 算法加密,数据复杂度为260.8个选择明文,存储复杂度约为295.8×(4+87.8/4)/16≈295.5个Midori-64 状态.

5 结 论

本文证明了在单密钥条件下Midori 算法的截断不可能差分区分器至多6 轮,并对6 轮截断不可能差分区分器进行分类;其次,根据Midori 算法6 轮截断不可能差分区分器的分类构造了一个较优的6 轮区分器,并给出了11 轮Midori-64 算法的不可能差分分析,其时间复杂度为2121.4,数据复杂度为260.8,存储复杂度为296.5.该结果表明,本文给出了一个较好的11 轮Midori-64 算法的分析.对于Midori-128 算法是否也可以根据Midori 算法6轮截断不可能差分区分器的分类构造出较优的区分器,以得到较好的不可能差分分析结果,这是我们下一步要考虑的问题.

作者注 本文是我们于2018 年4 月24 日投到《软件学报》的论文.该文是战略支援部队信息工程大学郭建胜老师(本文第二作者)指导的2018 届(2018 年12 月)毕业的研究生李明明(本文第一作者)的硕士学位论文《典型轻量级分组密码算法不可能差分分析研究》工作成果的一部分,特此说明.