Abstract
In this paper, we investigate the security of the lightweight block ciphers against the meet-in-the-middle (MITM) attack. Since the MITM attack mainly exploits low key-dependency in a key expanding function, the block ciphers having a simple key expanding function are likely to be vulnerable to the MITM attack. On the other hand, such a simple key expanding function leads compact implementation, and thus is utilized in several lightweight block ciphers. However, the security of such lightweight block ciphers against the MITM attack has not been studied well so far. We apply the MITM attack to the ciphers, then give more accurate security analysis for them. Specifically, combining thorough analysis with new techniques, we present the MITM attacks on 29, 8, 16, 14 and 21 rounds of XTEA, LED-64, LED-128, Piccolo-80 and Piccolo-128, respectively. Consequently, it is demonstrated that the MITM attack is the most powerful attack in the single-key setting on those ciphers with respect to the number of attacked rounds. Moreover, we consider the possibility of applying the recent speed-up keysearch based on MITM attack to those ciphers.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
3rd Generation Partnership Project, Technical Specification Group Services and System Aspects, 3G Security, Specification of the 3GPP Confidentiality and Integrity Algorithms; Document 2: KASUMI Specification, V3.1.1
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)
Biham, E., Dunkelman, O., Keller, N.: A Related-Key Rectangle Attack on the Full KASUMI. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 443–461. Springer, Heidelberg (2005)
Biham, E., Dunkelman, O., Keller, N., Shamir, A.: New data-efficient attacks on reduced-round IDEA. IACR Cryptology ePrint Archive, vol. 2011, p. 417 (2011)
Bogdanov, A., Khovratovich, D., Rechberger, C.: Biclique Cryptanalysis of the Full AES. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 344–371. Springer, Heidelberg (2011)
Bogdanov, A., Knudsen, L.R., Leander, G., Paar, C., Poschmann, A., Robshaw, M.J.B., Seurin, Y., Vikkelsoe, C.: PRESENT: An Ultra-Lightweight Block Cipher. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 450–466. Springer, Heidelberg (2007)
Bogdanov, A., Rechberger, C.: A 3-Subset Meet-in-the-Middle Attack: Cryptanalysis of the Lightweight Block Cipher KTANTAN. In: Biryukov, A., Gong, G., Stinson, D.R. (eds.) SAC 2010. LNCS, vol. 6544, pp. 229–240. Springer, Heidelberg (2011)
De Cannière, C., Dunkelman, O., Knežević, M.: KATAN and KTANTAN — A Family of Small and Efficient Hardware-Oriented Block Ciphers. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol. 5747, pp. 272–288. Springer, Heidelberg (2009)
Chen, J., Wang, M., Preneel, B.: Impossible differential cryptanalysis of the lightweight block ciphers TEA, XTEA and HIGHT. IACR Cryptology ePrint Archive, vol. 2011, p. 616 (2011)
Diffie, W., Hellman, M.E.: Exhaustive cryptanalysis of the NBS Data Encryption Standard. IEEE Computer 10, 74–84 (1977)
Dunkelman, O., Keller, N., Shamir, A.: A Practical-Time Related-Key Attack on the KASUMI Cryptosystem Used in GSM and 3G Telephony. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 393–410. Springer, Heidelberg (2010)
FIPS, Advanced Encryption Standard (AES). Federal Information Processing Standards Publication 197
Guo, J., Peyrin, T., Poschmann, A., Robshaw, M.: The LED Block Cipher. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 326–341. Springer, Heidelberg (2011)
Hong, D., Koo, B., Kwon, D.: Biclique attack on the full HIGHT. In: ICISC 2011(2011) (to appear)
Khovratovich, D., Leurent, G., Rechberger, C.: Narrow-Bicliques: Cryptanalysis of Full IDEA. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 392–410. Springer, Heidelberg (2012)
Khovratovich, D., Rechberger, C., Savelieva, A.: Bicliques for preimages: Attacks on Skein-512 and the SHA-2 family. In: FSE 2012 (to appear, 2012)
Knellwolf, S.: Meet-in-the-middle cryptanalysis of KATAN. In: Proceedings of the ECRYPT Workshop on Lightweight Cryptography (2011)
Needham, R.M., Wheeler, D.J.: Tea extensions. Techniacl report, Computer Laboratory, University of Cambridge (October 1997), http://www.cix.co.uk/~klockstone/xtea.pdf
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)
Sasaki, Y.: Meet-in-the-Middle Preimage Attacks on AES Hashing Modes and an Application to Whirlpool. In: Joux, A. (ed.) FSE 2011. LNCS, vol. 6733, pp. 378–396. Springer, Heidelberg (2011)
Sekar, G., Mouha, N., Velichkov, V., Preneel, B.: Meet-in-the-Middle Attacks on Reduced-Round XTEA. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol. 6558, pp. 250–267. Springer, Heidelberg (2011)
Shibutani, K., Isobe, T., Hiwatari, H., Mitsuda, A., Akishita, T., Shirai, T.: Piccolo: An Ultra-Lightweight Blockcipher. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 342–357. Springer, Heidelberg (2011)
van Oorschot, P.C., Wiener, M.: A Known-Plaintext Attack on Two-Key Triple Encryption. In: Damgård, I.B. (ed.) EUROCRYPT 1990. LNCS, vol. 473, pp. 318–325. Springer, Heidelberg (1991)
Wang, Y., Wu, W., Yu, X.: Biclique Cryptanalysis of Reduced-Round Piccolo Block Cipher. In: Ryan, M.D., Smyth, B., Wang, G. (eds.) ISPEC 2012. LNCS, vol. 7232, pp. 337–352. Springer, Heidelberg (2012)
Wei, L., Rechberger, C., Guo, J., Wu, H., Wang, H., Ling, S.: Improved Meet-in-the-Middle Cryptanalysis of KTANTAN (Poster). In: Parampalli, U., Hawkes, P. (eds.) ACISP 2011. LNCS, vol. 6812, pp. 433–438. Springer, Heidelberg (2011)
Bogdanov, A., Wang, M.: Zero Correlation Linear Cryptanalysis with Reduced Data Complexity. In: FSE 2012 (to appear, 2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Isobe, T., Shibutani, K. (2012). Security Analysis of the Lightweight Block Ciphers XTEA, LED and Piccolo. In: Susilo, W., Mu, Y., Seberry, J. (eds) Information Security and Privacy. ACISP 2012. Lecture Notes in Computer Science, vol 7372. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31448-3_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-31448-3_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31447-6
Online ISBN: 978-3-642-31448-3
eBook Packages: Computer ScienceComputer Science (R0)