Integral Attacks on SIMON64
-
摘要:
SIMON系列算法自提出以来便受到了广泛关注。积分分析方面，Wang，Fu和Chu等人给出了SIMON32和SIMON48算法的积分分析，该文在已有的分析结果上，进一步考虑了更长分组的SIMON64算法的积分分析。基于Xiang等人找到的18轮积分区分器，该文先利用中间相遇技术和部分和技术给出了25轮SIMON64/128算法的积分分析，接着利用等价密钥技术进一步降低了攻击过程中需要猜测的密钥量，并给出了26轮SIMON64/128算法的积分分析。通过进一步的分析，该文发现高版本的SIMON算法具有更好抵抗积分分析的能力。
Abstract:The SIMON block cipher receives extensive attention since its proposed. With respect to integral attacks, some integral attacks on SIMON32 and SIMON48 are presented by Wang, Fu and Chu et al. In this paper, on the basis of the existing analysis results, the integral attacks on SIMON64 are further studied. Based on known 18-round integral distinguisher presented by Xiang et al., the integral attacks on 25-round SIMON64/128 are presented using meet-in-the-middle and partial-sum techniques. Then the amount of subkeys that need to be guessed during the attack is further reduced by equivalent-subkey technique, and the improved integral attacks on 26-round SIMON64/128 are also presented. Through further analysis, it is found that the higher version of SIMON algorithm has better resistance to integral analysis.
-
Key words:
- Equivalent-subkey /
- SIMON 64 /
- Meet-in-the-middle /
- Partial-sum /
- Integral attacks
-
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$ 轮的输出为$$\left( {{X_{r + 1}},{Y_{r + 1}}} \right) = \left( {F\left( {{X_r}} \right) \oplus {Y_r} \oplus {K_r},{X_r}} \right)$$ (1) 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)的关系$${K_{i + m}} = \left\{ \begin{array}{l} c \oplus {z_{j,\left\{ i \right\}}} \oplus {K_i} \oplus \left( {{K_{i + 1}} > > > 3} \right) \oplus \left( {{K_{i + 1}} > > > 4} \right),\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\quad\; m = 2 \\ c \oplus {z_{j,\left\{ i \right\}}} \oplus {K_i} \oplus \left( {{K_{i + 2}} > > > 3} \right) \oplus \left( {{K_{i + 2}} > > > 4} \right) ,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\quad\; m = 3 \\ c \oplus {z_{j,\left\{ i \right\}}} \oplus {K_i} \oplus {K_{i + 1}} \oplus \left( {{K_{i + 1}} > > > 1} \right) \oplus \left( {{K_{i + 3}} > > > 3} \right) \oplus \left( {{K_{i + 3}} > > > 4} \right),\;\;\;\;\;\;\;\;m = 4 \\ \end{array} \right.$$ (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所示的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}}}}$ 。下面采用中间相遇技术和部分和技术来降低密钥恢复过程的计算复杂度。注意到
${\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子密钥。对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} }$ 表 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} }$ (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可以看出，采用等价密钥技术后算法的中间状态也会相应变成原状态和某些等价子密钥的异或，然而由于积分分析研究的是中间状态值求和的性质，而添加密钥常数不影响状态和的值，为叙述方便，下面仍用符号
${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子密钥，同样采用中间相遇方法降低计算复杂度。注意到
${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}$ 的过程中需要猜测的等价子密钥比特和中间状态比特。表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} } } }$ 表 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} } } } $ 复杂度分析：同第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}}}}$ -
表 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
表 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
表 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
-
KNUDSEN L and WAGNER D. Integral cryptanalysis[C]. The 9th International Workshop on Fast Software Encryption, Leuven, Belgium, 2002: 112–127. DAEMEN J, KNUDSEN L, and RIJMEN V. The block cipher Square[C]. The 4th International Workshop on Fast Software Encryption, Haifa, Israel, 1997: 149–165. FERGUSON N, KELSEY J, LUCKS S, et al. Improved cryptanalysis of rijndael[C]. The 7th International Workshop on Fast Software Encryption, New York, USA, 2001: 213–230. TODO Y. Integral cryptanalysis on full MISTY1[C]. The 35th Annual Cryptology Conference, Santa Barbara, USA, 2015: 413–432. BEAULIEU R, SHORS D, SMITH J, et al. The SIMON and SPECK families of lightweight block ciphers[EB/OL]. https: //eprint.iacr.org/2013/404, 2013. ABED F, LIST E, LUCKS S, et al. Differential cryptanalysis of round-reduced SIMON and SPECK[C]. The 21st International Workshop on Fast Software Encryption, London, UK, 2015: 525–545. BIRYUKOV A, ROY A, and VELICHKOV V. Differential analysis of block ciphers SIMON and SPECK[C]. The 21st International Workshop on Fast Software Encryption, London, UK, 2015: 546–570. KÖLBL S, LEANDER G, and TIESSEN T. Observations on the SIMON block cipher family[C]. The 35th Annual Cryptology Conference, Santa Barbara, USA, 2015: 161–185. QIAO Kexin, HU Lei, and SUN Siwei. Differential analysis on simeck and simon with dynamic key-guessing techniques[C]. The 2nd International Conference on Information Systems Security and Privacy, Rome, Italy, 2017: 64–85. LIU Zhengbin, LI Yongqiang, and WANG Mingsheng. Optimal differential trails in SIMON-like ciphers[J]. IACR Transactions on Symmetric Cryptology, 2017(1): 358–379. doi: 10.13154/tosc.v2017.i1.358-379 WANG Ning, WANG Xiaoyun, JIA Keting, et al. Differential attacks on reduced SIMON versions with dynamic key-guessing techniques[J]. Science China Information Sciences, 2018, 61(9): 098103. doi: 10.1007/s11432-017-9231-5 ALIZADEH J, ALKHZAIMI H A, AREF M R, et al. Cryptanalysis of SIMON variants with connections[C]. The 10th International Workshop on Radio Frequency Identification: Security and Privacy Issues, Oxford, United Kingdom, 2014: 90–107. ABDELRAHEEM N A, ALIZADEH J, ALKHZAIMI H A, et al. Improved linear cryptanalysis of reduced-round SIMON[EB/OL]. https: //eprint.iacr.org/2014/681, 2014. CHEN Huaifeng and WANG Xiaoyun. Improved linear hull attack on round-reduced Simon with dynamic key-guessing techniques[C]. The 23rd International Conference on Fast Software Encryption, Bochum, Germany, 2016: 428–449. WANG Qingju, LIU Zhiqiang, VARICI K, et al. Cryptanalysis of reduced-round SIMON32 and SIMON48[C]. The 15th International Conference on Cryptology in India, New Delhi, India, 2014: 143–160. BOURA C, NAYA-PLASENCIA M, and SUDER V. Scrutinizing and improving impossible differential attacks: Applications to CLEFIA, Camellia, LBlock and Simon[C]. The 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, China, 2014: 179–199. 陈展, 王宁. SIMON算法的不可能差分分析[J]. 密码学报, 2015, 2(6): 505–514. doi: 10.13868/j.cnki.jcr.000097CHEN Zhan and WANG Ning. Impossible differential cryptanalysis of reduced-round SIMON[J]. Journal of Cryptologic Research, 2015, 2(6): 505–514. doi: 10.13868/j.cnki.jcr.000097 YU Xiaoli, WU Wenling, SHI Zhenqing, et al. Zero-correlation linear cryptanalysis of reduced-round SIMON[J]. Journal of Computer Science and Technology, 2015, 30(6): 1358–1369. doi: 10.1007/s11390-015-1603-5 XIANG Zejun, ZHANG Wentao, BAO Zhenzhen, et al. Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers[C]. The 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, 2016: 648–678. FU Kai, SUN Ling, and WANG Meiqin. New integral attacks on SIMON[J]. IET Information Security, 2017, 11(5): 277–286. doi: 10.1049/iet-ifs.2016.0241 CHU Zhihui, CHEN Huaifeng, WANG Xiaoyun, et al. Improved integral attacks on SIMON32 and SIMON48 with dynamic key-guessing techniques[J]. Security and Communication Networks, 2018: 5160237. doi: 10.1155/2018/5160237 期刊类型引用(1)
1. 叶涛，韦永壮，李灵琛. ACE密码算法的积分分析. 电子与信息学报. 2021(04): 908-914 . 
本站查看其他类型引用(1)
-
下载:
计量
- 文章访问数: 2382
- HTML全文浏览量: 871
- PDF下载量: 114
- 被引次数: 2
下载:
