一种大状态轻量级密码S盒的设计与分析

doi:10.19665/j.issn1001-2400.2023.04.017

摘要/Abstract

摘要：

Alzette是2020年美密会上提出的基于ARX结构的64比特轻量级S盒,具备软硬件性能出色、扩散性强和安全性高等诸多优点,受到了国内外的广泛关注。然而,具有杰出性能与安全性的64比特轻量级S盒极少,如何设计出一种比Alzette性能更佳的大状态轻量级S盒是目前研究的难点。基于ARX结构,设计出一种性能与安全性兼优的大状态轻量级密码S盒,提出了“层次筛选法”,通过提前设置最优差分/线性特征的界来确定最佳循环移位参数,并对新密码S盒给出了安全性评估。结果表明:新密码S盒与Alzette的软硬件实现性能相当;同时5轮新密码S盒最优差分特征(线性逼近)的概率达到2^-17(2^-8),7轮新密码S盒的最优线性逼近概率达到2^-17;而Alzette的5轮最优差分特征(线性逼近)概率为2^-10>2^-17(2^-5>2^-8),7轮最优线性逼近概率为2^-13>2^-17。新密码S盒表现出更强的抗差分/线性密码分析的能力。

关键词: 轻量级分组密码, 密码S盒, 差分密码分析, 线性密码分析

Abstract:

Alzette is a 64 bit lightweight S-box based on the ARX structure proposed at the CRYPTO 2020.It has many advantages such as excellent hardware and software performance,strong diffusion and high security,so that it receives wide attention domestically and internationally.However,64-bit lightweight S-boxes with execllent performance and security are rare.Whether it is possible to design the large state lightweight S-box with better performance than Alzette is difficult in current research.In this paper,a large state lightweight cryptographic S-box based on the ARX structure with an excellent performance and security is designed.A “hierarchy filtering method” is proposed to determine the optimal rotation parameters by setting the best differential/linear characteristic bounds in advance,and the security evaluation for the new S-box is given.It is shown that the software and hardware implementation performance of the new S-box is equivalent to that of the Alzette.For the new S-box,the probability of 5-round best differential characteristic (linear approximation) up to 2^-17(2^-8),and the probability of 7-round best linear approximation reaches 2^-17.But for the Alzette,the 5-round best differential characteristic (linear approximation) with probability of 2^-10>2^-17(2^-5>2^-8),and the 7-round best linear approximation with probability of 2^-13>2^-17.The new S-box shows a stronger resistance against differential cryptanalysis and linear cryptanalysis.

Key words: lightweight block cipher, cryptographic S-box, differential cryptanalysis, linear cryptanalysis

中图分类号:

TN918.4

樊婷,冯伟,韦永壮. 一种大状态轻量级密码S盒的设计与分析[J]. 西安电子科技大学学报, 2023, 50(4): 170-179.

FAN Ting,FENG Wei,WEI Yongzhuang. The design and cryptanalysis of a large state lightweight cryptographic S-box[J]. Journal of Xidian University, 2023, 50(4): 170-179.

图/表 9

图1

图2

表1

表2

96组参数"

(t₀,t₁,t₂,t₃,t₄,t₅,t₆,t₇)
(1,31,8,15,17,0,24,16),	(1,31,8,17,15,0,24,16),	(1,15,8,31,17,0,24,16),	(1,15,8,17,31,0,24,16),
(1,17,8,31,15,0,24,16),	(1,17,8,15,31,0,24,16),	(31,1,8,15,17,0,24,16),	(31,1,8,17,15,0,24,16),
(31,15,8,1,17,0,24,16),	(31,15,8,17,1,0,24,16),	(31,17,8,1,15,0,24,16),	(31,17,8,15,1,0,24,16),
(15,1,8,31,17,0,24,16),	(15,1,8,17,31,0,24,16),	(15,31,8,1,17,0,24,16),	(15,31,8,17,1,0,24,16),
(15,17,8,1,31,0,24,16),	(15,17,8,31,1,0,24,16),	(17,1,8,31,15,0,24,16),	(17,1,8,15,31,0,24,16),
(17,31,8,1,15,0,24,16),	(17,31,8,15,1,0,24,16),	(17,15,8,1,31,0,24,16),	(17,15,8,31,1,0,24,16),
(1,31,24,15,17,0,8,16),	(1,31,24,17,15,0,8,16),	(1,15,24,31,17,0,8,16),	(1,15,24,17,31,0,8,16),
(1,17,24,31,15,0,8,16),	(1,17,24,15,31,0,8,16),	(31,1,24,15,17,0,8,16),	(31,1,24,17,15,0,8,16),
(31,15,24,1,17,0,8,16),	(31,15,24,17,1,0,8,16),	(31,17,24,1,15,0,8,16),	(31,17,24,15,1,0,8,16),
(15,1,24,31,17,0,8,16),	(15,1,24,17,31,0,8,16),	(15,31,24,1,17,0,8,16),	(15,31,24,17,1,0,8,16),
(15,17,24,1,31,0,8,16),	(15,17,24,31,1,0,8,16),	(17,1,24,31,15,0,8,16),	(17,1,24,15,31,0,8,16),
(17,31,24,1,15,0,8,16),	(17,31,24,15,1,0,8,16),	(17,15,24,1,31,0,8,16),	(17,15,24,31,1,0,8,16),
(1,31,8,15,17,16,24,0),	(1,31,8,17,15,16,24,0),	(1,15,8,31,17,16,24,0),	(1,15,8,17,31,16,24,0),
(1,17,8,31,15,16,24,0),	(1,17,8,15,31,16,24,0),	(31,1,8,15,17,16,24,0),	(31,1,8,17,15,16,24,0),
(31,15,8,1,17,16,24,0),	(31,15,8,17,1,16,24,0),	(31,17,8,1,15,16,24,0),	(31,17,8,15,1,16,24,0),
(15,1,8,31,17,16,24,0),	(15,1,8,17,31,16,24,0),	(15,31,8,1,17,16,24,0),	(15,31,8,17,1,16,24,0),
(15,17,8,1,31,16,24,0),	(15,17,8,31,1,16,24,0),	(17,1,8,31,15,16,24,0),	(17,1,8,15,31,16,24,0),
(17,31,8,1,15,16,24,0),	(17,31,8,15,1,16,24,0),	(17,15,8,1,31,16,24,0),	(17,15,8,31,1,16,24,0),
(1,31,24,15,17,16,8,0),	(1,31,24,17,15,16,8,0),	(1,15,24,31,17,16,8,0),	(1,15,24,17,31,16,8,0),
(1,17,24,31,15,16,8,0),	(1,17,24,15,31,16,8,0),	(31,1,24,15,17,16,8,0),	(31,1,24,17,15,16,8,0),
(31,15,24,1,17,16,8,0),	(31,15,24,17,1,16,8,0),	(31,17,24,1,15,16,8,0),	(31,17,24,15,1,16,8,0),
(15,1,24,31,17,16,8,0),	(15,1,24,17,31,16,8,0),	(15,31,24,1,17,16,8,0),	(15,31,24,17,1,16,8,0),
(15,17,24,1,31,16,8,0),	(15,17,24,31,1,16,8,0),	(17,1,24,31,15,16,8,0),	(17,1,24,15,31,16,8,0),
(17,31,24,1,15,16,8,0),	(17,31,24,15,1,16,8,0),	(17,15,24,1,31,16,8,0),	(17,15,24,31,1,16,8,0)

表2

表3

图3

图4

表4

表5

参考文献 22

[1]	NIST. Lightweight Cryptography Projects (2021)[EB/OL].[2021-03-29]. https://csrc.nist.gov/Projects/lightweight-Cryptography/finalists.
[2]	CACR. 全国密码算法设计竞赛 (2018)[EB/OL].[2018-06-11]. https://sfjs.cacrnet.org.cn/site/term/list_76_1.html.
[3]	吴文玲, 张蕾, 郑雅菲, 等. 分组密码uBlock[J]. 密码学报, 2019, 6(6):690-703. doi: 10.13868/j.cnki.jcr.000334
	WU Wenling, ZHANG Lei, ZHENG Yafei, et al. The Block Cipher uBlock[J]. Journal of Cryptologic Research, 2019, 6(6):690-703. doi: 10.13868/j.cnki.jcr.000334
[4]	崔婷婷, 王美琴, 樊燕红, 等. Ballet:一个软件实现友好的分组密码算法[J]. 密码学报, 2019, 6(6):704-712. doi: 10.13868/j.cnki.jcr.000335
	CUI Tingting, WANG Meiqin, FAN Yanhong, et al. Ballet:A Software-Friendly Block Cipher[J]. Journal of Cryptologic Research, 2019, 6(6):704-712. doi: 10.13868/j.cnki.jcr.000335
[5]	CSRC. Lightweight Cryptography-Round 2 Candidates (2020)[EB/OL].[2020-06-20]. https://csrc.nist.gov/Projects/lightweightcryptog-raphy/round-2-candidates.
[6]	BERNSTEIN D J, KÖLBL S, LUCKS S, et al. Gimli:A Cross-Platform Permutation[C]// Proceedings of the 19th International Conference on Cryptographic Hardware and Embedded Systems (CHES 2017).Heidelberg:Springer, 2017:299-320.
[7]	BEIERLE C, BIRYUKOV A, DOS SANTOS L C, et al. Lightweight AEAD and Hashing Using the SPARKLE Permutation Family[J]. IACR Transactions on Symmetric Cryptology, 2020, 2020(S1):208-261.
[8]	叶涛, 韦永壮, 李灵琛. KNOT认证加密算法的零和区分器分析[J]. 西安电子科技大学学报, 2021, 48(1):76-86.
	YE Tao, WEI Yongzhuang, LI Lingchen. Analysis of Zero-Sum Distinguisher of the KNOT Authenticated Encryption Algorithm[J]. Journal of Xidian University, 2021, 48(1):76-86.
[9]	谭豪, 申兵, 苗旭东, 等. Gimli认证加密方案的不可能差分分析[J]. 西安电子科技大学学报, 2022, 49(5):213-220.
	TAN Hao, SHEN Bing, MIAO Xudong, et al. Impossible Differential Cryptanalysis of the Gimli Authenticated Encryption Scheme[J]. Journal of Xidian University, 2022, 49(5):213-220.
[10]	BEIERLE C, BIRYUKOV A, DOS SANTOS L C, et al. Alzette:A 64-bit ARX-Box[C]// Proceedings of the 40th Annual International Cryptology Conference (CRYPTO 2020).Heidelberg:Springer, 2020:419-448.
[11]	许峥, 李永强, 王明生. Alzette的安全性分析[J]. 密码学报, 2022, 9(4):698-708.
	XU Zheng, LI Yongqiang, WANG Mingsheng. Security Analysis of Alzette[J]. Journal of Cryptologic Research, 2022, 9(4):698-708.
[12]	HUANG M, XU Z, WANG L. On the Probability and Automatic Search of Rotational-XOR Cryptanalysis on ARX Ciphers[J]. The Computer Journal, 2022, 65(12):3062-3080. doi: 10.1093/comjnl/bxab126
[13]	LIU Y, SUN S, LI C. Rotational Cryptanalysis from a Differential-Linear Perspective[C]// Proceedings of the 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2021).Heidelberg:Springer, 2021:741-770.
[14]	NIU Z, SUN S, LIU Y, et al. Rotational Differential-Linear Distinguishers of ARX Ciphers with Arbitrary Output Linear Masks[C]// Proceedings of 42nd Annual International Cryptology Conference (CRYPTO 2022).Heidelberg:Springer, 2022:3-32.
[15]	LIU Y, NIU Z, SUN S, et al. Rotational Differential-Linear Cryptanalysis Revisited[J]. Journal of Cryptology 2023, 36(3):1-45. doi: 10.1007/s00145-022-09441-3
[16]	MORAWIECKI P, PIEPRZYK J, SREBRNY M. Rotational Cryptanalysis of Round-Reduced Keccak[C]// Proceedings of the 20th International Workshop on Fast Software Encryption (FES 2013).Heidelberg:Springer, 2013:241-262.
[17]	BERTONI G, DAEMEN J, PEETERS M, et al. Keccak[C]// Proceedings of the 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2013).Heidelberg:Springer, 2013:313-314.
[18]	LIPMAA H, MORIAI S. Efficient Algorithms for Computing Differential Properties of Addition[C]// Proceedings of the 8th International Workshop on Fast Software Encryption (FSE 2001).Heidelberg:Springer, 2002:336-350.
[19]	WALLÉN J. Linear Approximations of Addition Modulo 2ⁿ[C]// Proceedings of the 10th International Workshop on Fast Software Encryption (FSE 2003).Heidelberg:Springer, 2003:261-273.
[20]	NYBERG K, WALLÉN J. Improved Linear Distinguishers for SNOW 2.0[C]// Proceedings of the 13th International Workshop on Fast Software Encryption (FSE 2006).Heidelberg:Springer, 2006:144-162.
[21]	FU K, WANG M, GUO Y, et al. MILP-Based Automatic Search Algorithms for Differential and Linear Trails for Speck[C]// Proceedings of the 23rd International Conference on Fast Software Encryption (FSE 2016).Heidelberg:Springer, 2016:268-288.
[22]	GUROBI. Gurobi optimizer 10.0.0 (2022)[EB/OL].[2022-11-10]. http://www.gurobi.cn/.

cost	循环移位量
0	{0,16}
2.00	{8,24}
2.66	{1,31,15,17}

分析方法	轮数
分析方法	1	2	3	4	5	6	7	8
差分密码分析	2^-1	2^-1	2^-6	2^-6	2^-16	2^-16	-	-
线性密码分析	1	1	2^-2	2^-2	2^-8	2^-8	2^-17	2^-17

“层次筛选法”执行步骤	T₁/s	T₂/s
第2步	1 004.8	188.0
第3步	1 329.8	492.4
第4步	55 930.5	27 636.6
第5步	288 336.7	24 4791.7