一种计算ARX密码差分—线性偏差的新方法  

New method for calculating the differential-linear bias of the ARX cipher

作　　者：张峰 刘正斌[1] 张晶 张文政 ZHANG Feng;LIU Zhengbin;ZHANG Jing;ZHANG Wenzheng(Science and Technology on Communication Security Laboratory,Chengdu 610041,China;China Academy of Electronics and Information Technology,Beijing 100041,China)

机构地区：[1]保密通信重点实验室,四川成都610041 [2]中国电子科技集团公司电子科学研究院,北京100041

出　　处：《西安电子科技大学学报》2024年第2期211-223,共13页Journal of Xidian University

基　　金：国家重点研发计划青年科学家项目(2021YFB3100200);四川省保密通信重点实验室基金(61421030111012101)。

摘　　要：ARX密码由模加、循环移位和异或这3种基本运算组成。目前ARX密码差分—线性区分器偏差的计算大多采用统计分析的方法。在2022年美密会上,NIU等给出了一种计算ARX密码差分—线性区分器相关度的非统计分析的方法,并给出了SPECK32/64的10轮差分—线性区分器。基于BLONDEAU等和BAR-ON等的方法,给出了差分—线性特征的定义,并首次提出了用差分—线性特征计算差分—线性区分器偏差的方法。同时,提出了一种基于布尔可满足性问题(SAT)自动化技术搜索差分—线性特征的方法,给出了计算ARX密码差分—线性区分器偏差的非统计分析的新方法。作为应用,对NIU等给出的SPECK32/64的10轮差分—线性区分器偏差进行计算,得到的理论值为2-15.00,非常接近统计分析的实验值2-14.90,且优于NIU等给出的理论值2-16.23。同时,首次给出了SIMON32/64的9轮差分—线性区分器偏差的理论值2-8.41,接近统计分析得到的实验值2-7.12。实验结果说明了这种方法的有效性。The ARX cipher consists of three basic operations,additions,rotations and XORs.Statistical analysis is currently used to calculate the bias of the ARX cipher differential-linear distinguishers.At CRYPTO 2022,NIU et al.gave a method for evaluating the correlation of the ARX cipher differential-linear distinguishers without using statistical analysis.They gave a 10-round differential-linear distinguisher for SPECK32/64.This paper gives the definition of differential-linear characteristics.It presents the first method for calculating the bias of differential-linear distinguishers using differential-linear characteristics based on the methods by BLONDEAU et al.and BAR-ON et al.Also,a method for searching for differential-linear characteristics based on Boolean Satisfiability Problem(SAT)automation techniques is proposed,which is a new method for calculating the bias of the ARX cipher differential-linear distinguisher without statistical analysis.As an application,the bias of the 10-round differential-linear distinguisher for SPECK32/64 given by NIU et al.is calculated with the theoretical value 2-15.00 obtained,which is very close to the experimental value 2-14.90 from the statistical analysis and better than the theoretical value 2-16.23 given by NIU et al.Also,the first theoretical value 2-8.41 for the bias of the 9-round differential-linear distinguisher for SIMON32/64 is given,which is close to the experimental value 2-7.12 obtained by statistical analysis.Experimental results fully demonstrate the effectiveness of this method.

关 键 词：差分—线性区分器 ARX密码 SAT/SMT SPECK SIMON 

分 类 号：TN918.4[电子电信—通信与信息系统]