1.   引言

积分分析是分组密码的重要分析方法，由Knudsen等人^[1]在Square攻击^[2]等方法基础上提出，对AES^[3], MISTY^[4]等算法都有很好的攻击效果。积分分析的核心思想是通过选择特定输入明文集，分析经多轮加密后某些位置比特是否具有特定的积分性质，比如平衡性，即对应的状态集求和为0的情形，再根据这些积分性质排除错误密钥。

SIMON系列算法^[5]由美国国家安全局设计提出，是一类重要的轻量分组密码。算法轮函数结构简单，仅由循环移位、异或和按位与构成，其中按位与为主要的非线性部件。目前对SIMON算法安全性能的分析主要包括差分分析^[6-11]、线性分析^[8,12-14]、不可能差分分析^[12,15-17]、零相关线性分析^[15,18]和积分分析^[19-21]等。在积分分析方面，Wang等人^[15]给出了SIMON32算法的15轮积分区分器和21轮积分分析，Xiang等人^[19]利用混合整数线性规划方法给出了SIMON系列算法的积分区分器，Fu等人^[20]利用等价密钥技术将SIMON32算法积分分析的轮数提高了一轮，并且给出了SIMON48算法的积分分析，Chu等人^[21]利用动态密钥猜测技术进一步提高了攻击轮数，本文在此基础上考虑了更长分组的SIMON64算法的积分分析。基于Xiang等人^[19]找到的18轮积分区分器，本文首先利用中间相遇技术和部分和技术给出了对25轮SIMON64/128算法的积分分析，接着利用等价密钥技术进一步降低攻击过程中需要猜测的密钥量，将攻击轮数又提高了一轮，给出了26轮SIMON64/128算法的积分分析。

本文后续部分安排如下：第2节简要介绍SIMON系列算法及相关符号。第3节基于已有的SIMON64算法的18轮积分区分器，用中间相遇技术和部分和技术给出对25轮SIMON64/128算法的积分分析。第4节介绍等价密钥技术，并基于此给出改进的26轮SIMON64/128算法的积分分析。第5节是结束语。

2.   SIMON算法简介

2.1   符号说明

${X_r}$表示算法第$r$轮左边的输入；${Y_r}$表示算法第$r$轮右边的输入；${K_r}$表示第$r$轮的子密钥；$K_r^*$表示第$r$轮的等价子密钥；${X_{r,\left\{ {i\sim j} \right\}}}$表示${X_r}$的第$i\sim j$ bit; ${Y_{r,\left\{ {i\sim j} \right\}}}$表示${Y_r}$的第$i\sim j$ bit; $X < < < s$表示$X$循环左移$s$ bit；$X > > > s$表示$X$循环右移$s$ bit；$\oplus$表示按位异或；$\wedge$表示按位与。

2.2   SIMON算法简介

SIMON系列算法^[5]采用Feistel结构，其轮函数如图1所示。设初始明文为$\left( {{X_0},{Y_0}} \right)$，第$r$轮的输入为$\left( {{X_r},{Y_r}} \right)$，记算法的轮函数$F\left( X \right) = \left( {X < < < 1} \right) \wedge$$\left( {X < < < 8} \right) \oplus \left( {X < < < 2} \right)$，则第$r + 1$轮的输出为

图 1  SIMON算法的轮函数

下载: 全尺寸图片 幻灯片

SIMON系列算法支持多种分组长度和密钥长度的组合，不妨简记分组长度为$2n$ bit，密钥长度为$mn$ bit的SIMON算法为SIMON${\rm{2}}n/mn$算法，其中$n \in \left\{ {16,24,32,48,64} \right\}$, $m \in \left\{ {2,3,4} \right\}$。SIMON算法的密钥扩展方案会根据字数$m$值的不同而有所不同，前$m$轮子密钥由主密钥直接生成，剩余轮子密钥的生成满足式(2)的关系

其中$i = 0,1 ··· ,T - m$, $c = {2^n} - 4$, ${z_j}\left( {j \in \left\{ {0,1,2,3,4} \right\}} \right)$是和版本有关的常数序列。从SIMON的密钥扩展算法可以看出，每个子密钥均可用主密钥线性表示，并且已知任意连续$m$个子密钥就可以恢复出主密钥。

3.   SIMON64算法的积分分析

本节利用Xiang等人^[19]找到的积分区分器给出对SIMON 64/128和SIMON 64/96算法的积分分析。他们找到的SIMON 64算法的17轮积分区分器形如$\left( {CA ···A,A ··· A} \right){ \to _{17}}\left( {?··· ?,BBBBBBBBBBB} \right.$$\left. ????? { B?????BBBBBBBBBB} \right)$，其中$A$表示活跃比特，$B$表示平衡比特，$?$表示未知比特，$C$表示常量比特。类似于Wang等人^[15]的处理方法，该区分器可以自然向前扩展一轮，得到如图2所示的SIMON64算法的18轮积分区分器。

图 2  SIMON 64算法的18轮积分区分器

下载: 全尺寸图片 幻灯片

图2所示的18轮积分区分器输出的右边部分有22个平衡比特，下面以最右边的平衡比特为例，在后面添加7轮，给出对SIMON64/128算法的25轮积分分析。图3给出了密钥恢复过程需要用到的子密钥和中间状态比特。密钥恢复过程需要猜测${K_{19,\left\{ {24,30,31} \right\}}}$, ${K_{20,\left\{ {0,16,22,23,28\sim 30} \right\}}}$, ${K_{21,\left\{ {8,14,15,20\sim 22,24,26\sim 31} \right\}}}$, ${K_{22,\left\{ {0,6,7,12\sim 14,16,18\sim 30} \right\}}}$, ${K_{23,\left\{ {4\sim 6,8,10\sim 31} \right\}}}$, ${K_{24,\left\{ {0,2\sim 30} \right\}}}$共99 bit子密钥，攻击中需要的选择明文数为${2^{63}}$，直接计算的复杂度超过${{\rm{2}}^{{\rm{128}}}}$。下面采用中间相遇技术和部分和技术来降低密钥恢复过程的计算复杂度。

图 3  25轮积分分析的密钥恢复过程

下载: 全尺寸图片 幻灯片

注意到${\left( {{Y_{18}} \oplus {K_{18}}} \right)_{\left\{ 0 \right\}}}{\rm{ = }}\left( {{X_{18,\left\{ {31} \right\}}} \wedge {X_{18,\left\{ {24} \right\}}}} \right) \oplus$${\left( {{X_{18}} \oplus {X_{19}}} \right)_{\left\{ {30} \right\}}}$，要判断$\oplus {\left( {{Y_{18}} \oplus {K_{18}}} \right)_{\left\{ 0 \right\}}} = 0$是否成立，只要判断$\oplus \left( {{X_{18,\left\{ {31} \right\}}} \wedge {X_{18,\left\{ {24} \right\}}}} \right) =$$\oplus {\left( {{X_{18}} \oplus {X_{19}}} \right)_{\left\{ {30} \right\}}}$是否成立，因此可以分别计算和式$\oplus \left( {{X_{18,\left\{ {31} \right\}}} \wedge {X_{18,\left\{ {24} \right\}}}} \right)$和$\oplus {\left( {{X_{18}} \oplus {X_{1{\rm{9}}}}} \right)_{\left\{ {30} \right\}}}$，并比较二者是否相等。图4和图5分别给出了计算$\oplus \left( {{X_{18,\left\{ {31} \right\}}} \wedge {X_{18,\left\{ {24} \right\}}}} \right)$和$\oplus {\left( {{X_{18}} \oplus {X_{19}}} \right)_{\left\{ {30} \right\}}}$时需要猜测的子密钥和中间状态比特，其中计算前者需要猜测73 bit子密钥，计算后者需要猜测81 bit子密钥，重复猜测55 bit子密钥。

图 4  计算${X_{18,\left\{ {31} \right\}}} \wedge {X_{18,\left\{ {24} \right\}}}$的过程

下载: 全尺寸图片 幻灯片

图 5  计算${\left( {{X_{18}} \oplus {X_{19}}} \right)_{\left\{ {30} \right\}}}$的过程

下载: 全尺寸图片 幻灯片

对25轮SIMON64/128算法进行积分分析的主要步骤如下：

(1) 利用密钥扩展算法，将子密钥比特${K_{19,\left\{ {24,30,31} \right\}}}$和${K_{20,\left\{ {0,16,22,23,28\sim 30} \right\}}}$用$\left( {K_{21}},{K_{22}},{K_{23}}, \right.$$\left.{K_{24}} \right)$线性表出；

(2) 选择${2^{63}}$个明文，它们在一轮加密后仅左边第1个比特为常数，其余均为活动比特；

(3) 猜测73 bit相关的子密钥，计算$\oplus$$\left( {{X_{18,\left\{ {31} \right\}}} \wedge {X_{18,\left\{ {24} \right\}}}} \right)$，并将结果存储在表 ${T_1}$中；

(4) 猜测81 bit相关的子密钥，计算$\oplus$${\left( {{X_{18}} \oplus {X_{19}}} \right)_{\left\{ {30} \right\}}}$，并将结果存储在表 ${T_2}$中；

(5) 对每组猜测的子密钥，若表${T_1}$和${T_2}$匹配，则保留相应的子密钥为正确的候选子密钥，匹配后剩下${2^{73 + 81 - 1 - 55}} = {2^{98}}$个候选子密钥集；

(6) 对剩下的子密钥比特，猜测${K_{21,\left\{ {{\rm{2}}\sim 7,9\sim 13,{\rm{18,}}19} \right\}}}$, ${K_{22,\left\{ {4,5,8\sim 11,15,17,31} \right\}}}$, ${K_{{\rm{23,}}\left\{ {{\rm{1,2,3,}}7,9} \right\}}}$和${K_{{\rm{24,}}\left\{ {1,31} \right\}}}$共29 bit密钥，根据步骤(1)的线性关系用高斯消元法可求得${K_{2{\rm{1}},\left\{ {{\rm{0,1,16,17,23,25}}} \right\}}}$, ${K_{22,\left\{ {1\sim 3} \right\}}}$和${K_{{\rm{23,}}\left\{ 0 \right\}}}$共10 bit的密钥信息再利用密钥扩展算法由最后4轮子密钥$\left( {{K_{21}},{K_{22}},{K_{23}},{K_{24}}} \right)$恢复出主密钥，并用两组明密文对验证密钥的正确性。

表1和表2分别给出了第3步和第4步中计算$\oplus \left( {{X_{18,\left\{ {31} \right\}}} \wedge {X_{18,\left\{ {24} \right\}}}} \right)$和$\oplus {\left( {{X_{18}} \oplus {X_{19}}} \right)_{\left\{ {30} \right\}}}$的详细过程和复杂度分析，其中计算$\oplus \left( {{X_{18,\left\{ {31} \right\}}} \wedge {X_{18,\left\{ {24} \right\}}}} \right)$的具体步骤如下：

表 1  计算$\oplus \left( {{X_{18,\left\{ {31} \right\}}} \wedge {X_{18,\left\{ {24} \right\}}}} \right)$的复杂度

步骤	猜测密钥(比特数)	统计状态(比特数)	时间复杂度
(1)	${K_{24,\left\{ {2\sim 5,8\sim 12,14\sim 19,21\sim 26,28\sim 30} \right\}}}$(24)	${X_{24,\left\{ {4\sim 6,10\sim 13,16\sim 20,23\sim 27,30,31} \right\}}}$(19), ${Y_{24,\left\{ {2\sim 5,8\sim 12,14\sim 19,21\sim 26,28\sim 30} \right\}}}$(24)	${2^{24} } \cdot {2^{63} } \cdot \dfrac{ {24} }{ {32 \cdot 25} } \approx {2^{81.94} }$
(2)	${K_{23,\left\{ {4\sim 6,10\sim 13,16\sim 20,23\sim 27,30,31} \right\}}}$(19)	${X_{2{\rm{3}},\left\{ {0,6,7,12\sim 14,18\sim 21,25\sim 28} \right\}}}$(14), ${Y_{23,\left\{ {4\sim 6,10\sim 13,16\sim 20,23\sim 27,30,31} \right\}}}$(19)	${2^{43} } \cdot {2^{43} } \cdot \dfrac{ {19} }{ {32 \cdot 25} } \approx {2^{80.61} }$
(3)	${K_{22,\left\{ {0,6,7,12\sim 14,18\sim 21,25\sim 28} \right\}}}$(14)	${X_{2{\rm{2}},\left\{ {8,14,15,20\sim 22,27\sim 29} \right\}}}$(9), ${Y_{22,\left\{ {0,6,7,12\sim 14,18\sim 21,25\sim 28} \right\}}}$(14)	${2^{57} } \cdot {2^{33} } \cdot \dfrac{ {14} }{ {32 \cdot 25} } \approx {2^{84.16} }$
(4)	${K_{21,\left\{ {8,14,15,20\sim 22,27\sim 29} \right\}}}$(9)	${X_{2{\rm{1}},\left\{ {16,22,23,29,30} \right\}}}$(5), ${Y_{21,\left\{ {8,14,15,20\sim 22,27\sim 29} \right\}}}$(9)	${2^{66} } \cdot {2^{23} } \cdot \dfrac{9}{ {32 \cdot 25} } \approx {2^{82.53} }$
(5)	${K_{20,\left\{ {16,22,23,29,30} \right\}}}$(5)	${X_{{\rm{20,}}\left\{ {{\rm{24,31}}} \right\}}}$(2), ${Y_{20,\left\{ {16,22,23,29,30} \right\}}}$(5)	${2^{71} } \cdot {2^{14} } \cdot \dfrac{5}{ {32 \cdot 25} } \approx {2^{77.68} }$
(6)	${K_{{\rm{19,}}\left\{ {{\rm{24,31}}} \right\}}}$(2)	${X_{18,\left\{ {24,31} \right\}}}$(2), ${X_{18,\left\{ {24} \right\}}} \wedge {X_{18,\left\{ {31} \right\}}}$(1)	${2^{73} } \cdot {2^7} \cdot \dfrac{3}{ {32 \cdot 25} } \approx {2^{71.95} }$

下载: 导出CSV 

| 显示表格

表 2  计算$\oplus {\left( {{X_{18}} \oplus {X_{19}}} \right)_{\left\{ {30} \right\}}}$的复杂度

步骤	猜测密钥(bit数)	统计状态(bit数)	时间复杂度
(1)	${K_{24,\left\{ {0,2\sim 4,6\sim 29} \right\}}}$(28)	${X_{2{\rm{4}},\left\{ {4,5,8,10\sim 12,14\sim 30} \right\}}}$(23), ${Y_{24,\left\{ {0,2\sim 4,6\sim 29} \right\}}}$(28)	${2^{28} } \cdot {2^{63} } \cdot \dfrac{ {28} }{ {32 \cdot 25} } \approx {2^{86.17} }$
(2)	${K_{23,\left\{ {4,5,8,10\sim 12,14\sim 30} \right\}}}$(23)	${X_{2{\rm{3}},\left\{ {6,12,13,16,18\sim 20,22\sim 30} \right\}}}$(16), ${Y_{23,\left\{ {4,5,8,10\sim 12,14\sim 30} \right\}}}$(23)	${2^{51} } \cdot {2^{51} } \cdot \dfrac{ {23} }{ {32 \cdot 25} } \approx {2^{96.88} }$
(3)	${K_{22,\left\{ {6,12,13,16,18\sim 20,22\sim 30} \right\}}}$(16)	${X_{2{\rm{2}},\left\{ {14,20,21,24,26\sim 28,30,31} \right\}}}$(9), ${Y_{22,\left\{ {6,12,13,16,18\sim 20,22\sim 30} \right\}}}$(16)	${2^{67} } \cdot {2^{39} } \cdot \dfrac{ {16} }{ {32 \cdot 25} } \approx {2^{100.36} }$
(4)	${K_{21,\left\{ {14,20,21,24,26\sim 28,30,31} \right\}}}$(9)	${X_{2{\rm{1}},\left\{ {0,22,28,29} \right\}}}$(4), ${Y_{21,\left\{ {14,20,21,24,26\sim 28,30,31} \right\}}}$(9)	${2^{76} } \cdot {2^{25} } \cdot \dfrac{9}{ {32 \cdot 25} } \approx {2^{94.53} }$
(5)	${K_{20,\left\{ {0,22,28,29} \right\}}}$(4)	${X_{{\rm{20}},\left\{ {30} \right\}}}$(1), ${Y_{20,\left\{ {0,22,28,29} \right\}}}$(4)	${2^{80} } \cdot {2^{13} } \cdot \dfrac{4}{ {32 \cdot 25} } \approx {2^{85.36} }$
(6)	${K_{19,\left\{ {30} \right\}}}$(1)	${X_{{\rm{18,}}\left\{ {{\rm{31}}} \right\}}}$(1), $\oplus {\left( {{X_{18}} \oplus {X_{19}}} \right)_{\left\{ {30} \right\}}}$ (1)	${2^{81} } \cdot {2^5} \cdot \dfrac{2}{ {32 \cdot 25} } \approx {2^{77.36} }$

下载: 导出CSV 

| 显示表格

(1) 对${2^{24}}$个猜测的密钥比特${K_{24,\left\{ {2\sim 5,8\sim 12,14\sim 19,21\sim 26,28\sim 30} \right\}}}$和${2^{63}}$个密文值，计算${Y_{24,\left\{ {2\sim 5,8\sim 12,14\sim 19,21\sim 26,28\sim 30} \right\}}}$的值，统计43 bit状态${X_{24,\left\{ {4\sim 6,10\sim 13,16\sim 20,23\sim 27,30,31} \right\}}}$和${Y_{24,\left\{ {2\sim 5,8\sim 12,14\sim 19,21\sim 26,28\sim 30} \right\}}}$，保留出现奇数次的情形，时间复杂度约为${2^{81.94}}$次25轮SIMON64/128算法加密；

(2) 对${{\rm{2}}^{{\rm{19}}}}$个猜测的密钥比特${K_{23,\left\{ {4\sim 6,10\sim 13,16\sim 20,23\sim 27,30,31} \right\}}}$和${{\rm{2}}^{{\rm{43}}}}$个保留状态，计算${Y_{23,\left\{ {4\sim 6,10\sim 13,16\sim 20,23\sim 27,30,31} \right\}}}$的值，统计33 bit状态${X_{2{\rm{3}},\left\{ {0,6,7,12\sim 14,18\sim 21,25\sim 28} \right\}}}$和${Y_{23,\left\{ {4\sim 6,10\sim 13,16\sim 20,23\sim 27,30,31} \right\}}}$，保留出现奇数次的情形，时间复杂度约为${2^{80.61}}$次25轮SIMON64/128算法加密；

(3) 对${{\rm{2}}^{{\rm{14}}}}$个猜测的密钥比特${K_{22,\left\{ {0,6,7,12\sim 14,18\sim 21,25\sim 28} \right\}}}$和${{\rm{2}}^{{\rm{33}}}}$个保留状态，计算${Y_{22,\left\{ {0,6,7,12\sim 14,18\sim 21,25\sim 28} \right\}}}$的值，统计23 bit状态${X_{2{\rm{2}},\left\{ {8,14,15,20\sim 22,27\sim 29} \right\}}}$和${Y_{22,\left\{ {0,6,7,12\sim 14,18\sim 21,25\sim 28} \right\}}}$，保留出现奇数次的情形，时间复杂度约为${2^{84.16}}$次25轮SIMON 64/128算法加密；

(4) 对${{\rm{2}}^{\rm{9}}}$个猜测的密钥比特${K_{21,\left\{ {8,14,15,20\sim 22,27\sim 29} \right\}}}$和${{\rm{2}}^{{\rm{23}}}}$个保留状态，计算${Y_{21,\left\{ {8,14,15,20\sim 22,27\sim 29} \right\}}}$的值，统计14 bit状态${X_{2{\rm{1}},\left\{ {16,22,23,29,30} \right\}}}$和${Y_{21,\left\{ {8,14,15,20\sim 22,27\sim 29} \right\}}}$，保留出现奇数次的情形，时间复杂度约为${{\rm{2}}^{{\rm{82}}{\rm{.53}}}}$次25轮SIMON64/128算法加密；

(5) 对${{\rm{2}}^{\rm{5}}}$个猜测的密钥比特${K_{20,\left\{ {16,22,23,29,30} \right\}}}$和${{\rm{2}}^{{\rm{14}}}}$个保留状态，计算${Y_{20,\left\{ {16,22,23,28,29} \right\}}}$的值，统计7 bit状态${X_{{\rm{20,}}\left\{ {{\rm{24,31}}} \right\}}}$和${Y_{20,\left\{ {16,22,23,29,30} \right\}}}$，保留出现奇数次的情形，时间复杂度约为${{\rm{2}}^{{\rm{77}}{\rm{.68}}}}$次25轮SIMON64/128算法加密；

(6) 对${{\rm{2}}^{\rm{2}}}$个猜测的密钥比特${K_{{\rm{19,}}\left\{ {{\rm{24,31}}} \right\}}}$和${{\rm{2}}^{\rm{7}}}$个保留状态，计算并统计3 bit状态${X_{18,\left\{ {24,31} \right\}}}$和${X_{18,\left\{ {24} \right\}}} \wedge {X_{18,\left\{ {31} \right\}}}$，保留出现奇数次的情形，时间复杂度约为${{\rm{2}}^{{\rm{71}}{\rm{.95}}}}$次25轮SIMON64/128算法加密。

上述计算$\oplus \left( {{X_{18,\left\{ {31} \right\}}} \wedge {X_{18,\left\{ {24} \right\}}}} \right)$的过程中总共需要猜测73 bit子密钥，计算复杂度约为${{\rm{2}}^{{\rm{84}}{\rm{.87}}}}$次25轮SIMON64/128算法加密，存储复杂度约为${{\rm{2}}^{{\rm{73}}}} \cdot {\rm{74}} \approx {{\rm{2}}^{{\rm{79}}{\rm{.21}}}}$ bit。类似地，计算$\oplus {\left( {{X_{18}} \oplus {X_{19}}} \right)_{\left\{ {30} \right\}}}$的过程中总共需要猜测81 bit子密钥，计算复杂度约为${{\rm{2}}^{{\rm{100}}{\rm{.51}}}}$次25轮SIMON64/128算法加密，存储复杂度约为${{\rm{2}}^{{\rm{81}}}} \cdot {\rm{82}} \approx {{\rm{2}}^{{\rm{87}}{\rm{.36}}}}$ bit。

复杂度分析：根据上面的分析，第(3)和第(4)步构造表${T_{\rm{1}}}$和${T_{\rm{2}}}$的时间复杂度约为${{\rm{2}}^{{\rm{100}}{\rm{.51}}}}{\rm{ + }}$${{\rm{2}}^{{\rm{84}}{\rm{.87}}}} \approx {{\rm{2}}^{{\rm{100}}{\rm{.51}}}}$次25轮SIMON64/128算法加密，剩下${{\rm{2}}^{{\rm{73 + 81 - 1 - 55}}}}{\rm{ = }}{{\rm{2}}^{{\rm{98}}}}$个候选子密钥。第(6)步中高斯消元的时间开销远低于25轮算法加密的复杂度可以忽略不计，而猜测剩下的29 bit子密钥，并用2组明密文对分别验证的复杂度约为${2^{98}} \cdot {2^{29}}\left( {1 + {2^{ - 64}}} \right) \approx {2^{127}}$次25轮SIMON64/128算法加密，故总的计算复杂度约为${{\rm{2}}^{127}}$次25轮SIMON64/128算法加密，存储复杂度约为${{\rm{2}}^{{\rm{79}}{\rm{.21}}}}{\rm{ + }}{{\rm{2}}^{{\rm{87}}{\rm{.36}}}} \approx {{\rm{2}}^{{\rm{87}}{\rm{.37}}}}$ bit，约为${{\rm{2}}^{{\rm{85}}}}$ Byte。

4.   SIMON64算法改进的积分分析

本节利用Fu等人^[20]提出的等价密钥技术进一步降低密钥恢复过程的密钥猜测量和计算复杂度，给出SIMON64算法的改进的积分分析，基于此方法攻击轮数可以再增加一轮。本文先给出SIMON64/128算法的26轮积分分析。

如图6所示，利用等价密钥技术，可以将SIMON64/128算法最后一轮(第25轮)的子密钥${K_{25}}$移至上一轮中，其中图6(a)为最后2轮变换的原形式，图6(c)为相应的等价形式，前面几轮也可以类似处理。一般地，记第$j$轮的等价子密钥为$K_{j + 1}^*$，则有$K_{25}^* = {K_{25}}$, $K_j^* = {K_j} \oplus \left( {K_{j + 1}^{\rm{*}} < < < 2} \right)$，其中$19 \le j \le 24$，这些等价密钥$\left( {K_{19}^*,K_{20}^*,··· ,K_{25}^*} \right)$可以由原子密钥$\left( {{K_{19}},{K_{{\rm{20}}}}, ··· ,{K_{25}}} \right)$线性表出。

图 6  等价密钥技术示意图

下载: 全尺寸图片 幻灯片

从图6可以看出，采用等价密钥技术后算法的中间状态也会相应变成原状态和某些等价子密钥的异或，然而由于积分分析研究的是中间状态值求和的性质，而添加密钥常数不影响状态和的值，为叙述方便，下面仍用符号${X_i}$和${Y_i}$表示算法的中间状态。图7给出了等价密钥情形下对SIMON64/128算法进行26轮积分分析密钥恢复过程中需要猜测的子密钥比特和中间状态比特。攻击过程中需要猜测$K_{19,\left\{ {24,31} \right\}}^*$, $K_{20,\left\{ {16,22,23,29,30} \right\}}^*$, $K_{21,\left\{ {8,14,15,20\sim 22,27\sim 29} \right\}}^*$, $K_{22,\left\{ {0,6,7,12\sim 14,18\sim 21,25\sim 28} \right\}}^*$, $K_{23,\left\{ {4\sim 6,10\sim 13,16\sim 20,23\sim 27,30,31} \right\}}^*$, $K_{24,\left\{ {2\sim 5,8\sim 12,14\sim 19,21\sim 26,28\sim 30} \right\}}^*$和$K_{25,\left\{ {0\sim 4,6\sim 29} \right\}}^*$共102 bit子密钥，同样采用中间相遇方法降低计算复杂度。

图 7  SIMON64/128算法的26轮积分分析

下载: 全尺寸图片 幻灯片

注意到${Y_{18,\left\{ 0 \right\}}} = \left( {{X_{18,\left\{ {31} \right\}}} \wedge {X_{18,\left\{ {24} \right\}}}} \right) \oplus {Y_{19,\left\{ {30} \right\}}}$$\oplus {X_{19,\left\{ 0 \right\}}}$，判断$\oplus {Y_{18,\left\{ 0 \right\}}}$是否等于0可以转化为判断$\oplus \left( {\left( {{X_{18,\left\{ {31} \right\}}} \wedge {X_{18,\left\{ {{\rm{24}}} \right\}}}} \right) \oplus {X_{19,\left\{ 0 \right\}}}} \right)$=$\oplus {Y_{19,\left\{ {30} \right\}}}$是否成立。不妨记${M_1} = \left( {{X_{18,\left\{ {31} \right\}}} \wedge {X_{18,\left\{ {{\rm{24}}} \right\}}}} \right) \oplus {X_{19,\left\{ 0 \right\}}}$，${M_2} = {Y_{19,\left\{ {30} \right\}}}$，图8和图9分别给出了计算$\oplus {M_1}$和$\oplus {M_2}$的过程中需要猜测的等价子密钥比特和中间状态比特。

图 8  计算$\oplus {M_1}$的过程

下载: 全尺寸图片 幻灯片

图 9  计算$\oplus {M_{\rm{2}}}$的过程

下载: 全尺寸图片 幻灯片

表3和表4分别给出了计算$\oplus {M_1}$和$\oplus {M_{\rm{2}}}$的详细过程和复杂度分析。计算$\oplus {M_1}$时需要猜测89 bit子密钥，计算复杂度约为${2^{92.31}}$次26轮加密，存储复杂度约为${2^{89}} \cdot 90 \approx {2^{95.50}}$ bit，而计算$\oplus {M_{\rm{2}}}$时需要猜测69 bit子密钥，计算复杂度约为${2^{71.92}}$次26轮加密，存储复杂度约为${{\rm{2}}^{{\rm{69}}}} \cdot {\rm{70}} \approx {{\rm{2}}^{{\rm{75}}{\rm{.13}}}}$ bit。

表 3  计算$\oplus {M_1}$值的复杂度

步骤	猜测密钥(比特数)	统计状态(比特数)	时间复杂度
(1)	$-$	${X_{25,\left\{ {2\sim 5,8\sim 12,14\sim 19,21\sim 26,28\sim 30} \right\}}}$(24), ${Y_{25,\left\{ {0\sim 4,6\sim 29} \right\}}}$(29)	${2^{63} } \cdot \dfrac{ {29} }{ {32 \cdot 26} } \approx {2^{58.16} }$
(2)	$K_{25,\left\{ {0\sim 4,6\sim 11,13\sim 18,20\sim 29} \right\}}^{\rm{*}}$(27)	${X_{{\rm{24,}}\left\{ {{\rm{4\sim 6,10\sim 13,16\sim 20,23\sim 27,30,31}}} \right\}}}$(19), ${Y_{2{\rm{4}},\left\{ {2\sim 5,8\sim 12,14\sim 19,21\sim 26,28\sim 30} \right\}}}$(24)	${2^{27} } \cdot {2^{53} } \cdot \dfrac{ {24} }{ {32 \cdot 26} } \approx {2^{74.89} }$
(3)	$K_{{\rm{24,}}\left\{ {{\rm{2,5,9,12,16,19,23,26,30}}} \right\}}^{\rm{*}}$(9)	${X_{23,\left\{ {2,3,9,10,16,17,23,24,28} \right\}}}$(9), ${Y_{23,\left\{ {6,10,13,17,20,24,27,31} \right\}}}$(8), ${X_{24,\left\{ {4,11,18,25} \right\}}}$(4)	${2^{36} } \cdot {2^{43} } \cdot \dfrac{8}{ {32 \cdot 26} } \approx {2^{72.30} }$
(4)	$K_{24,\left\{ {3,10,17,24,28} \right\}}^*$(5)	${X_{23,\left\{ {0,3,4,6\sim 8,10\sim 15,17\sim 22,25\sim 29} \right\}}}$(23), ${Y_{23,\left\{ {4,11,18,25} \right\}}}$(4), ${X_{24,\left\{ {2,12,16,19,23,26,30} \right\}}}$(7)	${2^{41} } \cdot {2^{21} } \cdot \dfrac{4}{ {32 \cdot 26} } \approx {2^{54.30} }$
(5)	$K_{24,\left\{ {4,8,11,15,18,22,25,29} \right\}}^*$(8)	${X_{23,\left\{ {{\rm{0,6,}}7,12\sim 14,18\sim 21,25\sim 28} \right\}}}$(14), ${Y_{{\rm{23,}}\left\{ {{\rm{4\sim 6,10\sim 13,16\sim 20,23\sim 27,30,31}}} \right\}}}$(19)	${2^{49} } \cdot {2^{34} } \cdot \dfrac{ {19} }{ {32 \cdot 26} } \approx {2^{77.55} }$
(6)	$K_{23,\left\{ {4,11,18,25} \right\}}^*$(4)	${X_{22,\left\{ {4,5,11,12,18,19,25,26,30} \right\}}}$(9), ${Y_{{\rm{22,}}\left\{ {{\rm{12,19,26}}} \right\}}}$(3), ${X_{{\rm{23,}}\left\{ {{\rm{6,13,20,27}}} \right\}}}$(4)	${2^{53} } \cdot {2^{33} } \cdot \dfrac{3}{ {32 \cdot 26} } \approx {2^{77.88} }$
(7)	$K_{23,\left\{ {5,12,19,26} \right\}}^*$(4)	${X_{22,\left\{ {5,6,8,10,12\sim 17,19\sim 24,26\sim 31} \right\}}}$(22), ${Y_{22,\left\{ {6,13,20,27} \right\}}}$(4), ${X_{23,\left\{ {0,7,14,18,21,25,28} \right\}}}$(7)	${2^{57} } \cdot {2^{16} } \cdot \dfrac{4}{ {32 \cdot 26} } \approx {2^{65.30} }$
(8)	$K_{23,\left\{ {6,10,13,17,20,24,27,31} \right\}}^*$(8)	${X_{22,\left\{ {8,14,15,20\sim 22,27\sim 29} \right\}}}$(9), ${Y_{22,\left\{ {0,6,7,12\sim 14,18\sim 21,25\sim 28} \right\}}}$(14)	${2^{65} } \cdot {2^{33} } \cdot \dfrac{ {14} }{ {32 \cdot 26} } \approx {2^{92.11} }$
(9)	$K_{22,\left\{ {0,7,14,21,28} \right\}}^*$(5)	${X_{21,\left\{ {6,12,13,19,20,27,28} \right\}}}$(7), ${Y_{21,\left\{ {8,15,22,29} \right\}}}$(4), ${X_{22,\left\{ {14,21,28} \right\}}}$(3)	${2^{70} } \cdot {2^{23} } \cdot \dfrac{4}{ {32 \cdot 26} } \approx {2^{85.30} }$
(10)	$K_{22,\left\{ {6,13,20,27} \right\}}^*$(4)	${X_{21,\left\{ {12,16,18,19,22,23,25,26,29,30} \right\}}}$(10), ${Y_{21,\left\{ {14,21,28} \right\}}}$(3), ${X_{22,\left\{ {20,27} \right\}}}$(2)	${2^{74} } \cdot {2^{14} } \cdot \dfrac{3}{ {32 \cdot 26} } \approx {2^{79.88} }$
(11)	$K_{22,\left\{ {12,19,26} \right\}}^*$(4)	${X_{21,\left\{ {16,22,23,29,30} \right\}}}$(5), ${Y_{21,\left\{ {8,14,15,20\sim 22,27\sim 29} \right\}}}$(9)	${2^{77} } \cdot {2^{15} } \cdot \dfrac{9}{ {32 \cdot 26} } \approx {2^{85.47} }$
(12)	$K_{21,\left\{ {8,15,22,29} \right\}}^*$(4)	${X_{20,\left\{ {14,20,21,24,27,28,31} \right\}}}$(7), ${Y_{20,\left\{ {16,23,30} \right\}}}$(3), ${X_{21,\left\{ {22,29} \right\}}}$(2)	${2^{81} } \cdot {2^{14} } \cdot \dfrac{3}{ {32 \cdot 26} } \approx {2^{86.88} }$
(13)	$K_{21,\left\{ {14,21,28} \right\}}^*$(3)	${X_{20,\left\{ {24,31} \right\}}}$(2), ${Y_{20,\left\{ {16,22,23,29,30} \right\}}}$(5)	${2^{84} } \cdot {2^{12} } \cdot \dfrac{5}{ {32 \cdot 26} } \approx {2^{88.62} }$
(14)	$K_{20,\left\{ {16,23,30} \right\}}^*$(3)	${X_{19,\left\{ 0 \right\}}}$(1), ${Y_{19,\left\{ {24,31} \right\}}}$(2)	${2^{ {\rm{87} } } } \cdot { {\rm{2} }^{\rm{7} } } \cdot \dfrac{ {\rm{2} } }{ {32 \cdot 26} } \approx {2^{ {\rm{85} }{\rm{.30} } } }$
(15)	$K_{19,\left\{ {24,31} \right\}}^*$(2)	$\left( {{X_{18,\left\{ {31} \right\}}} \wedge {X_{18,\left\{ {{\rm{24}}} \right\}}}} \right) \oplus {X_{19,\left\{ 0 \right\}}}$(1)	${2^{ {\rm{89} } } } \cdot { {\rm{2} }^{\rm{3} } } \cdot \dfrac{ {\rm{1} } }{ {32 \cdot 26} } \approx {2^{ {\rm{82} }{\rm{.30} } } }$

下载: 导出CSV 

| 显示表格

表 4  计算$\oplus {M_{\rm{2}}}$值的复杂度

步骤	猜测密钥(比特数)	统计状态(比特数)	时间复杂度
(1)	$-$	${X_{25,\left\{ {2\sim 4,8\sim 11,14\sim 18,20\sim 24,28,29} \right\}}}$(19), ${Y_{25,\left\{ {0\sim 3,6\sim 10,12\sim 23,26\sim 28} \right\}}}$(24)	${2^{63} } \cdot \dfrac{ { {\rm{24} } } }{ {32 \cdot 26} } \approx {2^{5{\rm{7} }{\rm{.89} } } }$
(2)	$K_{25\left\{ {0\sim 3,6\sim 10,12\sim 17,19\sim 23,26\sim 28} \right\}}^*$(22)	${X_{24,\left\{ {4,5,10\sim 12,16\sim 19,22\sim 25,30} \right\}}}$(14), ${Y_{24,\left\{ {2\sim 4,8\sim 11,14\sim 18,20\sim 24,28,29} \right\}}}$(19)	${2^{ {\rm{22} } } } \cdot { {\rm{2} }^{ {\rm{43} } } } \cdot \dfrac{ { {\rm{19} } } }{ {32 \cdot 26} } \approx {2^{ {\rm{59} }{\rm{.55} } } }$
(3)	$K_{24\left\{ {2\sim 4,8\sim 11,14\sim 18,21\sim 24,28,29} \right\}}^*$(18)	${X_{23,\left\{ {6,12,13,18\sim 20,24\sim 27} \right\}}}$(10), ${Y_{23,\left\{ {4,5,10\sim 12,16\sim 19,22\sim 25,30} \right\}}}$(14)	${2^{ {\rm{40} } } } \cdot { {\rm{2} }^{ {\rm{33} } } } \cdot \dfrac{ { {\rm{14} } } }{ {32 \cdot 26} } \approx {2^{ {\rm{67} }{\rm{.11} } } }$
(4)	$K_{23,\left\{ {4,5,10\sim 12,16\sim 19,23\sim 25,30} \right\}}^*$(13)	${X_{22,\left\{ {14,20,21,26\sim 28} \right\}}}$(6), ${Y_{22,\left\{ {6,12,13,18\sim 20,24\sim 27} \right\}}}$(10)	${2^{ {\rm{5} }3} } \cdot { {\rm{2} }^{ {\rm{24} } } } \cdot \dfrac{ { {\rm{1} }0} }{ {32 \cdot 26} } \approx {2^{ {\rm{70} }{\rm{.63} } } }$
(5)	$K_{22\left\{ {6,12,13,18\sim 20,25\sim 27} \right\}}^*$(9)	${X_{21,\left\{ {22,28,29} \right\}}}$(3), ${Y_{21,\left\{ {14,20,21,26\sim 28} \right\}}}$(6)	${2^{6{\rm{2} } } } \cdot { {\rm{2} }^{ {\rm{16} } } } \cdot \dfrac{ {\rm{6} } }{ {32 \cdot 26} } \approx {2^{ {\rm{70} }{\rm{.89} } } }$
(6)	$K_{21\left\{ {14,20,21,27,28} \right\}}^*$(5)	${X_{20,\left\{ {30} \right\}}}$(1), ${Y_{20,\left\{ {22,28,29} \right\}}}$(3)	${2^{6{\rm{7} } } } \cdot { {\rm{2} }^{\rm{9} } } \cdot \dfrac{3}{ {32 \cdot 26} } \approx {2^{ {\rm{67} }{\rm{.89} } } }$
(6)	$K_{20\left\{ {22,29} \right\}}^*$(2)	$\oplus {Y_{19,\left\{ {30} \right\}}}$(1)	${2^{6{\rm{9} } } } \cdot { {\rm{2} }^{\rm{4} } } \cdot \dfrac{ {\rm{1} } }{ {32 \cdot 26} } \approx {2^{ {\rm{63} }{\rm{.30} } } }$

下载: 导出CSV 

| 显示表格

复杂度分析：同第3节的分析。26轮SIMON64/128算法积分分析总的计算复杂度约为${2^{92.31}} + {2^{71.92}} + {2^{101 + 26}}\left( {1 + {2^{ - 64}}} \right) \approx {2^{127}}$次26轮算法加密，存储复杂度约为${2^{95.5}} + {2^{75.13}} \approx {2^{95.5}}$ bit，约为${{\rm{2}}^{{\rm{93}}}}$ Byte。

5.   结束语

本文考虑了SIMON64算法的积分分析，先利用中间相遇和部分和技术给出了25轮SIMON64/128算法的积分分析，接着利用等价密钥技术实现了更高一轮的积分分析。类似的方法，同样可以考虑更高分组长度的SIMON算法的积分分析，本文及对更高分组长度SIMON算法的攻击结果见表5。结合已有的攻击结果可以看出，随着SIMON算法版本的提高，积分分析能攻击的轮数并没有明显提高，相对而言它们具有更强的抵抗积分分析的能力。

表 5  SIMON算法的积分分析(分组长度64/96/128-bit)

算法	区分器轮数	数据量(CP)	攻击轮数	猜测密钥量(bit)	攻击复杂度(E)
SIMON64/96	18	${{\rm{2}}^{63}}$	25	73	${{\rm{2}}^{{\rm{95}}}}$
SIMON64/128	18	${{\rm{2}}^{63}}$	26	102	${{\rm{2}}^{127}}$
SIMON96/96	22	${{\rm{2}}^{{\rm{95}}}}$	28	64	${{\rm{2}}^{{\rm{95}}}}$
SIMON96/144	22	${{\rm{2}}^{{\rm{95}}}}$	30	138	${{\rm{2}}^{{\rm{95}}}}$
SIMON128/128	26	${{\rm{2}}^{{\rm{127}}}}$	33	98	${{\rm{2}}^{{\rm{127}}}}$
SIMON128/192	26	${{\rm{2}}^{{\rm{127}}}}$	35	187	${{\rm{2}}^{{\rm{127}}}}$
SIMON128/256	26	${{\rm{2}}^{{\rm{127}}}}$	36	241	${{\rm{2}}^{{\rm{127}}}}$

下载: 导出CSV 

| 显示表格