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

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

摘要/Abstract

摘要：

为了解决密码设计中最小活跃S盒个数的快速计算问题，研究了扩散层的差分和掩码传播性质，提出了一种计算最大距离可分（MDS）矩阵和二元域矩阵的差分/掩码模式分布表的方法，并证明了所提方法计算复杂度的下界。基于扩散矩阵的差分/掩码模式分布表，提出了一种快速搜索分组密码最小活跃S盒个数的算法，将其用于代入置换网络（SPN）型分组密码，找到了LED、SKINNY、CRAFT和FIDES的全轮最小活跃S盒个数。

关键词: 分组密码, 差分密码分析, 线性密码分析, 活跃S盒, 自动化搜索

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

中图分类号:

TN918

刘正斌, 李永强, 朱朝熹. 分组密码最小活跃S盒个数快速搜索算法[J]. 通信学报, 2023, 44(1): 118-128.

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.

图/表 6

图1

图2

表1

表2

表3

表4

参考文献 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.

轮数	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