第47卷第5期Vol.
47No.5
计算机工程
Computer Engineering
2021年5月蜜汁烤排骨
May2021 Midori64分组密码算法的积分攻击
王超1，2，陈怀凤1，2
（1.中国电子信息产业集团有限公司第六研究所，北京102209；2.密码科学技术国家重点实验室，北京100878）
摘要：积分攻击是一种重要的密钥恢复攻击方法，已被广泛应用于多种分组算法分析任务。Midori64算法是一种轻量级分组密码算法，为对其进行积分攻击，构建3个6轮零相关区分器，将其分别转化为6轮平衡积分区分器并合成为一个性质优良的6轮零和积分区分器，将该零和积分区分器向前扩展1轮得到一个7轮零和积分区分器。分别采用部分和技术与快速Walsh-Hadamard变换技术，得到Midori64算法的10轮积分攻击和11轮积分攻击。分析结果表明，10轮积分攻击的数据复杂度为240个明密文对，时间复杂度为267.85次10轮加密运算，11轮积分攻击的数据复杂度为240.09个明密文对，时间复杂度为2117.37次11轮加密运算。
关键词：密码分析；Midori64算法；积分攻击；部分和技术；快速Walsh-Hadamard变换技术
开放科学（资源服务）标志码（OSID）：
中文引用格式：王超，陈怀凤.Midori64分组密码算法的积分攻击［J］.计算机工程，2021，47（5）：117-123.
英文引用格式：WANG Chao，CHEN Huaifeng.Integral attacks on Midori64［J］.Computer Engineering，2021，47（5）：117-123.
Integral Attacks on Midori64
WANG Chao1，2，CHEN Huaifeng1，2
（1.The6th Rearch Institute of China Electronics Corporation，Beijing102209，China；
2.State Key Laboratory of Cryptology，Beijing100878，China）
【Abstract】Proven to be an important key recovery method，the technique of integral attacks has been widely ud in the analysis of block ciphers.This paper describes an attempt at integral attacks on the lightweight block cipher，Midori64.Three6-round zero-correlation distinguishers are constructed，transformed into three6-round balanced integral distinguishers，and then merged into one excellent6-round zero-sum integral distinguisher，which extends one round forward to obtain a7-round zero-sum integral distinguisher.On this basis，the partial-sum technique and the fast Walsh-Hadamard transform technique are ud for the10-round and11-round integral attacks on Midori64.The analysis results show that the data complexity and the time complexity of the10-round integral attacks are240and267.85respectively，and tho of11-round attacks are240.09and2117.37respectively.
【Key words】cryptanalysis；Midori64；integral attack；partial-sum technique；fast Walsh-Hadamard transform technique DOI：10.19678/j.issn.1000-3428.0057716
0概述
为了验证Midori算法［1］的安全性，研究人员对Midori算法进行了许多密码分析。文献［2］提出对Midori64算法的14轮相关密钥不可能差分分析，共猜测了84bit密钥。文献［3］提出对Midori64算法的12轮中间相遇攻击，该攻击的时间复杂度为2125.5次12轮加密，数据复杂度为255.5个64bit分组。文
献［4］提出对Midori64算法的11轮不可能差分分析，该攻击的时间复杂度为2121.6次11轮加密，数据复杂度为262.3个64bit分组。文献［5］对文献［4］的不可能差分分析进行优化，时间复杂度为2121.42次11轮加密，数据复杂度为260.82个64bit分组。文献［6］提出对Midori64算法的10轮多维零相关线性分析，其时间复杂度为279.35次10轮加密，数据复杂度为262.4个
64bit分组。文献［7］提出对Midori64算法的8轮积分分析，其时间复杂度为265次8轮加密，数据复杂度为219.80个64bit分组。文献［8-9］分别提出对
基金项目：密码科学技术国家重点实验室开放课题“新型轻量级序列密码设计与分析”。
作者简介：王超（1982—），男，高级工程师、博士，主研方向为信息安全；陈怀凤，高级工程师、博士。
收稿日期：2020-03-13修回日期：2020-04-30E⁃mail：*****************
·网络空间安全·文章编号：1000-3428（2021）05-0117-07文献标志码：A中图分类号：TP391
计算机工程2021年5月15日
Midori 64算法的不变子空间攻击和非线性不变量攻
击，并给出了算法的全轮弱密钥攻击。
文献［10］建立零相关区分器与积分区分器之间的等价关系［11-12］，证明从零相关路线a ®b a =(a 1 0) b =(b 1 0) a 1¹0 b 1¹0可以直接推导出一条积
分路线，其中，输入掩码部分值a 1与输出掩码部分值b 1相互独立。利用该性质，可以借助已找到的零相
关线性路线构造更优的积分路线。为了消除零相关路线向积分路线转化的条件限制，文献［13］提出一种新方法，无论a 1和b 1是否独立，都可以将零相关路线(a 1 0)®(b 1 0)转为积分路线。分离特性（Division
Property ）［14］是一种新型积分路线搜索方法，该方法
充分考虑非线性组件的代数次数，对积分性质的刻画更加精细。此后，基于混合整数线性规划MILP 技术的分离特性搜索方法也相继被提出，且文献［15］利用该方法构造了7轮积分路线。
本文对Midori 64算法的积分攻击问题进行研究，给出算法的6轮零相关区分器，得到相应的6轮积分区分器，向前扩展1轮得到7轮积分区分器，在此基础上，分别研究针对10轮、11轮Midori 64算法的积分攻击。
1
预备知识
1.1
符号说明
本文的符号说明如下：
Å表示按位异或， 表示字符串级联，
•表示函数复合，F n 2表示F 2上的n 维向量空间，+表示有限域内的模加运算，LSB 表示最低有效位，K j
i
表示第j 轮等价轮密钥的第i 个单元，U 表
示单元性质不可知，Z 表示单元具有零和性。1.2
Midori64算法描述
长少学习
Midori 算法于2015年由BANIK 等人在ASIACRYPT 会议上提出［1］，其采用SPN (Substitution Permutation Network )结构，具有低功耗的特点，是一种轻量级分组密码算法。Midori 算法的密钥长度为128bit ，分组长度为64bit 或128bit ，相应的迭代轮数为16轮或20轮，分别记作Midori 64和Midori 128。Midori 64算法的明文分组长度为64bit ，每个明文分组被分成16个4bit ，矩阵表示如下：
S =éëêêêêùû
úúúúS 0
S 4S 8S 12S 1
S 5S 9S 13S 2
S 6S 10S 14S 3S 7S 11S 15（1）
其中，S i (i =0 1 15)表示单元(Cell )。式（1）又称状
态矩阵。
Midori 64算法轮变换作用在状态矩阵上，由S 盒(SubCell ，简记为SB )、置换(ShuffleCell ，简记为SC )、
列混淆(MixColumn ，简记为MC )和密钥加(KeyAdd ，简记为KA )复合组成。1.2.1
密钥编排算法
Midori 64算法的密钥长度为128bit ，将密钥的高
64bit 记为Key 0，低64bit 记为Key 1。定义白化密钥
WK =Key 0ÅKey 1，轮密钥RK i =Key i mod 2Åq i (i =
0 1 14)，其中，q i 为4´4矩阵形式的轮密钥常数，其定义参考文献［1］。将Key 0与Key 1以4´4矩阵形式表示，
q i 按位异或在每个4bit 单元的LSB 位。1.2.2
S 盒
Midori 64算法使用的非线性S 盒取值如表1所
示，S 盒具有对合性质，即SB -1=SB 。
1.2.3
置换
重新排列状态矩阵中16个单元的位置称为置
换，置换及逆置换分别如式（2）和式（3）所示：
éëêêêêù
ûúúúúS 0
S 4S 8S 12S 1S 5S 9S 13S 2S 6S 10S 14S 3S 7S 11S 15®SC éëêêêêùûúúúúS 0S 14S 9S 7S 10S 4S 3S 13S 5S 11S 12S 2S 15S 1S 6S 8（2）
éëêêêêùû
úúúúS 0S 4S 8S 12S 1S 5S 9S 13S 2S 6S 10S 14S 3
S 7
S 11
S 15®SC
-1
éëêêêêùû
úúúúS 0S 5S 15S 10S 7S 2S 8S 13S 14S 11S 1S 4S 9
S 12
S 6
S 3（3）
1.2.4
列混淆
以almost MDS ［1］矩阵M 左乘更新状态矩阵称为
列混淆，如式（4）所示，其中，矩阵M 如式（5）所示，矩阵M 满足M -1=M 。
éëêêêêùûúúúúS 0
S 4S 8S 12S 1S 5S 9S 13S 2S 6S 10S 14S 3S 7S 11S 15®MC M •éëêêêêùû
úúúúS 0
S 4
S 8S 12S 1S 5S 9S 13S 2
S 6S 10S 14S 3S 7S 11S 15（4）表1
Midori64算法的S 盒Table 1
S-box of Midori64
x 01234567
SB(x )C A D 3
E B
F 7
x 89
A B C D E F SB(x )89150246
118
第47卷第5期
王超，陈怀凤：Midori64分组密码算法的积分攻击
M =éëêêêêêêùû
úúúúúú0
111101111011
1
1英语单词造句
0（5）
1.2.5
密钥加
Midori 64算法在加密过程中使用64bit 白化密
钥WK 和轮密钥RK i (i =0 1 14)对状态矩阵进行异或更新。
Midori 64算法在解密过程中使用64bit 白化密钥WK 和SC -1(MC(RK i ))(i =14 13 0)对状态矩阵进行异或更新。1.2.6
加密流程
Midori 64算法的加密流程如图1所示，在第1轮
之前添加使用白化密钥的密钥加，第1轮~第15轮使用轮密钥RK i (i =0 1 14)进行密钥加，第16轮使用白化密钥进行密钥加。
1.2.7
解密流程
Midori 64算法的解密流程如图2所示，在第1轮
之前添加使用白化密钥的密钥加，第1轮~第15轮使用SC -1(MC(RK i ))(i =14 13 0)进行密钥加，第16轮使用白化密钥进行密钥加。
2Midori64的6轮零相关区分器
零相关线性分析由BOGDANOV 和RIJMEN ［16］
于
2012年提出，攻击使用分组密码算法中以概率12
成
立的线性逼近，即相关度为零的线性逼近，由此区分分组密码算法与随机置换，进而恢复密钥。文献［17］建立了多重零相关分析模型，其克服了经典
零相关线性分析在数据复杂度方面的缺陷。文
献［18］建立了卡方多维零相关线性模型，其消除了对零相关数量的限制条件。
函数h ：F m 2®F n 2上线性逼近(α β)的相关度定义为：
C h (α β)=
12
n
∑x ÎF n
2
(-1)
α×x Åβ×h (x )
其中，α为输入掩码，β为输出掩码，·表示向量内积。
当C h (α β)=0时，称(α β)为零相关线性逼近［17］。
命题1（线性映射的相关度）［17］对于线性映射
h (x )=Mx ，若α=M T β，则C h (α β)=1；否则，
C h (α β)=0。零相关区分器是指在输入掩码与输出掩码作用下，目标输入与输出比特的线性相关度为0的一类线性区分器。根据命题1进行自动化搜索，可以得到大量Midori 64算法的5轮零相关区分器，按输入掩码权重与输出掩码权重进行分类，零相关区分器的个数统计结果如表2所示。
取3个输入掩码权重为7且输出掩码权重为1的5轮零相关区分器，然后对输出掩码部分继续扩展1轮，
得到6轮零相关区分器。令：
α1=a 0‖0‖0‖a 3‖a 4‖0‖a 6‖0‖a 8‖a 9‖0‖0‖a 12‖0‖0‖0β1=0‖d 0‖d 0‖d 0‖0‖0‖0‖0‖0‖0‖0‖0‖0‖0‖0‖0β2=d 5‖d 5‖0‖d 5‖0‖0‖0‖0‖0‖0‖0‖0‖0‖0‖0‖0
β3=d 15‖d 15‖d 15‖0‖0‖0‖0‖0‖0‖0‖0‖0‖
0‖0‖0‖0
其中，
a 0、a 3、a 4、a 6、a 8、a 9、a 12、d 0、d 5、d 15均为4bit
向图1
Midori64算法的加密流程Fig.1
The encryption procedure of Midori64
表2
Midori64算法的5轮零相关区分器个数统计
Table 2
Number statistics of Midori645-round zero-correlation discriminator
输入掩码权重1234567
零相关区分器个数
输出掩码权重为1256
139230403280201667296输出掩码权重为21392000000
输出掩码权重为33040000000
输出掩码权重为43280000000
输出掩码权重为52016000000
输出掩码权重为6672000000
输出掩码权重为79600000
图2
Midori64算法的解密流程Fig.2
The decryption procedure of Midori64
119
计算机工程2021年5月15日
量，0为4bit 零向量。（α1¾®¾¾6轮β1）、（α1¾®¾¾6轮
β2）和（α1¾®¾¾6轮β3）都是Midori 64算法的6轮零相关区分
器。第1个6轮零相关区分器的掩码扩展细节如图3所示
。
图3
Midori64算法的6轮零相关区分器
Fig.3
6-round zero-correlation discriminator of Midori64
3
Midori64的积分区分器
3.1
积分区分器构造虾皮炒冬瓜
积分攻击是一种选择明文攻击，最先应用于
Square 分组密码分析，其基本思想是通过分析一系列中间状态的和具有概率为1的性质，得出不能通过检测的密钥都是错误密钥，从而利用淘汰法直接恢复出正确密钥。积分攻击的主要环节是寻找积分区分器，积分区分器可以分为如下2类：
1）一系列中间状态的和遍历所有可能取值，且
每个可能取值的出现次数相同，该类积分区分器称为平衡积分区分器。2）一系列中间状态的异或和为零，该类积分区分器称为零和积分区分器。
当选择特定的输入集合（输入的部分比特固定为常数，其余比特遍历所有可能）时，经过几轮算法加密后，输出的某些比特存在概率为1的分布特性，输出目标值异或和为0时，为零和积分区分器；输出目标值均匀遍历所有可能时，为平衡积分区分器。实际上，平衡积分区分器与零相关区分器之间
存在一定的等价关系［10］，任意的零相关区分器都可以转化成一个平衡积分区分器，本文利用文献［10］中给出的两区分器等价性进行积分区分器构造。
若所有原像集的势都相同，则函数h ：
F s 2®F t 2是平衡的［10］，即集合h -1(y )={x ÎF s 2|h (x )=y }的大小与y 无关。
命题2［10］
对于函数h ：F r 2´F s 2®F t 2´F u 2 h ()x y =
()
h 1()x y h 2()
x y ，定义T λ：F s 2®F t 2 T λ(y )=h 1(λ y )。若"a Î
F s 2 b ÎF t 2 b ¹0且a 与b 独立，则函数h 上线性特征（a ‖0 b ‖0）的相关度为0等价于"λÎF r 2，函数T λ是
平衡的。3.2
Midori64的6轮积分区分器
记集合S in ={x =(c 0 b 1 b 2 c 3 c 4 b 5 c 6 b 7 c 8 c 9 b 10 b 11 c 12 b 13 b 14 b 15)}，其中，c 0‖c 3‖c 4‖c 6‖c 8‖c 9‖c 12取常数，b 1‖b 2‖b 5‖b 7
‖b 10‖b 11‖b 13‖b 14‖b 15遍历所有可能取值。S in 中存在236个元素，存在228个此类集
120
第47卷第5期王超，陈怀凤：Midori64分组密码算法的积分攻击
合。经过6轮加密后，得到对应的输出集合为S out =
{y =(y 0 y 1 y 15)|y =E 6
Key (x ) x ÎS in }。
令t 0=y 1Åy 2Åy 3、
t 1=y 0Åy 1Åy 3和t 2=y 0Åy 1Åy 2，则加密函数被分割为：
E 6
Key
：F r 2
´F s 2
®F t 2
´F u 2
E
6Key
(x y )=
()
h 1()x y h 2()dwg
x y 定理1当输入为S in 时，加密6轮后，
y 1是零和的。证明
加密函数E 6
Key 上线性特征(
α1 β1)、(α1 β2
)
和(
α1 β3)
的相关度都是0，由命题2可知T λ：F s 2®F t 2 T λ(x s )=h 1(λ x s )
是平衡的，得到t 0、t 1和t 2每
个取值的原像个数相同，于是∑t 0=0，∑t 1=0，
∑t 2=0，
从而∑y 1=∑t 0Å∑t 1Å∑t 2=0，证毕。6轮零和积分区分器如图4所示。农村电视剧大全集
3.3Midori64的7轮积分区分器
在6轮积分区分器的前面解密1轮可以得到
7轮积分区分器。对6轮积分区分器的输入S in 中各
单元进行逆向轮密钥异或操作，其中，第0个、第3个、第4个、第6个、第8个、第9个和第12个单元是固定常数，其余单元仍然遍历所有可能取值。因此，在构造7轮积分区分器的过程中，可忽略此逆向密钥加操作。记7轮积分区分器的明文集合为：
S *
in
={y =SB -1
(SC -1
(MC -1
(x )))|x ÎS in }
其中，列混淆、置换和S 盒都是可逆变换，复合变换y =SB -1(SC -1(MC -1(x )))
是双射。对由236个明文构
成的S *
in 进行1轮加密，其结果满足6轮零和积分区
分器的输入条件，因此，当输入为S *
in
时，加密7轮后y 1是零和的。存在一系列7轮积分路线，
令S in ={x =(c 0 b 1 b 2 c 3 c 4 b 5 c 6 b 7 b 8 b 9 c 10 c 11 c 12 b 13 c 14 c 15)}。
S *in 的定义与S *in 类似，当输入为S *in 时，加密7轮后y 13
是零和的。
4
Midori64的积分攻击
4.1
Midori64的10轮积分攻击
在7轮积分区分器的后面加密3轮可以得到
10轮积分区分器，如图5所示
。
图5Midori64算法的10轮密钥恢复攻击Fig.5
10-round key recovery attack of Midori64
为降低密钥的猜测量，本文利用等价密钥技术［19］，该技术结合Midori 64算法，将列混淆MC 与密钥加KA 进行位置交换，其中，线性等价的轮密钥加记为KA *，从而在攻击中减少密钥的猜测量。具体地，将图5中S out [1]标注为Z [1]，以*标注每个从
S *
out 计算至Z [1]时需要明确值的单元。设轮密钥经
过线性变换后的等价轮密钥为K i ，即K i =MC (RK i )。
利用部分和技术［17］，Midori 64算法的128bit 密钥恢复过程具体如下：
步骤1
选择一个明文集合S *
in ，收集相应的密
文得到S *out 。
步骤2
猜测第10轮等价轮密钥K 100、K 101、K 105、
K 107、K 108、K 109、K 1011、K 1012、K 1015
，共计36bit 。对S *
out 进行解密1轮及列混淆MC 逆运算，得到X [2]、
X []5、X []11对应的值。定义计数器向量N 0X [2]‖X []5‖X []11用于存储X [2]‖X [5]‖X [11]的个
数，共有212个计数器。从异或和的角度考虑，仅需考查奇偶性，则计数器只使用1bit 来标识奇偶性即可。
步骤3
猜测第9轮等价轮密钥K 92、K 95、K 9
11，共
活动开展情况报告
计12bit 。对X [2]、
X [5]、X [11]解密1轮得到Y [2]。定义计数器向量N 1[Y [2]]用于存储Y [2]的
奇偶性，共有24个计数器。
步骤4
由K 87=MC (MC(K 107)Åq 7Åq 9)
可知K 8
7不需要猜测，可计算得到Z [1]。计算∑Z []1，若为0，则相应的猜测密钥作为真实密钥的候选值；否则，
淘汰该猜测密钥。
步骤5针对上述48bit 密钥，选取m 组S *
in ，重
复步骤1~步骤4，可平均剩余2128-4m 个正确候选密钥。
步骤6
重复上述步骤，第9轮猜测12bit 密钥，
第10轮猜测20bit 密钥，选择n 组S in
，重复步骤1~步
骤4，可平均剩余2
128-4m -4n
个正确候选密钥
。
图4
Midori64算法的6轮零和积分区分器
Fig.4
孕妇中暑
6-round zero-sum integral discriminator of Midori64
121
