Differential property evaluation method based on GPU for large-state cryptographic S-boxes

doi:10.11772/j.issn.1001-9081.2023091268

Journal of Computer Applications ›› 2024, Vol. 44 ›› Issue (9): 2785-2790.DOI: 10.11772/j.issn.1001-9081.2023091268

• Cyber security • Previous Articles Next Articles

Differential property evaluation method based on GPU for large-state cryptographic S-boxes

Runlian ZHANG(), Mi ZHANG, Xiaonian WU, Rui SHU

Guangxi Key Laboratory of Cryptography and Information Security （Guilin University of Electronic Technology），Guilin Guangxi 541004，China

Received:2023-09-18 Revised:2023-12-19 Accepted:2023-12-20 Online:2024-01-31 Published:2024-09-10
Contact: Runlian ZHANG
About author:ZHANG Mi， born in 1998， M. S. candidate. Her research interests include information security.
WU Xiaonian， born in 1972， M. S.， professor. His research interests include information security， distributed computing.
SHU Rui， born in 1998， M. S. candidate. His research interests include information security.
Supported by:
National Natural Science Foundation of China(62062026);Key Research and Development Program of Guangxi(GuiKe AB23026131);Innovation Research Team Project of Guangxi(2019GXNSFGA245004)

基于GPU的大状态密码S盒差分性质评估方法

张润莲(), 张密, 武小年, 舒瑞

广西密码学与信息安全重点实验室（桂林电子科技大学），广西桂林 541004

通讯作者: 张润莲
作者简介:张润莲（1974—），女，山西介休人，副教授，博士，主要研究方向：信息安全、分布式计算
张密（1998—），女，贵州毕节人，硕士研究生，主要研究方向：信息安全
武小年（1972—），男，湖北监利人，教授，硕士，主要研究方向：信息安全、分布式计算
舒瑞（1998—），男，四川广安人，硕士研究生，主要研究方向：信息安全。
基金资助:
国家自然科学基金资助项目(62062026);广西重点研发计划项目(桂科AB23026131);广西创新研究团队项目(2019GXNSFGA245004)

Abstract

Abstract:

Large-state cryptographic S-boxes can provide better obfuscation for symmetric encryption algorithms， but the costs for evaluating their properties are very expensive. To efficiently evaluate the differential properties of large-state cryptographic S-boxes， a GPU-based method for evaluating the differential properties of large-state cryptographic S-boxes was proposed. According to the existing differential uniformity calculation method， the GPU parallel schemes were designed for evaluating differential uniformity of 16-bit S-boxes and differential properties of 32-bit S-boxes respectively. The execution efficiencies of kernel functions and GPU were improved by the schemes， and the time costs were reduced by optimizing GPU parallel granularity and load balancing. The test results show that， compared with CPU methods and GPU parallel methods， the time costs of the proposed schemes for evaluating the differential properties of large-state cryptographic S-boxes are greatly reduced. The time for computing the differential uniformity of 16-bit S-box is 0.3 min； for a single input differential of 32-bit S-box， the time for computing the maximum output differential probability is about 5 min， and the time for evaluating the differential properties is about 2.6 h.

Key words: cryptographic S-box, differential cryptanalysis, differential uniformity, maximum output differential probability, GPU parallel computing

摘要：

大状态的密码S盒能够为对称密码算法提供更好的混淆性，但对大状态S盒的性质评估开销巨大。为高效评估大状态密码S盒的差分性质，提出基于GPU并行计算的大状态密码S盒差分性质评估方法。该方法基于现有的差分均匀度计算方法，针对16比特S盒的差分均匀度和32比特S盒的差分性质，分别设计GPU并行方案，通过优化GPU并行粒度和负载均衡提高了核函数和GPU的执行效率，并缩短了计算时间。测试结果表明，相较于CPU方法和GPU并行方法，所提方法大幅降低了大状态S盒差分性质评估的计算时间，提高了对大状态S盒差分性质的评估效率：对16比特S盒差分均匀度的计算时间为0.3 min；对32比特S盒的单个输入差分的最大输出差分概率计算时间约5 min，对它的差分性质计算时间约2.6 h。

关键词: 密码S盒, 差分密码分析, 差分均匀度, 最大输出差分概率, GPU并行计算

CLC Number:

TP309

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.

张润莲, 张密, 武小年, 舒瑞. 基于GPU的大状态密码S盒差分性质评估方法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2785-2790.

Figures/Tables 5

Fig. 1 CPU hardware architecture

Fig. 2 GPU hardware architecture

Fig. 3 CPU-GPU heterogeneous programming architecture

Fig. 4 Implementation example of CUDA parallel protocol

Tab. 1 Comparison of 16-bit S-box differential uniformity calculation time among various methods

方法	计算时间
CPU^［14］	4 320.0
单GPU^［14］	420.0
多GPU^［14］	2.0
CPU（本文方法）	1.0
单GPU（本文方法）	0.3

References 18

1	BEN-AROYA I， BIHAM E. Differential cryptanalysis of Lucifer［C］// Proceedings of the 13th Annual International Cryptology Conference. Berlin： Springer， 1993： 187-199.
2	NYBERG K. S-boxes and round functions with controllable linearity and differential uniformity ［C］// Proceedings of the 2nd International Workshop on Fast Software Encryption. Berlin： Springer， 1994： 111-130.
3	NYBERG K. On the construction of highly nonlinear permutations［C］// Proceedings of the 1992 Workshop on the Theory and Application of Cryptographic Techniques. Berlin： Springer， 1992： 92-98.
4	PROUFF E. DPA attacks and S-boxes ［C］// Proceedings of the 12th International Workshop on Fast Software Encryption. Berlin： Springer， 2005： 424-441.
5	COOK S. CUDA Programming： a Developer’s Guide to Parallel Computing with GPUs ［M］. San Francisco： Morgan Kaufmann Publishers Inc.， 2012：21-36.
6	乐德广，常晋义，刘祥南，等. 基于GPU的MD5高速解密算法的实现［J］.计算机工程，2010，36（11）： 154-155.
	LE D G， CHANG J Y， LIU X N， et al. Implementation of MD5 fast decryption algorithm based on graphic processing unit ［J］. Computer Engineering， 2010， 36（11）： 154-155.
7	张润梅，王霄. 基于CUDA架构的MD5破解方法研究［J］. 计算机科学， 2011， 38（2）：302-304.
	ZHANG R M， WANG X. MD5 crack method based on compute unified device architecture ［J］. Computer Science， 2011， 38（2）： 302-304.
8	夏春林，周德云，张堃. AES算法的CUDA高效实现方法［J］.计算机应用研究，2013，30（6）：1907-1909.
	XIA C L， ZHOU D Y， ZHANG K. CUDA based high-efficiency implementation of AES algorithm ［J］. Application Research of Computers， 2013， 30（6）：1907-1909.
9	费雄伟，李肯立，阳王东，等. 基于CUDA的并行AES算法的实现和加速效率探索［J］. 计算机科学， 2015， 42（1）： 59-62.
	FEI X W， LI K L， YANG W D， et al. Implementation and exploring of acceleration efficiency of parallel AES algorithm on CUDA ［J］. Computer Science， 2015， 42（1）： 59-62.
10	ABDELRAHMAN A A， FOUAD M M， DAHSHAN H， et al. High performance CUDA AES implementation： a quantitative performance analysis approach ［C］// Proceedings of the 2017 Computing Conference. Piscataway： IEEE， 2017： 1077-1085.
11	W-Z YEOH， TEH J S， CHEN J. Automated search for block cipher differentials： a GPU-accelerated branch-and-bound algorithm ［C］// Proceedings of the 25th Australasian Conference on Information Security and Privacy. Cham： Springer， 2020： 160-179.
12	LI P， ZHOU S， CHEN J. A CPU-GPU-based parallel search algorithm for the best differential characteristics of block ciphers［J］. The Journal of Supercomputing， 2021， 77： 11460-11480.
13	W-Z YEOH， TEH J S， CHEN J. Automated enumeration of block cipher differentials： an optimized branch-and-bound GPU framework ［J］. Journal of Information Security and Applications， 2022， 65： 103087.
14	蔡婧雯，韦永壮，刘争红. 基于GPU的密码S盒代数性质评估方法［J］. 计算机应用， 2022， 42（9）： 2750-2756.
	CAI J W， WEI Y Z， LIU Z H. GPU-based method for evaluating algebraic properties of cryptographic S-boxes ［J］. Journal of Computer Applications， 2022， 42（9）： 2750-2756.
15	刘彦宾，谢海英. 最大差分和线性概率的计算方法［J］. 通信技术， 2009， 42（7）： 110-112.
	LIU Y B， XIE H Y. A method for computing maximum probability of differential characteristic and linear approximation ［J］. Communications Technology， 2009， 42（7）： 110-112.
16	NYBERG K. Differentially uniform mappings for cryptography［C］// Proceedings of the 1993 Workshop on the Theory and Application of Cryptographic Techniques. Berlin： Springer， 1993： 55-64.
17	徐洪，段明，谭林，等. 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.
18	田甜，戚文峰，叶晨东，等. 基于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.

[1]	Dongdong LIN, Manman LI, Shaozhen CHEN. Conditional differential cryptanalysis method of KATAN48 algorithm based on neural distinguishers [J]. Journal of Computer Applications, 2023, 43(8): 2462-2470.
[2]	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.
[3]	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.
[4]	WEI Haoyang ZENG Guosun DING Chunling. Parallel computing and numerical analysis of laminar diffusion combustion on GPU [J]. Journal of Computer Applications, 2013, 33(09): 2428-2431.

Differential property evaluation method based on GPU for large-state cryptographic S-boxes

基于GPU的大状态密码S盒差分性质评估方法

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 5

References 18

Related Articles 4

Recommended Articles

Metrics