软件学报  2019, Vol. 30 Issue (8): 2337-2348   PDF    
Midori-64算法的截断不可能差分分析
李明明, 郭建胜, 崔竞一, 徐林宏     
信息工程大学, 河南 郑州 450001
摘要: 分析了Midori-64算法在截断不可能差分攻击下的安全性.首先,通过分析Midori算法加、解密过程差分路径规律,证明了Midori算法在单密钥条件下的截断不可能差分区分器至多6轮,并对6轮截断不可能差分区分器进行了分类;其次,根据分类结果,构造了一个6轮区分器,并给出11轮Midori-64算法的不可能差分分析,恢复了128比特主密钥,其时间复杂度为2121.4,数据复杂度为260.8,存储复杂度为296.5.
关键词: 密码分析     轻量级分组密码     Midori     不可能差分分析     截断不可能差分区分器    
Truncated Impossible Differential Cryptanalysis of Midori-64
LI Ming-Ming, GUO Jian-Sheng, CUI Jing-Yi, XU Lin-Hong     
Information Engineering University, Zhengzhou 450001, China
Foundation item: Open Foundation of Science and Technology on Information Assurance Laboratory (KJ-17-003)
Abstract: The security of Midori-64 under truncated impossible differential cryptanalysis was studied. Firstly, by analyzing the differential paths of Midori in encryption and decryption direction, it was proved that the upper bound for the rounds of impossible differential distinguishers in single-key setting for Midori is 6. And the 6-round truncated impossible differential distinguisher was classified. Secondly, based on the classification, a 6-round distinguisher was constructed. At the same time the impossible differential attack on 11-round Midori-64 was given to recover the 128-bit master key with a time complexity of 2121.4 11-round encryptions, a data complexity of 260.8 chosen-plaintexts, and a memory complexity of 296.5 64-bit blocks.
Key words: cryptanalysis     lightweight block cipher     Midori     impossible differential cryptanalysis     truncated impossible differential distinguisher    

不可能差分分析, 由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轮经过列混合变换后的状态.

$({z'_i}, {z''_i})$:表示第i轮经过移位变换后输出的数据对.

kei:第i轮加密密钥.

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

$k_{ei}^*$:第i轮加密密钥经过SC-1·MC-1变换后状态, 即${k_{ei}} = MC \cdot SC(k_{ei}^*){\rm{.}}$

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比特SSb0, Sb1, 即Sb0, Sb1:{0, 1}4→ {0, 1}4.在Midori-64中使用一个SSb0.在Midori-128中使用由两个Sb1与4个不同的置换生成4个8比特的SSb0, Sb1, Sb2, Sb3.Sb0, Sb1以16进制表示形式给出, 见表 2.

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

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

$\left( {\begin{array}{*{20}{c}} {{s_0}}&{{s_4}}&{{s_8}}&{{s_{12}}} \\ {{s_1}}&{{s_5}}&{{s_9}}&{{s_{13}}} \\ {{s_2}}&{{s_6}}&{{s_{10}}}&{{s_{14}}} \\ {{s_3}}&{{s_7}}&{{s_{11}}}&{{s_{15}}} \end{array}} \right)\mathop \Rightarrow \limits^{SC} \left( {\begin{array}{*{20}{c}} {{s_0}}&{{s_{14}}}&{{s_9}}&{{s_7}} \\ {{s_{10}}}&{{s_4}}&{{s_3}}&{{s_{13}}} \\ {{s_5}}&{{s_{11}}}&{{s_{12}}}&{{s_2}} \\ {{s_{15}}}&{{s_1}}&{{s_6}}&{{s_8}} \end{array}} \right), \left( {\begin{array}{*{20}{c}} {{s_0}}&{{s_5}}&{{s_{15}}}&{{s_{10}}} \\ {{s_7}}&{{s_2}}&{{s_8}}&{{s_{13}}} \\ {{s_{14}}}&{{s_{11}}}&{{s_1}}&{{s_4}} \\ {{s_9}}&{{s_{12}}}&{{s_6}}&{{s_3}} \end{array}} \right)\mathop \Leftarrow \limits^{S{C^{ - 1}}} \left( {\begin{array}{*{20}{c}} {{s_0}}&{{s_4}}&{{s_8}}&{{s_{12}}} \\ {{s_1}}&{{s_5}}&{{s_9}}&{{s_{13}}} \\ {{s_2}}&{{s_6}}&{{s_{10}}}&{{s_{14}}} \\ {{s_3}}&{{s_7}}&{{s_{11}}}&{{s_{15}}} \end{array}} \right).$

●列混合变换:使用对合二元阵M对状态中每一列进行如下操作, 即M·(si, si+1, si+2, si+3)'→(si, si+1, si+2, si+3)', 其中, i=0, 4, 8, 12, M及其逆矩阵M-1如下:

$M = \left( {\begin{array}{*{20}{c}} 0&1&1&1 \\ 1&0&1&1 \\ 1&1&0&1 \\ 1&1&1&0 \end{array}} \right), {M^{ - 1}} = \left( {\begin{array}{*{20}{c}} 0&1&1&1 \\ 1&0&1&1 \\ 1&1&0&1 \\ 1&1&1&0 \end{array}} \right).$

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

密钥扩展算法:Midori算法使用128比特主密钥, 其密钥扩展算法较为简单.其中, Midori-64算法将128比特主密钥分为两部分K=k0||k1, 算法的入口与出口白化密钥均为WK=k0⊕k1, 圈子密钥kei=k(i+1) mod 2⊕α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算法移位变换后, 必定在同一行:

$\left( {\begin{array}{*{20}{c}} 0&4&8&{12} \\ 1&5&9&{13} \\ 2&6&{10}&{14} \\ 3&7&{11}&{15} \end{array}} \right)\xrightarrow{{SC}}\left( {\begin{array}{*{20}{c}} 0&{14}&9&7 \\ {10}&4&3&{13} \\ 5&{11}&{12}&2 \\ {15}&1&6&8 \end{array}} \right)\xrightarrow{{SC}}\left( {\begin{array}{*{20}{c}} 0&2&3&1 \\ {12}&{14}&{15}&{13} \\ 4&6&7&5 \\ 8&{10}&{11}&9 \end{array}} \right).$

性质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的半字节, 黑色表示差分活动的半字节, 斜线表示可能存在差分的半字节.

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

由性质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所示.

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

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

性质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所示.

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

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

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

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

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

证明:由SC, SB, KeyAdd, MC的性质可知, 任意状态, 其列与列之间的这4种变换是相互独立的.故z1${z'_1}$经相同的变换, ${z'_1}$经变换后, 输出状态有差分活动的比特块集合必定包含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所示.

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

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

证明:不妨将状态上可能有差分活动的所有比特块用集合H表示, 例如zm上可能有差分活动的所有个比特块集合用${H_{{z_m}}}$表示, 状态${z'_m}$上可能有差分活动的所有个比特块用集合${H_{{{z'}_m}}}$表示, 显然有${H_{{z_m}}} \subset {H_{{{z'}_m}}}{\rm{.}}$SC, SB, KeyAdd, MC的性质可知, ${H_{{y_m}}} \subset {H_{{{y'}_m}}}, {H_{{x_m}}} \subset {H_{{{x'}_m}}}, {H_{{w_{m - 1}}}} \subset {H_{{{w'}_{m - 1}}}}, {H_{{z_{m - 1}}}} \subset {H_{{{z'}_{m - 1}}}}$.故zm${z'_m}$经相同的变换, ${z'_m}$经变换后输出状态有差分活动的比特块集合, 必定包含zm经变换后的输出状态有差分活动的比特块集合, 所以该结论是成立的.

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

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

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

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

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个表.

●表T1:仅在${w'_9}[1, 3]$处差分活动的$\Delta {w'_{9, col(0)}}$共有28种取值, 故Δx10, col(0)有28种取值.以Δy10, col(0)的216种可能取值为索引, 根据性质2.2, 平均每个索引值对应28y10, col(0)及对应的${w'_9}[1, 3]$.因Δy10, col(0)Ccol(0)${w'_9}[1, 3] = {z'_9}[10, 15]$, 以216个密文差分ΔCcol(0)为索引, 平均可以得到28y10, col(0)$({z'_9}[10, 15], {z''_9}[10, 15]){\rm{, }}$将其存储在表T1中.

●表T2:仅在${w'_9}[4]$处差分活动的$\Delta {w'_{9, col(1)}}$共有24种取值.Δy10第1列中仅在第5~第7半字节差分活动, 以212个ΔCcol(1)为索引, 存储24y10[5, 6, 7]和$({z'_9}[14], {z''_9}[14])$在表T2中.

●表T3:在${w'_9}[8]$处差分活动的$\Delta {w'_{9, col(2)}}$共有24种取值.Δy10第2列中仅在第9~第11半字节差分活动, 以212个ΔCcol(2)为索引, 存储28y10[9, 10, 11]和$({z'_9}[9], {z''_9}[9])$在表T3中.

●表T4:在${w'_9}[13, 15]$处差分活动的$\Delta {w'_{9, col(3)}}$共有28种取值.以216个ΔCcol(3)为索引, 存储28y10, col(3)$({z'_9}[8, 13], {z''_9}[8, 13])$在表T4中.

(二)在线攻击阶段.

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, 得到28y10, col(0)$({z'_9}[10, 15], {z''_9}[10, 15])$, 可以确定密钥ke11[0, 1, 2, 3]=Ccol(0)⊕y10, col(0).以216ke11[0, 1, 2, 3]的可能值为索引, 平均存储2n+63×28/216=2n+55个明文对序号和$({z'_9}[10, 15], {z''_9}[10, 15])$在表Ω1中.

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

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

7.猜测$k_{e10}^*[8, 9, 10, 13, 14, 15]$.已知ke11[0, 1, 2, 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15], 利用表Ω4中2n+31个明文对, 穷举$\Delta {z'_8}[6, 7]$, 根据性质1.2可以得到28y9[8, 9, 10, 13, 14, 15], 故可以确定$k_{e10}^*[8, 9, 10, 13, 14, 15] = {y_9}[8, 9, 10, $ $13, 14, 15] \oplus {z'_9}[8, 9, 10, 13, 14, 15]$.以$k_{e10}^*[8, 9, 10, 13, 14, 15]$为索引, 表Ω5平均存储2n+31×28/224=2n+15个明文序号和$({z'_8}[6, 7], {z''_8}[6, 7])$.

8.猜测$k_{e9}^*[2, 3]$.已知ke11[0, 1, 2, 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15]与$k_{e10}^*[8, 9, 10, 13, 14, 15]$, 利用表Ω5中2n+15个明文对穷举$\Delta {z'_7}[1, 11]$, 可得24$k_{e9}^*[2, 3]$.以$k_{e9}^*[2, 3]$为索引, 表Ω6中存储2n+15×24/28=2n+11个明文对序号.

9.已知ke11[0, 1, 2, 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15]与$k_{e10}^*[8, 9, 10, 13, 14, 15]$$k_{e9}^*[2, 3]$取值, 根据密钥扩展算法, 由出口白化密钥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]处活动的明文对. 以$k_{e9}^*[2, 3]$为索引, 表Ω7中存储2n+11×2-24=2n-13个明文对序号.

10.已知密钥ke11[0, 1, 2, 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15]与$k_{e10}^*[8, 9, 10, 13, 14, 15]$$k_{e9}^*[2, 3]$取值, 穷举212个密钥ke1[0, 5, 15].利用上述密钥对Ω7中2n-13个明文对加密1/2轮, 以2-8的概率得到不可能差分区分器的输入.将通过检测的密钥列为候选密钥, 最后对候选密钥穷举10个半字节密钥$k_{e10}^*[0, 1, 4, 5, 6, 7, 11, 12]$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算法加密; 经过检测后候选密钥集规模$\varepsilon = {2^{100}} \times {(1 - {2^{ - 8}})^{{2^{n - 13}}}}$, 对剩余40比特密钥进行穷举恢复主密钥的时间复杂度为ε×240.当n=24.8时, 11轮Midori-64算法不可能差分分析总时间复杂度为296.6+24.8+283.5+24.8+2100×${(1 - {2^{ - 8}})^{{2^{24.8 - 13}}}}$×240≈2121.4次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月)毕业的研究生李明明(本文第一作者)的硕士学位论文《典型轻量级分组密码算法不可能差分分析研究》工作成果的一部分, 特此说明.

参考文献
[1]
Knudsen L. DEAL-A 128-bit block cipher. Technical Report, No.151, Department of Informatics, University of Bergen, 1998.
[2]
Biham E, Biryukov A, Shamir A. Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials. In: Proc. of the EUROCRYPT'99. Berlin, Heidelberg: Springer-Verlag, 1999. 12-23.
[3]
Kim J, Hong S, Lim J. Impossible differential cryptanalysis using matrix method. Discrete Mathematics, 2010, 310(5): 988-1002. [doi:10.1016/j.disc.2009.10.019]
[4]
Luo YY, Lai XJ, Wu ZM, Gong G. A unified method for finding impossible differentials of block cipher structures. Information Sciences, 2014, 263(1): 211-220. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=e15441eddd0e1fe90adcac1fbc8ef3de
[5]
Sun B, Liu M, Guo J, Rijmen V, Li RL. Provable security evaluation of structures against impossible differential and zero correlation linear cryptanalysis. In: Proc. of the Advances in Cryptology (EUROCRYPT 2016). Berlin, Heidelberg: Springer-Verlag, 2016. 196-213.
[6]
Bogdanov A, Knudsen LR, Leander G, Paar C, Poschmann A, Robshaw MJB, Seurin Y, Vikkelsoe C. PRESENT: An ultra-lightweight block cipher. In: Proc. of the CHES 2007. Berlin, Heidelberg: Springer-Verlag, 2007. 450-466.
[7]
Izadi M, Sadeghiyan B, Sadeghian SS, Khanook HA. MIBS: A new lightweight block cipher. In: Proc. of the CANS 2009. Berlin, Heidelberg: Springer-Verlag, 2009. 334-348.
[8]
Dolmatov V. GOST 28147-89 encryption, decryption and MAC algorithms. RFC 5830, IETF, 2010. http://tools.ietf.org/html/rfc5830
[9]
Gong Z, Nikova S, Law YW. KLEIN: A new family of lightweight block ciphers. In: Proc. of the Int'l Workshop on Radio Frequency Identification: Security and Privacy Issues. Berlin, Heidelberg: Springer-Verlag, 2011. 1-18.
[10]
Guo J, Peyrin T, Poschmann A, Robshaw M. The LED block cipher. In: Proc. of the CHES 2011. Berlin, Heidelberg: Springer-Verlag, 2011. 326-341.
[11]
Shibutani K, Isobe T, Hiwatari H, Mitsuda A, Akishita T, Shirai T. Piccolo: An ultra-lightweight block cipher. In: Proc. of the CHES 2011. Berlin, Heidelberg: Springer-Verlag, 2011. 342-357.
[12]
Wu WL, Zhang L. LBlock: A lightweight block cipher. In: Proc. of the Int'l Conf. on Applied Cryptography and Network Security. Berlin, Heidelberg: Springer-Verlag, 2011. 327-344.
[13]
Borghoff J, Canteaut A, Güneysu T, Kavun EB, Knezevic M, Knudsen LR, Leander G, Nikov V, Paar C, Rechberger C, Rombouts P, Thomsen SS, Yalçin T. PRINCE-A low-latency block cipher for pervasive computing applications. In: Proc. of the Int'l Conf. on the Theory and Application of Cryptology and Information Security. Berlin, Heidelberg: Springer-Verlag, 2012. 208-225.
[14]
Banik S, Bogdanov A, Isobe T, Shibutani K, Hiwatari H, Akishita T, Regazzoni F. Midori: A block cipher for low energy. In: Proc. of the ASIACRYPT 2015. Berlin, Heidelberg: Springer-Verlag, 2015. 411-436.
[15]
Lin L, Wu WL. Meet-in-the-Middle attacks on reduced-round Midori64. IACR Trans. on Symmetric Cryptology, 2017, 2017(1): 215-239. http://cn.bing.com/academic/profile?id=99a4c3dd89255a5ca25840731fa40b5f&encoded=0&v=paper_preview&mkt=zh-cn
[16]
Guo J, Jean J, Nikolić I, Qiao K, Sasaki Y, Sim SM. Invariant subspace attack against full midori64. In: Proc. of the IACR Cryptology ePrint Archive. 2015. https://eprint.iacr.org/2015/1189.pdf
[17]
Chen Z, Wang XY. Impossible differential cryptanalysis of Midori. In: Proc. of the Int'l Conf. on Mechatronics and Automation, World Scientific. 2017. 221-229.[doi:10.1142/9789813208537_0028]
[18]
Cui JY. Research on cryptanalysis based on meet-in-the-middle[MS. Thesis]. Zhengzhou: Information Engineering University, 2017(in Chinese with English abstract).
[18]
崔竞一.基于中间相遇思想的攻击方法研究[硕士学位论文].郑州: 信息工程大学, 2017.