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

doi:10.19665/j.issn1001-2400.20230404

摘要/Abstract

摘要：

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。实验结果说明了这种方法的有效性。

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

Abstract:

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.

Key words: differential-linear cryptanalysis, ARX, SAT/SMT, SPECK, SIMON

中图分类号:

TN918.4

张峰, 刘正斌, 张晶, 张文政. 一种计算ARX密码差分—线性偏差的新方法[J]. 西安电子科技大学学报, 2024, 51(2): 211-223.

ZHANG Feng, LIU Zhengbin, ZHANG Jing, ZHANG Wenzheng. New method for calculating the differential-linear bias of the ARX cipher[J]. Journal of Xidian University, 2024, 51(2): 211-223.

图/表 16

表1

表2

符号说明"

符号	说明	符号	说明
Δ_I	输入差分	w	差分—线性特征相关度权重
Δ_O	输出差分	w_i	每轮的差分概率/线性相关度权重
λ_I	输入掩码	A_i	w_i的取值空间
λ_O	输出掩码	$ε Δ I$ ,λ_O	差分—线性区分器(Δ_I→λ_O)的偏差
(α₀,α₁,…,α_m)	m轮差分特征	$c Δ I$ ,λ_O	差分—线性区分器(Δ_I→λ_O)的相关度
(β₀,β₁,…,β_n)	n轮线性特征	w_min/w_max	w的最小值/最大值
(α₀,α₁,…,α_m,β₀,β₁,…,β_n)	m+n轮差分—线性特征	☉	点乘

表2

图1

图2

表4

表5

表6

表7

表8

图3

表3

表9

表10

表11

表12

表13

参考文献 18

[1]	董新锋, 张文政, 许春香. Feistel 结构的8比特轻量化S盒[J]. 西安电子科技大学学报, 2021, 48(1):69-75.
	DONG Xinfeng, ZHANG Wenzheng, XU Chunxiang. 8 Bits Lightweight S-box with the Feistel Structure[J]. Journal of Xidian University, 2021, 48(1):69-75.
[2]	BEAULIEU R, SHORS D, SMITH J, et al. The SIMON and SPECK Families of Lightweight Block Ciphers(2013)[J/OL].[2023-06-20]. https://eprint.iacr.org/2013/404.
[3]	LANGFORD S K, HELLMAN M E. Differential-Linear Cryptanalysis[C]//Advances in Cryptology—CRYPTO 1994.Berlin:Springer, 1994:17-25.
[4]	BIHAM E, DUNKELMAN O, KELLER N. Enhancing Differential-Linear Cryptanalysis[C]//Advances in Cryptology—ASIACRYPT 2002. Berlin:Springer, 2002:254-266.
[5]	BLONDEAU C, LEANDER G, NYBERG K. Differential-Linear Cryptanalysis Revisited[J]. Journal of Cryptology, 2017, 30(3):859-888.
[6]	BAR-ON A, DUNKELMAN O, KELLER N, et al. DLCT:A New Tool for Differential-Linear Cryptanalysis[C]//Advances in Cryptology-EUROCRYPT 2019. Berlin:Springer, 2019:313-342.
[7]	LEURENT G. Improved Differential-Linear Cryptanalysis of 7-Round Chaskey with Partitioning[C]//Advances in Cryptology-EUROCRYPT 2016. Berlin:Springer, 2016:344-371.
[8]	BEIERLE C, BROLL M, CANALE F, et al. Improved Differential-Linear Attacks with Applications to ARX Ciphers[J]. Journal of Cryptology, 2022, 35(4):1-61.
[9]	COUTINHO M, SOUZA NETO T C. Improved Linear Approximations to ARX Ciphers and Attacks Against ChaCha[C]//Advances in Cryptology-EUROCRYPT 2021. Berlin:Springer, 2021:711-740.
[10]	DEY S, GARAI H K, SARKAR S, et al. Revamped Differential-Linear Cryptanalysis on Reduced Round ChaCha[C]//Advances in Cryptology-EUROCRYPT 2022. Berlin:Springer, 2022:86-114.
[11]	王非凡. 轻量级ARX型分组密码的差分-线性攻击框架[D]. 上海: 华东师范大学, 2022.
[12]	LIU Y, SUN S, LI C. Rotational Cryptanalysis from a Differential-Linear Perspective[C]//Advances in Cryptology-EUROCRYPT 2021. Berlin:Springer, 2021:741-770.
[13]	MORAWIECKI P, PIEPRZYK J, SREBRNY M. Rotational Cryptanalysis of Round-Reduced Keccak[C]//Fast Software Encryption: 20th International Workshop. Berlin:Springer, 2013:241-262.
[14]	NIU Z, SUN S, LIU Y, et al. Rotational Differential-Linear Distinguishers of ARX Ciphers with Arbitrary Output Linear Masks[C]//Advances in Cryptology-CRYPTO 2022. Berlin:Springer, 2022:3-32.
[15]	MOUHA N, PRENEEL B. Towards Finding Optimal Differential Characteristics for ARX:Application to Salsa20 (2013)[J/OL].[2023-11-13]. https://eprint.iacr.org/2013/328.
[16]	KÖLBL S, LEANDER G, TIESSEN T. Observations on the SIMON Block Cipher Family[C]//Advances in Cryptology-CRYPTO 2015. Berlin:Springer, 2015:161-185.
[17]	LIU Y, WANG Q, RIJMEN V. Automatic Search of Linear Trails in ARX with Applications to SPECK and Chaskey[C]//Applied Cryptography and Network Security:14th International Conference.Berlin:Springer,2016:485-499.
[18]	SUN L, WANG W, WANG M. Accelerating the Search of Differential and Linear Characteristics with the SAT Method[J]. IACR Transactions on Symmetric Cryptology, 2021(1):269-315.

算法	区分器轮数	偏差		参考文献
算法	区分器轮数	理论值	实验值	参考文献
SPECK32/64	7	2^-4.00	2^-3.88	文中节4.1
	8	2^-9.23	2^-7.87	文献[14]
	8	2^-8.00	2^-7.87	文中节4.1
	9	2^-12.58		文献[11]
	9	2^-11.23	2^-9.93	文献[14]
	9	2^-10.00	2^-9.93	文中节4.1
	10	2^-15.58		文献[11]
	10	2^-16.23	2^-14.90	文献[14]
	10	2^-15.00	2^-14.90	文中节4.1
SIMON32/64	9	2^-8.41	2^-7.12	文中节4.2
	12	2^-14.41	2^-12.61	文中节4.2

权重w	11	12	13	14	15	16	17	18	19	20	21	22	23
Δ☉λ=0	0	0	0	96	256	416	576	704	608	448	320	256	0
Δ☉λ=1	0	0	0	0	0	0	32	256	320	320	320	256	0

权重w	11	12	13	14	15	16	17	18	19	20	21	22	23	24
Δ☉λ=0	0	0	0	32	128	352	576	752	816	752	592	448	288	0
Δ☉λ=1	0	0	0	0	0	0	48	160	288	384	448	448	288	0

权重w	11	12	13	14	15	16	17	18	19	20	21	22	23	24
Δ☉λ=0	4	24	60	224	516	928	1 308	1 576	1 512	1 264	944	704	288	0
Δ☉λ=1	0	0	0	0	8	40	152	488	680	768	800	704	288	0

权重w	11	12	13	14	15	16	17	18	19
Δ☉λ=0	4	24	60	224	536	1 192	2 608	4 704	7 424
Δ☉λ=1	0	0	0	0	8	40	152	572	1 424
权重w	20	21	22	23	24	25	26	27	28
Δ☉λ=0	11 604	16 612	20 756	21 944	19 296	13 168	5 520	1 568	0
Δ☉λ=1	3 116	6 188	10 584	15 136	15 752	12 384	5 520	1 568	0