近20年来，伴随着物联网技术的飞速发展，资源受限设备如低成本的RFID（radio frequency identification）标签、无线传感器、嵌入式系统等的应用越来越广泛. 为资源受限设备研制低成本、低能耗的轻量级密码算法是一项具有挑战性的工作，吸引了许多密码学者的关注. 例如，Leander等人^[1]设计了DES（data encryption standard）加密算法的一个轻量级变体DESL；Poschmann等人^[2]设计了一个比DESL更强的DES的变体DESXL；Bogdanov等人^[3]提出了著名的轻量级密码算法PRESENT；Banik等人^[4]设计了比PRESENT更安全、高效的轻量级密码算法GIFT.

MIBS是一个适用于资源受限环境的轻量级分组密码算法，由Izadi等人^[5]在CANS 2009会议上提出. 针对MIBS分组密码算法的现有分析结果包括差分分析^[6]、线性分析^[6]、积分分析、不可能差分分析^[7]等. 目前对于MIBS-64最好的分析结果是14轮的差分分析，成功概率为50.15%；对MIBS-80最好的分析结果是18轮的线性分析，成功概率为72.14%.

积分分析是由Knudsen等人^[8]在FSE 2002上提出来的，由于它的思想原型首先被应用于分组密码Square^[9]，因此也被称为Square攻击. 积分分析是当前评估分组密码算法安全性的基础分析方法之一，已经在许多分组密码算法上得到了较好的攻击结果，例如AES^[10], PRESENT^[11]等. 可分性是积分分析的推广，在EUROCRYPT 2015上被Todo^[12]提出. Todo结合密码算法非线性部件的代数次数，优化了积分性质，使得积分特征能够用一种更精确的方式推导. 一个显著的应用是第一次在理论上对全轮的MISTY1进行了积分攻击^[13]. 在ASIACRYPT 2016上，Xiang等人^[14]将基于混合整数线性规划（mixed integer linear programming, MILP）建模的方法引入基于比特的可分性，进一步提高了积分区分器可自动化搜索的密码算法的规模. 2017年，Todo等人^[15]对上述MILP模型进行了补充，并将其应用于多个流密码算法的立方攻击，得到了多个流密码当时最好的密钥恢复攻击. 近几年，对分组密码算法的积分区分器搜索的改进主要围绕改进非线性层^[16-19]和线性层^[19-24]的模型进行.

目前，对MIBS算法的积分分析已经存在一些结论. 2013年，于晓丽等人^[25]基于一个5轮的积分区分器，利用高阶积分技术将该区分器向前扩展3轮，分别对MIBS-64和MIBS-80进行了8, 9, 10轮的积分攻击. 2014年，潘志舒等人^[26]构造了MIBS的5轮积分区分器，利用Feistel结构的等价结构以及MIBS密钥编排算法中主密钥和轮密钥的关系，给出10轮MIBS算法的积分攻击. 2016年，伊文坛等人^[27]利用零相关线性逼近和积分区分器之间的联系，推导出MIBS的8轮积分区分器，进而对11轮的MIBS-80进行了攻击. 2021年，李艳俊等人^[28]基于5轮的积分区分器，向前、向后各扩展3轮，给出了一个11轮MIBS-64的积分攻击.

部分和（partial sum technique）技术是Ferguson 等人^[10]在分析Rijndael时提出的一种降低攻击复杂度的方法，是改进积分攻击的有效方法. 该方法主要利用积分攻击需要对中间状态进行求和的特点，通过压缩密钥恢复过程中的数据量来有效减少计算时间，例如，将对6轮Rijndael的密钥恢复时间复杂度从${2^{72}}$降低为${2^{49}}$^[10].

本文研究MIBS-64和MIBS-80的积分分析，主要贡献有4个方面：

1） 针对密钥编排算法，利用密钥搭桥技术，得到了轮密钥之间的一些相关性质；

2） 构造了MIBS的8轮和9轮积分区分器；

3） 对于MIBS-64，基于8轮的积分区分器，在区分器末尾增加4轮，给出了12轮的密钥恢复攻击；

4） 对于MIBS-80，基于9轮积分区分器，在末尾增加5轮，给出了14轮的密钥恢复攻击.

3）和4）这2个攻击是目前对MIBS-64和MIBS-80已知的最好的积分攻击，与已有积分攻击结果的对比如表1所示.

表  1  对MIBS的积分攻击结果

Table  1.  The Integral Attack Results on MIBS

算法	轮数	数 据 复杂度	时 间 复杂度	参考来源
MIBS-64	10	${{\text{2}}^{{\text{61}}{\text{.6}}}}$	${{\text{2}}^{{\text{40}}}}$	文献[25]
	10	${2^{28}}$	${2^{52.7}}$	文献[26]
	11	${2^{58}}$	${2^{59.75}}$	文献[28]
	12	${{\text{2}}^{{\text{60}}}}$	${{\text{2}}^{{\text{63}}{\text{.42}}}}$	本文第3节
MIBS-80	10	${{\text{2}}^{{\text{61}}{\text{.6}}}}$	${{\text{2}}^{{\text{40}}}}$	文献[25]
	10	${2^{28.2}}$	${2^{53.2}}$	文献[26]
	11	${{\text{2}}^{{\text{60}}}}$	${{\text{2}}^{{\text{59}}{\text{.8}}}}$	文献[27]
	14	${{\text{2}}^{{\text{63}}}}$	${{\text{2}}^{{\text{66}}}}$	本文第4节

下载: 导出CSV 

| 显示表格

1.   预备知识

1.1   符号说明

${C_{[i:j]}}$: 密文的第$j$比特到第$i$比特；

${X_{t,[i:j]}}$: 第$t$轮中间状态的第$j$比特到第$i$比特；

$X_t^i$: 第$t$轮中间状态的第$i$个半字节；

$s{k_{t,[i:j]}}$: 第$t$轮密钥的第$j$比特到第$i$比特；

$sk_t^i$: 第$t$轮密钥的第$i$个半字节；

${\boldsymbol{stat}}{{\boldsymbol{e}}_{[i:j]}}$: 中间状态的第$j$比特至第$i$比特；

$S/{S_t}$: S盒函数/第$t$个S盒函数；

$a$/$c$: 一个活跃比特/常数比特；

$\mathcal{A}$/$\mathcal{C}$: 一个活跃半字节/常数半字节；

$\mathcal{B}$/$\mathcal{U}$: 一个平衡半字节/未知半字节；

$> > >$: 右循环移位操作；

$||$: 字符串的连接操作；

$\circ$ 函数的复合符号.

1.2   MIBS加密算法简介

分组密码MIBS整体采用Feistel结构，轮函数使用SP结构，其分组长度64 b，MIBS支持64 b和80 b这2种密钥长度，分别记为MIBS-64和MIBS-80，迭代轮数为32轮. MIBS中所有的运算都是基于半字节的.

设MIBS的轮函数为$F$，第$i$轮的轮密钥为${K_i}$，输入为$({X_i},{X_{i - 1}})$，那么输出为$({X_{i + 1}},{X_i})$，其中${X_{i + 1}} = F({X_i}, {K_i}) \oplus {X_{i - 1}}$. 轮函数$F$由异或子密钥层$AK$、S盒层（$4 \times 4$的S盒）和线性变换$P$组成，记为$F = P \circ S \circ AK$，具体如图1所示.

图  1  MIBS的轮函数

Figure  1.  Round function of MIBS

下载: 全尺寸图片 幻灯片

设线性变换$P:{(\mathbb{F}_2^4)^8} \to {(\mathbb{F}_2^4)^8}$的输入为$y = ({y_7},$

${y_6},{y_5},{y_4},{y_3},{y_2},{y_1},{y_0})$，输出为$y' = ({y'_7},{y'_6},{y'_5},{y'_4},{y'_3},$

${y'_2},{y'_1},{y'_0})$，那么

${y'_7} = {y_0} \oplus {y_2} \oplus {y_3} \oplus {y_5} \oplus {y_6} \oplus {y_7}$ ,

${y'_6} = {y_0} \oplus {y_1} \oplus {y_2} \oplus {y_5} \oplus {y_6}$ ,

${y'_5} = {y_0} \oplus {y_1} \oplus {y_3} \oplus {y_4} \oplus {y_5}$ ,

${y'_4} = {y_0} \oplus {y_2} \oplus {y_3} \oplus {y_4} \oplus {y_7}$,

${y'_3} = {y_1} \oplus {y_2} \oplus {y_3} \oplus {y_6} \oplus {y_7}$,

${y'_2} = {y_0} \oplus {y_1} \oplus {y_2} \oplus {y_4} \oplus {y_5} \oplus {y_7}$,

${y'_1} = {y_1} \oplus {y_2} \oplus {y_3} \oplus {y_4} \oplus {y_5} \oplus {y_6}$,

${y'_0} = {y_0} \oplus {y_1} \oplus {y_3} \oplus {y_4} \oplus {y_6} \oplus {y_7}$ .

1.3   MIBS密钥编排算法简介

MIBS的密钥编排采用了与PRESENT的密钥编排相同的设计原则.

1）MIBS-64的密钥编排算法

设${\boldsymbol{M}} {{\boldsymbol{K}}_{64}}$是长度为64 b的主密钥，记为${\boldsymbol{M}} {{\boldsymbol{K}}_{64}} = ({k_{63}}, {k_{62}}, … , {k_0})$. 设密钥编排算法第$i$轮的中间状态为${\boldsymbol{state}^i}$. 由主密钥生成长度为32 b的轮密钥${{{K}}_i}$（$1 \leqslant i \leqslant 32$）的过程为：

${\boldsymbol{state}^0} = {\boldsymbol{M}} {{\boldsymbol{K}}_{64}}$；

${\boldsymbol{state}^i} \leftarrow {\boldsymbol{state}^i} > > > 15$；

${\boldsymbol{state}^i} \leftarrow S(\boldsymbol{state}_{[63:60]}^i)||\boldsymbol{state}_{[59:0]}^i$；

${\boldsymbol{state}^i} \leftarrow {\boldsymbol{state}}_{[63:16]}^i||{\boldsymbol{state}}_{[15:11]}^i \oplus RC||{\boldsymbol{state}}_{[10:0]}^i$；

${K_i} = \boldsymbol{state}_{[63:32]}^i$.

其中$RC$表示轮计数，第$i$轮状态${\boldsymbol{state}^i}$的左32 b作为第$i$轮的轮密钥.

2）MIBS-80的密钥编排算法

设${{\boldsymbol{MK}}_{80}}$是长度为80 b的主密钥，记为${\boldsymbol{M}} {{\boldsymbol{K}}_{80}} = ({k_{80}}, {k_{79}}, … ,{k_0})$. 设密钥编排算法第$i$轮的中间状态为${\boldsymbol{state}^i}$. 由主密钥生成长度为32 b的轮密钥${{{K}}_i}$（$1 \leqslant i \leqslant 32$）的过程为：

${\boldsymbol{state}^0} \leftarrow {\boldsymbol{M}} {{\boldsymbol{K}}_{80}}$；

${\boldsymbol{state}^i} \leftarrow {\boldsymbol{state}^i} > > > 19$；

${\boldsymbol{state}^i} \leftarrow S({\boldsymbol{state}}_{[79:76]}^i)||S({\boldsymbol{state}}_{[75:72]}^i)||{\boldsymbol{state}}_{[71:0]}^i$；

${\boldsymbol{state}^i} \leftarrow {\boldsymbol{state}}_{[79:19]}^i||{\boldsymbol{state}}_{[18:14]}^i \oplus RC||{\boldsymbol{state}}_{[13:0]}^i$；

${{{K}}_i} \leftarrow {\boldsymbol{state}}_{[79:48]}^i$.

其中第$i$轮状态${\boldsymbol{state}^i}$的左32 b作为第$i$轮的轮密钥.

1.4   密钥搭桥技术

密钥搭桥技术最早是在文献[29]中针对AES-192提出的. 该技术的主要作用是根据密钥编排算法，推导出某些轮密钥之间存在的依赖关系，即：从某些轮密钥字节中计算出其他的轮密钥字节，即使这些字节距离很多的扩散步骤. 在FSE 2016上，Lin等人^[30]提出了一个高效的比特迭代型密钥搭桥自动搜索算法，这个算法可以改进几乎所有对分组密码攻击的复杂度.

比特迭代型密钥搭桥自动搜索算法的输入为一个表示密钥编排算法的方程系统和一个想要找到其中变量关系的密钥变量集合${\mathcal{K}_0}$，输出是密钥变量集合${\mathcal{K}_0}$中存在的密钥桥，具体过程可以划分为2个阶段：

1）知识传播阶段，主要利用Gauss-Jordan消元法处理方程系统的系数矩阵；

2）关系导出阶段，根据1）处理之后矩阵的秩，导出密钥间的线性关系，即密钥桥.

2.   MIBS的密钥编排性质和积分区分器

2.1   MIBS密钥编排的相关性质

针对MIBS-64和MIBS-80的密钥编排算法，利用文献[30]的密钥搭桥技术搜索轮密钥之间可能存在的相关关系，即密钥桥. 算法1描述了这一过程. 设$\mathcal{K}$表示MIBS密钥编排算法的所有中间密钥变量的集合，${{\mathcal{K}}_0}$表示MIBS-64第9~12轮的部分轮密钥集合和MIBS-80第10~14轮的部分轮密钥集合，${{\mathcal{K}}_1}$表示${{\mathcal{K}}_0}$可以扩张到的集合，$\mathcal{S}$表示S盒的输入输出比特变量集合，${{\boldsymbol{M}}_{{\text{key}}}}$表示由密钥编排算法生成的密钥方程系统$E$的系数矩阵. 矩阵中变量的顺序为$({\mathcal{K}} - \mathcal{S} - {{\mathcal{K}}_1}, \mathcal{S},{{\mathcal{K}}_1},c)$，其中${\mathcal{K }}- \mathcal{S} - {{\mathcal{K}}_1}$表示${\mathcal{S}}$和${{\mathcal{K}}_1}$在${\mathcal{K }}$中的补集，$c$表示常数的列. $G({{\boldsymbol{M}}_{{\text{key}}}})$表示利用Gauss-Jordan消元法将${{\boldsymbol{M}}_{{\text{key}}}}$变为对角矩阵；${G_n}({{\boldsymbol{M}}_{{\text{key}}}})$表示利用Gauss-Jordan消元法将${{\boldsymbol{M}}_{{\text{key}}}}$的前$n$列变为对角矩阵. 算法1的目标是找到${{\mathcal{K}}_0}$间潜在的关系式.

算法1. MIBS轮密钥关系搜索算法.

输入：轮数$r$、种子密钥$K$、待测试密钥集${{\mathcal{K}}_0}$；

输出：密钥桥集合$R$.

① Generate_key_equation（$r,$$K,$$sk$）：/*生成种子密 钥K与轮密钥$sk$之间的具体关系式，忽略 常数加操作*/

② for $i$ in range （$0,r$） do

③ $E(K,sk) \leftarrow$key_schedule（$i,$$s{k_i}$）；/*$s{k_i}$是第$i$轮密 钥，$s{k_0}$ = K，E是关于K和sk的密钥方程系统*/

④ end for

⑤ return $E(K,sk)$.

⑥ function Propagation（${\mathcal{K}},$${{\mathcal{K}}_0},$${\mathcal{ S}},$${{\boldsymbol{M}}_{{\text{key}}}}$）：/*知识传 播阶段，扩展${{\mathcal{K}}_0}$到所有可表出的密钥*/

⑦ ${\boldsymbol{ M}}$$\leftarrow {G}_{{\mathcal{K}}-{{\mathcal{K}}}_{1}-{\mathcal{S}}}({\boldsymbol{M}})$；/*${\boldsymbol{M}}$表示${\mathcal{K}} - {{\mathcal{K}}_1} - {\mathcal{S}}$对应的 系数矩阵*/

⑧ for $row$ in ${{\boldsymbol{M}}_{{\text{key}}}}$ do

⑨ if 在前$|{\mathcal{K}} - {{\mathcal{K}}_1} - {\mathcal{S}}|$行有1个$row$属于$case$ then

⑩ 移动$x$,$S(x)$,或者$x$与$S(x)$所对应的列；

⑪ $({{\mathcal{K}}_1},{\mathcal{S}}) \leftarrow ({{\mathcal{K}}_1},\mathcal{S}) \cup \{ x\}$$(\{ S(x)\}$,$\{ x,$

$S(x)\} )$；/*添加新变量*/

⑫ end if

⑬ end for

⑭ return ${{\mathcal{K}}_1},$ ${M_{{\text{key}}}}$.

⑮ function Derivation（${{\mathcal{K}}_0}$, ${{\mathcal{K}}_1}$, ${\boldsymbol{A}}$）：/*关系导出阶段， 对系数矩阵${{\boldsymbol{M}}_{{\text{key}}}}$中变量${{\mathcal{K}}_1}$对应的分块矩阵 ${\boldsymbol{ A}}$进行处理*/

⑯ ${\boldsymbol{ A}} \leftarrow {G_{{{\mathcal{K}}_{\text{1}}} - {{\mathcal{K}}_0} - {\mathcal{S}}}}({\boldsymbol{A}})$；

⑰ for $row$ in ${{\boldsymbol{B}}_1}$ do /*${{\boldsymbol{B}}_1}$为矩阵${\boldsymbol{ A}}$中变量${\mathcal{ S}}$对应的分 块矩阵*/

⑱ if $Rank({{\boldsymbol{B}}_1}) \geqslant 4 - N$then/*$N$为${\mathcal{ S}}$中元素在${{\mathcal{K}}_0}$ 中出现的个数*/

⑲ 向${\boldsymbol{ A}}$中增加与$\varphi$和$x + \varphi '$相应的新行和新列；

⑳ if $Rank({{\boldsymbol{B}}_1}) > 4 - N$then

㉑ 向${\boldsymbol{ A}}$中增加与$\psi$和$\psi '$相应的新行和新列；

㉒ end if

㉓ end if

㉔ end for

㉕ ${\boldsymbol{ A}} \leftarrow {G_{{{\mathcal{K}}_{\text{1}}} - {{\mathcal{K}}_0} - {\mathcal{S}}}}({\boldsymbol{A}})$；

㉖ for $row$ in ${{\boldsymbol{B}}_2}$ do /*${{\boldsymbol{B}}_2}$是矩阵${\boldsymbol{A }}$中变量${{\mathcal{K}}_0}$对应的 分块矩阵*/

㉗ $R \leftarrow$导出所有密钥桥；

㉘ end for

㉙ return $R$.

行⑨$case = {\text{\{ }}cas{e_1}{\text{,}}cas{e_2}{\text{\} }}$，其中：

$cas{e_1} = (0, … ,0,{e_x},0, … ,0,{e_{S(x)}}, 0, … ,0,{e_{|\mathcal{K} - {\mathcal{K}_1} - {\mathcal{S}}|}}, …$, ${e_n})$；

$case_2= \left\{ (0, … ,0,{e_t}, {e_x},0, … ,0, {e_{|\mathcal{K} - {\mathcal{K}_1} - {\mathcal{S}}|}}, … ,{e_n} ) , (0, … , \right.$ $0,{e_s},{e_{{\mathcal{S}}(x)}},0, … ,0, {e'_{|\mathcal{K} - {\mathcal{K}_1} - {\mathcal{S}}|}}, … ,{e'_n}),t \ne s,{e_t} = {e_s} = 0, {e_j} = c \cdot {e'_j},$ $\left. j = |\mathcal{K}-{\mathcal{K}_1} - {\mathcal{S}}|, …,n - 1 \right\}$ .

行⑲的$\varphi$为${\mathcal{S }}$中剩余的$8 - Rank({{\boldsymbol{B}}_1}) - N$个变量，$\varphi '$是关于$\varphi$的线性组合.

行㉑的$\psi$为${\mathcal{ S }}$中剩余的$Rank({{\boldsymbol{B}}_1}) - 4 + N$个变量，$\psi '$是关于$\psi$的线性组合，它们用于表示可以由$S$扩展得到的密钥比特.

利用算法1，搜索到了MIBS-64和MIBS-80的密钥编排的相关性质——性质1和性质2. 此外，我们也通过密钥编排算法推导验证了性质1和性质2.

性质1. 根据MIBS-64的密钥编排算法，第11轮的密钥$s{k_{11,[31:17]}}$可由第12轮密钥$s{k_{12,[16:02]}}$得到；第10轮密钥$s{k_{10,[31:30]}}$可由第12轮密钥$s{k_{12,[01:00]}}$得到；第10轮密钥$s{k_{10,[31:15]}}$可由第11轮密钥$s{k_{11,[16:00]}}$得到；第9轮的轮密钥$s{k_{{\text{9}},[{\text{12}}:{\text{00}}]}}$可由第12轮轮密钥$s{k_{12,[{\text{31}}:{\text{19}}]}}$得到，第9轮的轮密钥$s{k_{{\text{9}},[{\text{31}}:{\text{15}}]}}$可由第10轮的轮密钥$s{k_{{\text{10}},[{\text{16}}:{\text{00}}]}}$得到.

性质2. 根据MIBS-80的密钥编排算法，第13轮的轮密钥$s{k_{13,[31:19]}}$可由第14轮的轮密钥$s{k_{14,[12:00]}}$得到；第12轮密钥$s{k_{12,[31:19]}}$可由第13轮的轮密钥$s{k_{13,[12:00]}}$得到；第11轮的密钥$s{k_{11,[31:19]}}$可由第12轮密钥$s{k_{12,[12:00]}}$得到；第11轮的密钥$s{k_{11,[08:00]}}$可由第14轮密钥$s{k_{14,[31:23]}}$得到；第10轮密钥$s{k_{10,[31:19]}}$可由第11轮密钥$s{k_{11,[12:00]}}$得到；第10轮密钥$s{k_{10,[27:00]}}$可由第14轮密钥$s{k_{14,[31:04]}}$得到.

文献[26]提出了一个关于MIBS-64的轮密钥和主密钥之间关系的性质. 与密钥搭桥技术考虑所有轮密钥之间的具体关系式不同，文献[26]通过密钥编排算法的循环移位操作来判断轮密钥可能涉及的所有主密钥位置. 例如，考虑性质1的密钥桥$s{k_{12,[16:02]}}\xrightarrow{{}}s{k_{11,[31:17]}}$. 根据文献[26]，猜测$s{k_{12,[16:02]}}$需要猜测主密钥${K_{[39:20]}}$，猜测$s{k_{11,[31:17]}}$需要猜测主密钥${K_{[36:21]}}$，因此轮密钥$s{k_{12,[16:02]}}$与$s{k_{11,[31:17]}}$之间似乎并不能互相独立推导得出. 事实上，根据密钥编排算法写出它们之间的表达式，发现二者是可以互相推导的，而这恰好是密钥搭桥技术的思想. 密钥搭桥技术通过处理轮密钥之间的具体关系式，精准地判断出所有潜在的密钥桥.

文献[26]也提出了MIBS-80的轮密钥和主密钥之间关系的性质. 类似地，考虑密钥桥$s{k_{14,[12:00]}}\xrightarrow{{}} s{k_{13,[31:19]}}$. 那么，根据文献[26]，猜测 $s{k_{14,[12:00]}}$ 需要猜测主密钥 ${K_{[79:74,09:00]}}$，猜测 $s{k_{13,[31:19]}}$ 需要猜测主密钥 ${K_{[79:71,06:00]}}$. 因此 $s{k_{14,[12:00]}}$ 和 $s{k_{13,[31:19]}}$ 似乎不能完全互相推导得出. 事实上，根据轮密钥之间的关系式，$s{k_{14,[12:00]}}$和$s{k_{13,[31:19]}}$也是可以互相推导出的.

2.2   MIBS的积分区分器

目前，MIBS最长的积分区分器为5轮，都是基于加密算法的结构特点推导求得的^[25,28]. 结合文献[14,31]的基于比特自动化建模方法，分别对线性变换和S盒生成约束条件，建立MIBS的MILP模型，搜索更长的积分区分器. 具体过程为：首先，对MIBS加密算法的每一个基本操作建模；然后，生成MIBS的$r$轮可分性传播的线性不等式系统；接着，给定输入和输出可分性；最后，利用求解器求解$r$轮可分性传播系统.

MIBS的加密算法仅包含S盒、线性变换$P$、异或操作、置换操作. 对于S盒，利用文献[31]的方法，使用Quine-Mclusky方法建立约束条件. 首先，求出S盒的所有可分迹，然后利用Logic Friday软件生成约束这些可分迹的合取范式，最后将合取范式转换为线性不等式（具体约束如附录A所示）.

对于置换操作，仅需要改变变量的位置即可. 对于异或操作$b = {a_0} \oplus {a_1}$，使用的建模规则为：

另外，还需使用复制操作$b \to ({a_0},{a_1})$，使用的建模规则为：

线性层中异或操作和复制操作的建模比较简单，只需根据建模规则，直接代入状态变量即可. 对于线性变换$P$，对应的基于半字节的矩阵在附录B中给出. 根据此矩阵和异或操作、复制操作的建模规则，可以直接写出其对应的基于比特的约束不等式（具体参考附录B）.

按照式（1）（2）的建模方式迭代$r$次，MIBS的$r$轮可分性传播的线性不等式系统即可生成. 然后，挑选仅有几比特为常数. 其余比特全活跃的输入状态，确定输入可分性，并且将输出对应的变量写成目标函数，添加到不等式系统中，完成对MILP模型的建模过程. 最后，通过求解不等式系统判断积分区分器的存在性.

根据上面的自动化建模搜索方法，可以构造MIBS的8轮积分区分器：从明文集的最高32比特选择4比特为常数，其余比特都活跃，那么经过8轮MIBS加密之后，输出的最低32比特都是平衡的. 例如，当明文的最高4比特为常数时，对应的输入和输出可分性表示

当选择的明文集只有1个比特为常数时，可以构造9轮积分区分器，具体如定理1所示.

定理1. 选择明文集$X$，满足最高32比特中的任一比特为常数，其余比特都为活跃比特，即对于一个固定的$i \in \{ 0,1, … ,31\}$，${x_i} = c$；对于任意$j \ne i$，${x_j} = a$. 那么，该明文集经过9轮MIBS加密之后，输出的最低32比特都是平衡的，即输出值的求和有形式为：

设每一轮的输入可分性$\mathcal{D}{\text{ = }}{\mathcal{D}_{[63:32]}}||{\mathcal{D}_{[31:00]}}$, 表2展示了当最高比特为常数时，9轮积分区分器每一轮中间状态对应的可分性.

表  2  MIBS 9轮积分区分器中间状态的可分性

Table  2.  Division Property of Intermediate States for the 9-Round Integral Distinguisher of MIBS

轮数	左32 b可分性${ { {\mathcal D } }_{[63:32]} }$	右32 b可分性${ {\mathcal{D} }_{[31:00]} }$
0	${\textit{z} }{{\mathcal {I} }_{31} }$	${{\mathcal {I} }_{32} }$
1	${{\mathcal {I} }_{32} }$	${\textit{z} }{{\mathcal {I} }_{31} }$
2	${{\mathcal {I} }_{32} }$	$i{{\mathcal {Z} }_3}{{\mathcal {I} }_{28} }$
3	${{ \mathcal {I} }_{32} }$	$i{{ \mathcal {Z} }_{\text{5} } }i{\textit{z} }{ {\mathcal {I} }_4}{\textit{z} }i{\textit{z} }{\textit{z} }{ {\mathcal {I} }_{16} }$
4	${{\mathcal {I} }_5}{\textit{z} }{{\mathcal {I} }_{26} }$	${\textit{z} }i{\textit{z} }{\textit{z} }i{\mathcal {Z}_5}ii{\textit{z} }i{\textit{z} }{\textit{z} }i{{ {\textit{z} } }_3}i{\mathcal {Z} }i{ \mathcal {Z}_4}ii{\textit{z} }{\textit{z} }i$
5	${\mathcal {I} _3}{\textit{z} }i{\textit{z} }ii{\textit{z} }{\mathcal {I} _5}{\textit{z} }ii{\textit{z} }{\mathcal {I} _3}{\textit{z} }ii{\textit{z} }{\textit{z} }{\mathcal {I} _3}{\textit{z} }{\textit{z} }i$	${{\mathcal {Z} }_3}i{{\mathcal {Z} }_6}i{{\mathcal {Z} }_3}i{{\mathcal {Z} }_5}i{{\mathcal {Z} }_4}i{{\mathcal {Z} }_3}izz$
6	${\textit{z} }i{\textit{z} }i{ { \mathcal {Z}_6}i{{\mathcal {Z} }_3}i{\mathcal {Z} }_5}{ {\mathcal {I} }_3}{\textit{z} }{\textit{z} }{ {\mathcal {I} }_5}{\textit{z} }i$	${{\mathcal {Z} }_{32} }$
7	${\mathcal {Z}_8}i{\textit{z} }ii{\mathcal {Z }_9}{ {\mathcal {I} }_3}{\mathcal {Z}_8}$	${{\mathcal {Z} }_{32} }$
8	${{\mathcal {Z} }_3}i{{\mathcal {Z} }_{21} }i{{\mathcal {Z} }_6}$	${{\mathcal {Z} }_{32} }$
9	${{\mathcal {Z} }_{32} }$	${{\mathcal {Z} }_3}i{{\mathcal {Z} }_{21} }i{{\mathcal {Z} }_6}$
注: ${{\mathcal {I} }_m}$,${{\mathcal {Z} }_m}$表示连续$m( m\geqslant 3)$比特的可分性，分别对应$(1,1, … ,1)$, $(0,0, … , 0)$；i, z表示基于比特的可分性，分别对应1和0. 例如，${{\mathcal {Z} }_8}i{\textit{z} }ii$表示可分性$(0, 0, 0,0,0,0,0,0,1,0,1,1)$.

下载: 导出CSV 

| 显示表格

3.   12轮MIBS-64的密钥恢复攻击

本节利用2.2节中MIBS的8轮积分区分器：最高4位是常数，其余位均活跃，8轮之后输出的最低32位是平衡的，在区分器末尾增加4轮，完成了对12轮MIBS-64的密钥恢复攻击，如图2所示.

图  2  MIBS-64的密钥恢复攻击

${X_9}$与${X'_9}$之间的虚线表示：为了计算$X_8^0$，从第10轮${X_9}$中选取部分状态，即$X_9^{0,1,3,4,6,7}$参与计算

Figure  2.  Key recovery attack of MIBS-64

下载: 全尺寸图片 幻灯片

3.1   攻击过程

整个密钥恢复过程分为6步，具体攻击步骤为：

Step1. 选择明文集$X = {X_1}||{X_0}$，X共${{\text{2}}^{{\text{60}}}}$个明文，满足明文的第1个半字节为常数，其余半字节都是活跃的，查询其12轮MIBS-64加密之后的密文$C = {C_{[63:32]}}||{C_{[31:00]}}$.

Step2. 已知密文$C$，猜测第12轮的密钥$s{k_{12,[31:00]}}$，解密计算${X_{11}} = P \circ S({C_{[63:32]}} \oplus s{k_{12}})$ $\oplus {C_{[31:00]}}$.

Step3. 已知密文和${X_{11}}$，猜测第11轮的轮密钥$s{k_{11,[31:00]}}$，计算${X_{10}} = P \circ S({X_{11}} \oplus s{k_{11}}) \oplus {C_{[63:32]}}$. 根据性质1，部分密钥可以根据12轮的轮密钥直接得到，因此实际只需猜测15 b，即$s{k_{11,[14:00]}}$.

Step4. 已知${X_{11}}$和${X_{10}}$，猜测第10轮的轮密钥$s{k_{10,[31:00]}}$，计算${X_9} = P \circ S({X_{10}} \oplus s{k_{10}}) \oplus {X_{11}}$. 根据性质1，部分密钥可以根据第12,11轮的轮密钥直接得到，因此实际只需猜测15b，即$s{k_{10,[14:00]}}$.

Step5. 已知${X_{10}}$和${X_9}$，猜测第9轮的轮密钥$s{k_{9,[31:00]}}$，计算${X_8} = P \circ S({X_9} \oplus s{k_9}) \oplus {X_{10}}$. 根据性质1，部分密钥可以根据第12,11,10轮的轮密钥直接得到，因此实际只需猜测15b，即$s{k_{9,[14:00]}}$.

Step6. 根据2.2节，$X$经8轮MIBS加密之后的低32比特都是平衡比特. 因此，满足$\displaystyle\sum_i {{X_{i,8}}} = 0$ 的密钥可能为正确密钥. 筛选概率为${2^{ - 32}}$，共得到${2^{32 + 15 + 15 + 15}} \times {2^{ - 32}} = {2^{{\text{45}}}}$个候选密钥.

3.2   利用密钥搭桥与部分和技术降低复杂度

3.1节的攻击过程已经根据密钥桥调整了需要猜测的密钥个数，下面介绍利用部分和技术降低复杂度.

对于Step2，利用部分和技术，逐个计算${X_{11}}$中每半字节的值. 由于$S({C_{[63:32]}} \oplus s{k_{12}}) = {S_7}({C_{[63:60]}} \oplus$$s{k_{12,[31:28]}})||… ||{S_0}({C_{[35:32]}} \oplus s{k_{12,[03:00]}})$，根据线性变换$P$，有式（3）~（10）成立：

1）根据式（3）计算$X_{11}^0$. 首先猜测$sk_{12}^0$和$sk_{12}^1$，解密计算求和${S_0}(C_{[31:00]}^0 \oplus sk_{12}^0) \oplus {S_1}(C_{[31:00]}^1 \oplus sk_{12}^1$$)$出现的次数；接着猜测$sk_{12}^3$，计算第0, 1, 3个S盒的求和值出现的次数；以此类推，依次猜测$sk_{12}^4$，$sk_{12}^6$，$sk_{12}^7$，最终计算得到$X_{11}^0$每个可能值出现的次数. 实际上，因为解密得到的所有值最终要求异或和，所以只需统计每个值出现的次数是奇数还是偶数即可.

2）根据式（4）计算$X_{11}^1$. 由于在1）中已经猜测了$sk_{12}^{1,3,4,6}$，因此这里只需再猜测$sk_{12}^2$和$sk_{12}^5$的值. 通过猜测的密钥，统计$X_{11}^1$的所有可能值出现次数的奇偶性.

3）以此类推，根据猜测的密钥和式（5）~（10），计算${X_{11}}$其他半字节的值.

对于Step3，只需要猜测$s{k_{11,[14:00]}}$. 与Step2类似，首先猜测$sk_{11}^{0,1}$，计算${S_0}(X_{11}^0 \oplus sk_{11}^0) \oplus$ ${S_1}(X_{11}^1 \oplus sk_{11}^1)$；接着猜测$sk_{11}^2$，$s{k_{11,[14:12]}}$，计算${X_{10}}$每个半字节的值.

Step4, Step5的过程与Step3类似. 图2也展示了第9轮利用部分和与密钥搭桥技术恢复$X_8^0$的过程，即$X_8^0 = X_{10}^0 \oplus \displaystyle\sum_{i \in \{ 0,1,3,4,6,7\} } {{S_i}(X_9^i \oplus sk_9^i)}$${X_9}$与${X'_9}$之间的虚线表 示：为了计算$X_8^0$，从第10轮${X_9}$中选取部分状态， 即$X_9^{0,1,3,4,6,7}$参与计算.

3.3   复杂度分析

3.1节的攻击过程的时间复杂度主要来自于Step2~5.

Step2的时间复杂度约为${2^{6{\text{0}}}} \times {2^{\text{8}}}{\text{ + }}{2^{6{\text{0}}}} \times {2^{\text{4}}} \times {\text{6}}$次S盒查表；Step3的时间复杂度约为${2^{6{\text{0}}}} \times {2^{\text{8}}}{\text{ + }}{2^{6{\text{0}}}} \times {2^{\text{4}}}$$\times {\text{1}}{\text{.75}}$次S盒查表；Step4和Step5的时间复杂度都为${2^{6{\text{0}}}} \times {2^{\text{8}}}$${\text{ + }}{2^{6{\text{0}}}} \times {2^{\text{4}}} \times {\text{1}}{\text{.75}}$次S盒查表. 因此总的时间复杂度为${2}^{6\text{0}}\times {2}^{\text{8}}\times \text{4}/ （12\times 8）\approx {\text{2}}^{\text{63}\text{.42}}$次12轮MIBS-64解密计算. 数据复杂度为${{\text{2}}^{{\text{60}}}}$的选择明文.

4.   14轮MIBS-80的密钥恢复攻击

利用2.2节中MIBS的任意一个9轮积分区分器，在末尾增加5轮，都能完成一个对14轮MIBS-80的密钥恢复攻击. 本节以MIBS所示的一个区分器为例，介绍详细的攻击过程如图3所示.

图  3  MIBS-80的密钥恢复攻击

Figure  3.  Key recovery attack of MIBS-80

下载: 全尺寸图片 幻灯片

4.1   攻击过程

Step1. 选择明文集$X$，X中共有${{\text{2}}^{{\text{63}}}}$个明文，满足明文的第1个比特为常数，其余比特都是活跃的，查询其14轮MIBS-80加密之后的密文$C = {C_{[63:32]}}||{C_{[31:00]}}$.

Step2. 已知密文$C$，猜测第14轮的密钥$s{k_{14}}$，解密计算${X_{13}} = P \circ S({C_{[63:32]}} \oplus s{k_{14}}) \oplus {C_{[31:00]}}$.

Step3. 猜测第13轮的轮密钥$s{k_{13}}$，解密计算${X_{12}} = P \circ S({X_{13}} \oplus s{k_{13}}) \oplus {X_{14}}$. 根据性质2，部分密钥比特可以根据$s{k_{14,[12:00]}}$直接得到，因此实际只需猜测19 b，即$s{k_{13,[18:00]}}$.

Step4. 猜测第12轮的轮密钥$s{k_{12}}$，解密计算${X_{11}} = P \circ S({X_{12}} \oplus s{k_{12}}) \oplus {X_{13}}$. 根据性质2，部分密钥可以根据$s{k_{13,[12:00]}}$直接得到，因此实际只需猜测19 b，即$s{k_{12,[18:00]}}$.

Step5. 猜测第11轮的轮密钥$s{k_{11}}$，解密计算${X_{10}} = P \circ S({X_{11}} \oplus s{k_{11}}) \oplus {X_{12}}$. 根据性质2，部分密钥可以根据13,12轮的轮密钥得到，实际上只需要猜测10 b，即$s{k_{11,[18:09]}}$.

Step6. 根据性质2，$s{k_{10}}$可由$s{k_{11,[12:00]}}$和$s{k_{14,[31:04]}}$得到，解密计算${X_9} = P \circ S({X_{10}} \oplus s{k_{10}}) \oplus {X_{11}}$.

Step7. 根据定理1，$X$经9轮MIBS加密之后的低32比特都是平衡比特. 因此，满足$\displaystyle \sum_i {{X_{i,9}}} = 0$的密钥可能为正确密钥. 筛选概率为${2^{ - 32}}$，共得到${2^{32 + 19 + 19 + 10}} \times {2^{ - 32}} = {2^{{\text{48}}}}$个候选密钥.

4.2   利用密钥搭桥与部分和技术降低复杂度

4.1节中的攻击过程已经根据密钥桥调整了需要猜测的密钥个数，下面介绍利用部分和技术降低复杂度.

对于Step2，利用部分和技术，逐个计算${X_{13}}$每半字节的值. 根据线性变换$P$，有式（11）（12）成立：

1）根据式（11），计算$X_{13}^0$. 首先猜测$sk_{14}^0$和$sk_{14}^1$的值，由于密文已知，解密计算${S_0}(C_{[31:00]}^0 \oplus sk_{14}^0) \oplus$${S_1}(C_{[31:00]}^1\oplus sk_{14}^1)$出现的次数；接着猜测$sk_{14}^3$，计算第0, 1, 3个S盒的求和值出现的次数；以此类推，依次猜测$sk_{14}^4$，$sk_{14}^6$，$sk_{14}^7$，最终计算得到$X_{13}^0$每个可能值出现次数的奇偶性.

2）根据式（12），计算$X_{13}^1$. 由于在1）中已经猜测了$sk_{14}^{1,3,4,6}$，因此这里只需再猜测$sk_{14}^2$和$sk_{14}^5$的值. 通过猜测的密钥，统计$X_{13}^1$每个可能值出现次数的奇偶性.

3）类似于1）和2），根据猜测的密钥及线性变换$P$计算${X_{13}}$其他半字节的值.

Step3~6的过程与Step2类似，区别在于需要猜测的密钥长度小于32 b.

4.3   复杂度分析

4.1节中的攻击过程的时间复杂度主要来自于Step2~5. Step2的时间复杂度约为${2^{63}} \times {2^{\text{8}}}{\text{ + }}{2^{63}} \times {2^{\text{4}}} \times {\text{6}}$次S盒查表，Step3和Step4的时间复杂度都为${2^{63}} \times {2^{\text{8}}} + {2^{63}} \times {2^{\text{4}}} \times {\text{2}}{\text{.75}}$次S盒查表，Step5的时间复杂度约为${2^{63}} \times {2^7}{\text{ + }}{2^{63}} \times {2^{\text{4}}} \times {\text{0}}{\text{.75}}$次S盒查表，因此总的时间约为${2^{63}} \times {2^{\text{8}}} \times {\text{3}}{\text{.5}}/14 \times 8 \approx {{\text{2}}^{{\text{66}}}}$次14轮的MIBS-80解密计算，数据复杂度为${{\text{2}}^{{\text{63}}}}$的选择明文.

5.   总　　结

本文对分组密码算法MIBS进行了积分分析. 对于MIBS-64，在8轮积分区分器的末尾增加4轮进行了12轮MIBS-64的密钥恢复攻击；对于MIBS-80，在9轮积分区分器的末尾增加5轮进行了14轮MIBS-80的密钥恢复攻击. 在MIBS的密钥恢复过程中，我们利用密钥搭桥技术与部分和技术，有效地降低了时间复杂度. MIBS的密钥编排算法比较简单，例如，MIBS-64的2轮实际上只用了47 b互不相关的轮密钥. 因此，利用密钥搭桥技术可以极大降低猜测的密钥量. 由此可见，轮密钥之间的关系对算法的安全性具有重要的影响.

作者贡献声明：毛永霞提出实验方案并撰写论文；吴文玲提出指导意见并修改论文；张丽负责修改论文.