Abstract
Impossible differential (ID) cryptanalysis is one of the most important attacks on block ciphers. The Mixed Integer Linear Programming (MILP) model is a popular method to determine whether a specific difference pair is an ID. Unfortunately, due to the huge search space (approximately \(2^{2n}\) for a cipher with a block size n bits), we cannot leverage this technique to exhaust all difference pairs, which is a well-known long-standing problem.
In this paper, we propose a systematic method to find all IDs for SPN block ciphers. The idea is to partition the whole difference pair space into lots of small disjoint sets, each of which has a representative difference pair. All difference pairs in one small set are possible if its representative pair is possible, and this can be conveniently checked by the MILP model. In this way, the overall search space is drastically reduced to a practical size by excluding the sets containing no IDs. We then examine the remaining difference pairs to identify all IDs (if some IDs exist). If our method cannot find any ID, the target cipher is proved free of ID distinguishers.
Our method works especially well for SPN ciphers with block size 64. We apply our method to SKINNY-64 and successfully find all 432 and 12 truncated IDs (we find all IDs but all of them can be assembled into certain truncated IDs) for 11 and 12 rounds, respectively. We also prove, for the first time, that 13-round SKINNY-64 is free of ID distinguishers even when considering the differential transitions through the Difference Distribution Table (DDT). Similarly, we find all 12 truncated IDs (all IDs are assembled into 12 truncated IDs) for 13-round CRAFT and prove there is no ID for 14 rounds. For SbPN cipher GIFT-64, we prove that there is no ID for 8 rounds.
For SPN ciphers with larger block sizes, we show that our idea is also useful to strengthen the current search methods. For example, if we consider the Sbox to be ideal and only consider the branch number information of the diffusion matrix, we can find all 6,750 truncated IDs for 6-round Rijndael-192 in 1 s and prove that there is no truncated ID for 7 rounds. Previously, we need to solve approximately \(2^{48}\) MILP models to achieve the same goal. For GIFT-128, we exhausted all difference patterns that have an active superbox in the plaintext and ciphertext and proved there is no ID of such patterns for 8 rounds.
Although we have searched for a larger or even full space for IDs, no longer ID distinguishers have been found. This implies the reasonableness of the intuition that a small number (usually one or two) of active bits/words at the beginning and end of an ID will be the longest.
The full version of this paper is https://eprint.iacr.org/2022/1034.pdf.
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
Similar content being viewed by others
References
Banik, S., Pandey, S.K., Peyrin, T., Sasaki, Y., Sim, S.M., Todo, Y.: GIFT: a small present. In: Fischer, W., Homma, N. (eds.) Cryptographic Hardware and Embedded Systems - CHES 2017. Lecture Notes in Computer Science(), vol. 10529, pp. 321–345. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66787-4_16
Beaulieu, R., Shors, D., Smith, J., Treatman-Clark, S., Weeks, B., Wingers, L.: The SIMON and SPECK lightweight block ciphers. In: DAC 2015, pp. 1–6. ACM (2015)
Beierle, C., et al.: The SKINNY family of block ciphers and its low-latency variant MANTIS. In: Robshaw, M., Katz, J. (eds.) Advances in Cryptology - CRYPTO 2016. Lecture Notes in Computer Science(), vol. 9815, pp. 123–153. Springer, Berlin (2016). https://doi.org/10.1007/978-3-662-53008-5_5
Beierle, C., Leander, G., Moradi, A., Rasoolzadeh, S.: CRAFT: lightweight tweakable block cipher with efficient protection against DFA attacks. IACR Trans. Symmetric Cryptol. 2019(1), 5–45 (2019)
Biham, E., Biryukov, A., Shamir, A.: Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials. In: Stern, J. (ed.) Advances in Cryptology - EUROCRYPT ’99. Lecture Notes in Computer Science, vol. 1592, pp. 12–23. Springer, Berlin (1999). https://doi.org/10.1007/3-540-48910-x_2
Biryukov, A.: Miss-in-the-middle attack. In: Encyclopedia of Cryptography and Security, 2nd ed., page 786. Springer, Cham (2011)
Bogdanov, A., et al.: PRESENT: an ultra-lightweight block cipher. In: Paillier, P., Verbauwhede, I. (eds.) Cryptographic Hardware and Embedded Systems - CHES 2007. Lecture Notes in Computer Science, vol. 4727, pp. 450–466. Springer, Berlin (2007). https://doi.org/10.1007/978-3-540-74735-2_31
Bogdanov, A., Rijmen, V.: Linear hulls with correlation zero and linear cryptanalysis of block ciphers. Des. Codes Crypt. 70(3), 369–383 (2014)
Cui, T., Chen, S., Jia, K., Fu, K., Wang, M.: New automatic tool for finding impossible differentials and zero-correlation linear approximations. Sci. China Inf. Sci. 64(2) (2021)
Cui, T., Chen, S., Jia, K., Fu, K., Wang, M.: New automatic search tool for impossible differentials and zero-correlation linear approximations. IACR Cryptol. ePrint Arch., 689 (2016)
Daemen, J., Rijmen, V.: AES and the Wide Trail Design Strategy. In: Knudsen, L.R. (ed.) Advances in Cryptology - EUROCRYPT 2002. Lecture Notes in Computer Science, vol. 2332, pp. 108–109. Springer, Berlin (2002). https://doi.org/10.1007/3-540-46035-7_7
Daemen, J., Rijmen, V.: The Design of Rijndael: AES - The Advanced Encryption Standard. ISC. Springer, Cham (2002). https://doi.org/10.1007/978-3-662-04722-4
Dunkelman, O., Huang, S., Lambooij, E., Perle, S.: Single tweakey cryptanalysis of reduced-round SKINNY-64. In: Dolev, S., Kolesnikov, V., Lodha, S., Weiss, G. (eds.) Cyber Security Cryptography and Machine Learning. Lecture Notes in Computer Science(), vol. 12161, pp. 1–17. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-49785-9_1
Jean, J., Nikolic, I., Peyrin, T.: Tweaks and keys for block ciphers: the TWEAKEY framework. In: Sarkar, P., Iwata, T. (eds.) Advances in Cryptology - ASIACRYPT 2014. Lecture Notes in Computer Science, vol. 8874, pp. 274–288. Springer, Berlin (2014). https://doi.org/10.1007/978-3-662-45608-8_15
Kim, J., Hong, S., Sung, J., Lee, S., Lim, J., Sung, S.: Impossible differential cryptanalysis for block cipher structures. In: Johansson, T., Maitra, S. (eds.) Progress in Cryptology - INDOCRYPT 2003. Lecture Notes in Computer Science, vol. 2904, pp. 82–96. Springer, Berlin (2003). https://doi.org/10.1007/978-3-540-24582-7_6
Knudsen, L.: Deal-a 128-bit block cipher. Complexity 258(2), 216 (1998)
Lu, J., Dunkelman, O., Keller, N., Kim, J.: New impossible differential attacks on AES. In: Chowdhury, D.R., Rijmen, V., Das, A. (eds.) Progress in Cryptology - INDOCRYPT 2008. Lecture Notes in Computer Science, vol. 5365, pp. 279–293. Springer, Berlin (2008). https://doi.org/10.1007/978-3-540-89754-5_22
Luo, Y., Lai, X., Wu, Z., Gong, G.: A unified method for finding impossible differentials of block cipher structures. Inf. Sci. 263, 211–220 (2014)
Mouha, N., Wang, Q., Gu, D., Preneel, B.: Differential and linear cryptanalysis using mixed-integer linear programming. In: Wu, C.K., Yung, M., Lin, D. (eds.) Information Security and Cryptology. Lecture Notes in Computer Science, vol. 7537, pp. 57–76. Springer, Berlin (2011)
Sasaki, Y., Todo, Y.: New impossible differential search tool from design and cryptanalysis aspects. In: Coron, J.S., Nielsen, J. (eds.) Advances in Cryptology - EUROCRYPT 2017. Lecture Notes in Computer Science(), vol. 10212, pp. 185–215. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56617-7_7
Sun, B., Liu, M., Guo, J., Rijmen, V., Li, R.: Provable security evaluation of structures against impossible differential and zero correlation linear cryptanalysis. In: Fischlin, M., Coron, J.S. (eds.) Advances in Cryptology - EUROCRYPT 2016. Lecture Notes in Computer Science(), vol. 9665, pp. 196–213. Springer, Berlin (2016). https://doi.org/10.1007/978-3-662-49890-3_8
Sun, L., Gérault, D., Wang, W., Wang, M.: On the usage of deterministic (related-key) truncated differentials and multidimensional linear approximations for SPN ciphers. IACR Trans. Symmetric Cryptol. 2020(3), 262–287 (2020)
Sun, S., Hu, L., Wang, P., Qiao, K., Ma, X., Song, L.: Automatic security evaluation and (related-key) differential characteristic search: application to SIMON, PRESENT, LBlock, DES(L) and other bit-oriented block ciphers. In: Sarkar, P., Iwata, T. (eds.) Advances in Cryptology – ASIACRYPT 2014. Lecture Notes in Computer Science, vol. 8873, pp. 158–178. Springer, Berlin (2014). https://doi.org/10.1007/978-3-662-45611-8_9
Wang, Q., Jin, C.: More accurate results on the provable security of AES against impossible differential cryptanalysis. Des., Codes Cryptograp. 87(12), 3001–3018 (2019)
Wang, Q., Jin, C.: Bounding the length of impossible differentials for SPN block ciphers. Des., Codes Cryptograp. 89(11), 2477–2493 (2021)
Wu, S., Wang, M.: Automatic search of truncated impossible differentials for word-oriented block ciphers. In: Galbraith, S., Nandi, M. (eds.) Progress in Cryptology - INDOCRYPT 2012. Lecture Notes in Computer Science, vol. 7668, pp. 283–302. Springer, Berlin (2012). https://doi.org/10.1007/978-3-642-34931-7_17
Acknowledgment
The authors would like to thank the anonymous reviewers for their valuable comments and suggestions. Meiqin Wang is supported by the National Natural Science Foundation of China (Grant No. 62002201, Grant No. 62032014), the National Key Research and Development Program of China (Grant No. 2018YFA0704702, 2018YFA0704704), the Major Scientific and Technological Innovation Project of Shandong Province, China (Grant No. 2019JZZY010133), the Major Basic Research Project of Natural Science Foundation of Shandong Province, China (Grant No. ZR202010220025).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Hu, K., Peyrin, T., Wang, M. (2024). Finding All Impossible Differentials When Considering the DDT. In: Smith, B., Wu, H. (eds) Selected Areas in Cryptography. SAC 2022. Lecture Notes in Computer Science, vol 13742. Springer, Cham. https://doi.org/10.1007/978-3-031-58411-4_13
Download citation
DOI: https://doi.org/10.1007/978-3-031-58411-4_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-58410-7
Online ISBN: 978-3-031-58411-4
eBook Packages: Computer ScienceComputer Science (R0)