Design and implementation of cipher component security criteria testing tool

doi:10.11772/j.issn.1001-9081.2022091443

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (10): 3156-3161.DOI: 10.11772/j.issn.1001-9081.2022091443

• Cyber security • Previous Articles Next Articles

Design and implementation of cipher component security criteria testing tool

Shanshan HUO¹^,², Yanjun LI¹^,²(), Jian LIU¹, Yinshuang LI³

^1.Information Technology Security Testing and Evaluation Center，The 15th Research Institute of China Electronics Technology Group Corporation，Beijing 100083，China
^2.Guangxi Key Laboratory of Cryptography and Information Security （Guilin University of Electronic Technology），Guilin Guangxi 541004，China
^3.Department of Cryptographic Science and Technology，Beijing Electronic Science and Technology Institute，Beijing 100070，China

Received:2022-09-29 Revised:2022-12-16 Accepted:2022-12-28 Online:2023-03-16 Published:2023-10-10
Contact: Yanjun LI
About author:HUO Shanshan， born in 1981， senior engineer. Her research interests include information security， information system evaluation.
LIU Jian， born in 1983， M. S.， senior engineer. His research interests include network and information security， security assessment of commercial cryptographic applications.
LI Yinshuang， born in 1999， M. S. candidate. Her research interests include block cryptanalysis methods.
Supported by:
Open Project of Guangxi Key Laboratory of Cryptography and Information Security(GCIS201912);Open Project of Henan Key Laboratory of Network Cryptography Technology(LNCT2020-A09);Advanced Discipline Construction Project of Beijing Universities(20210101Z0401)

密码组件安全指标测试工具设计与实现

霍珊珊¹^,², 李艳俊¹^,²(), 刘健¹, 李寅霜³

^1.中国电子科技集团公司第十五研究所信息产业信息安全测评中心，北京 100083
^2.广西密码学与信息安全重点实验室（桂林电子科技大学），广西桂林 541004
^3.北京电子科技学院密码科学与技术系，北京 100070

通讯作者: 李艳俊
作者简介:霍珊珊（1981—），女，北京人，高级工程师，主要研究方向：信息安全、信息系统评估
刘健（1983—），男，浙江文成人，高级工程师，硕士，主要研究方向：网络与信息安全、商用密码应用安全性评估
李寅霜（1999—），女，四川成都人，硕士研究生，主要研究方向：分组密码分析方法。
基金资助:
广西密码学与信息安全重点实验室开放课题(GCIS201912);河南省网络密码技术重点实验室开放课题(LNCT2020?A09);北京高校“高精尖”学科建设项目(20210101Z0401)

Abstract

Abstract:

Symmetric cryptography is the core technology of data confidentiality in information systems. At the same time， nonlinear S-box is usually the key cryptographic component， and is widely used in the design of block cipher， stream cipher， MAC （Message Authentication Code） algorithm， etc. In order to ensure the security of the cryptographic algorithm design， firstly， the criteria testing methods for differential uniformity， nonlinearity， fixed point number， algebraic degree and item number， algebraic immunity， avalanche characteristic and diffusion characteristic were researched. Secondly， the results of each security criterion of the S-box were designed and output in the visual window， and the detailed descriptions of the corresponding security criterion were given in a pop-up window way. Thirdly， the design of the sub-components of nonlinearity and algebraic immunity was focused， and the linear distribution table was simplified according to the nonlinearity. At the same time， based on the theorem， the calculation process of algebraic immunity was optimized and illustrated with an example. Finally， the S-box testing tool was implemented with seven security criteria， and the test cases were demonstrated. The proposed tool is mainly used to test the security criteria of the nonlinear component S-box in the symmetric cryptographic algorithm， and then provides a guarantee for the security of the overall algorithm.

Key words: nonlinear component, S-box, security criterion, nonlinearity, algebraic immunity

摘要：

对称密码是信息系统中数据保密的核心技术，而非线性S盒通常是其中的关键密码组件，广泛用于分组密码、序列密码和MAC（Message Authentication Code）算法等设计。为了保障密码算法设计的安全性，首先，研究了差分均匀度、非线性度、不动点数、代数次数与项数、代数免疫度、雪崩特性、扩散特性的指标测试方法；其次，通过可视化窗口设计输出S盒的各个安全指标结果，并以弹窗形式给出对应安全指标的细节描述；再次，重点设计了S盒非线性度和代数免疫度的子模块，并对应非线性度简化了线性分布表，且基于定理对代数免疫度计算过程进行了优化和举例说明；最后，实现了S盒的测试工具，并给出了7种安全指标测试和案例演示。所提测试工具主要应用于对称密码算法的非线性组件S盒安全指标的测试，进而为算法整体提供安全保障。

关键词: 非线性组件, S盒, 安全指标, 非线性度, 代数免疫度

CLC Number:

TP393.08

Shanshan HUO, Yanjun LI, Jian LIU, Yinshuang LI. Design and implementation of cipher component security criteria testing tool[J]. Journal of Computer Applications, 2023, 43(10): 3156-3161.

霍珊珊, 李艳俊, 刘健, 李寅霜. 密码组件安全指标测试工具设计与实现[J]. 《计算机应用》唯一官方网站, 2023, 43(10): 3156-3161.

Figures/Tables 9

Fig. 1 S-box cryptographic criteria testing tool module

Tab. 1 Truth table for S1(x)

$x 2$	$x 1$	$S 1 (x)$	$x 3$	$x 2$	$x 1$	$S 1 (x)$
0	0	0	1	0	0	1
0	1	1	1	0	1	1
1	0	0	1	1	0	0
1	1	1	1	1	1	0

Tab. 1 Truth table for S1(x)

$x 2$	$x 1$	$S 1 (x)$	$x 3$	$x 2$	$x 1$	$S 1 (x)$
0	0	0	1	0	0	1
0	1	1	1	0	1	1
1	0	0	1	1	0	0
1	1	1	1	1	1	0

Tab. 2 Example of 4×4 S-box

x	y	x	y	x	y	x	y
0	2	4	13	8	10	12	3
1	1	5	4	9	14	13	9
2	6	6	8	10	0	14	12
3	11	7	7	11	15	15	5

Fig. 2 Display interface of S-box security criteria

Fig. 3 Distribution tables of differential and linearity

Fig. 4 Details of algebraic terms and algebraic immunity

Fig. 5 Details of avalanche and diffusion characteristics

Tab. 3 Testing results

算法	差分均匀度	非线性度	代数次数细节	代数项数细节	雪崩性	测试时间/ms
算法	差分均匀度	非线性度	代数次数细节	代数项数细节	雪崩性	本文工具	SET	BSAT
Present	4	4	3，3，3，2	8，8，7，4	3，3，3，1	6	1	7
AES	4	112	7，7，7，7，7，7，7，7	110，112，114，131，136，145，133，132	1，2，3，2，3，0，0，0	394	650	404
SM4	4	112	7，7，7，7，7，7，7，7	124，139，124，126，123，128，130，134	1，1，0，0，0，0，0，2	399	—	—

Tab. 4 Comparison of S-box testing tools

测试工具

差分

均匀度

非线性度

不动点

代数次数和项数

代数

免疫度

References 21

1	WEBSTER A F， TAVARES S E. On the design of S-boxes［C］// Proceedings of the 1985 Conference on the Theory and Application of Cryptographic Techniques， LNCS 218. Berlin： Springer， 1986： 523-534. 10.1007/3-540-39799-x_41
2	ADAMS C， TAVARES S. The structured design of cryptographically good S-boxes［J］. Journal of Cryptology， 1990， 3（1）： 27-41. 10.1007/bf00203967
3	DETOMBE J， TAVARES S. Constructing large cryptographically strong S-boxes［C］// Proceedings of the 1992 International Workshop on the Theory and Application of Cryptographic Techniques， LNCS 718. Berlin： Springer， 1993： 165-181. 10.1007/3-540-57220-1_60
4	MILLAN W. How to improve the nonlinearity of bijective S-boxes［C］// Proceedings of the 1998 Australasian Conference on Information Security and Privacy， LNCS 1438. Berlin： Springer， 1998： 181-192.
5	MATSUI M. New block encryption algorithm MISTY［C］// Proceedings of the 1997 International Workshop on Fast Software Encryption， LNCS 1267. Berlin： Springer， 1997： 54-68.
6	CARLET C， DALAI D K， GUPTA K C， et al. Algebraic immunity for cryptographically significant Boolean functions： analysis and construction［J］. IEEE Transactions on Information Theory， 2006， 52（7）： 3105-3121. 10.1109/tit.2006.876253
7	STOFFELEN K. Optimizing S-box implementations for several criteria using SAT solvers［C］// Proceedings of the 2016 International Conference on Fast Software Encryption， LNCS 9783. Berlin： Springer， 2016： 140-160.
8	LU Z， WANG W， HU K， et al. Pushing the limits： searching for implementations with the smallest area for lightweight S-boxes［C］// Proceedings of the 2021 International Conference on Cryptology in India， LNCS 13143. Cham： Springer， 2021： 159-178.
9	KELLY M， KAMINSKY A， KURDZIEL M， et al. Customizable sponge-based authenticated encryption using 16-bit S-boxes［C］// Proceedings of the 2015 IEEE Military Communications Conference. Piscataway： IEEE， 2015： 43-48. 10.1109/milcom.2015.7357416
10	李艳俊，张伟国，葛耀东，等. 基于多项式基的Camellia算法S盒硬件优化［J］. 电子与信息学报， 2023， 45（3）：921-928. 10.11999/JEIT220499
	LI Y J， ZHANG W G， GE Y D， et al. Hardware optimization of S-box of Camellia algorithm based on polynomial basis［J］. Journal of Electronics and Information Technology， 2023， 45（3）：921-928. 10.11999/JEIT220499
11	中国科学院软件研究所. 一种快速的S盒透明阶检测方法： 200810102906.9［P］. 2008-09-03.
	Institute of Software of Chinese Academy of Sciences. A fast detection method of S-box transparency order： 200810102906.9［P］. 2008-09-03.
12	中国科学院软件研究所. 一种S盒差分均匀性快速检测方法： 201010533858.6［P］. 2011-03-30.
	Institute of Software of Chinese Academy of Sciences. A fast detection method for S-box differential uniformity： 201010533858.6［P］. 2011-03-30.
13	桂林电子科技大学. 密码S盒评估方法： 201611265264.5［P］. 2017-05-31.
	Guilin University of Electronic Technology. Evaluation method of cryptographic S-box： 201611265264.5［P］. 2017-05-31.
14	蔡婧雯，韦永壮，刘争红. 基于GPU的密码S盒代数性质评估方法［J］. 计算机应用， 2022， 42（9）： 2750-2756. 10.11772/j.issn.1001-9081.2021081382
	CAI J W， WEI Y Z， LIU Z H. GPU-based method for evaluating the algebraic properties of cryptographic S-boxes［J］. Journal of Computer Applications， 2022， 42（9）： 2750-2756. 10.11772/j.issn.1001-9081.2021081382
15	严迎建，郑震，郭朋飞，等. 一种检测S盒能量信息泄漏的t检验方法［J］. 北京理工大学学报， 2021， 41（5）：542-547.
	YAN Y J， ZHENG Z， GUO P F， et al. A t-test method for detecting power information leakage of S-box［J］. Transactions of Beijing Institute of Technology， 2021， 41（5）： 542-547.
16	关杰，卢健伟，刘帅. 一类新的基于元胞自动机的S盒的线性性质研究［J］. 密码学报， 2021， 8（4）： 650-659.
	GUAN J， LU J W， LIU S. Research on linear properties of a new S-box based on cellular automata［J］. Journal of Cryptologic Research， 2021， 8（4）： 650-659.
17	PICEK S， BATINA L， JAKOBOVIĆ D， et al. S-box， SET， match： a toolbox for S-box analysis［C］// Proceedings of the 2014 IFIP International Workshop on Information Security Theory and Practice， LNCS 8501. Berlin： Springer， 2014： 140-149.
18	BEHERA P K， GANGOPADHYAY S. BSAT： a new tool for analyzing cryptographic strength of Boolean function and S-Box of symmetric cryptosystem［M］// PANIGRAHI C R， PATI B， PATTANAYAK B K， et al. Progress in Advanced Computing and Intelligent Engineering： Proceedings of ICACIE 2020， AISC 1299. Singapore： Springer， 2021： 557-569. 10.1007/978-981-33-4299-6_46
19	中国电子科技集团公司第十五研究所，中电科（北京）信息测评认证有限公司. 一种用于测试对称密码组件安全性的系统及方法：202210785240.1［P］. 2022-10-14.
	The 15th Research Institute of China Electronics Technology Group Corporation， CETC （Beijing） Information Evaluation and Certification Co.， Ltd. A system and method for testing the security of symmetric cryptographic components：202210785240.1［P］. 2022-10-14.
20	MATSUI M. Linear cryptanalysis method for DES cipher［C］// Proceedings of the 1993 Workshop on the Theory and Application of Cryptographic Techniques， LNCS 765. Berlin： Springer， 1994： 386-397. 10.1007/3-540-48285-7_33
21	吴文玲，冯登国，张文涛. 分组密码的设计与分析［M］. 2版. 北京：清华大学出版社， 2009： 225-234.
	WU W L， FENG D G， ZHANG W T. Design and Analysis of Block Cipher［M］. 2nd ed. Beijing： Tsinghua University Press， 2009： 225-234.

[1]	Runlian ZHANG, Mi ZHANG, Xiaonian WU, Rui SHU. Differential property evaluation method based on GPU for large-state cryptographic S-boxes [J]. Journal of Computer Applications, 2024, 44(9): 2785-2790.
[2]	Yanjun LI, Yaodong GE, Qi WANG, Weiguo ZHANG, Chen LIU. Improved KLEIN algorithm and its quantum analysis [J]. Journal of Computer Applications, 2024, 44(9): 2810-2817.
[3]	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.
[4]	Jinwei PU, Qingjian GAO, Xin ZHENG, Yinghui XU. SM4 resistant differential power analysis lightweight threshold implementation [J]. Journal of Computer Applications, 2023, 43(11): 3490-3496.
[5]	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.
[6]	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.
[7]	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.
[8]	MAN Le, ZHAO Yu, WANG Haoxian. Improved nonlinear brightness-lifting model for restoring backlight images [J]. Journal of Computer Applications, 2017, 37(2): 564-568.
[9]	ZHANG Yiyi, MENG Fanrong, ZHANG Fengrong, SHI Jihong. Construction of balanced Boolean functions using plateaued functions [J]. Journal of Computer Applications, 2016, 36(6): 1563-1566.
[10]	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.
[11]	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.
[12]	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.
[13]	CHEN Yindong XIANG Hongyan ZHANG Yanan. Construction of even-variable rotation symmetric Boolean functions with optimum algebraic immunity [J]. Journal of Computer Applications, 2014, 34(2): 444-447.
[14]	YUAN Hongbo YANG Xiaoyuan. Construction of almost optimal resilient Boolean functions via concatenation [J]. Journal of Computer Applications, 2013, 33(12): 3503-3505.
[15]	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.

Design and implementation of cipher component security criteria testing tool

密码组件安全指标测试工具设计与实现

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 9

References 21

Related Articles 15

Recommended Articles

Metrics