[en] Recently, Biryukov et al. presented a new technique for key recovery in differential cryptanalysis, called meet-in-the-filter (MiF). In this work, we develop theoretical and practical aspects of the technique, which helps understanding and simplifies application. In particular, we show bounds on MiF complexity and conditions when the MiF-enhanced attack may reach them. We present a method based on trail counting which allows to estimate filtering strength of involved rounds and perform consequent complexity analysis with pen and paper, compared to the computer-aided approach of the original work. Furthermore, we show how MiF can be combined with plaintext structures for linear key schedules, allowing to increase the number of attacked rounds or to reduce the data complexity. We illustrate our methods on block cipher families CHAM and KATAN and show best-to-date single-key differential attacks for these ciphers.
Disciplines :
Sciences informatiques
Auteur, co-auteur :
BIRYUKOV, Alexei ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)
TEH, Je Sen ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > Cryptolux ; Universiti Sains Malaysia
UDOVENKO, Aleksei ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > Cryptolux
Co-auteurs externes :
yes
Langue du document :
Anglais
Titre :
Advancing the Meet-in-the-Filter Technique: Applications to CHAM and KATAN
Date de publication/diffusion :
mai 2024
Nom de la manifestation :
Selected Areas in Cryptography (SAC 2022)
Lieu de la manifestation :
Windsor, Ontario, Canada
Date de la manifestation :
from 24-08-2022 to 26-08-2022
Manifestation à portée :
International
Titre de l'ouvrage principal :
Selected Areas in Cryptography 2022
Editeur scientifique :
Smith, Benjamin
Wu, Huapeng
Maison d'édition :
Springer International Publishing
ISBN/EAN :
978-3-031-58410-7 978-3-031-58411-4
Collection et n° de collection :
SAC: International Conference on Selected Areas in Cryptography
Albrecht, M.R., Leander, G.: An all-in-one approach to differential cryptanalysis for small block ciphers. In: Knudsen, L.R., Wu, H. (eds.) SAC 2012. LNCS, vol. 7707, pp. 1–15. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-35999-6_1
Beaulieu, R., Shors, D., Smith, J., Treatman-Clark, S., Weeks, B., Wingers, L.: The SIMON and SPECK families of lightweight block ciphers. Cryptology ePrint Archive, Report 2013/404 (2013)
Biham, E., Shamir, A.: Differential Cryptanalysis of the Data Encryption Standard. Springer, Heidelberg (1993). https://doi.org/10.1007/978-1-4613-9314-6
Biryukov, A., dos Santos, L.C., Teh, J.S., Udovenko, A., Velichkov, V.: Meet-in-the-filter and dynamic counting with applications to speck. Cryptology ePrint Archive, Paper 2022/673 (2022). https://eprint.iacr.org/2022/673, https://eprint.iacr.org/2022/673
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). https://doi.org/10.1007/978-3-642-04138-9_20
Chen, J., Teh, J., Liu, Z., Su, C., Samsudin, A., Xiang, Y.: Towards accurate statistical analysis of security margins: New searching strategies for differential attacks. IEEE Trans. Comput. 66(10), 1763–1777 (2017)
Dinur, I.: Improved differential cryptanalysis of round-reduced speck. In: Joux, A., Youssef, A. (eds.) SAC 2014. LNCS, vol. 8781, pp. 147–164. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13051-4_9
Eichlseder, M., Kales, D.: Clustering related-tweak characteristics: application to MANTIS-6. IACR Trans. Symmetric Cryptol. 2018(2), 111–132 (2018)
Knellwolf, S., Meier, W., Naya-Plasencia, M.: Conditional differential cryptanalysis of NLFSR-based cryptosystems. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 130–145. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17373-8_8
Koo, B., Roh, D., Kim, H., Jung, Y., Lee, D.-G., Kwon, D.: CHAM: a family of lightweight block ciphers for resource-constrained devices. In: Kim, H., Kim, D.-C. (eds.) ICISC 2017. LNCS, vol. 10779, pp. 3–25. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78556-1_1
Rasoolzadeh, S., Raddum, H.: Multidimensional meet in the middle cryptanalysis of KATAN. IACR Cryptol. ePrint Arch. 77 (2016)
Roh, D., Koo, B., Jung, Y., Jeong, I.W., Lee, D.-G., Kwon, D., Kim, W.-H.: Revised version of block cipher CHAM. In: Seo, J.H. (ed.) ICISC 2019. LNCS, vol. 11975, pp. 1–19. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-40921-0_1
