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

doi:10.19665/j.issn1001-2400.20230404

Abstract

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

CLC Number:

TN918.4

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.

Figures/Tables 16

符号	说明	符号	说明
Δ_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轮差分—线性特征	☉	点乘

References 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

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

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 16

References 18

Related Articles 8

Metrics

Comments

Recommended 0

轮数r	每轮差分/掩码	差分概率/线性相关度
0	2800 0010
1	0040 0000	2^-2
2	8000 8000	2⁰
3	8100 8102	2^-1
4	8000 840A	2^-2
5	850A 9520	2^-4
5	0100 8003
6	0000 0002	2^-1
7	0008 0008	2⁰

轮数	输入差分	输出掩码	偏差
轮数	输入差分	输出掩码	理论值	实验值
7	(0x2800,0x0010)	(0x0008,0x0008)	2^-4.00	2^-3.88
8	(0x0211,0x0A04)	(0x0008,0x0008)	2^-8.00	2^-7.87
9	(0x0211,0x0A04)	(0x5820,0x4020)	2^-10.00	2^-9.93
10	(0x0A20,0x4205)	(0x5820,0x4020)	2^-15.00	2^-14.90

轮数r	每轮差分/掩码	差分概率/线性相关度
0	0044 0100
1	0010 0044	2^-4
2	0004 0010	2^-2
3	0000 0004	2^-2
4	0004 0000	2⁰
5	0010 0004	2^-2
6	0044 0010	2^-2
6	2002 8000
7	8000 0002	2^-1
8	0002 0000	2^-1
9	0000 0002	2⁰

权重w	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30
Δ☉λ=0	16	0	288	128	1 728	1 280	4 352	3 456	7 424	5 632	9 984	8 192	5 632	5 120	0
Δ☉λ=1	0	0	0	0	0	0	128	128	1 280	1 536	3 328	4 096	2 560	3 072	0

[1]	DUAN Tingyu, SHUI Penglang, FENG Tian. Non-coherent integration constant false alarm rate detectors against the log-normal textured sea clutter [J]. Journal of Xidian University, 2022, 49(5): 1-8.
[2]	NI Jie;WANG Junping;YANG Guoyu;WU Yao;MA Shuliang. New soft morphological parameterized symmetric logarithmic image processing filtering algorithm [J]. Journal of Xidian University, 2017, 44(5): 25-31+45.
[3]	CHEN Jianhong;ZHAO Yongjun;SHI Yinshui;LIU Wei. Fast Bayesian non-local means of polarimetric SAR image despeckling [J]. J4, 2015, 42(3): 148-153+204.
[4]	XU Yuelei;TIAN Song;LI Junwei;FENG Hongxiao. SAR image despeckling based on edge detection and the plural pervasion equation in the Shearlet domain [J]. J4, 2012, 39(6): 142-146+153.
[5]	ZHU Lei;SHUI Penglang;WU Aijing. New algorithm for reducing speckle noise in the SAR image [J]. J4, 2012, 39(2): 80-86.
[6]	GUO Rui;LIU Yanyang;ZANG Bo;XING Mengdao. Polarimetric SAR filtering method to preserve scattering characteristics [J]. J4, 2011, 38(1): 90-95.
[7]	SUN Qiang;JIAO Li-cheng;HOU Biao. SAR image despeckling using statistical priors in nonsubsampled contourlet transform domain [J]. J4, 2008, 35(1): 14-21.
[8]	SHENG Guo-fang1;LENG Zhao-xia2;JIAO Li-cheng1. Application of data fusion in SAR image denoising [J]. J4, 2004, 31(1): 91-95.