0 概述

为了验证Midori算法^[1]的安全性，研究人员对Midori算法进行了许多密码分析。文献[2]提出对Midori64算法的14轮相关密钥不可能差分分析，共猜测了84 bit密钥。文献[3]提出对Midori64算法的12轮中间相遇攻击，该攻击的时间复杂度为2^125.5次12轮加密，数据复杂度为2^55.5个64 bit分组。文献[4]提出对Midori64算法的11轮不可能差分分析，该攻击的时间复杂度为2^121.6次11轮加密，数据复杂度为2^62.3个64 bit分组。文献[5]对文献[4]的不可能差分分析进行优化，时间复杂度为$ {2}^{121.42} $次11轮加密，数据复杂度为$ {2}^{60.82} $个64 bit分组。文献[6]提出对Midori64算法的10轮多维零相关线性分析，其时间复杂度为2^79.35次10轮加密，数据复杂度为2^62.4个64 bit分组。文献[7]提出对Midori64算法的8轮积分分析，其时间复杂度为2⁶⁵次8轮加密，数据复杂度为2^19.80个64 bit分组。文献[8-9]分别提出对Midori64算法的不变子空间攻击和非线性不变量攻击，并给出了算法的全轮弱密钥攻击。

文献[10]建立零相关区分器与积分区分器之间的等价关系^[11-12]，证明从零相关路线$ a{\not \to }b, a=({a}_{1}, 0), b=({b}_{1}, 0), {a}_{1}\ne 0, {b}_{1}\ne 0 $可以直接推导出一条积分路线，其中，输入掩码部分值$ {a}_{1} $与输出掩码部分值$ {b}_{1} $相互独立。利用该性质，可以借助已找到的零相关线性路线构造更优的积分路线。为了消除零相关路线向积分路线转化的条件限制，文献[13]提出一种新方法，无论$ {a}_{1} $和$ {b}_{1} $是否独立，都可以将零相关路线$ ({a}_{1}, 0){\not \to }({b}_{1}, 0) $转为积分路线。分离特性（Division Property）^[14]是一种新型积分路线搜索方法，该方法充分考虑非线性组件的代数次数，对积分性质的刻画更加精细。此后，基于混合整数线性规划MILP技术的分离特性搜索方法也相继被提出，且文献[15]利用该方法构造了7轮积分路线。

本文对Midori64算法的积分攻击问题进行研究，给出算法的6轮零相关区分器，得到相应的6轮积分区分器，向前扩展1轮得到7轮积分区分器，在此基础上，分别研究针对10轮、11轮Midori64算法的积分攻击。

1 预备知识 1.1 符号说明

本文的符号说明如下：$ \oplus $表示按位异或，//表示字符串级联，$ • $表示函数复合，$ {F}_{2}^{n} $表示$ {F}_{2} $上的n维向量空间，$ + $表示有限域内的模加运算，LSB表示最低有效位，$ {K}_{i}^{j} $表示第j轮等价轮密钥的第i个单元，U表示单元性质不可知，Z表示单元具有零和性。

1.2 Midori64算法描述

Midori算法于2015年由BANIK等人在ASIACRYPT会议上提出^[1]，其采用SPN$ ( $Substitution Permutation Network$ ) $结构，具有低功耗的特点，是一种轻量级分组密码算法。Midori算法的密钥长度为128 bit，分组长度为64 bit或128 bit，相应的迭代轮数为16轮或20轮，分别记作Midori64和Midori128。Midori64算法的明文分组长度为64 bit，每个明文分组被分成16个4 bit，矩阵表示如下：

$ {{\mathit{\boldsymbol{\boldsymbol{S}}}}}=\left[\begin{array}{cccc}{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] $

(1)

其中，$ {S}_{i}(i=\mathrm{0, 1}, \cdots , 15) $表示单元$ ( $Cell$ ) $。式（1）又称状态矩阵。

Midori64算法轮变换作用在状态矩阵上，由S盒$ ( $SubCell，简记为SB$ ) $、置换$ ( $ShuffleCell，简记为SC$ ) $、列混淆$ ( $MixColumn，简记为MC$ ) $和密钥加$ ( $KeyAdd，简记为KA$ ) $复合组成。

1.2.1 密钥编排算法

Midori64算法的密钥长度为128 bit，将密钥的高64 bit记为$ \mathrm{K}\mathrm{e}{\mathrm{y}}_{0} $，低64 bit记为$ \mathrm{K}\mathrm{e}{\mathrm{y}}_{1} $。定义白化密钥$ \mathrm{W}\mathrm{K}=\mathrm{K}\mathrm{e}{\mathrm{y}}_{0}\oplus \mathrm{K}\mathrm{e}{\mathrm{y}}_{1} $，轮密钥$ \mathrm{R}{\mathrm{K}}^{i}=\mathrm{K}\mathrm{e}{\mathrm{y}}_{i\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{ }2}\oplus {q}_{i}(i=\mathrm{0, 1}, \cdots , 14) $，其中，$ {q}_{i} $为$ 4\times 4 $矩阵形式的轮密钥常数，其定义参考文献[1]。将$ \mathrm{K}\mathrm{e}{\mathrm{y}}_{0} $与$ \mathrm{K}\mathrm{e}{\mathrm{y}}_{1} $以$ 4\times 4 $矩阵形式表示，$ {q}_{i} $按位异或在每个4 bit单元的LSB位。

1.2.2 S盒

Midori64算法使用的非线性S盒取值如表 1所示，S盒具有对合性质，即$ \mathrm{S}{\mathrm{B}}^{-1}=\mathrm{S}\mathrm{B} $。

1.2.3 置换

重新排列状态矩阵中16个单元的位置称为置换，置换及逆置换分别如式（2）和式（3）所示：

$ \left[\begin{array}{cccc}{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]\stackrel{\mathrm{S}\mathrm{C}}{\to }\left[\begin{array}{cccc}{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] $

(2)

$ \left[\begin{array}{cccc}{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]\stackrel{\mathrm{S}{\mathrm{C}}^{-1}}{\to }\left[\begin{array}{cccc}{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] $

(3)

1.2.4 列混淆

以almost MDS^[1]矩阵M左乘更新状态矩阵称为列混淆，如式（4）所示，其中，矩阵M如式（5）所示，矩阵M满足$ {{\mathit{\boldsymbol{M}}}}^{-1}={\mathit{\boldsymbol{M}}} $。

$ \left[\begin{array}{cccc}{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]\stackrel{\mathrm{M}\mathrm{C}}{\to }{\mathit{\boldsymbol{M}}}•\left[\begin{array}{cccc}{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] $

(4)

$ {\mathit{\boldsymbol{M}}}=\left[\begin{array}{cccc}0& 1& 1& 1\\ 1& 0& 1& 1\\ 1& 1& 0& 1\\ 1& 1& 1& 0\end{array}\right] $

(5)

1.2.5 密钥加

Midori64算法在加密过程中使用64 bit白化密钥$ \mathrm{W}\mathrm{K} $和轮密钥$ \mathrm{R}{\mathrm{K}}_{i}(i=\mathrm{0, 1}, \cdots , 14) $对状态矩阵进行异或更新。

Midori64算法在解密过程中使用64 bit白化密钥$ \mathrm{W}\mathrm{K} $和$ \mathrm{S}{\mathrm{C}}^{-1}\left(\mathrm{M}\mathrm{C}\right(\mathrm{R}{\mathrm{K}}_{i}\left)\right)\mathrm{ }(i=\mathrm{14, 13}, \cdots , 0) $对状态矩阵进行异或更新。

1.2.6 加密流程

Midori64算法的加密流程如图 1所示，在第1轮之前添加使用白化密钥的密钥加，第1轮~第15轮使用轮密钥$ \mathrm{R}{\mathrm{K}}_{i}(i=\mathrm{0, 1}, \cdots , 14) $进行密钥加，第16轮使用白化密钥进行密钥加。

1.2.7 解密流程

Midori64算法的解密流程如图 2所示，在第1轮之前添加使用白化密钥的密钥加，第1轮~第15轮使用$ \mathrm{S}{\mathrm{C}}^{-1}\left(\mathrm{M}\mathrm{C}\right(\mathrm{R}{\mathrm{K}}_{i}\left)\right)\mathrm{ }(i=\mathrm{14, 13}, \cdots , 0) $进行密钥加，第16轮使用白化密钥进行密钥加。

2 Midori64的6轮零相关区分器

零相关线性分析由BOGDANOV和RIJMEN^[16]于2012年提出，攻击使用分组密码算法中以概率$ \frac{1}{2} $成立的线性逼近，即相关度为零的线性逼近，由此区分分组密码算法与随机置换，进而恢复密钥。文献[17]建立了多重零相关分析模型，其克服了经典零相关线性分析在数据复杂度方面的缺陷。文献[18]建立了卡方多维零相关线性模型，其消除了对零相关数量的限制条件。

函数$ h:{F}_{2}^{m}\to {F}_{2}^{n} $上线性逼近$ \left({\mathit{\boldsymbol{\alpha }}}, {\mathit{\boldsymbol{\beta }}}\right) $的相关度定义为：

$ {C}_{h}({\mathit{\boldsymbol{\alpha }}}, {\mathit{\boldsymbol{\beta }}})=\frac{1}{{2}^{n}}\sum\limits _{{\mathit{\boldsymbol{x}}}\in {F}_{2}^{n}}^{}{(-1)}^{{\mathit{\boldsymbol{\alpha }}}\cdot {\mathit{\boldsymbol{x}}}\oplus {\mathit{\boldsymbol{\beta }}}\cdot h\left({\mathit{\boldsymbol{x}}}\right)} $

其中，$ {\mathit{\boldsymbol{\alpha }}} $为输入掩码，$ {\mathit{\boldsymbol{\beta }}} $为输出掩码，·表示向量内积。当$ {C}_{h}({\mathit{\boldsymbol{\alpha }}}, {\mathit{\boldsymbol{\beta }}})=0 $时，称$ \left({\mathit{\boldsymbol{\alpha }}}, {\mathit{\boldsymbol{\beta }}}\right) $为零相关线性逼近^[17]。

命题1（线性映射的相关度）^[17]对于线性映射$ h\left({\mathit{\boldsymbol{x}}}\right)={\mathit{\boldsymbol{M}}}{\mathit{\boldsymbol{x}}} $，若$ {\mathit{\boldsymbol{\alpha }}}={{\mathit{\boldsymbol{M}}}}^{\mathrm{T}}{\mathit{\boldsymbol{\beta }}} $，则$ {C}_{h}({\mathit{\boldsymbol{\alpha }}}, {\mathit{\boldsymbol{\beta }}})=1 $；否则，$ {C}_{h}({\mathit{\boldsymbol{\alpha }}}, {\mathit{\boldsymbol{\beta }}})=0 $。

零相关区分器是指在输入掩码与输出掩码作用下，目标输入与输出比特的线性相关度为0的一类线性区分器。根据命题1进行自动化搜索，可以得到大量Midori64算法的5轮零相关区分器，按输入掩码权重与输出掩码权重进行分类，零相关区分器的个数统计结果如表 2所示。

取3个输入掩码权重为7且输出掩码权重为1的5轮零相关区分器，然后对输出掩码部分继续扩展1轮，得到6轮零相关区分器。令：

$ {{\mathit{\boldsymbol{\alpha }}}}_{1}={{\mathit{\boldsymbol{a}}}}_{0}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {{\mathit{\boldsymbol{a}}}}_{3}\Vert {{\mathit{\boldsymbol{a}}}}_{4}\Vert {\bf{0}}\Vert {{\mathit{\boldsymbol{a}}}}_{6}\Vert {\bf{0}}\Vert {{\mathit{\boldsymbol{a}}}}_{8}\Vert {{\mathit{\boldsymbol{a}}}}_{9}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {{\mathit{\boldsymbol{a}}}}_{12}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {\bf{0}} $

$ {{\mathit{\boldsymbol{\beta }}}}_{1}=0\Vert {{\mathit{\boldsymbol{d}}}}_{0}\Vert {{\mathit{\boldsymbol{d}}}}_{0}\Vert {{\mathit{\boldsymbol{d}}}}_{0}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {\bf{0}}\Vert 0\Vert {\bf{0}}\Vert {\bf{0}}\Vert 0 $

$ {{\mathit{\boldsymbol{\beta }}}}_{2}={{\mathit{\boldsymbol{d}}}}_{5}\Vert {{\mathit{\boldsymbol{d}}}}_{5}\Vert {\bf{0}}\Vert {{\mathit{\boldsymbol{d}}}}_{5}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {\bf{0}} $

$ {{\mathit{\boldsymbol{\beta }}}}_{3}={{\mathit{\boldsymbol{d}}}}_{15}\Vert {{\mathit{\boldsymbol{d}}}}_{15}\Vert {{\mathit{\boldsymbol{d}}}}_{15}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {\bf{0}}\Vert {\bf{0}} $

其中，$ {{\mathit{\boldsymbol{a}}}}_{0}\mathrm{、}{{\mathit{\boldsymbol{a}}}}_{3}\mathrm{、}{{\mathit{\boldsymbol{a}}}}_{4}\mathrm{、}{{\mathit{\boldsymbol{a}}}}_{6}\mathrm{、}{{\mathit{\boldsymbol{a}}}}_{8}\mathrm{、}{{\mathit{\boldsymbol{a}}}}_{9}\mathrm{、}{{\mathit{\boldsymbol{a}}}}_{12}\mathrm{、}{{\mathit{\boldsymbol{d}}}}_{0}\mathrm{、}{\mathit{\boldsymbol{d}}}{}_{5}\mathrm{、}{{\mathit{\boldsymbol{d}}}}_{15} $均为4 bit向量，0为4 bit零向量。（$ {{\mathit{\boldsymbol{\alpha }}}}_{1}\xrightarrow{6轮} $$ {{\mathit{\boldsymbol{\beta }}}}_{1} $）、（$ {{\mathit{\boldsymbol{\alpha }}}}_{1} \xrightarrow{6轮}$$ {{\mathit{\boldsymbol{\beta }}}}_{2} $）和（$ {{\mathit{\boldsymbol{\alpha }}}}_{1} \xrightarrow{6轮} $$ {{\mathit{\boldsymbol{\beta }}}}_{3} $）都是Midori64算法的6轮零相关区分器。第1个6轮零相关区分器的掩码扩展细节如图 3所示。

3 Midori64的积分区分器 3.1 积分区分器构造

积分攻击是一种选择明文攻击，最先应用于Square分组密码分析，其基本思想是通过分析一系列中间状态的和具有概率为1的性质，得出不能通过检测的密钥都是错误密钥，从而利用淘汰法直接恢复出正确密钥。积分攻击的主要环节是寻找积分区分器，积分区分器可以分为如下2类：

1）一系列中间状态的和遍历所有可能取值，且每个可能取值的出现次数相同，该类积分区分器称为平衡积分区分器。

2）一系列中间状态的异或和为零，该类积分区分器称为零和积分区分器。

当选择特定的输入集合（输入的部分比特固定为常数，其余比特遍历所有可能）时，经过几轮算法加密后，输出的某些比特存在概率为1的分布特性，输出目标值异或和为0时，为零和积分区分器；输出目标值均匀遍历所有可能时，为平衡积分区分器。实际上，平衡积分区分器与零相关区分器之间存在一定的等价关系^[10]，任意的零相关区分器都可以转化成一个平衡积分区分器，本文利用文献[10]中给出的两区分器等价性进行积分区分器构造。

若所有原像集的势都相同，则函数$ h:{F}_{2}^{s}\to {F}_{2}^{t} $是平衡的^[10]，即集合$ {h}^{-1}\left({\mathit{\boldsymbol{y}}}\right)=\{{\mathit{\boldsymbol{x}}}\in {F}_{2}^{s}|h\left({\mathit{\boldsymbol{x}}}\right)={\mathit{\boldsymbol{y}}}\} $的大小与y无关。

命题2^[10]对于函数$ h:{F}_{2}^{r}\times {F}_{2}^{s}\to {F}_{2}^{t}\times {F}_{2}^{u}, h\left({\mathit{\boldsymbol{x}}}, {\mathit{\boldsymbol{y}}}\right)= $ $ \left(\begin{array}{c}{h}_{1}\left({\mathit{\boldsymbol{x}}}, {\mathit{\boldsymbol{y}}}\right)\\ {h}_{2}\left({\mathit{\boldsymbol{x}}}, {\mathit{\boldsymbol{y}}}\right)\end{array}\right) $，定义$ {T}_{{\mathit{\boldsymbol{\lambda }}}}:{{\mathit{\boldsymbol{F}}}}_{2}^{s}\to {F}_{2}^{t}, {T}_{{\mathit{\boldsymbol{\lambda }}}}\left({\mathit{\boldsymbol{y}}}\right)={h}_{1}\left({\mathit{\boldsymbol{\lambda }}}, {\mathit{\boldsymbol{y}}}\right) $。若$ \forall {\mathit{\boldsymbol{a}}}\in $ $ {F}_{2}^{s}, {\mathit{\boldsymbol{b}}}\in {F}_{2}^{t}, {\mathit{\boldsymbol{b}}}\ne 0 $且$ {\mathit{\boldsymbol{a}}} $与$ {\mathit{\boldsymbol{b}}} $独立，则函数$ h $上线性特征$ （{\mathit{\boldsymbol{a}}}\Vert 0, {\mathit{\boldsymbol{b}}}\Vert 0） $的相关度为0等价于$ \forall {\mathit{\boldsymbol{\lambda }}}\in {F}_{2}^{r} $，函数$ {T}_{{\mathit{\boldsymbol{\lambda }}}} $是平衡的。

3.2 Midori64的6轮积分区分器

记集合$ {{\mathit{\boldsymbol{S}}}}_{\mathrm{i}\mathrm{n}}=\{\bf{x}=({{\mathit{\boldsymbol{c}}}}_{0}, {{\mathit{\boldsymbol{b}}}}_{1}, {{\mathit{\boldsymbol{b}}}}_{2}, {{\mathit{\boldsymbol{c}}}}_{3}, {{\mathit{\boldsymbol{c}}}}_{4}, {{\mathit{\boldsymbol{b}}}}_{5}, {{\mathit{\boldsymbol{c}}}}_{6}, {{\mathit{\boldsymbol{b}}}}_{7}, {{\mathit{\boldsymbol{c}}}}_{8}, {{\mathit{\boldsymbol{c}}}}_{9}, $ $ {{\mathit{\boldsymbol{b}}}}_{10}, {{\mathit{\boldsymbol{b}}}}_{11}, {{\mathit{\boldsymbol{c}}}}_{12}, {{\mathit{\boldsymbol{b}}}}_{13}, {{\mathit{\boldsymbol{b}}}}_{14}, {{\mathit{\boldsymbol{b}}}}_{15}\left)\right\} $，其中，$ {{\mathit{\boldsymbol{c}}}}_{0}\Vert {{\mathit{\boldsymbol{c}}}}_{3}\Vert {{\mathit{\boldsymbol{c}}}}_{4}\Vert {{\mathit{\boldsymbol{c}}}}_{6}\Vert {{\mathit{\boldsymbol{c}}}}_{8}\Vert {{\mathit{\boldsymbol{c}}}}_{9}\Vert $ $ {{\mathit{\boldsymbol{c}}}}_{12} $取常数，$ {{\mathit{\boldsymbol{b}}}}_{1}\Vert {{\mathit{\boldsymbol{b}}}}_{2}\Vert {{\mathit{\boldsymbol{b}}}}_{5}\Vert {{\mathit{\boldsymbol{b}}}}_{7}\Vert {{\mathit{\boldsymbol{b}}}}_{10}\Vert {{\mathit{\boldsymbol{b}}}}_{11}\Vert {{\mathit{\boldsymbol{b}}}}_{13}\Vert {{\mathit{\boldsymbol{b}}}}_{14}\Vert {{\mathit{\boldsymbol{b}}}}_{15} $遍历所有可能取值。$ {{\mathit{\boldsymbol{S}}}}_{\mathrm{i}\mathrm{n}} $中存在$ {2}^{36} $个元素，存在$ {2}^{28} $个此类集合。经过6轮加密后，得到对应的输出集合为$ {{\mathit{\boldsymbol{S}}}}_{\mathrm{o}\mathrm{u}\mathrm{t}}=\{{\mathit{\boldsymbol{y}}}=({y}_{0}, {y}_{1}, \cdots , {y}_{15}\left)\right|{\mathit{\boldsymbol{y}}}={E}_{\mathrm{K}\mathrm{e}\mathrm{y}}^{6}\left({\mathit{\boldsymbol{x}}}\right), {\mathit{\boldsymbol{x}}}\in {{\mathit{\boldsymbol{S}}}}_{\mathrm{i}\mathrm{n}}\} $。

令$ {{\mathit{\boldsymbol{t}}}}_{0}={{\mathit{\boldsymbol{y}}}}_{1}\oplus {{\mathit{\boldsymbol{y}}}}_{2}\oplus {{\mathit{\boldsymbol{y}}}}_{3} $、$ {{\mathit{\boldsymbol{t}}}}_{1}={{\mathit{\boldsymbol{y}}}}_{0}\oplus {{\mathit{\boldsymbol{y}}}}_{1}\oplus {{\mathit{\boldsymbol{y}}}}_{3} $和$ {{\mathit{\boldsymbol{t}}}}_{2}={{\mathit{\boldsymbol{y}}}}_{0}\oplus {{\mathit{\boldsymbol{y}}}}_{1}\oplus {{\mathit{\boldsymbol{y}}}}_{2} $，则加密函数被分割为：

$ {E}_{\mathrm{K}\mathrm{e}\mathrm{y}}^{6}:{F}_{2}^{r}\times {F}_{2}^{s}\to {F}_{2}^{t}\times {F}_{2}^{u}, {E}_{\mathrm{K}\mathrm{e}\mathrm{y}}^{6}\left({\mathit{\boldsymbol{x}}}, {\mathit{\boldsymbol{y}}}\right)=\left(\begin{array}{c}{h}_{1}\left({\mathit{\boldsymbol{x}}}, {\mathit{\boldsymbol{y}}}\right)\\ {h}_{2}\left({\mathit{\boldsymbol{x}}}, {\mathit{\boldsymbol{y}}}\right)\end{array}\right) $

定理1  当输入为$ {{\mathit{\boldsymbol{S}}}}_{\mathrm{i}\mathrm{n}} $时，加密6轮后，$ {{\mathit{\boldsymbol{y}}}}_{1} $是零和的。

证明  加密函数$ {E}_{\mathrm{K}\mathrm{e}\mathrm{y}}^{6} $上线性特征$ \left({{\mathit{\boldsymbol{\alpha }}}}_{1}, {{\mathit{\boldsymbol{\beta }}}}_{1}\right) $、$ \left({{\mathit{\boldsymbol{\alpha }}}}_{1}, {{\mathit{\boldsymbol{\beta }}}}_{2}\right) $和$ \left({{\mathit{\boldsymbol{\alpha }}}}_{1}, {{\mathit{\boldsymbol{\beta }}}}_{3}\right) $的相关度都是0，由命题2可知$ {T}_{\lambda }:{F}_{2}^{s}\to {F}_{2}^{t}, {T}_{\lambda }\left({{\mathit{\boldsymbol{x}}}}_{s}\right)={h}_{1}\left({\mathit{\boldsymbol{\lambda }}}, {{\mathit{\boldsymbol{x}}}}_{s}\right) $是平衡的，得到$ {t}_{0} $、$ {t}_{1} $和$ {t}_{2} $每个取值的原像个数相同，于是$ \sum {t}_{0}=0 $，$ \sum {t}_{1}=0 $，$ \sum {t}_{2}=0 $，从而$ \sum {y}_{1}=\sum {t}_{0}\oplus \sum {t}_{1}\oplus \sum {t}_{2}=0 $，证毕。

6轮零和积分区分器如图 4所示。

3.3 Midori64的7轮积分区分器

在6轮积分区分器的前面解密1轮可以得到7轮积分区分器。对6轮积分区分器的输入$ {{\mathit{\boldsymbol{S}}}}_{\mathrm{i}\mathrm{n}} $中各单元进行逆向轮密钥异或操作，其中，第0个、第3个、第4个、第6个、第8个、第9个和第12个单元是固定常数，其余单元仍然遍历所有可能取值。因此，在构造7轮积分区分器的过程中，可忽略此逆向密钥加操作。记7轮积分区分器的明文集合为：

$ {{\mathit{\boldsymbol{S}}}}_{\mathrm{i}\mathrm{n}}^{\mathrm{*}}=\left\{{\mathit{\boldsymbol{y}}}=\mathrm{S}{\mathrm{B}}^{-1}\left(\mathrm{S}{\mathrm{C}}^{-1}\left(\mathrm{M}{\mathrm{C}}^{-1}\left({\mathit{\boldsymbol{x}}}\right)\right)\right)\left|{\mathit{\boldsymbol{x}}}\in \right.{{\mathit{\boldsymbol{S}}}}_{\mathrm{i}\mathrm{n}}\right\} $

其中，列混淆、置换和S盒都是可逆变换，复合变换$ {\mathit{\boldsymbol{y}}}=\mathrm{S}{\mathrm{B}}^{-1}\left(\mathrm{S}{\mathrm{C}}^{-1}\left(\mathrm{M}{\mathrm{C}}^{-1}\left({\mathit{\boldsymbol{x}}}\right)\right)\right) $是双射。对由$ {2}^{36} $个明文构成的$ {{\mathit{\boldsymbol{S}}}}_{\mathrm{i}\mathrm{n}}^{\mathrm{*}} $进行1轮加密，其结果满足6轮零和积分区分器的输入条件，因此，当输入为$ {{\mathit{\boldsymbol{S}}}}_{\mathrm{i}\mathrm{n}}^{\mathrm{*}} $时，加密7轮后$ {{\mathit{\boldsymbol{y}}}}_{1} $是零和的。存在一系列7轮积分路线，令$ {\widehat{{\mathit{\boldsymbol{S}}}}}_{\mathrm{i}\mathrm{n}}=\{{\mathit{\boldsymbol{x}}}=({{\mathit{\boldsymbol{c}}}}_{0}, {{\mathit{\boldsymbol{b}}}}_{1}, {{\mathit{\boldsymbol{b}}}}_{2}, {{\mathit{\boldsymbol{c}}}}_{3}, {{\mathit{\boldsymbol{c}}}}_{4}, {{\mathit{\boldsymbol{b}}}}_{5}, {{\mathit{\boldsymbol{c}}}}_{6}, {{\mathit{\boldsymbol{b}}}}_{7}, {{\mathit{\boldsymbol{b}}}}_{8}, {{\mathit{\boldsymbol{b}}}}_{9}, {{\mathit{\boldsymbol{c}}}}_{10}, {{\mathit{\boldsymbol{c}}}}_{11}, {{\mathit{\boldsymbol{c}}}}_{12}, {{\mathit{\boldsymbol{b}}}}_{13}, {{\mathit{\boldsymbol{c}}}}_{14}, {{\mathit{\boldsymbol{c}}}}_{15}\left)\right\}\mathrm{。} $$ {\widehat{{\mathit{\boldsymbol{S}}}}}_{\mathrm{i}\mathrm{n}}^{\mathrm{*}} $的定义与$ {{\mathit{\boldsymbol{S}}}}_{\mathrm{i}\mathrm{n}}^{\mathrm{*}} $类似，当输入为$ {\widehat{{\mathit{\boldsymbol{S}}}}}_{\mathrm{i}\mathrm{n}}^{\mathrm{*}} $时，加密7轮后$ {{\mathit{\boldsymbol{y}}}}_{13} $是零和的。

4 Midori64的积分攻击 4.1 Midori64的10轮积分攻击

在7轮积分区分器的后面加密3轮可以得到10轮积分区分器，如图 5所示。

为降低密钥的猜测量，本文利用等价密钥技术^[19]，该技术结合Midori64算法，将列混淆MC与密钥加KA进行位置交换，其中，线性等价的轮密钥加记为$ \mathrm{K}{\mathrm{A}}^{\mathrm{*}} $，从而在攻击中减少密钥的猜测量。具体地，将图 5中$ {{\mathit{\boldsymbol{S}}}}_{\mathrm{o}\mathrm{u}\mathrm{t}}\left[1\right] $标注为$ {\mathit{\boldsymbol{Z}}}\left[1\right] $，以$ \mathrm{*} $标注每个从$ {{\mathit{\boldsymbol{S}}}}_{\mathrm{o}\mathrm{u}\mathrm{t}}^{\mathrm{*}} $计算至$ {\mathit{\boldsymbol{Z}}}\left[1\right] $时需要明确值的单元。设轮密钥经过线性变换后的等价轮密钥为$ {K}^{i} $，即$ {K}^{i}=\mathrm{M}\mathrm{C}\left(\mathrm{R}{\mathrm{K}}^{i}\right) $。

利用部分和技术^[17]，Midori64算法的128 bit密钥恢复过程具体如下：

步骤1  选择一个明文集合$ {{\mathit{\boldsymbol{S}}}}_{\mathrm{i}\mathrm{n}}^{\mathrm{*}} $，收集相应的密文得到$ {{\mathit{\boldsymbol{S}}}}_{\mathrm{o}\mathrm{u}\mathrm{t}}^{\mathrm{*}} $。

步骤2  猜测第10轮等价轮密钥$ {{\mathit{\boldsymbol{K}}}}_{0}^{10}\mathrm{、}{{\mathit{\boldsymbol{K}}}}_{1}^{10}\mathrm{、}{{\mathit{\boldsymbol{K}}}}_{5}^{10}\mathrm{、} $ $ {{\mathit{\boldsymbol{K}}}}_{7}^{10}\mathrm{、}{{\mathit{\boldsymbol{K}}}}_{8}^{10}\mathrm{、}{{\mathit{\boldsymbol{K}}}}_{9}^{10}\mathrm{、}{{\mathit{\boldsymbol{K}}}}_{11}^{10}\mathrm{、}{{\mathit{\boldsymbol{K}}}}_{12}^{10}\mathrm{、}{{\mathit{\boldsymbol{K}}}}_{15}^{10} $，共计36 bit。对$ {{\mathit{\boldsymbol{S}}}}_{\mathrm{o}\mathrm{u}\mathrm{t}}^{\mathrm{*}} $进行解密1轮及列混淆MC逆运算，得到$ {\mathit{\boldsymbol{X}}}\left[2\right]\mathrm{、} $ $ {\mathit{\boldsymbol{X}}}\left[5\right]\mathrm{、}{\mathit{\boldsymbol{X}}}\left[11\right] $对应的值。定义计数器向量$ {{\mathit{\boldsymbol{N}}}}_{0}{\mathit{\boldsymbol{X}}}\left[2\right]\Vert $ $ {\mathit{\boldsymbol{X}}}\left[5\right]\Vert {\mathit{\boldsymbol{X}}}\left[11\right] $用于存储$ {\mathit{\boldsymbol{X}}}\left[2\right]\Vert {\mathit{\boldsymbol{X}}}\left[5\right]\Vert {\mathit{\boldsymbol{X}}}\left[11\right] $的个数，共有$ {2}^{12} $个计数器。从异或和的角度考虑，仅需考查奇偶性，则计数器只使用1 bit来标识奇偶性即可。

步骤3  猜测第9轮等价轮密钥$ {{\mathit{\boldsymbol{K}}}}_{2}^{9}\mathrm{、}{{\mathit{\boldsymbol{K}}}}_{5}^{9}\mathrm{、}{{\mathit{\boldsymbol{K}}}}_{11}^{9} $，共计12 bit。对$ {\mathit{\boldsymbol{X}}}\left[2\right]\mathrm{、}{\mathit{\boldsymbol{X}}}\left[5\right]\mathrm{、}{\mathit{\boldsymbol{X}}}\left[11\right] $解密1轮得到$ {\mathit{\boldsymbol{Y}}}\left[2\right] $。定义计数器向量$ {{\mathit{\boldsymbol{N}}}}_{1}\left[{\mathit{\boldsymbol{Y}}}\left[2\right]\right] $用于存储$ {\mathit{\boldsymbol{Y}}}\left[2\right] $的奇偶性，共有$ {2}^{4} $个计数器。

步骤4  由$ {{\mathit{\boldsymbol{K}}}}_{7}^{8}=\mathrm{M}\mathrm{C}\left(\mathrm{M}\mathrm{C}\left({{\mathit{\boldsymbol{K}}}}_{7}^{10}\right)\oplus {q}_{7}\oplus {q}_{9}\right) $可知$ {{\mathit{\boldsymbol{K}}}}_{7}^{8} $不需要猜测，可计算得到$ {\mathit{\boldsymbol{Z}}}\left[1\right] $。计算$ \sum {\mathit{\boldsymbol{Z}}}\left[1\right] $，若为0，则相应的猜测密钥作为真实密钥的候选值；否则，淘汰该猜测密钥。

步骤5  针对上述48 bit密钥，选取m组$ {{\mathit{\boldsymbol{S}}}}_{\mathrm{i}\mathrm{n}}^{\mathrm{*}} $，重复步骤1~步骤4，可平均剩余$ {2}^{128-4m} $个正确候选密钥。

步骤6  重复上述步骤，第9轮猜测12 bit密钥，第10轮猜测20 bit密钥，选择n组$ {\widehat{{\mathit{\boldsymbol{S}}}}}_{\mathrm{i}\mathrm{n}} $，重复步骤1~步骤4，可平均剩余$ {2}^{128-4m-4n} $个正确候选密钥。

步骤7  使用2组明密文对进行剩余正确密钥的穷搜猜测。

4.1.1 数据复杂度分析

为了平衡总时间复杂度与数据复杂度，取m=12，n=4。10轮积分攻击的数据复杂度为$ {2}^{36}\times 12+{2}^{36}\times 4={2}^{40} $个64 bit长明密文对。

4.1.2 时间复杂度分析

10轮积分攻击的步骤1复杂度为选择明文的复杂度，计算$ {{\mathit{\boldsymbol{S}}}}_{\mathrm{i}\mathrm{n}}^{\mathrm{*}} $时，需要查$ \mathrm{S}{\mathrm{B}}^{-1} $表共$ {2}^{36} $次，由于10轮算法共查表$ 16\times 10 $次，因此，在忽略其他运算耗时的假设下，相当于$ {2}^{36}/\left(16\times 10\right)\approx {2}^{28.68} $次10轮加密。收集$ {{\mathit{\boldsymbol{S}}}}_{\mathrm{o}\mathrm{u}\mathrm{t}}^{\mathrm{*}} $时进行$ {2}^{36} $次10轮加密。步骤2进行$ 9\times {2}^{36}\times {2}^{36} $次查表，相当于$ 9\times {2}^{36}\times {2}^{36}/\left(16\times 10\right)\approx {2}^{67.85} $次10轮加密。步骤3进行$ 3\times {2}^{36}\times {2}^{12}\times {2}^{12} $次查表，相当于$ 3\times {2}^{36}\times {2}^{12}\times {2}^{12}/\left(16\times 10\right)\approx {2}^{54.26} $次10轮加密。步骤4进行$ {2}^{36}\times {2}^{12}\times {2}^{4} $次查表，相当于$ {2}^{36}\times {2}^{12}\times {2}^{4}/\left(16\times 10\right)\approx $ $ {2}^{44.68} $次10轮加密。步骤5与步骤6的时间复杂度可以忽略。步骤7进行穷搜验证时，需要$ {2}^{65}+3 $次10轮加密。

综上，10轮积分攻击的总时间复杂度为$ {2}^{28.68}+{2}^{36}+{2}^{67.85}+{2}^{54.26}+{2}^{44.68}+{2}^{65}+3\approx {2}^{67.85} $次10轮加密。

4.2 Midori64的11轮积分攻击

利用快速Walsh-Hadamard变换技术^[20-21]对Midori64进行11轮积分攻击，具体步骤如下：

步骤1  选择一个明文集合$ {{\mathit{\boldsymbol{S}}}}_{\mathrm{i}\mathrm{n}}^{\mathrm{*}} $，收集相应的密文得到$ {{\mathit{\boldsymbol{S}}}}_{\mathrm{o}\mathrm{u}\mathrm{t}}^{\mathrm{*}} $。

步骤2  猜测第10轮等价轮密钥$ {{\mathit{\boldsymbol{K}}}}_{0}^{10}\mathrm{、}{{\mathit{\boldsymbol{K}}}}_{1}^{10}\mathrm{、}{{\mathit{\boldsymbol{K}}}}_{5}^{10}\mathrm{、} $ $ {{\mathit{\boldsymbol{K}}}}_{7}^{10}\mathrm{、}{{\mathit{\boldsymbol{K}}}}_{8}^{10}\mathrm{、}{{\mathit{\boldsymbol{K}}}}_{9}^{10}\mathrm{、}{{\mathit{\boldsymbol{K}}}}_{11}^{10}\mathrm{、}{{\mathit{\boldsymbol{K}}}}_{12}^{10}\mathrm{、}{{\mathit{\boldsymbol{K}}}}_{15}^{10} $和第9轮等价轮密钥$ {{\mathit{\boldsymbol{K}}}}_{2}^{9}\mathrm{、}{{\mathit{\boldsymbol{K}}}}_{5}^{9}\mathrm{、}{{\mathit{\boldsymbol{K}}}}_{11}^{9} $，合记为$ {{\mathit{\boldsymbol{K}}}}_{1} $，共计48 bit。根据Midori64密钥编排算法可推导出$ {{\mathit{\boldsymbol{K}}}}_{7}^{8}=\mathrm{M}\mathrm{C}\left(\mathrm{M}\mathrm{C}\left({{\mathit{\boldsymbol{K}}}}_{7}^{10}\right)\oplus {q}_{7}\oplus {q}_{9}\right) $，$ {{\mathit{\boldsymbol{K}}}}_{2}^{11}=\mathrm{M}\mathrm{C}\left(\mathrm{M}\mathrm{C}\left({{\mathit{\boldsymbol{K}}}}_{2}^{9}\right)\oplus {q}_{8}\oplus {q}_{10}\right) $，$ {{\mathit{\boldsymbol{K}}}}_{5}^{11}=\mathrm{M}\mathrm{C}\left(\mathrm{M}\mathrm{C}\left({{\mathit{\boldsymbol{K}}}}_{5}^{9}\right)\oplus {q}_{8}\oplus {q}_{10}\right) $，$ {{\mathit{\boldsymbol{K}}}}_{11}^{11}=\mathrm{M}\mathrm{C}\left(\mathrm{M}\mathrm{C}\left({{\mathit{\boldsymbol{K}}}}_{11}^{9}\right)\oplus {q}_{8}\oplus {q}_{10}\right) $。

步骤3  $ \sum {\mathit{\boldsymbol{Z}}}{\left[1\right]}^{\left(i\right)}=\sum\limits _{{{\mathit{\boldsymbol{C}}}}_{1}}{F}_{{{\mathit{\boldsymbol{K}}}}_{1}}^{\left(i\right)}\left({f}_{{{\mathit{\boldsymbol{C}}}}_{1}, {{\mathit{\boldsymbol{K}}}}_{2}}({{\mathit{\boldsymbol{C}}}}_{2}\oplus {{\mathit{\boldsymbol{K}}}}_{3})\right) $，其中，$ i=\mathrm{1, 2}, \mathrm{3, 4} $，$ {{\mathit{\boldsymbol{C}}}}_{1}={{\mathit{\boldsymbol{S}}}}_{\mathrm{o}\mathrm{u}\mathrm{t}}^{\mathrm{*}}[\mathrm{2, 5}, 11] $，记$ \overline{{{\mathit{\boldsymbol{C}}}}_{1}}={F}_{2}^{12} $，$ {{\mathit{\boldsymbol{C}}}}_{2} $为第11轮输出的其余密文，记$ \overline{{{\mathit{\boldsymbol{C}}}}_{2}}={F}_{2}^{52} $，$ {{\mathit{\boldsymbol{K}}}}_{2}={{\mathit{\boldsymbol{K}}}}_{2}^{11}\Vert {{\mathit{\boldsymbol{K}}}}_{5}^{11}\Vert {{\mathit{\boldsymbol{K}}}}_{11}^{11} $，$ {{\mathit{\boldsymbol{K}}}}_{3} $为第11轮使用的其余等价轮密钥，$ {f}_{{{\mathit{\boldsymbol{C}}}}_{1}, {{\mathit{\boldsymbol{K}}}}_{2}} $为关于$ \overline{{{\mathit{\boldsymbol{C}}}}_{2}} $的第11轮解密函数，$ {F}_{{{\mathit{\boldsymbol{K}}}}_{1}}^{\left(i\right)} $为获得$ {\mathit{\boldsymbol{Z}}}{\left[1\right]}^{\left(i\right)} $的解密函数。遍历$ {{\mathit{\boldsymbol{C}}}}_{1} $，利用快速Walsh-Hadamard变换技术计算$ \sum {F}_{{{\mathit{\boldsymbol{K}}}}_{1}}^{\left(i\right)}\left({f}_{{{\mathit{\boldsymbol{C}}}}_{1}, {{\mathit{\boldsymbol{K}}}}_{2}}\left(\overline{{{\mathit{\boldsymbol{C}}}}_{2}}\right)\right) $，然后在$ {F}_{2} $上关于$ {{\mathit{\boldsymbol{C}}}}_{1} $求累加和，若和不为0，则淘汰密钥。

步骤4  选取m组$ {{\mathit{\boldsymbol{S}}}}_{\mathrm{i}\mathrm{n}}^{\mathrm{*}} $，重复步骤1~步骤3。

步骤5  使用猜测等价轮密钥加密$ {{\mathit{\boldsymbol{S}}}}_{\mathrm{i}\mathrm{n}}^{\mathrm{*}} $中的明文，若其与$ {{\mathit{\boldsymbol{S}}}}_{\mathrm{o}\mathrm{u}\mathrm{t}}^{\mathrm{*}} $中对应处密文相同，则相应的猜测等价轮密钥作为真实等价轮密钥的候选值；否则，淘汰该猜测等价轮密钥。

步骤6  由上述恢复的等价轮密钥计算密钥。

4.2.1 数据复杂度分析

为了平衡总时间复杂度与数据复杂度，取m=17，11轮积分攻击的数据复杂度为$ {2}^{36}\times 17\approx {2}^{40.09} $个64 bit长明密文对。

4.2.2 时间复杂度分析

11轮积分攻击的步骤1复杂度为选择明文的复杂度，平均重复17次，时间复杂度为$ 17\times \left({2}^{28.54}+{2}^{36}\right)\approx {2}^{40.09} $次11轮加密。步骤3进行简单运算，相当于$ 4\times {2}^{48}\times \left({2}^{12}\times \left(17\times 2\times 52\times {2}^{52}+52\times {2}^{52}\right)+{2}^{12}\right) $ $ \approx {2}^{117.37} $次11轮加密。步骤5进行穷搜验证时，需要$ \left({2}^{32}+1\right)\times {2}^{28}\approx {2}^{60} $次11轮加密。

综上，11轮积分攻击的时间复杂度为$ {2}^{40.09}+{2}^{117.37}+{2}^{60}\approx {2}^{117.37} $次11轮加密。

4.3 Midori64的积分攻击对比

将本文积分攻击与已有Midori64算法的积分攻击进行性能对比，结果如表 3所示，从表 3可以看出，本文积分攻击的轮数相比文献[7]积分攻击提高2轮。与文献[15]相比，本文找到的路线输入集合大小为$ {2}^{36} $，而文献[15]中算法分析需要的数据量为$ {2}^{63} $，为整个明文空间的一半。与已有Midori64算法其他攻击相比，在不考虑弱密钥情况下，本文积分攻击的数据复杂度和时间复杂度具有较大优势。

5 结束语

本文构建6轮零相关区分器，利用零相关区分器与平衡积分区分器之间的等价关系，将6轮零相关区分器转换为6轮平衡积分区分器，然后将3个6轮平衡积分区分器合成为一个性能优良的6轮零和积分区分器，向前扩展1轮得到一个7轮零和积分区分器。将该7轮零和积分区分器向后扩展3轮，对10轮Midori64算法实施密钥恢复攻击，攻击的数据复杂度约为$ {2}^{40} $个明密文对，时间复杂度约为$ {2}^{67.85} $次10轮加密运算。将该7轮零和积分区分器向后扩展4轮，对11轮Midori64算法实施密钥恢复攻击，攻击的数据复杂度约为$ {2}^{40.09} $个明密文对，时间复杂度约为$ {2}^{117.37} $次11轮加密运算。10轮积分攻击中采用部分和技术，11轮积分攻击中采用快速Walsh-Hadamard变换技术。下一步将利用基于MILP技术的分离特性搜索方法攻击Midori64算法。