GPU-based method for evaluating algebraic properties of cryptographic S-boxes

doi:10.11772/j.issn.1001-9081.2021081382

Journal of Computer Applications ›› 2022, Vol. 42 ›› Issue (9): 2750-2756.DOI: 10.11772/j.issn.1001-9081.2021081382

Special Issue: 网络空间安全

• Cyber security • Previous Articles Next Articles

GPU-based method for evaluating algebraic properties of cryptographic S-boxes

Jingwen CAI¹, Yongzhuang WEI¹(), Zhenghong LIU²

^1.Guangxi Key Laboratory of Cryptography and Information Security（Guilin University of Electronic Technology），Guilin Guangxi 541004，China
^2.Guangxi Key Laboratory of Wireless Wideband Communication and Signal Processing（Guilin University of Electronic Technology），Guilin Guangxi 541004，China

Received:2021-08-03 Revised:2021-11-20 Accepted:2021-11-21 Online:2022-01-07 Published:2022-09-10
Contact: Yongzhuang WEI
About author:CAI Jingwen， born in 1997， M. S. candidate. Her research interests include block cipher algorithm， GPU parallel computing.
LIU Zhenghong， born in 1979， M. S.， senior experimentalist. His research interests include wireless broadband communications， FPGA， GPU parallel computing.
Supported by:
National Natural Science Foundation of China(61872103);Natural Science Foundation of Guangxi(2019GXNSFGA245004)

基于GPU的密码S盒代数性质评估方法

蔡婧雯¹, 韦永壮¹(), 刘争红²

^1.广西密码学与信息安全重点实验室(桂林电子科技大学), 广西桂林 541004
^2.广西无线宽带通信与信号处理重点实验室(桂林电子科技大学), 广西桂林 541004

通讯作者: 韦永壮
作者简介:蔡婧雯（1997—），女，广东东莞人，硕士研究生，主要研究方向：分组密码算法、GPU并行计算；
刘争红（1979—），男，湖北红安人，高级实验师，硕士，主要研究方向：无线宽带通信、FPGA、GPU并行计算。
基金资助:
国家自然科学基金资助项目(61872103);广西自然科学基金资助项目(2019GXNSFGA245004)

Abstract

Abstract:

Cryptographic S-boxes （or black boxes） are nonlinear components in symmetric encryption algorithms， and their algebraic properties usually determine the security performance of these encryption algorithms. Differential uniformity， nonlinearity and revised transparency order are three basic indicators to evaluate the security properties of cryptographic S-boxes. They describe the S-box’s ability against differential cryptanalysis， linear cryptanalysis and differential power attack respectively. When the input size of the cryptographic S-box is large （for example， the input length of the S-box is larger than 15 bits）， the needed solving time in Central Processing Unit （CPU） is still too long， or even the solution is impracticable. How to evaluate the algebraic properties of the large-size S-box quickly is currently a research hot point in the field. Therefore， a method to evaluate the algebraic properties of cryptographic S-boxes quickly was proposed on the basis of Graphics Processing Unit （GPU）. In this method， the kernel functions were split into multiple threads by slicing technique， and an optimization scheme was proposed by combining the characteristics of solving differential uniformity， nonlinearity and revised transparency order to realize parallel computing. Experimental results show that compared with CPU-based implementation environment， single GPU based environment has the implementation efficiency significantly improved. Specifically， the time spent on calculating differential uniformity， nonlinearity， and revised transparency order is saved by 90.28%， 80%， and 66.67% respectively， which verifies the effectiveness of this method.

Key words: symmetric encryption algorithm, cryptographic S-box, Graphics Processing Unit (GPU), parallel computing, differential uniformity, nonlinearity, revised transparency order

摘要：

密码S盒即黑盒，作为对称密码算法中的非线性部件，其代数性质往往决定着密码算法的安全性能。差分均匀度、非线性度及透明阶作为衡量密码S盒安全性质的三个基本指标，分别刻画了S盒抵御差分密码分析、线性密码分析及差分功耗攻击的能力。当密码S盒输入尺寸较大（如S盒输入长度大于15比特）时在中央处理器（CPU）中的求解所需时间仍过长，甚至求解不可行。如何针对大尺寸输入密码S盒的代数性质进行快速评估是目前业界的研究热点。基于图形处理器（GPU）提出一种快速评估密码S盒代数性质的方法。该方法利用切片技术将内核函数拆分至多线程，并结合求解差分均匀度、非线性度及透明阶的特征提出优化方案，从而实现并行计算。测试结果表明，与基于CPU的实现环境相比，基于单块GPU的环境下的实现效率得到了显著的提升。具体来说，计算差分均匀度、非线性度及透明阶所花时间分别节省了90.28%、78.57%、60%，验证了该方法的有效性。

关键词: 对称密码算法, 密码S盒, 图形处理器, 并行计算, 差分均匀度, 非线性度, 透明阶

CLC Number:

TP309.7

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.

蔡婧雯, 韦永壮, 刘争红. 基于GPU的密码S盒代数性质评估方法[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2750-2756.

Figures/Tables 9

Fig. 1 Difference between CPU and GPU architectures

Fig. 2 Task time consumption comparison of CPU and GPU

Tab. 1 Three modes of NBC algorithm

算法模式	明文长度/bit	密钥长度/bit	轮数
NBC-128/128	128	128	32
NBC-128/256	128	256	34
NBC-256/256	256	256	38

Fig. 3 One-round NBC-128/128 structure with 8 branches

Fig. 4 S-box structure of NBC-128 algorithm

Fig. 5 CPU-GPU heterogeneous parallel flowchart

Fig. 6 Multi-GPU node architecture

Fig. 7 Comparison of time cost with and without overlapping optimization

Fig. 8 Comparison of running time under CPU， single GPU and multi-GPU

References 21

1	BENNETT C H， SHOR P W. Quantum information theory［J］. IEEE Transactions on Information Theory， 1998， 44（6）： 2724-2742. 10.1109/18.720553
2	National Institute of Standards and Technology. Lightweight cryptography-round-1-candidates［EB/OL］. ［2020-08-12］.. 10.3390/electronics9111940
3	BEIERLE C， BIRYUKOV A， CARDOSO DOS SANTOS L， et al. Lightweight AEAD and hashing using the SPARKLE permutation family［J］. IACR Transactions on Symmetric Cryptology， 2020， 2020（S1）： 208-261. 10.46586/tosc.v2020.is1.208-261
4	BANIK S， CHAKRABORTI A， IWATA T， et al. GIFT-COFB［EB/OL］. （2020-06-18）［2021-06-12］..
5	中国密码学会. 关于举办全国密码算法设计竞赛的通知［EB/OL］. （2018-06-11）［2021-06-12］.. 10.17706/jcp.11.2.140-148
	Chinese Association for Cryptologic Research. Notice on holding a national cryptographic algorithm design competition［EB/OL］. （2018-06-11）［2021-06-12］.. 10.17706/jcp.11.2.140-148
6	徐洪，段明，谭林，等. NBC算法［J］. 密码学报， 2019， 6（6）： 760-767. 10.13868/j.cnki.jcr.000339
	XU H， DUAN M， TAN L， et al. On the NBC algorithm［J］. Journal of Cryptologic Research， 2019， 6（6）： 760-767. 10.13868/j.cnki.jcr.000339
7	田甜，戚文峰，叶晨东，等. 基于NFSR的分组密码算法SPRING［J］. 密码学报， 2019， 6（6）： 815-834. 10.13868/j.cnki.jcr.000343
	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. 10.13868/j.cnki.jcr.000343
8	BEIERLE C， CARDOSO DOS SANTOS L， et al. Alzette： a 64-bit ARX-box （feat. CRAX and TRAX）［C］// Proceedings of the 2020 Annual International Cryptology Conference， LNCS 12172 . Cham： Springer， 2020： 419-448.
9	CANTEAUT A， DUVAL S， LEURENT G. Construction of lightweight S-boxes using Feistel and MISTY structures［C］// Proceedings of the 2015 International Conference on Selected Areas in Cryptography， LNCS 9566. Cham： Springer， 2016： 373-393.
10	GHOSHAL A， SADHUKHAN R， PATRANABIS S， et al. Lightweight and side-channel secure 4×4 S-boxes from cellular automata rules［J］. IACR Transactions on Symmetric Cryptology， 2018， 2018（3）： 311-334. 10.46586/tosc.v2018.i3.311-334
11	PICEK S， MARIOT L， YANG B H， et al. Design of S-boxes defined with cellular automata rules［C］// Proceedings of the 2017 ACM International Conference on Computing Frontiers. New York： ACM， 2017： 409-414. 10.1145/3075564.3079069
12	LI H Z， ZHOU Y B， MING J D， et al. The notion of transparency order， revisited［J］. The Computer Journal， 2020， 63（12）： 1915-1938. 10.1093/comjnl/bxaa069
13	MARIOT L， PICEK S， LEPORATI A， et al. Cellular automata-based S-boxes［J］. Cryptography and Communications， 2019， 11（1）： 41-62. 10.1007/s12095-018-0311-8
14	BIHAM E， SHAMIR A. Differential cryptanalysis of DES-like cryptosystems［J］. Journal of Cryptology， 1991， 4（1）： 3-72. 10.1007/bf00630563
15	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.
16	KOCHER P， JAFFE J， JUN B. Differential power analysis［C］// Proceedings of the 1999 Annual International Cryptology Conference， LNCS 1666. Berlin： Springer， 1999： 388-397.
17	KEDEM G， ISHIHARA Y. Brute force attack on UNIX passwords with SIMD computer［C］// Proceedings of the 8th USENIX Security Symposium. Berkeley： USENIX Association， 1999： 93-98.
18	MANAVSKI S A. CUDA compatible GPU as an efficient hardware accelerator for AES cryptography［C］// Proceedings of the 2007 IEEE International Conference on Signal Processing and Communications. Piscataway： IEEE， 2007： 65-68. 10.1109/icspc.2007.4728256
19	CHEONG H S， LEE W K. Fast implementation of block ciphers and PRNGs for Kepler GPU architecture［C］// Proceedings of the 5th International Conference on IT Convergence and Security. Piscataway： IEEE， 2015： 1-5. 10.1109/icitcs.2015.7292982
20	YEOH W Z， TEH J S， CHEN J G. Automated search for block cipher differentials： a GPU-accelerated branch-and-bound algorithm［C］// Proceedings of the 2020 Australasian Conference on Information Security and Privacy， LNCS 12248. Cham： Springer， 2020： 160-179.
21	李超，孙兵，李瑞林. 分组密码的攻击方法与实例分析［M］. 北京：科学出版社， 2010：72-73， 98-100.
	LI C， SUN B， LI R L. Attack Method and Case Analysis of Block Cipher［M］. Beijing： Science Press， 2010： 72-73， 98-100.

[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]	Jinxing TU, Zhixiong LI, Jianqiang HUANG. Dynamic partition algorithm for diagonal sparse matrix vector multiplication based on GPU [J]. Journal of Computer Applications, 2024, 44(11): 3521-3529.
[3]	Li LIU, Changbo CHEN. Band sparse matrix multiplication and efficient GPU implementation [J]. Journal of Computer Applications, 2023, 43(12): 3856-3867.
[4]	Qian LIU, Yangming ZHANG, Dingsheng WAN. Parallel computing algorithm of grid-based distributed Xin’anjiang hydrological model [J]. Journal of Computer Applications, 2023, 43(11): 3327-3333.
[5]	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.
[6]	JIANG Songyan, LIAO Xiaojuan, CHEN Guangzhu. Optimal task scheduling method based on satisfiability modulo theory for multiple processors with communication delay [J]. Journal of Computer Applications, 2023, 43(1): 185-191.
[7]	Xinyuan QIU, Zecong YE, Xiaolong CUI, Zhiqiang GAO. Survey of communication overhead of federated learning [J]. Journal of Computer Applications, 2022, 42(2): 333-342.
[8]	Qidi XU, Zhenghong LIU, Lin ZHENG. Low density parity check code decoding acceleration technology based on GPU [J]. Journal of Computer Applications, 2022, 42(12): 3841-3846.
[9]	XIE Wenbo, WEI Yongzhuang, LIU Zhenghong. Parallel implementation and analysis of SKINNY encryption algorithm using CUDA [J]. Journal of Computer Applications, 2021, 41(4): 1136-1141.
[10]	YANG Xianfeng, GUI Hongjun, FU Chunchang. F-X domain predictive filtering parallel algorithm based on compute unified device architecture [J]. Journal of Computer Applications, 2021, 41(2): 486-491.
[11]	Fan PING, Xiaochun TANG, Yanyu PAN, Zhanhuai LI. Scheduling strategy of irregular tasks on graphics processing unit cluster [J]. Journal of Computer Applications, 2021, 41(11): 3295-3301.
[12]	Zhiyang ZENG, Yan CHEN, Ke WANG. Design and implementation of parallel genetic algorithm for cutting stock of circular parts [J]. Journal of Computer Applications, 2020, 40(2): 392-397.
[13]	CUI Yixin, CHEN Xiaodong. Spark framework based optimized large-scale spectral clustering parallel algorithm [J]. Journal of Computer Applications, 2020, 40(1): 168-172.
[14]	HE Xi, WU Yantao, DI Zhenwei, CHEN Jia. GPU-based morphological reconstruction system [J]. Journal of Computer Applications, 2019, 39(7): 2008-2013.
[15]	SHA Zongxuan, XUE Fei, ZHU Jie. Scheduling strategy of cloud robots based on parallel reinforcement learning [J]. Journal of Computer Applications, 2019, 39(2): 501-508.

GPU-based method for evaluating algebraic properties of cryptographic S-boxes

基于GPU的密码S盒代数性质评估方法

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 9

References 21

Related Articles 15

Recommended Articles

Metrics