Meet-in-the-middle attacks on reduced-round XTEA. (English) Zbl 1284.94109

Kiayias, Aggelos (ed.), Topics in cryptology – CT-RSA 2011. The cryptographers’ track at the RSA conference 2011, San Francisco, CA, USA, February 14–18, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-19073-5/pbk). Lecture Notes in Computer Science 6558, 250-267 (2011).
Summary: The block cipher XTEA, designed by Needham and Wheeler, was published as a technical report in 1997. The cipher was a result of fixing some weaknesses in the cipher TEA (also designed by Wheeler and Needham), which was used in Microsoft’s Xbox gaming console. XTEA is a 64-round Feistel cipher with a block size of 64 bits and a key size of 128 bits. In this paper, we present meet-in-the-middle attacks on twelve variants of the XTEA block cipher, where each variant consists of 23 rounds. Two of these require only 18 known plaintexts and a computational effort equivalent to testing about \(2^{117}\) keys, with a success probability of \(1 - 2^{ - 1025}\). Under the standard (single-key) setting, there is no attack reported on 23 or more rounds of XTEA, that requires less time and fewer data than the above. This paper also discusses a variant of the classical meet-in-the-middle approach. All attacks in this paper are applicable to XETA as well, a block cipher that has not undergone public analysis yet. TEA, XTEA and XETA are implemented in the Linux kernel.
For the entire collection see [Zbl 1206.94004].


94A60 Cryptography


Full Text: DOI Link


[1] Aoki, K., Guo, J., Matusiewicz, K., Sasaki, Y., Wang, L.: Preimages for Step-Reduced SHA-2. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 578–597. Springer, Heidelberg (2009) · Zbl 1267.94030
[2] Aoki, K., Sasaki, Y.: Preimage Attacks on One-Block MD4, 63-Step MD5 and More. In: Avanzi, R.M., Keliher, L., Sica, F. (eds.) SAC 2008. LNCS, vol. 5381, pp. 103–119. Springer, Heidelberg (2009) · Zbl 1256.94040
[3] Bouillaguet, C., Dunkelman, O., Leurent, G., Fouque, P.-A.: Another Look at Complementation Properties. In: Hong, S., Iwata, T. (eds.) FSE 2010. LNCS, vol. 6147, pp. 347–364. Springer, Heidelberg (2010) · Zbl 1279.94055
[4] Chaum, D., Evertse, J.-H.: Cryptanalysis of DES with a Reduced Number of Rounds: Sequences of Linear Factors in Block Ciphers. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 192–211. Springer, Heidelberg (1986) · Zbl 0592.94009
[5] Diffie, W., Hellman, M.E.: Exhaustive Cryptanalysis of the NBS Data Encryption Standard. Computer 10(6), 74–84 (1977) · Zbl 05332334
[6] Dunkelman, O., Sekar, G., Preneel, B.: Improved Meet-in-the-Middle Attacks on Reduced-Round DES. In: Srinathan, K., Pandu Rangan, C., Yung, M. (eds.) INDOCRYPT 2007. LNCS, vol. 4859, pp. 86–100. Springer, Heidelberg (2007) · Zbl 1153.94371
[7] Grothe, A.: Kernel v2.6.14 tea.c. Linux Headquarters (2004), http://www.linuxhq.com/kernel/v2.6/14/crypto/tea.c
[8] Hong, S., Hong, D., Ko, Y., Chang, D., Lee, W., Lee, S.: Differential Cryptanalysis of TEA and XTEA. In: Lim, J.-I., Lee, D.-H. (eds.) ICISC 2003. LNCS, vol. 2971, pp. 402–417. Springer, Heidelberg (2004) · Zbl 1092.94507
[9] Hong, D., Koo, B., Sasaki, Y.: Improved Preimage Attack for 67-Step HAS-160. In: Lee, D., Hong, S. (eds.) ICISC 2009. LNCS, vol. 5984, pp. 332–348. Springer, Heidelberg (2010) · Zbl 05757491
[10] Indesteege, S., Keller, N., Dunkelman, O., Biham, E., Preneel, B.: A Practical Attack on KeeLoq. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 1–18. Springer, Heidelberg (2008) · Zbl 1149.94322
[11] Kaps, J.-P.: Chai-Tea, Cryptographic Hardware Implementations of xTEA. In: Chowdhury, D.R., Rijmen, V., Das, A. (eds.) INDOCRYPT 2008. LNCS, vol. 5365, pp. 363–375. Springer, Heidelberg (2008) · Zbl 1203.94105
[12] Kelsey, J., Schneier, B., Wagner, D.: Key-Schedule Cryptoanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 237–251. Springer, Heidelberg (1996) · Zbl 1329.94066
[13] Kelsey, J., Schneier, B., Wagner, D.: Related-key cryptanalysis of 3-WAY, Biham-DES, CAST, DES-X, NewDES, RC2, and TEA. In: Han, Y., Okamoto, T., Qing, S. (eds.) ICICS 1997. LNCS, vol. 1334, pp. 233–246. Springer, Heidelberg (1997)
[14] Ko, Y., Hong, S., Lee, W., Lee, S., Kang, J.-S.: Related-Key Differential Attacks on 27 Rounds of XTEA and Full-Round GOST. In: Roy, B.K., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 299–316. Springer, Heidelberg (2004) · Zbl 1079.68548
[15] Lee, E., Hong, D., Chang, D., Hong, S., Lim, J.: A Weak Key Class of XTEA for a Related-Key Rectangle Attack. In: Nguyen, P.Q. (ed.) VIETCRYPT 2006. LNCS, vol. 4341, pp. 286–297. Springer, Heidelberg (2006) · Zbl 1295.94102
[16] Lu, J.: Related-key rectangle attack on 36 rounds of the XTEA block cipher. International Journal of Information Security 8(1), 1–11 (2009), http://jiqiang.googlepages.com/IJIS8.pdf · Zbl 05671966
[17] Moon, D., Hwang, K., Lee, W., Lee, S., Lim, J.: Impossible Differential Cryptanalysis of Reduced Round XTEA and TEA. In: Daemen, J., Rijmen, V. (eds.) FSE 2002. LNCS, vol. 2365, pp. 49–60. Springer, Heidelberg (2002) · Zbl 1045.94529
[18] Needham, R.M., Wheeler, D.J.: Tea extensions, technical report, Computer Laboratory, University of Cambridge (October 1997), http://www.cix.co.uk/ klockstone/xtea.pdf
[19] Needham, R.M., Wheeler, D.J.: Correction to xtea. Technical report, Computer Laboratory, University of Cambridge (October 1998), http://www.movable-type.co.uk/scripts/xxtea.pdf
[20] Saarinen, M.-J.: Cryptanalysis of Block TEA, unpublished manuscript (October 1998), http://groups.google.com/group/sci.crypt.research/msg/f52a533d1e2fa15e
[21] Sasaki, Y., Aoki, K.: Finding Preimages in Full MD5 Faster Than Exhaustive Search. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 134–152. Springer, Heidelberg (2009) · Zbl 1239.94064
[22] Shannon, C.E.: Communication Theory of Secrecy Systems. Bell System Technical Journal 28(4), 656–715 (1949) · Zbl 1200.94005
[23] Steil, M.: 17 Mistakes Microsoft Made in the Xbox Security System. In: Chaos Communication Congress 2005 (2005), http://events.ccc.de/congress/2005/fahrplan/events/559.en.html
[24] Wheeler, D.J., Needham, R.M.: TEA, a Tiny Encryption Algorithm. In: Preneel, B. (ed.) FSE 1994. LNCS, vol. 1008, pp. 363–366. Springer, Heidelberg (1995) · Zbl 0939.94550
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.