Improved Multi-Dimensional Meet-in-the-Middle Cryptanalysis of Katan

Rasoolzadeh, Shahram; Raddum, Håvard

doi:10.1515/tmmp-2016-0037

Abstract

We study multidimensional meet-in-the-middle attacks on the KATAN block cipher family. Several improvements to the basic attacks are explained. The most noteworthy of these is the technique of guessing only non-linearly involved key bits, which reduces the search space by a significant factor. The optimization decreases the complexity of multidimensional meet-in-the-middle attacks, allowing more rounds of KATAN to be efficiently attacked than previously reported.

References

[1] DE CANNIÈRE, C.—DUNKELMAN, O.—KNEŽEVIC, M.: KATAN and KTANTAN–a family of small and efficient hardware-oriented block ciphers, in: Cryptogr. Hardware and Embed. Syst.—CHES ’09, The 11th Int. Workshop (C. Christophe et al., eds.) Lausanne, CH, 2009, Lecture Notes in Comput. Sci., Vol. 5747, Springer-Verlag, Berlin, 2009, pp. 272–288.
Search in Google Scholar Back to article
[2] BARD, G. V.—COURTOIS, N. T.—NAKAHARA, J.—SEPEHRDAD, P.—ZHANG, B.: Algebraic, Aida/Cube and side channel analysis of KATAN family of block ciphers, in: Progress in Cryptology—INDOCRYPT ’10, The 11th Int. Conf. on Cryptology, Hyderabad, India, 2010 (G. Guang et al., eds.), Lecture Notes in Comput. Sci., Vol. 6498, Springer-Verlag, Berlin, 2010, pp. 176–196.
Search in Google Scholar Back to article
[3] KNELLWOLF, S.—MEIER, W.—NAYA-PLASENCIA, M.: Conditional differential cryptanalysis of NLFSR-based cryptosystems, in: Adv. in Crypt.—ASIACRYPT ’10, 16th Int. Conf. on the Theory and Appl. of Crypt. and Inform. Sec., Singapore (A. Masayuki, ed.), Lecture Notes in Comput. Sci., Vol. 6477, Springer-Verlag, Berlin, 2010, pp. 130–145.
Search in Google Scholar Back to article
[4] ISOBE, T.—SHIBUTANI, K.: All subkeys recovery attack on block ciphers: extending meet-in-the-middle approach, in: Selected Areas in Cryptography—SAC ’12, 19th Int. Conf., Windsor, Canada, 2012 (L. R. Knudsen et al., eds.), Lecture Notes in Comput. Sci., Vol. 7707, Springer-Verlag, Berlin, 2012, pp. 202–221.
Search in Google Scholar Back to article
[5] ALBRECHT, M. R.—LEANDER, G.: An all-in-one approach to differential cryptanalysis for small block ciphers, in: Selected Areas in Cryptography—SAC ’12, 19th Int. Conf., Windsor, Canada, 2012 (L. R. Knudsen et al., eds.), Lecture Notes in Comput. Sci., Vol. 7707, Springer-Verlag, Berlin, 2012, pp. 1–15.
Search in Google Scholar Back to article
[6] ISOBE, T.—SHIBUTANI, K.: Improved all-subkeys recovery attacks on FOX, KATAN and SHACAL-2 block ciphers, in: Int. Workshop on Fast Software Encr.—FSE ’14, Lecture Notes in Comput. Sci., Vol. 8540, Springer-Verlag, Berlin, 2015, pp. 104–126.
Search in Google Scholar Back to article
[7] FUHR, T.—MINAUD, B.: Match box meet-in-the-middle attack against KATAN, in: Int. Workshop on Fast Software Encr.—FSE ’14, Lecture Notes in Comput. Sci., Vol. 8540, Springer-Verlag, Berlin, 2015, pp. 61–81.
Search in Google Scholar Back to article
[8] ZHU, B.—GONG, G.: Multidimensional meet-in-the-middle attack and its applications to KATAN 32/48/64, Cryptogr. Commun. 6 (2014), 313–333.10.1007/s12095-014-0102-9
Search in Google Scholar Back to article
[9] AHMADIAN, Z.—RASOOLZADEH, SH.—SALMASIZADEH, M.—AREF, M. R.: Automated dynamic cube attack on block ciphers: cryptanalysis of SIMON and KATAN, Cryptology ePrint Archive, report 2015/040, 2015.
Search in Google Scholar Back to article
[10] DIFFIE, W.—HELLMAN, M.: Exhaustive cryptanalysis of the NBS data encryption standard, IEEE Comp.Soc.Press 10 (1977), 74–84.10.1109/C-M.1977.217750
Search in Google Scholar Back to article

Improved Multi-Dimensional Meet-in-the-Middle Cryptanalysis of Katan

Abstract

Paradigm

My account