SIMON类非线性函数的线性性质研究

关杰; 卢健伟

doi:10.11999/JEIT200999

SIMON类非线性函数的线性性质研究

doi: 10.11999/JEIT200999

关杰,
卢健伟^,

战略支援部队信息工程大学郑州 450001

基金项目: 国家自然科学基金(61572516)

详细信息

作者简介:
关杰：女，1974年生，教授，博士生导师，研究方向为密码理论和密码算法分析

卢健伟：男，1997年生，硕士生，研究方向为对称密码设计与分析

通讯作者:
卢健伟　lujianwei1997@163.com

中图分类号: TN918.1
计量
- 文章访问数: 816
- HTML全文浏览量: 366
- PDF下载量: 73
- 被引次数: 0
出版历程
- 收稿日期: 2020-11-25
- 修回日期: 2021-03-30
- 网络出版日期: 2021-05-06
- 刊出日期: 2021-11-23

Research on Linear Properties of SIMON Class Nonlinear Function

Jie GUAN,
Jianwei LU^,

Strategic Support Forces Information Engineering University, Zhengzhou 450001, China

Funds: The National Natural Science Foundation of China (61572516)

摘要

摘要: SIMON算法是由美国国家安全局(NSA)在2013 年推出的一簇轻量级分组密码算法，具有实现代价低、安全性能好等优点，其轮函数采用了$F(x) = (x < < < a){{\& }}(x < < < b) \oplus (x < < < c)$类型的非线性函数。该文研究了移位参数(a,b,c)一般化时SIMON类算法轮函数的线性性质，解决了这类非线性函数的Walsh谱分布规律问题，证明了其相关优势只可能取到${{0}}$或${2^{ - k}}$，其中$k \in Z$且${{0}} \le k \le \left\lfloor {{2^{ - 1}}n} \right\rfloor $，并且对于特定条件下的每一个$k$，都存在相应的掩码对使得相关优势等于${2^{ - k}}$，给出了相关优势取到${2^{ - 1}}$时的充分必要条件及掩码对的计数，给出了特定条件下非平凡相关优势取到最小值时的充分必要条件与掩码对的计数。
- SIMON算法 /
- 线性性质 /
- 循环移位 /
- S盒
Abstract: SIMON algorithm is a group of lightweight block cipher algorithms introduced by the National Security Agency (NSA) in 2013. It has the advantages of low implementation cost and good security performance. Its round function adopts $F(x) = (x < < < a){{\& }}(x < < < b) \oplus (x < < < c)$ type nonlinear function. In this paper, the linear properties of the round function of SIMON algorithm when the shift parameters (a, b, c) are generalized are studied. The problem of Walsh spectrum distribution of this kind of nonlinear function is solved, it is proved that the correlation advantage can only be equal to 0 or ${2^{ - k}}$, where $k \in Z$ and ${{0}} \le k \le \left\lfloor {{2^{ - 1}}n} \right\rfloor $, and for each k under specific conditions, there are corresponding mask pairs so that the correlation advantage is equal to ${2^{ - k}}$. The necessary and sufficient conditions for the correlation advantage to be equal to 1/2 and the count of mask pairs are given. And the necessary and sufficient conditions for the nontrivial correlation advantage to be equal to the minimum value and the count of mask pairs under specific conditions are also given.
- SIMON algorithm /
- Linear property /
- Cyclic shift /
- S-box

HTML全文

表 1 ${F_{abc}}(x)$相关优势计数表

	$ \left\| \rho \right\|$
	0	1	1/2	1/4	1/8	1/16	1/32
$F_{182}^8$	48255	1	64	1280	8256	7680	0
$F_{051}^8$	48255	1	64	1280	8256	7680	0
$F_{182}^9$	207863	1	72	1728	15360	37120	0
$F_{051}^9$	207863	1	72	1728	15360	37120	0

下载: 导出CSV

表 2 转变成不相交2次型算法(算法1)

输入：2次型布尔函数$f\left( x \right) = f\left( {{x_1},{x_2}, \cdots ,{x_n}} \right)$
输出：可逆矩阵${\boldsymbol{M}}$，不相交二次型$\hat f\left( x \right)$使得$\hat f\left( x \right){\rm{ = }}f\left( {x{\boldsymbol{M}}} \right)$
(1)　/初始化/
(2)　${\boldsymbol{M}} \leftarrow {\boldsymbol{I}}$　　　　　　　　　　/${\boldsymbol{I}}$是$n \times n$的可逆矩阵/
(3)　$\hat f\left( x \right) \leftarrow f\left( {{x_1},{x_2}, \cdots ,{x_n}} \right)$
(4)　$v \leftarrow {\rm{PickIndex} }\left( {\hat f} \right)$
(5)　/不相交化/
(6)　当$\sigma \left( {\hat f,{x_v}} \right) \ge 2$时，执行
(7)　　$m \leftarrow \sigma \left( {\hat f,{x_v}} \right)$　　　/$\hat f$中包含${x_v}$的2次项个数/
(8)　　在$\hat f$中找出所有的2次项${x_v}{x_{{t_i}}}$满足${t_1} < {t_2} < \cdots < {t_m}$
(9)　　$\hat f \leftarrow {\rm{Substitute}}\left( {\hat f,{{\boldsymbol{I}}_{{t_1} \leftarrow {t_1},{t_2}, \cdots ,{t_m}}}} \right)$
(10)　　${\boldsymbol{M}} \leftarrow {{\boldsymbol{I}}_{{t_1} \leftarrow {t_1},{t_2}, \cdots ,{t_m}}} \cdot {\boldsymbol{M}}$
(11)　　如果$\sigma \left( {\hat f,{x_{{t_1}}}} \right) \ge 2$，执行
(12)　　　$k \leftarrow \sigma \left( {\hat f,{x_{{t_1}}}} \right)$
(13)　　　在$\hat f$中找出所有的2次项${x_{{t_1}}}{x_{{s_i}}}$满足　　　　　　${s_1} < {s_2} < \cdots < {s_m}$，

下载: 导出CSV

参考文献(20)

[1]	BEAULIEU R, SHORS D, SMITH J, et al. The SIMON and SPECK lightweight block ciphers[C]. The 52nd Annual Design Automation Conference. San Francisco, USA, 2015: 1-6.
[2]	WANG N, WANG X, JIA K, et al. Difffferential attacks on reduced SIMON versions with dynamic key-guessing techniques[J]. IACR Cryptology ePrint Archive, 2014: 2014/448.
[3]	董向忠, 关杰. SIMON类算法轮函数的差分性质分析[J]. 密码学报, 2015, 2(3): 207–216. doi: 10.13868/j.cnki.jcr.000072 DONG Xiangzhong, GUAN Jie. Analysis on difffferential properties of the round function of SIMON family of block ciphers[J]. Journal of Cryptologic Research, 2015, 2(3): 207–216. doi: 10.13868/j.cnki.jcr.000072
[4]	SEYED MOJTABA DEHNAVI. Further Observations on SIMON and SPECK Block Cipher Families[J]. Cryptography, 2018, 3(1): 1. doi: 10.3390/cryptography3010001
[5]	董向忠, 关杰. SIMON类算法轮函数的线性性质[J]. 山东大学学报(理学版), 2015, 50(9): 49–54. DONG Xiangzhong, GUAN Jie. Linear properties of the round function of SIMON family of block ciphers[J]. 山东大学学报, 2015, 50(9): 49–54.
[6]	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.
[7]	CHEN H, WANG X. Improved linear hull attack on round-reduced SIMON with dynamic key-guessing techniques[C]. Fast Software Encryption—FSE 2016. Berlin, Germany, 2016: 428–449. doi: 10.1007/978-3-662-52993-5_22.
[8]	SHI Danping, HU Lei, SUN Siwei, et al. Improved linear(hull) cryptanalysis of round-reduced versions of SIMON[J]. Science China (Information Sciences) 60.03(2017): 223–225. doi: 10.1007/s11432-015-0007-1.
[9]	REHAM A and POORVI L. V linear cryptanalysis of reduced-round simon using super rounds[J]. Cryptography, 2020, 4(1): 9. doi: 10.3390/cryptography4010009
[10]	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.
[11]	陈展, 王宁. SIMON算法的不可能差分分析[J]. 密码学报, 2015, 2(6): 505–514. doi: 10.13868/j.cnki.jcr.000097 CHEN Zhan and WANG Ning. Impossible difffferential cryptanalysis of reduced-round SIMON[J]. Journal of Cryptologic Research, 2015, 2(6): 505–514. doi: 10.13868/j.cnki.jcr.000097
[12]	KONDO K, SASAKI Y, TODO Y, et al. On the design rationale of SIMON block cipher: Integral attacks and impossible differential attacksagainst SIMON variants[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2018, 101(1): 88–98.
[13]	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
[14]	SUN L, FU K, and WANG M. Improved zero-correlation cryptanalysis on SIMON[C]. Information Security and Cryptology—INSCRYPT 2015. Beijing, China, 2015: 125–143.
[15]	ZHANG Kai, Guanjie, HU Bin, et al. Security evaluation on Simeck against zero-correlation linear cryptanalysis[C]. IET Information Security, 2018, 12(1): 87–93. doi: 10.1049/iet-ifs.2016.0503.
[16]	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
[17]	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
[18]	YANG G, ZHU B, SUDER V, et al. The Simeck Family of Lightweight Block Ciphers[C]. Güneysu T, Handschuh H. (eds) Cryptographic Hardware and Embedded Systems, CHES 2015. Lecture Notes in Computer Science, vol 9293. Springer, Berlin, Germany, https://doi.org/10.1007/978-3-662-48324-4_16.
[19]	SHI D, SUN S, SASAKI Y, et al. Correlation of Quadratic Boolean Functions: Cryptanalysis of All Versions of Full MORUS[M]. Advances in Cryptology–CRYPTO, 2019.
[20]	鞠桂枝, 赵亚群. 多输出部分Bent函数若干性质的研究[J]. 工程数学学报, 2005(6): 183–186.