SIMON類非線性函數(shù)的線性性質(zhì)研究

關(guān)杰; 盧健偉

doi:10.11999/JEIT200999

SIMON類非線性函數(shù)的線性性質(zhì)研究

doi: 10.11999/JEIT200999

關(guān)杰,
盧健偉^,

戰(zhàn)略支援部隊信息工程大學(xué) 鄭州 450001

基金項目: 國家自然科學(xué)基金(61572516)

詳細(xì)信息

作者簡介:
關(guān)杰：女，1974年生，教授，博士生導(dǎo)師，研究方向為密碼理論和密碼算法分析

盧健偉：男，1997年生，碩士生，研究方向為對稱密碼設(shè)計與分析

通訊作者:
盧健偉　lujianwei1997@163.com

中圖分類號: TN918.1
計量
- 文章訪問數(shù): 870
- HTML全文瀏覽量: 397
- PDF下載量: 73
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2020-11-25
- 修回日期: 2021-03-30
- 網(wǎng)絡(luò)出版日期: 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 年推出的一簇輕量級分組密碼算法，具有實現(xiàn)代價低、安全性能好等優(yōu)點，其輪函數(shù)采用了$F(x) = (x < < < a){{\& }}(x < < < b) \oplus (x < < < c)$類型的非線性函數(shù)。該文研究了移位參數(shù)(a,b,c)一般化時SIMON類算法輪函數(shù)的線性性質(zhì)，解決了這類非線性函數(shù)的Walsh譜分布規(guī)律問題，證明了其相關(guān)優(yōu)勢只可能取到${{0}}$或${2^{ - k}}$，其中$k \in Z$且${{0}} \le k \le \left\lfloor {{2^{ - 1}}n} \right\rfloor $，并且對于特定條件下的每一個$k$，都存在相應(yīng)的掩碼對使得相關(guān)優(yōu)勢等于${2^{ - k}}$，給出了相關(guān)優(yōu)勢取到${2^{ - 1}}$時的充分必要條件及掩碼對的計數(shù)，給出了特定條件下非平凡相關(guān)優(yōu)勢取到最小值時的充分必要條件與掩碼對的計數(shù)。
- SIMON算法 /
- 線性性質(zhì) /
- 循環(huán)移位 /
- 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)$相關(guān)優(yōu)勢計數(shù)表

	$ \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

下載: 導(dǎo)出CSV

表 2 轉(zhuǎn)變成不相交2次型算法(算法1)

輸入：2次型布爾函數(shù)$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)　當(dāng)$\sigma \left( {\hat f,{x_v}} \right) \ge 2$時，執(zhí)行
(7)　　$m \leftarrow \sigma \left( {\hat f,{x_v}} \right)$　　　/$\hat f$中包含${x_v}$的2次項個數(shù)/
(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$，執(zhí)行
(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}$，

下載: 導(dǎo)出CSV

參考文獻(xiàn)(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]	董向忠, 關(guān)杰. SIMON類算法輪函數(shù)的差分性質(zhì)分析[J]. 密碼學(xué)報, 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]	董向忠, 關(guān)杰. SIMON類算法輪函數(shù)的線性性質(zhì)[J]. 山東大學(xué)學(xué)報(理學(xué)版), 2015, 50(9): 49–54. DONG Xiangzhong, GUAN Jie. Linear properties of the round function of SIMON family of block ciphers[J]. 山東大學(xué)學(xué)報, 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]. 密碼學(xué)報, 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函數(shù)若干性質(zhì)的研究[J]. 工程數(shù)學(xué)學(xué)報, 2005(6): 183–186.