分组密码最小活跃S盒个数快速搜索算法

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

Abstract

Abstract:

To solve the problem of fast calculation of the minimum number of active S-boxes in cryptographic design, the difference and mask propagation of the diffusion layer were investigated, and a method was proposed to compute the difference (resp.mask) pattern distribution table of MDS (maximum distance separable) matrices and binary matrices.A lower bound on the computation complexity of the proposed method was also given.Based on the difference (resp.mask) pattern distribution table of diffusion matrix, a fast algorithm to search for the minimum number of active S-boxes of block cipher was proposed.The proposed algorithm is applied to some SPN (substitution permutation network) block ciphers, and finds the minimum number of active S-boxes for the full round of LED, SKINNY, CRAFT and FIDES.

Key words: block cipher, differential cryptanalysis, linear cryptanalysis, active S-box, automatic search

CLC Number:

TN918

Zhengbin LIU, Yongqiang LI, Chaoxi ZHU. Fast algorithm to search for the minimum number of active S-boxes of block cipher[J]. Journal on Communications, 2023, 44(1): 118-128.

Figures/Tables 6

References 32

[1]	BIHAM E , SHAMIR A . Differential cryptanalysis of DES-like cryptosystems[J]. Journal of Cryptology, 1991,4(1): 3-72.
[2]	MATSUI M , . Linear cryptanalysis method for DES cipher[C]// Proceedings of International Conference on the Theory and Application of Cryptographic Techniques. Berlin:Springer, 1993: 386-397.
[3]	DAEMEN J , RIJMEN V . The design of Rijndael:AES - the advanced encryption standard[M]. Berlin: Springer, 2002.
[4]	MATSUI M , . On correlation between the order of S-boxes and the strength of DES[C]// Proceedings of International Conference on the Theory and Application of Cryptographic Techniques. Berlin:Springer, 1994: 366-375.
[5]	OHTA K , MORIAI S , AOKI K . Improving the search algorithm for the best linear expression[C]// Proceedings of 15th Annual International Cryptology Conference. Berlin:Springer, 1995: 157-170.
[6]	AOKI K , KOBAYASHI K , MORIAI S . Best differential characteristic search of FEAL[C]// Proceedings of International Conference on Fast Software Encryption. Berlin:Springer, 1997: 41-53.
[7]	ARNAUD B , NICOLAS B , ERIC F . Automatic search for a maximum probability differential characteristic in a substitution-permutation network[C]// Proceedings of the 48th Hawaii International Conference on System Sciences. Piscataway:IEEE Press, 2015: 5165-5174.
[8]	JI F L , ZHANG W T , DING T Y . Improving Matsui’s search algorithm for the best differential/linear trails and its applications for DES,DESL and GIFT[J]. The Computer Journal, 2020,64(4): 610-627.
[9]	KIM S , HONG D , SUNG J ,et al. Accelerating the best trail search on AES-like ciphers[J]. IACR Transactions on Symmetric Cryptology, 2022,2022(2): 201-252.
[10]	MOUHA N , WANG Q , GU D ,et al. Differential and linear cryptanalysis using mixed-integer linear programming[C]// Proceedings of International Conference on Information Security and Cryptology. Berlin:Springer, 2011: 57-76.
[11]	SUN S W , HU L , WANG P ,et al. Automatic security evaluation and (related-key) differential characteristic search:application to SIMON,PRESENT,LBlock,DES(L) and other bit-oriented block ciphers[C]// Proceedings of the 20th International Conference on the Theory and Application of Cryptology and Information Security. Berlin:Springer, 2014: 158-178.
[12]	ABDELKHALEK A , SASAKI Y , TODO Y ,et al. MILP modeling for (large) S-boxes to optimize probability of differential characteristics[J]. IACR Transactions on Symmetric Cryptology, 2017,2017(4): 99-129.
[13]	QUINE W V . The problem of simplifying truth functions[J]. The American Mathematical Monthly, 1952,59(8): 521-531.
[14]	MCCLUSKEY E J J . Minimization of Boolean functions[J]. Bell System Technical Journal, 1956,35(6): 1417-1444.
[15]	BRAYTON R K , HACHTEL G D , MCMULLEN C T ,et al. Logic minimization algorithms for VLSI synthesis[M]. Berlin: Springer, 1984.
[16]	ZHANG Y , SUN S , CAI J ,et al. Speeding up MILP aided differential characteristic search with Matsui's strategy[C]// Proceedings of International Conference on Information Security. Berlin:Springer, 2018: 101-115.
[17]	ZHOU C N , ZHANG W T , DING T Y ,et al. Improving the MILP-based security evaluation algorithm against differential/linear cryptanalysis using a divide-and-conquer approach[J]. IACR Transactions on Symmetric Cryptology, 2019,2019(4): 438-469.
[18]	FU K , WANG M Q , GUO Y H ,et al. MILP-based automatic search algorithms for differential and linear trails for speck L[C]// Proceedings of International Conference on Fast Software Encryption. Berlin:Springer, 2016: 268-288.
[19]	XIANG Z J , ZHANG W T , BAO Z Z ,et al. Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers[C]// Proceedings of the 22nd International Conference on the Theory and Application of Cryptology and Information Security. Berlin:Springer, 2016: 648-678.
[20]	SASAKI Y , TODO Y . New impossible differential search tool from design and cryptanalysis aspects - revealing structural properties of several ciphers[C]// Proceedings of the 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2017: 185-215.
[21]	BOURA C , COGGIA D . Efficient MILP modelings for Sboxes and linear layers of SPN ciphers[J]. IACR Transactions on Symmetric Cryptology, 2020,2020(3): 99-129.
[22]	BAO Z , DONG X , GUO J ,et al. Automatic search of meet-in-the-middle preimage attacks on AES-like hashing[C]// Proceedings of the 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2021: 771-804.
[23]	UDOVENKO A , . Convexity of division property transitions:theory,algorithms and compact models[C]// Proceedings of the 27th International Conference on the Theory and Application of the Cryptology and Information Security. Berlin:Springer, 2021: 332-361.
[24]	WANG Q , HAO Y , TODO Y ,et al. Improved division property based cube attacks exploiting algebraic properties of superpoly[C]// Proceedings of the 38th Annual International Cryptology Conference. Berlin:Springer, 2018: 275-305.
[25]	GUO H , SUN S W , SHI D P ,et al. Differential attacks on CRAFT exploiting the involutory S-boxes and tweak additions[J]. IACR Transactions on Symmetric Cryptology, 2020,2020(3): 119-151.
[26]	DERBEZ P , LAMBIN B . Fast MILP models for division property[J]. IACR Transactions on Symmetric Cryptology,2022, 2022(2): 289-321.
[27]	BEIERLE C , JEAN J , K?LBL S ,et al. The SKINNY family of block ciphers and its low-latency variant MANTIS[C]// Proceedings of the 36th Annual International Cryptology Conference. Berlin:Springer, 2016: 123-153.
[28]	BEIERLE C , LEANDER G , MORADI A ,et al. CRAFT:lightweight tweakable block cipher with efficient protection against DFA attacks[J]. IACR Transactions on Symmetric Cryptology, 2019,2019(1): 5-45.
[29]	BILGIN B , BOGDANOV A , KNEZEVIC M ,et al. Fides:lightweight authenticated cipher with side-channel resistance for constrained hardware[C]// Proceedings of International Conference on Cryptographic Hardware and Embedded Systems. Berlin:Springer, 2013: 142-158.
[30]	王念平, 郭祉成 . 动态密码结构抵抗差分密码分析能力评估[J]. 通信学报, 2021,42(8): 70-79.
	WANG N P , GUO Z C . Security evaluation against differential cryp-tanalysis for dynamic cryptographic structure[J]. Journal on Commu-nications, 2021,42(8): 70-79.
[31]	MACWILLIAMS F , SLOANE N . The theory of error-correcting codes[M]. Amsterdam: North-Holland Publishing Company, 1981.
[32]	GUO J , PEYRIN T , POSCHMANN A ,et al. The LED block cipher[C]// Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems. Berlin:Springer, 2011: 326-341.

Metrics

Recommended 0

No Suggested Reading articles found!

轮数	MILP		本文算法
轮数	#S_D	T_MILP/s	#S_D	T_OurA/s
1	1	—	1	0
2	5	—	5	0.01
3	9	—	9	0.01
4	25	—	25	16.62
5	26	—	26	0.01
6	30	—	30	0.01
7	34	—	34	0.01
8	50	—	50	16.59
9	51	—	51	0.01
10	55	—	55	0.01
11	59	—	59	0.01
12	75	—	75	17.02
13	76	—	76	0.02
14	80	—	80	0.02
15	84	—	84	0.02
16	100	—	100	16.55
17	—	—	101	0.02
18	—	—	105	0.02
19	—	—	109	0.02
20	—	—	125	16.55
21	—	—	126	0.02
22	—	—	130	0.02
23	—	—	134	0.02
24	—	—	150	16.53
25	—	—	151	0.02
26	—	—	155	0.02
27	—	—	159	0.02
28	—	—	175	17.01
29	—	—	176	0.02
30	—	—	180	0.02
31	—	—	184	0.02
32	—	—	200	16.58
33	—	—	201	0.02
34	—	—	205	0.02
35	—	—	209	0.02
36	—	—	225	16.57
37	—	—	226	0.03
38	—	—	230	0.03
39	—	—	234	0.03
40	—	—	250	16.55
41	—	—	251	0.03
42	—	—	255	0.04
43	—	—	259	0.04
44	—	—	275	16.93
45	—	—	276	0.03
46	—	—	280	0.03
47	—	—	284	0.03
48	—	—	300	16.55

轮数	MILP			本文算法
轮数	#S_D	#S_L	T_MILP/s	#S_D	T_OurA/s	#S_L	T_OurA/s
1	1	1	—	1	0	1	0
2	2	2	—	2	0	2	0.01
3	5	5	—	5	0.01	5	0.01
4	8	8	—	8	0.01	8	0.01
5	12	13	—	12	0.01	13	0.01
6	16	19	—	16	0.01	19	0.03
7	26	25	—	26	0.18	25	0.05
8	36	32	—	36	2.67	32	0.2
9	41	38	—	41	0.39	38	0.21
10	46	43	—	46	0.79	43	0.16
11	51	48	—	51	0.82	48	0.2
12	55	52	—	55	0.3	52	0.1
13	58	55	—	58	0.1	55	0.02
14	61	58	—	61	0.03	58	0.02
15	66	64	—	66	0.05	64	0.03
16	75	70	—	75	0.39	70	0.07
17	82	76	—	82	0.61	76	0.11
18	88	80	—	88	0.46	80	0.02
19	92	85	—	92	0.06	85	0.03
20	96	90	—	96	0.07	90	0.05
21	102	96	—	102	0.28	96	0.15
22	108	102	—	108	0.60	102	0.47
23	114	107	—	112	0.21	107	0.22
24	116	110	—	116	0.19	110	0.03
25	124	118	—	124	0.77	115	0.05
26	132	122	—	128	0.06	121	0.1
27	138	128	—	132	0.04	127	0.17
28	136	136	—	136	0.02	130	0.03
29	148	141	—	142	0.04	135	0.05
30	158	143	—	148	0.06	141	0.1
31	—	—	—	154	0.16	147	0.42
32	—	—	—	160	0.21	153	0.59
33	—	—	—	164	0.04	157	0.09
34	—	—	—	168	4	160	0.04
35	—	—	—	172	0.03	166	0.09
36	—	—	—	176	0.03	172	0.13
37	—	—	—	182	0.04	177	0.09
38	—	—	—	188	0.05	180	0.04
39	—	—	—	194	0.06	186	0.09
40	—	—	—	200	0.07	192	0.33

轮数	MILP		本文算法
轮数	#S_D	T_MILP/s	#S_D	T_OurA/s
1	1	—	1	0
2	2	—	2	0.01
3	4	—	4	0.02
4	6	—	6	0.03
5	10	—	10	0.03
6	14	—	14	0.04
7	20	—	20	0.04
8	26	—	26	0.05
9	32	—	32	0.05
10	36	—	36	0.06
11	40	—	40	0.06
12	44	—	44	0.06
13	48	—	48	0.06
14	52	—	52	0.06
15	56	—	56	0.08
16	60	—	60	0.08
17	64	—	64	0.09
18	—	—	68	0.14
19	—	—	72	0.11
20	—	—	76	0.1
21	—	—	80	0.11
22	—	—	84	0.11
23	—	—	88	0.13
24	—	—	92	0.1
25	—	—	96	0.1
26	—	—	100	0.1
27	—	—	104	0.11
28	—	—	108	0.12
29	—	—	112	0.12
30	—	—	116	0.12
31	—	—	120	0.12

轮数	MILP		本文算法
轮数	#S_D	T_MILP/s	#S_D	T_OurA/s
1	1	—	1	0
2	4	—	4	0.01
3	7	—	7	0.01
4	16	—	16	8.97
5	22	—	25	21.94
6	32	—	36	229.86
7	42	—	47	430.37
8	48	—	60	0.83×3 600
9	—	—	66	8.44
10	—	—	72	16.42
11	—	—	77	0.31
12	—	—	86	12.31
13	—	—	95	24.28
14	—	—	104	12.27
15	—	—	114	55.99
16	—	—	124	57.96

Fast algorithm to search for the minimum number of active S-boxes of block cipher

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 32

Related Articles 15

Metrics

Recommended 0

[1]	Bin HU, Xiao TAN, Senpeng WANG. SAT-based differential automatic search algorithm using divide-and-conquer strategy and its applications [J]. Journal on Communications, 2023, 44(4): 137-144.
[2]	Shaoyu DU. Improved integral attack——random linear distinguish and key recovery attack [J]. Journal on Communications, 2023, 44(4): 145-153.
[3]	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.
[4]	Zilong JIANG, Chenhui JIN. Impossible differential cryptanalysis of Saturnin algorithm [J]. Journal on Communications, 2022, 43(3): 53-62.
[5]	Nianping WANG, Qing YIN. Differential security evaluation of Piccolo-like structure [J]. Journal on Communications, 2022, 43(2): 55-64.
[6]	Nianping WANG, Zhicheng GUO. Security evaluation against differential cryptanalysis for dynamic cryptographic structure [J]. Journal on Communications, 2021, 42(8): 70-79.
[7]	Min XIE,Jiaqi LI,Feng TIAN. Differential fault attack on FeW [J]. Journal on Communications, 2020, 41(4): 143-149.
[8]	Xiaonian WU,Yingxin LI,Yongzhuang WEI,Yaping SUN. Impossible differential distinguisher analysis of GRANULE and MANTRA algorithm [J]. Journal on Communications, 2020, 41(1): 94-101.
[9]	Min XIE,Feng TIAN,Jiaqi LI. Related-key impossible boomerang cryptanalysis on TWINE [J]. Journal on Communications, 2019, 40(9): 184-192.
[10]	Yu SHEN,Wei LI,Dawu GU,Yixin WU,Shan CAO,Ya LIU,Zhiqiang LIU,Zhihong ZHOU. Integral fault analysis of the ARIA cipher [J]. Journal on Communications, 2019, 40(2): 164-173.
[11]	Yang GAO,Yong-juan WANG,Lei WANG,Tao WANG. Improvement Differential fault attack on TWINE [J]. Journal on Communications, 2017, 38(Z2): 178-184.
[12]	Min XIE,Yan-li MU. Related-key impossible boomerang cryptanalysis on LBlock [J]. Journal on Communications, 2017, 38(5): 66-71.
[13]	Jie CUI,Hai-feng ZUO,Hong ZHONG. Biclique cryptanalysis on lightweight block ciphers I-PRESENT-80 and I-PRESENT-128 [J]. Journal on Communications, 2017, 38(11): 13-23.
[14]	Min WANG,Zhen WU,Jin-tao RAO,Hang LING. Round reduction-based fault attack on SM4 algorithm [J]. Journal on Communications, 2016, 37(Z1): 98-103.
[15]	Yong-juan WANG,Quan-yu2 REN,Shi-yi ZHANG. Differential fault attack on lightweight block cipher Klein [J]. Journal on Communications, 2016, 37(Z1): 111-115.