SPS结构大规模S盒设计与分析

doi:10.11959/j.issn.1000-436x.2023033

Abstract

Abstract:

A class of optimal linear transformation P over a finite field ${(F_{2}^{m})}^{4}$ was constructed based on cyclic shift and XOR operation.Using the idea of inverse proof of input-output relation of linear transformation for reference, a proof method was put forward that transformed the objective problem of optimal linear transformation into several theorems of progressive relation, which not only solved the proof of that kind of optimal linear transformation, but also was suitable for the proof of any linear transformation.By means of small-scale S-box and optimal cyclic shift-XOR linear transformation P, a large-scale S-box model with 2-round SPS structure was established, and a series of lightweight large-scale S-boxes with good cryptographic properties were designed.Only three kind of basic operations such as look-up table, cyclic shift and XOR were used in the proposed design scheme, which improved the linearity and difference uniformity of large-scale S-boxes.Theoretical proof and case analysis show that, compared with the existing large-scale S-box construction methods, the proposed large-scale S-box design scheme has lower computational cost and better cryptographic properties such as difference and linearity, which is suitable for the design of nonlinear permutation coding of lightweight cryptographic algorithms.

Key words: SPS structure, large-scale S-box, cyclic shift-XOR linear transformation

CLC Number:

TN918.1

Lan ZHANG, Liangsheng HE, Bin YU. Large-scale S-box design and analysis of SPS structure[J]. Journal on Communications, 2023, 44(2): 27-40.

Figures/Tables 10

S盒	最大差分概率	差分均匀度	最大线性概率	线性度	ASIC硬件实现（标准门电路个数）/个	软件实现
S₁	$\frac{96}{65 536} \approx 2^{- 9.41}$	96	${(2 \times \frac{1 6 00}{65 536})}^{2} \approx 2^{- 8.71}$	3 200	368	一次查表
SPS:循环移位+异或	$\frac{96}{65 536} \approx 2^{- 9.41}$	96	${(2 \times \frac{1 6 00}{65 536})}^{2} \approx 2^{- 8.71}$	3 200	368	一次查表
Piccolo算法S₂	$\frac{128}{65 536} = 2^{- 9}$	128	${(2 \times \frac{2048}{65 536})}^{2} = 2^{- 8}$	4 096	432	一次查表
SPS:MDS	$\frac{128}{65 536} = 2^{- 9}$	128	${(2 \times \frac{2048}{65 536})}^{2} = 2^{- 8}$	4 096	432	一次查表
NBC算法S₃	$\frac{22}{65 536} = 2^{- 11.541}$	22	${(2 \times \frac{1 572}{65 536})}^{2} = 2^{- 1 0. 764}$	3 144	440	一次查表
Galois:16级NFSR	$\frac{22}{65 536} = 2^{- 11.541}$	22	${(2 \times \frac{1 572}{65 536})}^{2} = 2^{- 1 0. 764}$	3 144	440	一次查表

小规模4 bit S盒	最大差分概率	差分均匀度	最大线性概率	线性度
4,0,1,15,2,11,6,7,3,9,10,5,12,13,14,8	$\frac{128}{65 536} = 2^{- 9}$	128	${(2 \times \frac{1 6 00}{65 536})}^{2} \approx 2^{- 8.71}$	3 200
8,0,1,12,2,5,6,9,4,3,10,11,7,13,14,15	$\frac{136}{65 536} \approx 2^{- 8.91}$	136	${(2 \times \frac{2048}{65 536})}^{2} = 2^{- 8}$	4 096
8,0,1,12,15,5,6,7,4,3,10,11,9,13,14,2	$\frac{128}{65 536} = 2^{- 9}$	128	${(2 \times \frac{1 6 00}{65 536})}^{2} \approx 2^{- 8.71}$	3 200
2,0,1,8,3,13,6,7,4,9,10,5,12,11,14,15	$\frac{148}{65 536} \approx 2^{- 8.79}$	148	${(2 \times \frac{2048}{65 536})}^{2} = 2^{- 8}$	4 096
2,0,1,8,3,15,6,7,4,9,5,11,12,13,14,10	$\frac{128}{65 536} = 2^{- 9}$	128	${(2 \times \frac{1 664}{65 536})}^{2} \approx 2^{- 8.59}$	3 328
2,0,1,8,3,11,6,7,4,9,10,15,12,13,14,5	$\frac{72}{65 536} \approx 2^{- 9.83}$	72	${(2 \times \frac{1 6 00}{65 536})}^{2} \approx 2^{- 8.71}$	3 200
4,8,1,2,3,11,6,7,0,9,10,14,12,13,5,15	$\frac{164}{65 536} \approx 2^{- 8.64}$	164	${(2 \times \frac{1 6 00}{65 536})}^{2} \approx 2^{- 8.71}$	3 200
8,0,1,9,2,5,13,7,4,6,10,11,12,3,14,15	$\frac{128}{65 536} = 2^{- 9}$	128	${(2 \times \frac{1 6 00}{65 536})}^{2} \approx 2^{- 8.71}$	3 200
8,14,1,2,3,5,6,7,4,12,10,11,9,13,0,15	$\frac{128}{65 536} = 2^{- 9}$	128	${(2 \times \frac{2048}{65 536})}^{2} = 2^{- 8}$	4 096
8,14,1,2,3,5,6,7,4,9,15,11,12,13,0,10	$\frac{128}{65 536} = 2^{- 9}$	128	${(2 \times \frac{2048}{65 536})}^{2} = 2^{- 8}$	4 096
8,15,1,2,3,5,12,7,4,9,10,11,6,13,14,0	$\frac{128}{65 536} = 2^{- 9}$	128	${(2 \times \frac{2048}{65 536})}^{2} = 2^{- 8}$	4 096
8,15,1,2,3,5,6,13,4,9,10,11,12,7,14,0	$\frac{128}{65 536} = 2^{- 9}$	128	${(2 \times \frac{1 792}{65 536})}^{2} \approx 2^{- 8.38}$	3 584
12,0,1,9,3,5,4,7,6,2,10,11,8,13,14,15	$\frac{128}{65 536} = 2^{- 9}$	128	${(2 \times \frac{2048}{65 536})}^{2} = 2^{- 8}$	4 096
12,11,1,2,3,5,4,7,6,9,10,0,8,13,14,15	$\frac{144}{65 536} \approx 2^{- 8.83}$	144	${(2 \times \frac{2048}{65 536})}^{2} = 2^{- 8}$	4 096
12,9,1,2,3,5,4,7,6,0,10,11,8,13,14,15	$\frac{132}{65 536} \approx 2^{- 8.95}$	132	${(2 \times \frac{2048}{65 536})}^{2} = 2^{- 8}$	4 096
8,14,1,2,3,5,4,7,6,9,10,0,12,13,11,15	$\frac{128}{65 536} = 2^{- 9}$	128	${(2 \times \frac{2048}{65 536})}^{2} = 2^{- 8}$	4 096

S盒	最大差分概率	差分均匀度	最大线性概率	线性度	ASIC硬件实现（标准门电路个数）/个
2轮SPS结构	$\frac{1 0^{4}}{2^{32}}$	10⁴	${(\frac{2^{24}}{2^{32}})}^{2}$	2²⁴	1 168
SPS:循环移位+异或	$\frac{1 0^{4}}{2^{32}}$	10⁴	${(\frac{2^{24}}{2^{32}})}^{2}$	2²⁴	1 168
SPRING算法S₃	$\frac{40}{2^{32}}$	40	${(\frac{119 \times 2^{11}}{2^{32}})}^{2}$	119×2¹¹	6 848
Galois:32 bit NFSR	$\frac{40}{2^{32}}$	40	${(\frac{119 \times 2^{11}}{2^{32}})}^{2}$	119×2¹¹	6 848

S盒	最大差分概率	差分均匀度Diff(S)	最大线性概率	线性度Lin(S)	ASIC硬件实现（标准门电路个数）/个
2轮SPS结构	$\frac{72^{4}}{2^{64}}$	72 ⁴(＜2³²)	${(\frac{3 2 00^{4}}{2^{64}})}^{2}$	3 200(＜2^55.5)	3 456
SPS：循环移位+异或	$\frac{72^{4}}{2^{64}}$	72 ⁴(＜2³²)	${(\frac{3 2 00^{4}}{2^{64}})}^{2}$	3 200(＜2^55.5)	3 456
Alzette算法S盒	$\frac{2^{32}}{2^{64}}$	2 ³²	${(\frac{2^{55.5}}{2^{64}})}^{2}$	2 ^55.5	1 312
4轮ARX结构：64 bit	$\frac{2^{32}}{2^{64}}$	2 ³²	${(\frac{2^{55.5}}{2^{64}})}^{2}$	2 ^55.5	1 312

References ［31］

［31］	WANG J B , ． The optimal permutation in cryptography based on cyclic-shift linear transform［C］// Proceedings of ChinaCrypt 2007． Chengdu:Southwest Jiaotong University Press, 2007: 306-307．
［32］	LEANDER G , POSCHMANN A ． On the classification of 4 bit S-boxes［M］． Berlin: Springer, 2007．
［1］	LI Y Q , WANG M S ． Constructing S-boxes for lightweight cryptography with Feistel structure［C］// International Workshop on Cryptographic Hardware ＆ Embedded Systems． Berlin:Springer, 2014: 127-146．
［2］	龚涛, 陈少真．基于扩展Feistel结构S盒的构造分析［J］．信息工程大学学报, 2017,18(3): 328-332．
	GONG T , CHEN S Z ． Analysis of S-boxes with expanded feistel structure［J］． Journal of Information Engineering University, 2017,18(3): 328-332．
［3］	JUNOD P , VAUDENAY S ． FOX:a new family of block ciphers［M］． Berlin: Springer, 2004．
［4］	CANTEAUT A , DUVAL S , LEURENT G ． Construction of lightweight S-boxes using Feistel and MISTY structures［C］// International Workshop on Cryptographic Hardware and Embedded Systems． Berlin:Springer, 2015: 373-393．
［5］	MATSUI M ． New block encryption algorithm MISTY［M］． Berlin: Springer, 1997．
［6］	董新锋, 张文政, 许春香． Feistel结构的8比特轻量化S盒［J］．西安电子科技大学学报, 2021,48(1): 69-75．
	DONG X F , ZHANG W Z , XU C X ． 8 bits lightweight S-box with the Feistel structure［J］． Journal of Xidian University, 2021,48(1): 69-75．
［7］	LIU Y , LIU XI L , ZHAO Y M ． Security cryptanalysis of NUX for the Internet of things［J］． Security and Communication Networks, 2019:doi．org/10．1155/2019/2062697．
［8］	SHIBUTANI K , ISOBE T , HIWATARI H ,et al． Piccolo:an ultra-lightweight blockcipher［C］// International Workshop on Cryptographic Hardware and Embedded Systems． Berlin:Springer, 2011: 342-357．
［9］	徐洪, 段明, 谭林 ,等． NBC 算法［J］．密码学报, 2019,6(6): 760-767．
	XU H , DUAN M , TAN L ,et al． On the NBC algorithm［J］． Journal of Cryptologic Research, 2019,6(6): 760-767．
［10］	田甜, 戚文峰, 叶晨东 ,等．基于 NFSR 的分组密码算法SPRING［J］．密码学报, 2019,6(6): 815-834．
	TIAN T , QI W F , YE C D ,et al． SPRING:a family of small hardware-oriented block ciphers based on NFSRs［J］． Journal of Cryptologic Research, 2019,6(6): 815-834．
［11］	National Institute of Standards and Technology. Lightweight crylptography［R］． 2020．
［12］	BEIERLE C , BIRYUKOV A , CARDOSO D S L ,et al． Lightweight AEAD and hashing using the sparkle permutation family［J］． IACR Transactions on Symmetric Cryptology, 2020(S1): 208-261．
［13］	BANIK S , CHAKRABORTI A , IWATA T ,et al． GIFT-COFB［J］． Cryptology ePrint Archive, 2020,738: 1-25．
［14］	CHRISTOF B , ALEX B ,et al． Alzette:a 64-bit ARX-box (feat.CRAX and TRAX)［C］// Proceedings of the Advances in Cryptology． Berlin:Springer, 2020: 419-448．
［15］	NIST． Advanced Encryption Standard(AES)［S］． 2001．
［16］	吴文玲, 张蕾, 郑雅菲 ,等．分组密码 uBlock［J］．密码学报, 2019,6(6): 690-703．
	WU W L , ZHANG L , ZHENG Y F ,et al． The block cipher uBlock［J］． Journal of Cryptologic Research, 2019,6(6): 690-703．
［17］	LIU M C , SIM S M ． Lightweight MDS generalized circulant matrices［C］// International Conference on Fast Software Encryption． Berlin:Springer, 2016: 101-120．
［18］	李瑞林, 熊海, 李超．基于循环移位和异或运算的对合线性变换研究［J］．国防科技大学学报, 2012,34(2): 46-50．
	LI R L , XIONG H , LI C ． Research on involutional linear transformations based on rotation and XOR［J］． Journal of National University of Defense Technology, 2012,34(2): 46-50．
［19］	DONG H C , SANG J L , JONG I L ,et al． New block cipher Donut using pairwise perfect decorrelation［C］// Proceedings of the First International Conference on Progress in Cryptology． Berlin:Springer, 2000: 262-270．
［20］	CANTEAUT A , DUVAL S , LEURENT G ,et al． Saturnin:a suite of lightweight symmetric algorithms for post-quantum security［J］． IACR Transactions on Symmetric Cryptology, 2020(S1): 160-207．
［21］	SAJADIEH M , DAKHILALIAN M , MALA H ,et al． Recursive diffusion layers for block ciphers and hash functions［C］// International Workshop on Fast Software Encryption． Berlin:Springer, 2012: 385-401．
［22］	WU S B , WANG M S , WU W L ． Recursive diffusion layers for (lightweight) block ciphers and hash functions［C］// International Conference on Selected Areas in Cryptography． Berlin:Springer, 2013: 355-371．
［23］	AUGOT D , FINIASZ M ． Direct construction of recursive MDS diffusion layers using shortened BCH codes［C］// International Workshop on Fast Software Encryption． Berlin:Springer, 2015: 3-17．
［24］	LI S , SUN S W , SHI D P ,et al． Lightweight iterative MDS matrices:how small can we go?［J］． IACR Transactions on Symmetric Cryptology, 2019(4): 147-170．
［25］	LI S , SUN S W , LI C Y ,et al． Constructing low-latency involutory MDS matrices with lightweight circuits［J］． IACR Transactions on Symmetric Cryptology, 2019(1): 84-117．
［26］	GUO Z , LIU R , WU W ,et al． Direct construction of lightweight rotational-XOR MDS diffusion layers［J］． IACR Cryptology ePrint Archive, 2016(1036): 1-16．
［27］	GUO Z Y , LIU R Z , GAO S ,et al． Direct construction of optimal rotational-XOR diffusion primitives［J］． IACR Transactions on Symmetric Cryptology, 2017(4): 169-187．
［28］	苏俊, 王鑫, 王涛 ,等．循环移位与异或构造扩散层的新证明方法［J］．密码学报, 2020,7(6): 763-773．
	SU J , WANG X , WANG T ,et al． New proof method for cyclic shift and XOR structured diffusion layer［J］． Journal of Cryptologic Research, 2020,7(6): 763-773．
［29］	HONG S , LEE S J , LIM J ,et al． Provable security against differential and linear cryptanalysis for the SPN structure［M］． Berlin: Springer, 2001．
［30］	BON W K , HWAN S J , JUNG H S ． Constructing and cryptanalysis of a 16 × 16 binary matrix as a diffusion layer［C］// International Workshop on Information Security Applications． Berlin:Springer, 2003: 489-503．
［31］	王金波．基于循环移位构造最优线性变换［C］// 中国密码学会 2007年会论文集．成都:西南交通大学出版社, 2007: 306-307．

Metrics

Recommended 0

No Suggested Reading articles found!

序号	线性置换P₁的等价类{t₁,t₂,t₃,t₄,t₅}	线性置换P₂的等价类{t₁,t₂,t₃,t₄,t₅}
1	0,1,5,9,12	0,3,7,11,12
2	0,4,5,9,13	0,4,7,11,15
3	1,4,8,9,13	3,4,8,11,15
4	1,5,8,12,13	3,7,8,12,15

序号	线性置换P₃的等价类{t₁,t₂,t₃,t₄,t₅}	线性置换P₄的等价类{t₁,t₂,t₃,t₄,t₅}
1	0,2,10,18,24	0,6,14,22,24
2	0,8,10,18,26	0,8,14,22,30
3	2,8,16,18,26	6,8,16,22,30
4	2,10,16,24,26	6,14,16,24,30

序号	线性置换P₅的等价类{t₁,t₂,t₃,t₄,t₅}	线性置换P₆的等价类{t₁,t₂,t₃,t₄,t₅}
1	0,4,20,36,48	0,12,28,44,48
2	0,16,20,36,52	0,16,28,44,60
3	4,16,32,36,52	12,16,32,44,60
4	4,20,32,48,52	12,28,32,48,60

[1]	Dongyu CHEN, Hua CHEN, Limin FAN, Yifang FU, Jian WANG. Research on test strategy for randomness based on deep learning [J]. Journal on Communications, 2023, 44(6): 23-33.
[2]	Yanshuo ZHANG, Ning LIU, Yuqi YUAN, Yatao YANG. Adaptor signature scheme based on ISRSAC digital signature algorithm [J]. Journal on Communications, 2023, 44(3): 178-185.
[3]	Huawei HUANG. Security analysis of public-key cryptosystems based on matrix action problem against quantum attack [J]. Journal on Communications, 2023, 44(3): 220-226.
[4]	Shuai LIU, Jie GUAN, Bin HU, Sudong MA. Differential analysis of lightweight cipher algorithm ACE based on MILP [J]. Journal on Communications, 2023, 44(1): 39-48.
[5]	Zhaocun ZHOU, Dengguo FENG. Survey on approaches of stream cipher cryptanalysis [J]. Journal on Communications, 2022, 43(11): 183-198.
[6]	Runhua SHI, Hui YU, Weiyang KE, Xiaotong XU. Quantum anonymous one-vote veto protocol based on BB84 states [J]. Journal on Communications, 2022, 43(8): 109-120.
[7]	Manman LI, Shaozhen CHEN. Improved meet-in-the-middle attack on reduced-round Kiasu-BC algorithm [J]. Journal on Communications, 2022, 43(7): 41-48.
[8]	Anqi YIN, Yuanbo GUO, Ding WANG, Tongzhou QU, Lin CHEN. Provably secure quantum resistance two-server password-authenticated key exchange protocol [J]. Journal on Communications, 2022, 43(3): 14-29.
[9]	Zilong JIANG, Chenhui JIN. Impossible differential cryptanalysis of Saturnin algorithm [J]. Journal on Communications, 2022, 43(3): 53-62.
[10]	Nianping WANG, Qing YIN. Differential security evaluation of Piccolo-like structure [J]. Journal on Communications, 2022, 43(2): 55-64.
[11]	Nianping WANG, Zhicheng GUO. Security evaluation against differential cryptanalysis for dynamic cryptographic structure [J]. Journal on Communications, 2021, 42(8): 70-79.
[12]	Nianping WANG, Lirong HONG. Linear property and optimal design of MARS-like cryptographic structure [J]. Journal on Communications, 2021, 42(4): 169-176.
[13]	Longxia HUANG, Liangmin WANG, Gongxuan ZHANG. Security model without managers for blockchain trading system [J]. Journal on Communications, 2020, 41(12): 36-46.
[14]	Jiao DU,Chunhong LIU,Shanqi PANG. Constructions of rotation symmetric 2-resilient functions with 4t_-1 number of variables [J]. Journal on Communications, 2020, 41(11): 169-175.
[15]	Guoshuang ZHANG,Xiao CHEN,Dongdai LIN,Fengmei LIU. State recovery attack on ACORN v3 in nonce-reuse setting [J]. Journal on Communications, 2020, 41(8): 11-21.

Large-scale S-box design and analysis of SPS structure

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References ［31］

Related Articles 15

Metrics

Recommended 0