Compact constraint analysis of SPONGENT S-box based on mixed integer linear programming model

doi:10.11772/j.issn.1001-9081.2022040496

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (5): 1504-1510.DOI: 10.11772/j.issn.1001-9081.2022040496

• Cyber security • Previous Articles Next Articles

Compact constraint analysis of SPONGENT S-box based on mixed integer linear programming model

Yipeng SHI¹, Jie LIU¹(), Jinyuan ZU¹, Tao ZHANG¹, Guoqun ZHANG²

^1.School of Software，Northwestern Polytechnical University，Xi'an Shaanxi 710129，China
^2.Shanghai Institute of Mechanical and Electrical Engineering，Shanghai 201109，China

Received:2022-04-13 Revised:2022-05-26 Accepted:2022-06-06 Online:2022-06-20 Published:2023-05-10
Contact: Jie LIU
About author:SHI Yipengi， born in 2001. His research interests include cryptography， software engineering.
LIU Jie， born in 1985， Ph. D.， associate professor. His research interests include cryptography， cybersecurity.
ZU Jinyuan， born in 2001. His research interests include cryptography， information safety.
ZHANG Tao，born in 1976， Ph. D.， associate professor. His research interests include intelligent robot， artificial intelligence，reinforcement learning， software testing.
ZHANG Guoqun，born in 1978， M. S.， senior engineer. Hisresearch interests include software testing， software engineering.
Supported by:
Shanghai Aerospace Science and Technology Innovation Fund(SAST2021?054);Basic Research Program of Taicang City(TC2021JC32);Fundamental Research Fund for Central Universities(D5000210638)

基于混合整数线性规划模型的SPONGENT S盒紧凑约束分析

石一鹏¹, 刘杰¹(), 祖锦源¹, 张涛¹, 张国群²

^1.西北工业大学软件学院，西安 710129
^2.上海机电工程研究所，上海 201109

通讯作者: 刘杰
作者简介:石一鹏（2001—），男，山西朔州人，主要研究方向：密码学、软件工程
刘杰（1985—），男，河南南阳人，副教授，博士，CCF会员，主要研究方向：密码学、网络安全 lucky_jiel@nwpu.edu.cn
祖锦源（2001—），男，安徽合肥人，主要研究方向：密码学、信息安全
张涛（1976—），男，陕西扶风人，副教授，博士，主要研究方向：智能机器人、人工智能、强化学习、软件测试
张国群（1978—），男，江苏高邮人，高级工程师，硕士，主要研究方向：软件测试、软件工程化。
基金资助:
上海航天科技创新基金资助项目(SAST2021?054);太仓市基础研究计划面上项目(TC2021JC32);中央高校基本科研业务费专项资金资助项目(D5000210638)

Abstract

Abstract:

Applying the compact constraint calculation method of S-box based on Mixed Integer Linear Programming （MILP） model can solve the low efficiency of differential path search of SPONGENT in differential cryptanalysis. To find the best description of S box， a compactness verification algorithm was proposed to verify the inequality constraints in S-box from the perspective of the necessity of the existence of constraints. Firstly， the MILP model was introduced to analyze the inequality constraints of SPONGENT S-box， and the constraint composed of 23 inequalities was obtained. Then， an index for evaluating the existence necessity of constraint inequality was proposed， and a compactness verification algorithm for verifying the compactness of group of constraint inequalities was proposed based on this index. Finally， the compactness of the obtained SPONGENT S-box constraint was verified by using the proposed algorithm. Calculation analysis show that the 23 inequalities have a unique impossible difference mode that can be excluded， that is， each inequality has the necessity of existence. Furthermore， for the same case， the number of inequalities was reduced by 20% compared to that screened by using the greedy algorithm principle. Therefore， the obtained inequality constraint of S-box in SPONGENT is compact， and the proposed compactness verification algorithm outperforms the greedy algorithm.

Key words: differential cryptanalysis, Mixed Integer Linear Programming (MILP), Substitution-Permutation Network (SPN), SPONGENT, S-box

摘要：

应用基于混合整数线性规划（MILP）模型的S盒紧凑约束计算方法，可以较好地解决SPONGENT在差分密码分析过程中差分路径搜索效率低下的问题；为寻找S盒的最优描述，提出一种紧凑性验证算法从约束条件存在必要性的角度验证S盒的不等式约束的紧凑性问题。首先，引入MILP模型分析SPONGENT S盒的不等式约束，得到了由23个不等式组成的约束；然后，提出一种用于评价约束不等式存在必要性的指标，并基于该指标提出了一种验证约束不等式组紧凑程度的紧凑性验证算法；最后，使用所提算法验证所求得的SPONGENT S盒约束的紧凑性。计算分析表明，23个不等式都具有唯一可以排除的不可能差分模式，即每个不等式都有存在的必要性；同时，对于同一案例，与利用贪心算法原理筛选的不等式相比，数量减少了20%。因此，所得到的SPONGENT的S盒不等式约束是紧凑的，且所提紧凑性验证算法的效果要优于对比的贪心算法。

关键词: 差分密码分析, 混合整数线性规划, 代换?置换网络, SPONGENT, S盒

CLC Number:

TP309.7

Yipeng SHI, Jie LIU, Jinyuan ZU, Tao ZHANG, Guoqun ZHANG. Compact constraint analysis of SPONGENT S-box based on mixed integer linear programming model[J]. Journal of Computer Applications, 2023, 43(5): 1504-1510.

石一鹏, 刘杰, 祖锦源, 张涛, 张国群. 基于混合整数线性规划模型的SPONGENT S盒紧凑约束分析[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1504-1510.

Figures/Tables 7

Tab. 1 SPONGENT version parameters

版本名称（SPONGENT-size/capacity/rate）	state	round
SPONGENT-88/80/8	88	45
SPONGENT-88/176/88	264	135
SPONGENT-128/128/8	136	70
SPONGENT-128/256/128	384	195
SPONGENT-160/160/16	176	90
SPONGENT-160/160/80	240	120
SPONGENT-160/320/160	480	240
SPONGENT-224/224/16	240	120
SPONGENT-224/224/112	336	170
SPONGENT-224/448/224	672	340
SPONGENT-256/256/16	272	140
SPONGENT-256/256/128	384	195
SPONGENT-256/512/256	768	385

Tab. 2 Hexadecimal representation of S-box specification

$x$	$S (x)$	$x$	$S (x)$
0	E	8	7
1	D	9	A
2	B	A	8
3	0	B	5
4	2	C	9
5	1	D	C
6	4	E	3
7	F	F	6

Tab. 2 Hexadecimal representation of S-box specification

$x$	$S (x)$	$x$	$S (x)$
0	E	8	7
1	D	9	A
2	B	A	8
3	0	B	5
4	2	C	9
5	1	D	C
6	4	E	3
7	F	F	6

Tab. 3 Example of 2D guidance table

不可能差分模式	不等式
不可能差分模式	Q₁	Q₂	Q₃	…	Q_N
I₁	1	0	1	…	0
I₂	1	1	0	…	1
I₃	0	0	0	…	1
︙	︙	︙	︙		︙
I_M	1	0	1	…	0

Tab. 4 Input-output difference table

输入差分	输出差分
0000	0000
0001	0011，0101，1011，1101
0010	0101，0110，1010，1101，1110，1111
0011	0010，0101，0110，1101，1110，1111
0100	0011，0110，1011，1100，1110，1111
0101	0011，0100，0110，1011，1110，1111
0110	0001，0010，0100，1001，1010，1100
0111	0001，0010，0100，1001，1010，1100
1000	0011，0101，0111，1001，1011，1101
1001	0010，0100，1000，1010，1100，1110
1010	0001，0011，0110，0111，1000，1010，1100，1101
1011	0001，0010，0100，0101，0110，0111，1000，1011
1100	0001，0101，0110，0111，1000，1010，1011，1100
1101	0001，0010，0011，0100，0110，0111，1000，1101
1110	0010，0011，0100，0101，1010，1011，1100，1101
1111	0111，1000，1001，1110

Tab. 5 Case of redundant inequality constraints

不可能差分模式	不等式
不可能差分模式	$Q 1$	$Q 2$	$Q 3$	$Q 4$	$Q 5$	$Q 6$	$Q 7$	$Q 8$
$I 1$	1	0	1	1	0	1	0	0
$I 2$	1	1	0	0	1	0	0	0
$I 3$	0	1	0	1	1	0	0	0
$I 4$	1	1	0	0	0	0	0	0
$I 5$	1	0	1	0	0	0	0	0
$I 6$	0	0	0	1	0	1	0	0
$I 7$	0	1	0	0	0	0	0	1
$I 8$	1	0	1	0	0	0	1	1
$I 9$	0	0	1	1	0	1	0	0
$I 10$	1	1	1	0	0	0	0	0
$I 11$	0	0	0	0	1	0	1	0

Tab. 5 Case of redundant inequality constraints

不可能差分模式	不等式
不可能差分模式	$Q 1$	$Q 2$	$Q 3$	$Q 4$	$Q 5$	$Q 6$	$Q 7$	$Q 8$
$I 1$	1	0	1	1	0	1	0	0
$I 2$	1	1	0	0	1	0	0	0
$I 3$	0	1	0	1	1	0	0	0
$I 4$	1	1	0	0	0	0	0	0
$I 5$	1	0	1	0	0	0	0	0
$I 6$	0	0	0	1	0	1	0	0
$I 7$	0	1	0	0	0	0	0	1
$I 8$	1	0	1	0	0	0	1	1
$I 9$	0	0	1	1	0	1	0	0
$I 10$	1	1	1	0	0	0	0	0
$I 11$	0	0	0	0	1	0	1	0

Tab. 6 Optimization results of inequality constraint set

算法	不等式集合	必要度	紧凑性
贪心算法^［15］	$Q 1$ ， $Q 2$ ， $Q 3$ ， $Q 4$ ， $Q 5$	0，1，0，1，1	不紧凑
本文算法	$Q 2$ ， $Q 3$ ， $Q 4$ ， $Q 5$	2，2，1，1	紧凑

Tab. 6 Optimization results of inequality constraint set

算法	不等式集合	必要度	紧凑性
贪心算法^［15］	$Q 1$ ， $Q 2$ ， $Q 3$ ， $Q 4$ ， $Q 5$	0，1，0，1，1	不紧凑
本文算法	$Q 2$ ， $Q 3$ ， $Q 4$ ， $Q 5$	2，2，1，1	紧凑

Tab. 7 Necessities of inequality constraints

不等式	必要度	不等式	必要度
$I 9$	4	$I 132$	4
$I 12$	2	$I 155$	2
$I 18$	2	$I 180$	8
$I 21$	3	$I 182$	3
$I 41$	5	$I 194$	11
$I 48$	7	$I 211$	3
$I 70$	2	$I 224$	1
$I 83$	6	$I 240$	8
$I 89$	3	$I 250$	7
$I 97$	5	$I 270$	4
$I 101$	1	$I 285$	6
$I 116$	1

Tab. 7 Necessities of inequality constraints

不等式	必要度	不等式	必要度
$I 9$	4	$I 132$	4
$I 12$	2	$I 155$	2
$I 18$	2	$I 180$	8
$I 21$	3	$I 182$	3
$I 41$	5	$I 194$	11
$I 48$	7	$I 211$	3
$I 70$	2	$I 224$	1
$I 83$	6	$I 240$	8
$I 89$	3	$I 250$	7
$I 97$	5	$I 270$	4
$I 101$	1	$I 285$	6
$I 116$	1

References 19

1	BOGDANOV A， KNEŽEVIĆ M， LEANDER G， et al. SPONGENT： a lightweight hash function［C］// Proceedings of the 2011 International Workshop on Cryptographic Hardware and Embedded Systems， LNCS 6917. Berlin： Springer， 2011： 312-325.
2	BOGDANOV A， KNEŽEVIĆ M， LEANDER G， et al. SPONGENT： the design space of lightweight cryptographic hashing［J］. IEEE Transactions on Computers， 2013， 62（10）： 2041-2053. 10.1109/tc.2012.196
3	BOGDANOV A， KNUDSEN L R， LEANDER G， et al. PRESENT： an ultra-lightweight block cipher［C］// Proceedings of the 2007 International Workshop on Cryptographic Hardware and Embedded Systems， LNCS 4727. Berlin： Springer， 2007： 450-466.
4	ANKELE R， LIST E. Differential cryptanalysis of round-reduced Sparx-64/128［C］// Proceedings of the 2018 International Conference on Applied Cryptography and Network Security， LNCS 10892. Cham： Springer， 2018： 459-475.
5	ElSHEIKH M， YOUSSEF A M. Related-key differential cryptanalysis of full round CRAFT［C］// Proceedings of the 2019 International Conference on Security， Privacy， and Applied Cryptography Engineering， LNCS 11947. Cham： Springer， 2019： 50-66.
6	JI F L， ZHANG W T， ZHOU C N， et al. Improved （related-key） differential cryptanalysis on GIFT［C］// Proceedings of the 2020 International Conference on Selected Areas in Cryptography， LNCS 12804. Cham： Springer， 2021： 198-228.
7	杨继林，王念平. 类CLEFIA动态密码结构抵抗差分密码分析能力评估［J］. 电子学报， 2021， 49（11）：2279-2283. 10.12263/DZXB.20180973
	YANG J L， WANG N P. Security evaluation against differential cryptanalysis for CLEFIA-like dynamic cryptographic structure［J］. Acta Electronica Sinica， 2021， 49（11）：2279-2283. 10.12263/DZXB.20180973
8	WEI Y C， XU P， RONG Y S. Related-key impossible differential cryptanalysis on lightweight cipher TWINE［J］. Journal of Ambient Intelligence and Humanized Computing， 2019， 10（2）： 509-517. 10.1007/s12652-017-0675-1
9	MOGHADDAM A E， AHMADIAN Z. New automatic search method for truncated-differential characteristics application to Midori， SKINNY and CRAFT［J］. The Computer Journal， 2020， 63（12）： 1813-1825. 10.1093/comjnl/bxaa004
10	HUTAHAEAN I W， LESTARI A A， SUSANTI B H. A tutorial of boomerang attack on SMALLPRESENT-［4］［J］. Journal of Physics： Conference Series， 2021， 1836： No.012029. 10.1088/1742-6596/1836/1/012029
11	陈少真，薛平，杨行. 减轮GOST2的相关密钥差分攻击［J］. 信息工程大学学报， 2019， 20（3）：335-339， 345. 10.3969/j.issn.1671-0673.2019.03.014
	CHEN S Z， XUE P， YANG X. Related-key differential attack of reduced rounds of GOST2［J］. Journal of Information Engineering University， 2019， 20（3）：335-339， 345. 10.3969/j.issn.1671-0673.2019.03.014
12	MOUHA N， WANG Q J， GU D W， et al. Differential and linear cryptanalysis using mixed-integer linear programming［C］// Proceedings of the 2011 International Conference on Information Security and Cryptology， LNCS 7537. Berlin： Springer， 2012： 57-76.
13	GROSSO V， LEURENT G， STANDAERT F X， et al. LS-designs： bitslice encryption for efficient masked software implementations［C］// Proceedings of the 2014 International Workshop on Fast Software Encryption， LNCS 8540. Berlin： Springer， 2015： 18-37.
14	BANIK S， PANDEY S K， PEYRIN T， et al. GIFT： a small present： towards reaching the limit of lightweight encryption［C］// Proceedings of the 2017 International Conference on Cryptographic Hardware and Embedded Systems， LNCS 10529. Cham： Springer， 2017： 321-345.
15	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 2014 International Conference on the Theory and Application of Cryptology and Information Security， LNCS 8873. Berlin： Springer， 2014： 158-178.
16	SASAKI Y， TODO Y. New algorithm for modeling S-box in MILP based differential and division trail search［C］// Proceedings of the 2017 International Conference for Information Technology and Communications， LNCS 10543. Cham： Springer， 2017： 150-165.
17	ZHU B Y， DONG X Y， YU H B. MILP-based differential attack on round-reduced GIFT［C］// Proceedings of the 2019 Cryptographers’ Track at the RSA Conference， LNCS 11405. Cham： Springer， 2019： 372-390.
18	BAGHERZADEH E， AHMADIAN Z. MILP-based automatic differential search for LEA and HIGHT block ciphers［J］. IET Information Security， 2020， 14（5）： 595-603. 10.1049/iet-ifs.2018.5539
19	KUMAR M， YADAV T. MILP based differential attack on round reduced WARP［C］// Proceedings of the 2021 International Conference on Security， Privacy， and Applied Cryptography Engineering， LNCS 13162. Cham： Springer， 2022： 42-59.

[1]	Jingwen CAI, Yongzhuang WEI, Zhenghong LIU. GPU-based method for evaluating algebraic properties of cryptographic S-boxes [J]. Journal of Computer Applications, 2022, 42(9): 2750-2756.
[2]	Geng ZHAO, Senmin ZHANG, Yingjie MA, Shirui GAO. Design and analysis of dynamic S-box based on anti-degradation chaotic system [J]. Journal of Computer Applications, 2022, 42(10): 3069-3073.
[3]	ZHAO Ying, YE Tao, WEI Yongzhuang. New security analysis of several kinds of high-level cryptographical S-boxes [J]. Journal of Computer Applications, 2017, 37(9): 2572-2575.
[4]	HU Zhihua, YAN Shuo, XIONG Kuanjiang. Dynamic S-box construction method and dynamic cryptography property analysis [J]. Journal of Computer Applications, 2016, 36(5): 1257-1261.
[5]	QIN Guanjie, MA Jianshe, CHENG Xuemin. Method for increasing S-box nonlinearity based on combination of hill climbing [J]. Journal of Computer Applications, 2015, 35(8): 2195-2198.
[6]	LI Lingchen, WEI Yongzhuang, ZHU Jialiang. Meet-in-the-middle attack on 11-round reduced 3D block cipher [J]. Journal of Computer Applications, 2015, 35(3): 700-703.
[7]	HE Yuan TIAN Simei. Block encryption algorithm based on chaotic S-box for wireless sensor network [J]. Journal of Computer Applications, 2013, 33(04): 1081-1084.
[8]	. Construction method of S-box suitable for hardware implementation [J]. Journal of Computer Applications, 2010, 30(3): 674-676.
[9]	. S-boxes reorganization algorithm for a class of block ciphers [J]. Journal of Computer Applications, 2009, 29(08): 2198-2199.
[10]	. New S-boxes for hardware implementation of AES [J]. Journal of Computer Applications, 2007, 27(4): 852-853.
[11]	;. Optimum algorithm of S-boxes based on fast convergence speed genetic algorithm [J]. Journal of Computer Applications, 2006, 26(4): 803-805.

Compact constraint analysis of SPONGENT S-box based on mixed integer linear programming model

基于混合整数线性规划模型的SPONGENT S盒紧凑约束分析

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 19

Related Articles 11

Recommended Articles

Metrics