Research on Linear Properties of SIMON Class Nonlinear Function
-
摘要: 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}}$ 时的充分必要条件及掩码对的计数,给出了特定条件下非平凡相关优势取到最小值时的充分必要条件与掩码对的计数。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.-
Key words:
- SIMON algorithm /
- Linear property /
- Cyclic shift /
- S-box
-
表 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 表 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}$, -
[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.000072DONG 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.000097CHEN 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.
表(2)
计量
- 文章访问数: 830
- HTML全文浏览量: 372
- PDF下载量: 73
- 被引次数: 0