Differential-Linear Cryptanalysis of the SIMON Algorithm

doi:10.3969/j.issn.1671-1122.2022.09.008

Abstract

Abstract:

Differential cryptanalysis and linear cryptanalysis are currently the two most common methods to evaluate the security of block ciphers. Differential-linear cryptanalysis is an analysis method based on these two methods, which has been widely studied by the cryptography community in recent years. SIMON algorithm is an important lightweight block cipher, this paper mainly performed differential-linear attacks on SIMON 32/64 and SIMON 48, constructed 13 rounds differential-linear distinguishers respectively, made 16 rounds of key recovery attacks, whose data complexities are 2²⁶ and 2⁴², and time complexities are 2^40.59 and 2^61.59 respectively, thereby increased the security evaluation dimension of the SIMON algorithm and enriched the actual cases of differential-linear cryptanalysis.

Key words: lightweight block ciphers, differential-linear cryptanalysis, SIMON algorithm

CLC Number:

TP309

HU Yujia, DAI Zhengyi, SUN Bing. Differential-Linear Cryptanalysis of the SIMON Algorithm[J]. Netinfo Security, 2022, 22(9): 63-75.

Figures/Tables 17

等式左边	等式右边
$L_{7}^{13}$	$\begin{align} & (R_{7}^{16}\odot R_{14}^{16}\oplus R_{13}^{16}\oplus L_{15}^{16}\underrightarrow{\oplus K_{15}^{15}})\odot (R_{14}^{16}\odot R_{5}^{16}\oplus R_{4}^{16}\oplus L_{6}^{16}\underrightarrow{\oplus K_{6}^{15}}) \\ & \oplus (R_{13}^{16}\odot R_{4}^{16}\oplus R_{3}^{16}\oplus L_{5}^{16}\underleftarrow{\oplus K_{5}^{15}})\oplus R_{7}^{16}\underleftarrow{\oplus K_{7}^{14}} \\ \end{align}$
$L_{13}^{13}$	$\begin{align} & (R_{13}^{16}\odot R_{4}^{16}\oplus R_{3}^{16}\oplus L_{5}^{16}\underrightarrow{\oplus K_{5}^{15}})\odot (R_{4}^{16}\odot R_{11}^{16}\oplus R_{10}^{16}\oplus L_{12}^{16}\underrightarrow{\oplus K_{12}^{15}}) \\ & \oplus (R_{3}^{16}\odot R_{10}^{16}\oplus R_{9}^{16}\oplus L_{11}^{16}\underleftarrow{\oplus K_{11}^{15}})\oplus R_{13}^{16}\underleftarrow{\oplus K_{13}^{14}} \\ \end{align}$
$R_{3}^{13}$	$\begin{align} & [(R_{11}^{16}\odot R_{2}^{16}\oplus R_{1}^{16}\oplus L_{3}^{16}\underrightarrow{\oplus K_{3}^{15}})\odot (R_{2}^{16}\odot R_{9}^{16}\oplus R_{8}^{16}\oplus L_{10}^{16}\underrightarrow{\oplus K_{10}^{15}}) \\ & \oplus (R_{1}^{16}\odot R_{8}^{16}\oplus R_{7}^{16}\oplus L_{9}^{16}\underrightarrow{\oplus K_{9}^{15}})\oplus R_{11}^{16}\underrightarrow{\oplus K_{11}^{14}}] \\ & \odot [(R_{2}^{16}\odot R_{9}^{16}\oplus R_{8}^{16}\oplus L_{10}^{16}\underrightarrow{\oplus K_{10}^{15}})\odot (R_{9}^{16}\odot R_{0}^{16}\oplus R_{15}^{16}\oplus L_{1}^{16}\underrightarrow{\oplus K_{1}^{15}}) \\ & \oplus (R_{8}^{16}\odot R_{15}^{16}\oplus R_{14}^{16}\oplus L_{0}^{16}\underrightarrow{\oplus K_{0}^{15}})\oplus R_{2}^{16}\underrightarrow{\oplus K_{2}^{14}}] \\ & \oplus [(R_{1}^{16}\odot R_{8}^{16}\oplus R_{7}^{16}\oplus L_{9}^{16}\underrightarrow{\oplus K_{9}^{15}})\odot (R_{8}^{16}\odot R_{15}^{16}\oplus R_{14}^{16}\oplus L_{0}^{16}\underrightarrow{\oplus K_{0}^{15}}) \\ & \oplus (R_{7}^{16}\odot R_{14}^{16}\oplus R_{13}^{16}\oplus L_{15}^{16}\underleftarrow{\oplus K_{15}^{15}})\oplus R_{1}^{16}\underleftarrow{\oplus K_{1}^{14}}] \\ & \oplus (R_{11}^{16}\odot R_{2}^{16}\oplus R_{1}^{16}\oplus L_{3}^{16}\underleftarrow{\oplus K_{3}^{15}})\underleftarrow{\oplus K_{3}^{13}} \\ \end{align}$
$R_{11}^{13}$	$\begin{align} & [(R_{3}^{16}\odot R_{10}^{16}\oplus R_{9}^{16}\oplus L_{11}^{16}\underrightarrow{\oplus K_{11}^{15}})\odot (R_{10}^{16}\odot R_{1}^{16}\oplus R_{0}^{16}\oplus L_{2}^{16}\underrightarrow{\oplus K_{2}^{15}}) \\ & \oplus (R_{9}^{16}\odot R_{0}^{16}\oplus R_{15}^{16}\oplus L_{1}^{16}\underrightarrow{\oplus K_{1}^{15}})\oplus R_{3}^{16}\underrightarrow{\oplus K_{3}^{14}}] \\ & \odot [(R_{10}^{16}\odot R_{1}^{16}\oplus R_{0}^{16}\oplus L_{2}^{16}\underrightarrow{\oplus K_{2}^{15}})\odot (R_{1}^{16}\odot R_{8}^{16}\oplus R_{7}^{16}\oplus L_{9}^{16}\underrightarrow{\oplus K_{9}^{15}}) \\ & \oplus (R_{0}^{16}\odot R_{7}^{16}\oplus R_{6}^{16}\oplus L_{8}^{16}\underrightarrow{\oplus K_{8}^{15}})\oplus R_{10}^{16}\underrightarrow{\oplus K_{10}^{14}}] \\ & \oplus [(R_{9}^{16}\odot R_{0}^{16}\oplus R_{15}^{16}\oplus L_{1}^{16}\underrightarrow{\oplus K_{1}^{15}})\odot (R_{0}^{16}\odot R_{7}^{16}\oplus R_{6}^{16}\oplus L_{8}^{16}\underrightarrow{\oplus K_{8}^{15}}) \\ & \oplus (R_{15}^{16}\odot R_{6}^{16}\oplus R_{5}^{16}\oplus L_{7}^{16}\underleftarrow{\oplus K_{7}^{15}})\oplus R_{9}^{16}\underleftarrow{\oplus K_{9}^{14}}] \\ & \oplus (R_{3}^{16}\odot R_{10}^{16}\oplus R_{9}^{16}\oplus L_{11}^{16}\underleftarrow{\oplus K_{11}^{15}})\underleftarrow{\oplus K_{11}^{13}} \\ \end{align}$

等式左边	等式右边
$L_{0}^{13}$	$\begin{align} & (R_{8}^{16}\odot R_{15}^{16}\oplus R_{14}^{16}\oplus L_{16}^{16}\underrightarrow{\oplus K_{16}^{15}})\odot (R_{15}^{16}\odot R_{22}^{16}\oplus R_{21}^{16}\oplus L_{23}^{16}\underrightarrow{\oplus K_{23}^{15}}) \\ & \oplus (R_{14}^{16}\odot R_{21}^{16}\oplus R_{20}^{16}\oplus L_{22}^{16}\underleftarrow{\oplus K_{22}^{15}})\oplus R_{0}^{16}\underleftarrow{\oplus K_{0}^{14}} \\ \end{align}$
$L_{16}^{13}$	$\begin{align} & (R_{0}^{16}\odot R_{7}^{16}\oplus R_{6}^{16}\oplus L_{8}^{16}\underrightarrow{\oplus K_{8}^{15}})\odot (R_{7}^{16}\odot R_{14}^{16}\oplus R_{13}^{16}\oplus L_{15}^{16}\underrightarrow{\oplus K_{15}^{15}}) \\ & \oplus (R_{6}^{16}\odot R_{13}^{16}\oplus R_{12}^{16}\oplus L_{14}^{16}\underleftarrow{\oplus K_{14}^{15}})\oplus R_{16}^{16}\underleftarrow{\oplus K_{16}^{14}} \\ \end{align}$
$R_{2}^{13}$	$\begin{align} & [(R_{2}^{16}\odot R_{9}^{16}\oplus R_{8}^{16}\oplus L_{10}^{16}\underrightarrow{\oplus K_{10}^{15}})\odot (R_{9}^{16}\odot R_{16}^{16}\oplus R_{15}^{16}\oplus L_{17}^{16}\underrightarrow{\oplus K_{17}^{15}}) \\ & \oplus (R_{8}^{16}\odot R_{15}^{16}\oplus R_{14}^{16}\oplus L_{16}^{16}\underrightarrow{\oplus K_{16}^{15}})\oplus R_{18}^{16}\underrightarrow{\oplus K_{18}^{14}}] \\ & \odot [(R_{9}^{16}\odot R_{16}^{16}\oplus R_{15}^{16}\oplus L_{17}^{16}\underrightarrow{\oplus K_{17}^{15}})\odot (R_{16}^{16}\odot R_{23}^{16}\oplus R_{22}^{16}\oplus L_{0}^{16}\underrightarrow{\oplus K_{0}^{15}}) \\ & \oplus (R_{15}^{16}\odot R_{22}^{16}\oplus R_{21}^{16}\oplus L_{23}^{16}\underrightarrow{\oplus K_{23}^{15}})\oplus R_{1}^{16}\underrightarrow{\oplus K_{1}^{14}}] \\ & \oplus [(R_{8}^{16}\odot R_{15}^{16}\oplus R_{14}^{16}\oplus L_{16}^{16}\underrightarrow{\oplus K_{16}^{15}})\odot (R_{15}^{16}\odot R_{22}^{16}\oplus R_{21}^{16}\oplus L_{23}^{16}\underrightarrow{\oplus K_{23}^{15}}) \\ & \oplus (R_{14}^{16}\odot R_{21}^{16}\oplus R_{20}^{16}\oplus L_{22}^{16}\underleftarrow{\oplus K_{22}^{15}})\oplus R_{0}^{16}\underleftarrow{\oplus K_{0}^{14}}] \\ & \oplus (R_{18}^{16}\odot R_{1}^{16}\oplus R_{0}^{16}\oplus L_{2}^{16}\underleftarrow{\oplus K_{2}^{15}})\underleftarrow{\oplus K_{2}^{13}} \\ \end{align}$
$R_{14}^{13}$	$\begin{align} & [(R_{14}^{16}\odot R_{21}^{16}\oplus R_{20}^{16}\oplus L_{22}^{16}\underrightarrow{\oplus K_{22}^{15}})\odot (R_{21}^{16}\odot R_{4}^{16}\oplus R_{3}^{16}\oplus L_{5}^{16}\underrightarrow{\oplus K_{5}^{15}}) \\ & \oplus (R_{20}^{16}\odot R_{3}^{16}\oplus R_{2}^{16}\oplus L_{4}^{16}\underrightarrow{\oplus K_{4}^{15}})\oplus R_{6}^{16}\underrightarrow{\oplus K_{6}^{14}}] \\ & \odot [(R_{21}^{16}\odot R_{4}^{16}\oplus R_{3}^{16}\oplus L_{5}^{16}\underrightarrow{\oplus K_{5}^{15}})\odot (R_{4}^{16}\odot R_{11}^{16}\oplus R_{10}^{16}\oplus L_{12}^{16}\underrightarrow{\oplus K_{12}^{15}}) \\ & \oplus (R_{3}^{16}\odot R_{10}^{16}\oplus R_{9}^{16}\oplus L_{11}^{16}\underrightarrow{\oplus K_{11}^{15}})\oplus R_{13}^{16}\underrightarrow{\oplus K_{13}^{14}}] \\ & \oplus [(R_{20}^{16}\odot R_{3}^{16}\oplus R_{2}^{16}\oplus L_{4}^{16}\underrightarrow{\oplus K_{4}^{15}})\odot (R_{3}^{16}\odot R_{10}^{16}\oplus R_{9}^{16}\oplus L_{11}^{16}\underrightarrow{\oplus K_{11}^{15}}) \\ & \oplus (R_{2}^{16}\odot R_{9}^{16}\oplus R_{8}^{16}\oplus L_{10}^{16}\underleftarrow{\oplus K_{10}^{15}})\oplus R_{12}^{16}\underleftarrow{\oplus K_{12}^{14}}] \\ & \oplus (R_{6}^{16}\odot R_{13}^{16}\oplus R_{12}^{16}\oplus L_{14}^{16}\underleftarrow{\oplus K_{14}^{15}})\underleftarrow{\oplus K_{14}^{13}} \\ \end{align}$
$R_{18}^{13}$	$\begin{align} & [(R_{18}^{16}\odot R_{1}^{16}\oplus R_{0}^{16}\oplus L_{2}^{16}\underrightarrow{\oplus K_{2}^{15}})\odot (R_{1}^{16}\odot R_{8}^{16}\oplus R_{7}^{16}\oplus L_{9}^{16}\underrightarrow{\oplus K_{9}^{15}}) \\ & \oplus (R_{0}^{16}\odot R_{7}^{16}\oplus R_{6}^{16}\oplus L_{8}^{16}\underrightarrow{\oplus K_{8}^{15}})\oplus R_{10}^{16}\underrightarrow{\oplus K_{10}^{14}}] \\ & \odot [(R_{1}^{16}\odot R_{8}^{16}\oplus R_{7}^{16}\oplus L_{9}^{16}\underrightarrow{\oplus K_{9}^{15}})\odot (R_{8}^{16}\odot R_{15}^{16}\oplus R_{14}^{16}\oplus L_{16}^{16}\underrightarrow{\oplus K_{16}^{15}}) \\ & \oplus (R_{7}^{16}\odot R_{14}^{16}\oplus R_{13}^{16}\oplus L_{15}^{16}\underrightarrow{\oplus K_{15}^{15}})\oplus R_{17}^{16}\underrightarrow{\oplus K_{17}^{14}}] \\ & \oplus [(R_{0}^{16}\odot R_{7}^{16}\oplus R_{6}^{16}\oplus L_{8}^{16}\underrightarrow{\oplus K_{8}^{15}})\odot (R_{7}^{16}\odot R_{14}^{16}\oplus R_{13}^{16}\oplus L_{15}^{16}\underrightarrow{\oplus K_{15}^{15}}) \\ & \oplus (R_{6}^{16}\odot R_{13}^{16}\oplus R_{12}^{16}\oplus L_{14}^{16}\underleftarrow{\oplus K_{14}^{15}})\oplus R_{16}^{16}\underleftarrow{\oplus K_{16}^{14}}] \\ & \oplus (R_{10}^{16}\odot R_{17}^{16}\oplus R_{16}^{16}\oplus L_{18}^{16}\underleftarrow{\oplus K_{18}^{15}})\underleftarrow{\oplus K_{18}^{13}} \\ \end{align}$

References 23

[1]	FIPS. FIPS 46 Data Encryption Standard[EB/OL]. (1977-01-15)[2022-03-21]. https://csrc.nist.gov/publications/detail/fips/46/archive/1977-01-15.
[2]	DIFFIE W, HELLMAN M E. Special Feature Exhaustive Cryptanalysis of the NBS Data Encryption Standard[J]. Computer, 1977, 10(6): 74-84.
[3]	BIHAM E, SHAMIR A. Differential Cryptanalysis of DES-Like Cryptosystems[C]// Springer. 10th Annual International Cryptology Conference. Berlin: Springer, 1990: 2-21.
[4]	MATSUI M. Linear Cryptanalysis Method for DES Cipher[C]// Springer. Workshop on the Theory and Application of of Cryptographic Techniques. Berlin:Springer, 1993: 386-397.
[5]	LANGFORD S, HELLMAN M E. Differential-Linear Cryptanalysis[C]// Springer. 14th Annual International Cryptology Conference. Berlin: Springer, 1994: 17-25.
[6]	BIHAM E, DUNKELMAN O, KELLER N. Enhancing Differential-Linear Cryptanalysis[C]// Springer. 8th International Conference on the Theory and Application of Cryptology and Information Security. Berlin:Springer, 2002: 254-266.
[7]	LU Jiqiang. A Methodology for Differential-Linear Cryptanalysis and Its Applications[C]// Springer. 19th International Workshop. Berlin:Springer, 2012: 69-89.
[8]	BAR-ON A, DUNKELMAN O, KELLER N, et al. DLCT: A New Tool for Differential-Linear Cryptanalysis[C]// Springer. 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2019: 313-342.
[9]	CANTEAUT A, KOLSCH L, LI Chao, et al. Autocorrelations of Vectorial Boolean functions[C]// Springer. 7th International Conference on Cryptology and Information Security in Latin America. Berlin:Springer, 2021: 233-253.
[10]	LIU Meicheng, LU Xiaojuan, LIN Dongdai. Differential-Linear Cryptanalysis from an Algebraic Perspective[C]// Springer. 41st Annual International Cryptology Conference. Berlin:Springer, 2021: 247-277.
[11]	HE Yeping, WU Wenling, QING Sihan. Truncated Differential-Linear Cryptanalysis[J]. Journal of Software, 2000, 11(10): 1294-1298.
	贺也平, 吴文玲, 卿斯汉. 截断差分—线性密码分析[J]. 软件学报, 2000, 11(10): 1294-1298.
[12]	BIHAM E, DUNKELMAN O, NATHAN Keller. Differential-Linear Cryptanalysis of Serpent[C]// Springer. 10th International Workshop. Berlin:Springer, 2003: 9-21.
[13]	BLONDEAU C, GREGOR L, NYBERG K. Differential-Linear Cryptanalysis Revisited[J]. Journal of Cryptology, 2017, 30(3): 859-888.
[14]	BEAULIEU R, SHORS D, SMITH J, et al. The SIMON and SPECK Families of Lightweight Block Ciphers[C]// ACM. 52nd Annual Design Automation Conference. New York: ACM, 2015: 1-6.
[15]	ALKHZAIMI H A, LAURIDSEN M M. Cryptanalysis of the SIMON Family of Block Ciphers[EB/OL]. (2013-08-30)[2022-03-05]. https://eprint.iacr.org/2013/543.
[16]	SUN Siwei, HU Lei, WANG Peng, et a1. Automatic Security Evaluation and (Related-Key) Differential Characteristic Search: Application to SIMON, PRESENT, LBlock, DES(L) and Other Bit-Oriented Block Ciphers[C]// Springer. 20th International Conference on the Theory and Application of Cryptology and Information Security. Berlin:Springer, 2014: 158-178.
[17]	ABDELRAHEEM M A, ALIZADEH J, ALKHZAIMI H A, et al. Improved Linear Cryptanalysis of Reduced-Round SIMON-32 and SIMON-48[C]// Springer. 16th International Conference on Cryptology. Berlin:Springer, 2015: 153-179.
[18]	LIU Zhengbin, LI Yongqiang, WANG Mingsheng. The Security of SIMON-Like Ciphers against Linear Cryptanalysis[EB/OL]. (2017-06-13)[2022-03-21]. https://eprint.iacr.org/2017/576.pdf.
[19]	TODO Y. Structural Evaluation by Generalized Integral Property[C]// Springer. 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2015: 287-314.
[20]	TODO Y, MORII M. Bit-Based Division Property and Application to SIMON Family[C]// Springer. 23rd International Conference. Berlin:Springer, 2016: 357-377.
[21]	XIANG Zejun, ZHANG Wentao, LIN Dongdai. On the Division Property of Simon 48 and Simon 64[EB/OL]. (2016-09-06)[2022-03-21]. https://eprint.iacr.org/2016/839.
[22]	CHEN Yanqin, ZHANG Wenying. Differential-Linear Cryptanalysis of SIMON 32/64[J]. International Journal of Embedded Systems, 2018, 10(3): 196-202.
[23]	LI Chao, SUN Bing, LI Ruilin. Attack Method and Example Analysis of Block Cipher[M]. Beijing: Science Press, 2010.
	李超, 孙兵, 李瑞林. 分组密码的攻击方法与实例分析[M]. 北京: 科学出版社, 2010.

算法类型	区分器轮数/轮	密钥恢复攻击轮数/轮	数据复杂度	存储复杂度	时间复杂度
SIMON 32/64	13	15	${{2}^{26}}$	${{2}^{26}}$	${{2}^{27.09}}$
SIMON 32/64	13	16	${{2}^{26}}$	${{2}^{26}}$	${{2}^{40.59}}$
SIMON 48	13	15	${{2}^{42}}$	${{2}^{42}}$	${{2}^{45.19}}$
SIMON 48	13	16	${{2}^{42}}$	${{2}^{42}}$	${{2}^{61.59}}$

类型	状态大小/bit	主密钥大小/bit	轮数/轮	n	m
SIMON32/64	32	64	32	16	4
SIMON48/72	48	72	36	24	3
SIMON48/96	48	96	36	24	4

$\lambda _{in}^{1}$	$\lambda _{in}^{2}$	${{\lambda }_{out}}$	${{p}^{*}}$	${{p}^{*}}-1/2$
0	0	0	1	1/2
0	0	1	3/4	1/4
0	1	1	3/4	1/4
1	0	1	3/4	1/4
1	1	1	3/4	1/4

轮数/轮	掩码（左）	掩码（右）	线性偏差
0	0000 0000 0000 1000	0000 0000 0000 0000	—
1	0000 0000 0000 0000	0000 0000 0000 1000	${{2}^{-1}}$
2	0000 0000 0000 1000	0000 0000 0000 0010	${{2}^{-2}}$
3	0000 0000 0000 0010	1000 0000 0000 1000	${{2}^{-2}}$
4	1000 0000 0000 1000	0010 0000 1000 0000	${{2}^{-3}}$
5	0010 0000 1000 0000	0000 1000 0000 1000	${{2}^{-3}}$

轮数/轮	掩码（左）	掩码（右）	线性偏差
0	0000 0000 0000 0000 0000 0000	0000 0000 0000 0000 0000 0100	—
1	0000 0000 0000 0000 0000 0100	0000 0000 0000 0000 0000 0001	${{2}^{-2}}$
2	0000 0000 0000 0000 0000 0001	0100 0000 0000 0000 0000 0100	${{2}^{-2}}$
3	0100 0000 0000 0000 0000 0100	0001 0000 0000 0000 0000 0000	${{2}^{-3}}$
4	0001 0000 0000 0000 0000 0000	0100 0100 0000 0000 0000 0100	${{2}^{-2}}$
5	0100 0100 0000 0000 0000 0100	0000 0001 0000 0000 0000 0001	${{2}^{-4}}$
6	0000 0001 0000 0000 0000 0001	0000 0100 0100 0000 0000 0100	${{2}^{-3}}$