自动化搜索ARX密码差分特征的方法

doi:10.11959/j.issn.2096-109x.2016.00050

Abstract

Abstract:

How to compute the differential of modular addition efficiently is critical to automatic search for differential characteristic in ARX ciphers.To solve this problem,firstly,the concept of collerated difference distribution table (CDDT) was proposed.By looking up the CDDT,it was very efficient to compute the differential probability of modular addition.Secondly,extending Matsui’s algorithm to ARX cihpers and using CDDT,an automatic search algorithm was proposed,and the algorithm could give the differential characteristic with highest probability in ARX ciphers.Finally,the proposed algorithm was applied to the ARX cipher SPECK,and got the best differential characteristics for SPECK32,SPECK48 and SPECK64.

Key words: block cipher, ARX, differential characteristic, automatic search, SPECK

CLC Number:

TP393

Zheng-bin LIU. Automatic search algorithm for differential characteristics in ARX ciphers[J]. Chinese Journal of Network and Information Security, 2016, 2(5): 56-63.

Figures/Tables 6

A₀\|\|B₀	Γ₀
	${CS}_{0}^{0}$				${CS}_{0}^{1}$				${CS}_{0}^{2}$				${CS}_{0}^{3}$
	0	1	2	3	0	1	2	3	0	1	2	3	0	1	2	3
0	$\frac{5}{8}$	0	0	0	0	0	0	0	0	0	0	0	$\frac{3}{8}$	0	0	0
1	0	$\frac{3}{8}$	0	$\frac{1}{8}$	0	0	0	$\frac{1}{8}$	0	0	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$
2	0	0	$\frac{3}{8}$	0	0	0	$\frac{1}{4}$	0	0	0	$\frac{1}{4}$	0	0	0	$\frac{1}{8}$	0
3	0	$\frac{1}{8}$	0	$\frac{1}{4}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	0
4	0	$\frac{3}{8}$	0	$\frac{1}{8}$	0	0	0	$\frac{1}{8}$	0	0	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$
5	$\frac{3}{8}$	0	$\frac{1}{8}$	0	0	0	$\frac{1}{8}$	0	0	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0
6	0	$\frac{1}{8}$	0	$\frac{1}{4}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	0
7	$\frac{1}{8}$	0	$\frac{1}{4}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	0	0
8	0	0	$\frac{3}{8}$	0	0	0	$\frac{1}{4}$	0	0	0	$\frac{1}{4}$	0	0	0	$\frac{1}{8}$	0
9	0	$\frac{1}{8}$	0	$\frac{1}{4}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	0
10	$\frac{3}{8}$	0	0	0	$\frac{1}{4}$	0	0	0	$\frac{1}{4}$	0	0	0	$\frac{1}{8}$	0	0	0
11	0	$\frac{1}{4}$	0	0	0	$\frac{1}{8}$	0	$\frac{1}{4}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	0	0	0
12	0	$\frac{1}{8}$	0	$\frac{1}{4}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	0
13	$\frac{1}{8}$	0	$\frac{1}{4}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	0	0
14	0	$\frac{1}{4}$	0	0	0	$\frac{1}{8}$	0	$\frac{1}{4}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	0	0	0
15	$\frac{1}{4}$	0	0	0	$\frac{1}{8}$	0	$\frac{1}{4}$	0	$\frac{1}{8}$	0	$\frac{1}{8}$	0	0	0	0	0

A₀\|\|B₀	Γ₀
	CS_1,0				CS_1,1	CS_1,2		CS_1,3
	0	1	2	3	0	1		2	3	0	1	2	3	0	1	2	3
0	1	0	0	0	0	$\frac{1}{2}$	0	$\frac{1}{2}$	0	$\frac{1}{2}$	0	$\frac{1}{2}$		1	0	0	0
1	0	$\frac{1}{2}$	0	$\frac{1}{2}$	$\frac{1}{2}$	0	$\frac{1}{2}$	0	$\frac{1}{2}$	0	$\frac{1}{2}$	0		0	$\frac{1}{2}$	0	$\frac{1}{2}$
2	0	0	1	0	0	$\frac{1}{2}$	0	$\frac{1}{2}$	0	$\frac{1}{2}$	0	$\frac{1}{2}$		0	0	1	0
3	0	$\frac{1}{2}$	0	$\frac{1}{2}$	$\frac{1}{2}$	0	$\frac{1}{2}$	0	$\frac{1}{2}$	0	$\frac{1}{2}$	0		0	$\frac{1}{2}$	0	$\frac{1}{2}$
4	0	$\frac{1}{2}$	0	$\frac{1}{2}$	$\frac{1}{2}$	0	$\frac{1}{2}$	0	$\frac{1}{2}$	0	$\frac{1}{2}$	0		0	$\frac{1}{2}$	0	$\frac{1}{2}$
5	$\frac{1}{2}$	0	$\frac{1}{2}$	0	0	0	0	1	0	0	0	1		$\frac{1}{2}$	0	$\frac{1}{2}$	0
6	0	$\frac{1}{2}$	0	$\frac{1}{2}$	$\frac{1}{2}$	0	$\frac{1}{2}$	0	$\frac{1}{2}$	0	$\frac{1}{2}$	0		0	$\frac{1}{2}$	0	$\frac{1}{2}$
7	$\frac{1}{2}$	0	$\frac{1}{2}$	0	0	1	0	0	0	1	0	0		$\frac{1}{2}$	0	$\frac{1}{2}$	0
8	0	0	1	0	0	$\frac{1}{2}$	0	$\frac{1}{2}$	0	$\frac{1}{2}$	0	$\frac{1}{2}$		0	0	1	0
9	0	$\frac{1}{2}$	0	$\frac{1}{2}$	$\frac{1}{2}$	0	$\frac{1}{2}$	0	$\frac{1}{2}$	0	$\frac{1}{2}$	0		0	$\frac{1}{2}$	0	$\frac{1}{2}$
10	1	0	0	0	0	$\frac{1}{2}$	0	$\frac{1}{2}$	0	$\frac{1}{2}$	0	$\frac{1}{2}$		1	0	0	0
11	0	$\frac{1}{2}$	0	$\frac{1}{2}$	$\frac{1}{2}$	0	$\frac{1}{2}$	0	$\frac{1}{2}$	0	$\frac{1}{2}$	0		0	$\frac{1}{2}$	0	$\frac{1}{2}$
12	0	$\frac{1}{2}$	0	$\frac{1}{2}$	$\frac{1}{2}$	0	$\frac{1}{2}$	0	$\frac{1}{2}$	0	$\frac{1}{2}$	0		0	$\frac{1}{2}$	0	$\frac{1}{2}$
13	$\frac{1}{2}$	0	$\frac{1}{2}$	0	0	1	0	0	0	1	0	0		$\frac{1}{2}$	0	$\frac{1}{2}$	0
14	0	$\frac{1}{2}$	0	$\frac{1}{2}$	$\frac{1}{2}$	0	$\frac{1}{2}$	0	$\frac{1}{2}$	0	$\frac{1}{2}$	0		0	$\frac{1}{2}$	0	$\frac{1}{2}$
15	$\frac{1}{2}$	0	$\frac{1}{2}$	0	0	0	0	1	0	0	0	1		$\frac{1}{2}$	0	$\frac{1}{2}$	0

References 21

[1]	SHIMIZU A , MIYAGUCHI S . Fast data encipherment algorithm FEAL[C]// International Conference on Theory and Application of Cryptographic Techniques. c1987: 267-278.
[2]	WHEELER D J , NEEDHAM R M . Tea,a tiny encryption algorithm[M]// Fast Software Encryption. Berlin:Springer, 2015: 363-366.
[3]	RIVEST R L , . The RC5 encryption algorithm[C]// Fast Software Encryption:Second International Workshop. c1994: 14-16.
[4]	HONG D , SUNG J , HONG S ,et al. HIGHT:a new block cipher suitable for low-resource device[M]// Cryptographic Hardware and Embedded Systems-CHES 2006. Berlin:Springer, 2006: 46-59.
[5]	BEAULIEU R , SHORS D , SMITH J ,et al. The SIMON and SPECK families of lightweight block ciphers[R]. IACR Cryptology ePrint Archive, 2013.
[6]	BERNSTEIN D J . The salsa20 family of stream ciphers[R]. New Stream Cipher Designs-The eSTREAM Finalists , 2008.
[7]	RIVEST R L , . The MD4 message digest algorithm[C]// CRYPTO. c1990: 303-311.
[8]	FERGUSON N , LUCKS S , SCHNEIER B ,et al. The skein hashfunction family[R]. Submission to NIST(Round 3), 2010.
[9]	AUMASSON J P , HENZEN L , MEIER W ,et al. Sha-3 proposal blake[R]. Submission to NIST(Round 3), 2010.
[10]	BIHAM E , SHAMIR A . Differential cryptanalysis of des-like cryptosystems[J]. Journal of Cryptology, 1991,1(4): 3-72.
[11]	AOKI K , KOBAYASHI K , MORIAI S . Best differential characteristic search of FEAL[M]// Fast Software Encryption. Berlin :Springer, 1997: 41-53.
[12]	BANNIER A , BODIN N , FILIOL E . Automatic search for a maximum probability differential characteristic in a substitution-permutation network[C]// International Conference on System Sciences,IEEE Computer Society. c2015: 5165-5174.
[13]	BIRYUKOV A , NIKOLIC I . Automatic search for related-key differential characteristics in byte-oriented block ciphers :application to AES,camellia,khazad and others[C]// International Conference on the Theory and Applications of Cryptographic Techniques. c2010: 322-344.
[14]	BIRYUKOV A , NIKOLIC I . Search for related-key differential characteristics in des-like ciphers[C]// International Conference on FAST Software Encryption. c2011: 18-34.
[15]	BOUILLAGUET C , DERBEZ P , FOUQUE P . Automatic search of attacks on round-reduced AES and applications[R]. IACR Cryptology ePrint Archive, 2012.
[16]	MATSUI M , . On correlation between the order of s-boxes and the strength of DES[M]// Advances in Cryptology—EUROCRYPT'94. Berlin:Springer, 1994: 366-375.
[17]	MOUHA N , WANG Q , GU D ,et al. Differential and linear cryptanalysis using mixed-integer linear programming[C]// 7th International Conference on Information Security and Cryptology. c2011.
[18]	SUN S W , HU L , WANG P ,et al. Automatic security evaluation and (related-key) differential characteristic search:application to simon,present,lblock,DES(L) and other bit-oriented block ciphers[C]// The 20th International Conference on the Theory and Application of Cryptology and Information Security. c2014.
[19]	BIRYUKOV A , VELICHKOV V . Automatic search for differential trails in ARX ciphers[M]// Topics in Cryptology–CT-RSA 2014. Berlin:Springer , 2014: 227-250.
[20]	BIRYUKOV A , ROY A , VELICHKOV V . Differential analysis of block ciphers SIMON and SPECK[M]// Fast Software Encryption. Berlin:Springer Heidelberg, 2014: 546-570.
[21]	FU K , WANG M Q , GUO Y ,et al. MILP-based automatic search algorithms for differential and linear trails for speck[C]// Fast Software Encryption,23rd International Workshop. c2016.

Metrics

Recommended 0

No Suggested Reading articles found!

算法	轮数
算法	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
SPECK32	2^?1	2^?3	2^?5	2^?9	2^?13	2^?18	2^?24	2^?30	2^?34	—	—	—	—	—	—
SPECK48	2^?1	2^?3	2^?6	2^?10	2^?14	2^?19	2^?26	2^?33	2^?40	2^?45	2^?49	—	—	—	—
SPECK96	2^?1	2^?3	2^?6	2^?10	2^?15	2^?21	2^?29	2^?34	2^?38	2^?42	2^?46	2^?50	2^?56	2^?62	2^?70

轮数	SPECK32			SPECK48			SPECK64
轮数	?L	?R	p	?L	?R	p	?L	?R	p
0	56a	9000		1202	20002		924000c0	40104200
1	440a	408	2^?5	10	100000	2^?3	820200	1202	2^?6
2	1080	a0	2^?4	0	800000	2^?1	9000	10	2^?4
3	83	203	2^?4	800000	800004	1	80	0	2^?2
4	c	800	2^?6	808004	808020	2^?2	80000000	80000000	1
5	2000	0	2^?3	8400a0	8001a4	2^?4	80800000	80800004	2^?1
6	40	40	2^?1	608da4	608080	2^?9	80008004	84008020	2^?3
7	8040	8140	2^?1	42003	2400	2^?11	80808060	a0848164	2^?6
8	40	542	2^?2	12020	20	2^?5	40f24	4200401	2^?13
9	8542	904a	2^?4	200100	200000	2^?3	20200008	1202000	2^?8
10	—	—	—	202001	202000	2^?3	202001	202000	2^?4
11	—	—	—	210020	200021	2^?4	210020	200021	2^?2
12	—	—	—	—	—	—	800	800	2^?1
13	—	—	—	—	—	—	808	4808	2^?2
14	—	—	—	—	—	—	8004800	8020840	2^?4
15	—	—	—	—	—	—	80a0808	481a4a08	2^?6
概率		2^?30			2^?45			2^?62

Automatic search algorithm for differential characteristics in ARX ciphers

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 21

Related Articles 8

Metrics

Recommended 0

[1]	Ruiqi XIA, Manman LI, Shaozhen CHEN. Identification on the structures of block ciphers using machine learning [J]. Chinese Journal of Network and Information Security, 2023, 9(3): 79-89.
[2]	Zheng XU. Further accelerating the search of differential characteristics based on the SAT method [J]. Chinese Journal of Network and Information Security, 2022, 8(5): 129-139.
[3]	Zhengbin LIU. Differential-linear cryptanalysis of PRINCE cipher [J]. Chinese Journal of Network and Information Security, 2021, 7(4): 131-140.
[4]	Xinxin GE, Zhihu LI, Meiqin WANG, Kai HU. Effect of the difference enumeration attack on LowMC instances [J]. Chinese Journal of Network and Information Security, 2021, 7(3): 149-155.
[5]	Weijian CHEN, Haoxiang LUO. Differential fault attack on LiCi cipher [J]. Chinese Journal of Network and Information Security, 2021, 7(2): 104-109.
[6]	Ya HAN. Automatic method for searching impossible differentials and zero-correlation linear hulls of ARX block ciphers [J]. Chinese Journal of Network and Information Security, 2017, 3(7): 58-63.
[7]	Peng-fei LI. Construction of diffusion layers based on cipher structures [J]. Chinese Journal of Network and Information Security, 2017, 3(6): 65-76.
[8]	Peng-fei LI,Yong-qiang LI. Construction of MDS matrices [J]. Chinese Journal of Network and Information Security, 2016, 2(6): 44-53.