Differential Analysis Of The Block Cipher XTEA And The Study Of The Additive Differential Probability

Needham et al.proposed the block cipher:Tiny Encryption Algorithm block cipher in FSE 1994, which is one of lightweight block cipher. It has 64-bit block size,128-bit key, and 64-rounds, marked as TEA. The block cipher consists of exclusive-or operation, shift operation and addition operation, and it is Feistel structure. Since TEA was proposed, it has been focused by the scholars of cryptography. Needham mentioned that the TEA has two weak-nesses:one is that the mixing portion of TEA is attacked by the related-key cryptanalysis; another is that the effective length of the masterkey is 126 bits not 128. In order to overcome the above weaknesses Needham et al. proposed the block cipher Tea extensions, marked as XTEA.The block cipher XTEA also belongs to the ARX cipher. It has 64-bit block size,128-bit key and 64-rounds. The round function of XTEA is Feis-tel structure, and has shift operation, exclusive-or and addition by F232. the XTEA block cipher also attracted wide attention. Moon et al. present the impossible differential attack on XTEA, Hong et al. proposed the differential cryptanalysis and truncated differential attack on XTEA.In this paper, we review the differential probability of addition operation, the 3-round iterative differential characteristic of XTEA and the method of differential attack on SPECK block cipher. Taking advantage of the 14 round differential trail, we combine the differential attack on SPECK by Dinur-"2 round attack" with the round function of XTEA, attacking on XTEA. The data, time and memory complexity is 257.795 plaintexts,2123.795 and 222 bytes. It is the best result of differential attack currently and improves from 15 rounds to 21 rounds, recovering the key.Finally On the basis of Lipmaa and Mouha’s research results, this paper discusses the additive differential probability of exclusive-or. They only stud-ied the exclusive-or with two inputs and one output and mentioned that the exclusive-or with three inputs and one output is similar to that with two in-puts and one output, but didn’t give the corresponding matrices. On the basis of the paper, we obtain the 16 matrices to compute the additive differential probability of exclusive-or and also verify the paper probability of differential trail for the TEA cipher. We study the density of the possible additive differ-entials, and the probability is 6/15+7/240+2/15·1/16N,which is very helpful for the differential attack on ARX cipher.