SIMON算法的差分—线性密码分析

doi:10.3969/j.issn.1671-1122.2022.09.008

摘要/Abstract

摘要：

差分分析和线性分析是目前分组密码算法攻击中较常见的两种方法，差分—线性分析是基于这两种方法建立的一种分析方法，近年来受到密码学界的广泛关注。SIMON算法是一种重要的轻量级密码算法，文章主要对SIMON 32/64和SIMON 48进行差分—线性分析，分别构造13轮差分—线性区分器，基于区分器分别进行16轮密钥恢复攻击，数据复杂度分别为2²⁶和2⁴²，时间复杂度分别为2^40.59和2^61.59，增加了SIMON算法的安全性评估维度，丰富了差分—线性分析的实际案例。

关键词: 轻量级分组密码, 差分—线性分析, SIMON算法

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

中图分类号:

TP309

胡禹佳, 代政一, 孙兵. SIMON算法的差分—线性密码分析[J]. 信息网络安全, 2022, 22(9): 63-75.

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

图/表 17

表1

表2

表3

图1

图2

表4

图3

图4

表5

图5

表6

SIMON 32/64算法的16轮密钥恢复攻击关系

等式左边	等式右边
$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}$

表6

图6

表7

图7

表8

图8

表9

SIMON 48算法的16轮密钥恢复攻击关系

等式左边	等式右边
$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}$

表9

参考文献 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}}$