×

Lightweight block ciphers revisited: cryptanalysis of reduced round PRESENT and HIGHT. (English) Zbl 1307.94084

Boyd, Colin (ed.) et al., Information security and privacy. 14th Australasian conference, ACISP 2009, Brisbane, Australia, July 1–3, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-02619-5/pbk). Lecture Notes in Computer Science 5594, 90-107 (2009).
Summary: Design and analysis of lightweight block ciphers have become more popular due to the fact that the future use of block ciphers in ubiquitous devices is generally assumed to be extensive. In this respect, several lightweight block ciphers are designed, of which PRESENT and HIGHT are two recently proposed ones by A. Bogdanov et al. [CHES 2007, Lect. Notes Comput. Sci. 4727, 450–466 (2007; Zbl 1142.94334)] and D. Hong et al. [CHES 2006, Lect. Notes Comput. Sci. 4249, 46–59 (2006; Zbl 1307.94058)], respectively. In this paper, we propose new attacks on PRESENT and HIGHT. Firstly, we present the first related-key cryptanalysis of 128-bit keyed Present by introducing 17-round related-key rectangle attack with time complexity approximately \(2^{104}\) memory accesses. Moreover, we further analyze the resistance of HIGHT against impossible differential attacks by mounting new 26-round impossible differential and 31-round related-key impossible differential attacks where the former requires time complexity of \(2^{119.53}\) reduced round HIGHT evaluations and the latter is slightly better than exhaustive search.
For the entire collection see [Zbl 1165.94302].

MSC:

94A60 Cryptography

Software:

XTEA; TEA; HIGHT; PRESENT; mCrypton
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Daemen, J., Rijmen, V.: The Design of Rijndael. Springer, New York (2002) · Zbl 1065.94005 · doi:10.1007/978-3-662-04722-4
[2] Hong, D., Sung, J., Hong, S., Lim, J., Lee, S., Koo, B., Lee, C., Chang, D., Lee, J., Jeong, K., Kim, H., Kim, J., Chee, S.: HIGHT: A New Block Cipher Suitable for Low-Resource Device. In: Goubin, L., Matsui, M. (eds.) CHES 2006. LNCS, vol. 4249, pp. 46–59. Springer, Heidelberg (2006) · Zbl 1307.94058 · doi:10.1007/11894063_4
[3] South Korea Telecommunications Technology Associations (TTA). 64-bit Block Cipher HIGHT. Standardization Number TTAS.KO-12.0040, December 27 (2006)
[4] 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) · Zbl 1142.94334 · doi:10.1007/978-3-540-74735-2_31
[5] Lim, C.H., Korkishko, T.: mCrypton - A Lightweight Block Cipher for Security of Low-Cost RFID Tags and Sensors. In: Song, J.-S., Kwon, T., Yung, M. (eds.) WISA 2005. LNCS, vol. 3786, pp. 243–258. Springer, Heidelberg (2006) · doi:10.1007/11604938_19
[6] Standaert, F.-X., Piret, G., Gershenfeld, N., Quisquater, J.-J.: SEA: A Scalable Encryption Algorithm for Small Embedded Applications. In: Domingo-Ferrer, J., Posegga, J., Schreckling, D. (eds.) CARDIS 2006. LNCS, vol. 3928, pp. 222–236. Springer, Heidelberg (2006) · Zbl 1333.94048 · doi:10.1007/11733447_16
[7] Robshaw, M.J.B.: Searching for Compact Algorithms: CGEN. In: Nguyên, P.Q. (ed.) VIETCRYPT 2006. LNCS, vol. 4341, pp. 37–49. Springer, Heidelberg (2006) · Zbl 1295.94137 · doi:10.1007/11958239_3
[8] Leander, G., Paar, C., Poschmann, A., Schramm, K.: New Lightweight DES Variants. In: Biryukov, A. (ed.) FSE 2007. LNCS, vol. 4593, pp. 196–210. Springer, Heidelberg (2007) · Zbl 1184.94241 · doi:10.1007/978-3-540-74619-5_13
[9] 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 · doi:10.1007/3-540-60590-8_29
[10] Wheeler, D.J., Needham, R.M.: TEA Extensions (October 1997)
[11] The eSTREAM Portfolio. The eSTREAM Project (September 2008), http://www.ecrypt.eu.org/stream/
[12] Wang, M.: Differential Cryptanalysis of Reduced-Round PRESENT. In: Vaudenay, S. (ed.) AFRICACRYPT 2008. LNCS, vol. 5023, pp. 40–49. Springer, Heidelberg (2008) · Zbl 1142.94362 · doi:10.1007/978-3-540-68164-9_4
[13] Albrecht, M., Cid, C.: Algebraic Techniques in Differential Cryptanalysis. To appear in proceedings of FSE (2009) · Zbl 1291.94043
[14] Z’aba, M.R., Raddum, H., Henricksen, M., Dawson, E.: Bit-Pattern Based Integral Attack. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 363–381. Springer, Heidelberg (2008) · Zbl 1154.94443 · doi:10.1007/978-3-540-71039-4_23
[15] Collard, B., Standaert, F.-X.: A Statistical Saturation Attack against the Block Cipher PRESENT. To appear in proceedings of CT-RSA (2009) · Zbl 1237.94056
[16] Biryukov, A., Wagner, D.: Slide Attacks. In: Knudsen [26], pp. 245–259 · Zbl 0942.94020
[17] Biham, E.: New Types of Cryptanalytic Attacks Using Related Keys. Journal of Cryptology 7(4), 229–246 (1994) · Zbl 0812.94012 · doi:10.1007/BF00203965
[18] Lu, J.: Cryptanalysis of Block Ciphers. PhD thesis, Royal Holloway, University of London, England (July 2008)
[19] Lu, J.: Cryptanalysis of Reduced Versions of the HIGHT Block Cipher from CHES 2006. In: Nam, K.-H., Rhee, G. (eds.) ICISC 2007. LNCS, vol. 4817, pp. 11–26. Springer, Heidelberg (2007) · Zbl 1337.94054 · doi:10.1007/978-3-540-76788-6_2
[20] Biham, E., Dunkelman, O., Keller, N.: Related-Key Boomerang and Rectangle Attacks. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 507–525. Springer, Heidelberg (2005) · Zbl 1137.94338 · doi:10.1007/11426639_30
[21] Biham, E., Dunkelman, O., Keller, N.: New Combined Attacks on Block Ciphers. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 126–144. Springer, Heidelberg (2005) · Zbl 1140.94324 · doi:10.1007/11502760_9
[22] Biham, E., Dunkelman, O., Keller, N.: The Rectangle Attack - Rectangling the Serpent. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 340–357. Springer, Heidelberg (2001) · Zbl 0981.94017 · doi:10.1007/3-540-44987-6_21
[23] Biham, E., Biryukov, A., Shamir, A.: Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials. Journal of Cryptology 18(4), 291–311 (2005) · Zbl 1096.94023 · doi:10.1007/s00145-005-0129-3
[24] Biham, E., Biryukov, A., Shamir, A.: Miss in the Middle Attacks on IDEA and Khufu. In: Knudsen [26], pp. 124–138 · Zbl 0942.94010 · doi:10.1007/3-540-48519-8_10
[25] Dunkelman, O.: Techniques for Cryptanalysis of Block Ciphers. PhD thesis, Technion, Israel (February 2006) · Zbl 06015144
[26] Knudsen, L.R. (ed.): FSE 1999. LNCS, vol. 1636. Springer, Heidelberg (1999) · Zbl 0917.00016
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.