Finding the impossible: automated search for full impossible-differential, zero-correlation, and integral attacks. (English) Zbl 1528.94057
Hazay, Carmit (ed.) et al., Advances in cryptology – EUROCRYPT 2023. 42nd annual international conference on the theory and applications of cryptographic techniques, Lyon, France, April 23–27, 2023. Proceedings. Part IV. Cham: Springer. Lect. Notes Comput. Sci. 14007, 128-157 (2023).
Summary: Impossible differential (ID), zero-correlation (ZC), and integral attacks are a family of important attacks on block ciphers. For example, the impossible differential attack was the first cryptanalytic attack on 7 rounds of AES. Evaluating the security of block ciphers against these attacks is very important but also challenging: Finding these attacks usually implies a combinatorial optimization problem involving many parameters and constraints that is very hard to solve using manual approaches. Automated solvers, such as Constraint Programming (CP) solvers, can help the cryptanalyst to find suitable attacks. However, previous CP-based methods focus on finding only the ID, ZC, and integral distinguishers, often only in a limited search space. Notably, none can be extended to a unified optimization problem for finding full attacks, including efficient key-recovery steps.
In this paper, we present a new CP-based method to search for ID, ZC, and integral distinguishers and extend it to a unified constraint optimization problem for finding full ID, ZC, and integral attacks. To show the effectiveness and usefulness of our method, we applied it to several block ciphers, including SKINNY, CRAFT, SKINNYe-v2, and SKINNYee. For the ISO standard block cipher SKINNY, we significantly improve all existing ID, ZC, and integral attacks. In particular, we improve the integral attacks on SKINNY-\(n\)-\(3n\) and SKINNY-\(n\)-\(2n\) by 3 and 2 rounds, respectively, obtaining the best cryptanalytic results on these variants in the single-key setting. We improve the ZC attack on SKINNY-\(n\)-\(n\) (SKINNY-\(n\)-\(2n\)) by 2 (resp. 1) rounds. We also improve the ID attacks on all variants of SKINNY. Particularly, we improve the time complexity of the best previous single-tweakey (related-tweakey) ID attack on SKINNY-128-256 (resp. SKINNY-128-384) by a factor of \(2^{22.57}\) (resp. \(2^{15.39})\). On CRAFT, we propose a 21-round (20-round) ID (resp. ZC) attack, which improves the best previous single-tweakey attack by 2 (resp. 1) rounds. Using our new model, we also provide several practical integral distinguishers for reduced-round SKINNY, CRAFT, and Deoxys-BC. Our method is generic and applicable to other strongly aligned block ciphers.
For the entire collection see [Zbl 1525.94004].
In this paper, we present a new CP-based method to search for ID, ZC, and integral distinguishers and extend it to a unified constraint optimization problem for finding full ID, ZC, and integral attacks. To show the effectiveness and usefulness of our method, we applied it to several block ciphers, including SKINNY, CRAFT, SKINNYe-v2, and SKINNYee. For the ISO standard block cipher SKINNY, we significantly improve all existing ID, ZC, and integral attacks. In particular, we improve the integral attacks on SKINNY-\(n\)-\(3n\) and SKINNY-\(n\)-\(2n\) by 3 and 2 rounds, respectively, obtaining the best cryptanalytic results on these variants in the single-key setting. We improve the ZC attack on SKINNY-\(n\)-\(n\) (SKINNY-\(n\)-\(2n\)) by 2 (resp. 1) rounds. We also improve the ID attacks on all variants of SKINNY. Particularly, we improve the time complexity of the best previous single-tweakey (related-tweakey) ID attack on SKINNY-128-256 (resp. SKINNY-128-384) by a factor of \(2^{22.57}\) (resp. \(2^{15.39})\). On CRAFT, we propose a 21-round (20-round) ID (resp. ZC) attack, which improves the best previous single-tweakey attack by 2 (resp. 1) rounds. Using our new model, we also provide several practical integral distinguishers for reduced-round SKINNY, CRAFT, and Deoxys-BC. Our method is generic and applicable to other strongly aligned block ciphers.
For the entire collection see [Zbl 1525.94004].
MSC:
| 94A60 | Cryptography |
Keywords:
impossible differential attacks; zero-correlation attacks; integral attacks; SKINNY; SKINNYe; CRAFT; SKINNYee; deoxys-BCReferences:
| [1] | Ankele, R., Dobraunig, C., Guo, J., Lambooij, E., Leander, G., Todo, Y.: Zero-correlation attacks on tweakable block ciphers with linear tweakey expansion. IACR Trans. Symmetric Cryptol. 2019(1), 192-235 (2019). doi:10.13154/tosc.v2019.i1.192-235 |
| [2] | Avanzi, R.: The QARMA block cipher family. almost MDS matrices over rings with zero divisors, nearly symmetric even-mansour constructions with non-involutory central rounds, and search heuristics for low-latency s-boxes. IACR Trans. Symmetric Cryptol. 2017(1), 4-44 (2017). doi:10.13154/tosc.v2017.i1.4-44 |
| [3] | Beierle, C.; Jean, J.; Kölbl, S.; Leander, G.; Moradi, A.; Peyrin, T.; Sasaki, Yu; Sasdrich, P.; Sim, SM; Robshaw, M.; Katz, J., The SKINNY family of block ciphers and its low-latency variant MANTIS, Advances in Cryptology - CRYPTO 2016, 123-153 (2016), Heidelberg: Springer, Heidelberg · Zbl 1372.94412 · doi:10.1007/978-3-662-53008-5_5 |
| [4] | 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). doi:10.13154/tosc.v2019.i1.5-45 |
| [5] | Biham, E.; Biryukov, A.; Shamir, A.; Stern, J., Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials, Advances in Cryptology — EUROCRYPT ’99, 12-23 (1999), Heidelberg: Springer, Heidelberg · Zbl 0927.94013 · doi:10.1007/3-540-48910-X_2 |
| [6] | Biham, E.; Biryukov, A.; Shamir, A.; Knudsen, L., Miss in the middle attacks on IDEA and Khufu, Fast Software Encryption, 124-138 (1999), Heidelberg: Springer, Heidelberg · Zbl 0942.94010 · doi:10.1007/3-540-48519-8_10 |
| [7] | Bogdanov, A.; Leander, G.; Nyberg, K.; Wang, M.; Wang, X.; Sako, K., Integral and multidimensional linear distinguishers with correlation zero, Advances in Cryptology - ASIACRYPT 2012, 244-261 (2012), Heidelberg: Springer, Heidelberg · Zbl 1292.94031 · doi:10.1007/978-3-642-34961-4_16 |
| [8] | Bogdanov, A.; Rijmen, V., Linear hulls with correlation zero and linear cryptanalysis of block ciphers, Des. Codes Crypt., 70, 3, 369-383 (2012) · Zbl 1323.94103 · doi:10.1007/s10623-012-9697-z |
| [9] | Bogdanov, A.; Wang, M.; Canteaut, A., Zero correlation linear cryptanalysis with reduced data complexity, Fast Software Encryption, 29-48 (2012), Heidelberg: Springer, Heidelberg · Zbl 1282.94035 · doi:10.1007/978-3-642-34047-5_3 |
| [10] | Boura, C.; Lallemand, V.; Naya-Plasencia, M.; Suder, V., Making the impossible possible, J. Cryptol., 31, 1, 101-133 (2017) · Zbl 1421.94041 · doi:10.1007/s00145-016-9251-7 |
| [11] | Boura, C.; Naya-Plasencia, M.; Suder, V.; Sarkar, P.; Iwata, T., Scrutinizing and improving impossible differential attacks: applications to CLEFIA, Camellia, LBlock and Simon, Advances in Cryptology - ASIACRYPT 2014, 179-199 (2014), Heidelberg: Springer, Heidelberg · Zbl 1306.94035 · doi:10.1007/978-3-662-45611-8_10 |
| [12] | 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 Archive, Report 2016/689 (2016), https://eprint.iacr.org/2016/689 |
| [13] | Daemen, J.; Knudsen, L.; Rijmen, V.; Biham, E., The block cipher Square, Fast Software Encryption, 149-165 (1997), Heidelberg: Springer, Heidelberg · Zbl 1385.94025 · doi:10.1007/BFb0052343 |
| [14] | Derbez, P., Fouque, P.-A.: Automatic Search of Meet-in-the-Middle and Impossible Differential Attacks. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 157-184. Springer, Heidelberg (2016). doi:10.1007/978-3-662-53008-5_6 · Zbl 1372.94422 |
| [15] | Eskandari, Z., Kidmose, A.B., Kölbl, S., Tiessen, T.: Finding integral distinguishers with ease. In: SAC. LNCS, vol. 11349, pp. 115-138. Springer, Cham (2018). doi:10.1007/978-3-030-10970-7_6 · Zbl 1447.94035 |
| [16] | Ferguson, N.; Goos, G.; Hartmanis, J.; van Leeuwen, J.; Schneier, B., Improved cryptanalysis of Rijndael, Fast Software Encryption, 213-230 (2001), Heidelberg: Springer, Heidelberg · Zbl 0994.68631 · doi:10.1007/3-540-44706-7_15 |
| [17] | Gurobi Optimization LLC: Gurobi Optimizer Reference Manual (2022). https://www.gurobi.com |
| [18] | Hadipour, H., Eichlseder, M.: Autoguess: A tool for finding guess-and-determine attacks and key bridges. In: ACNS 2022. LNCS, vol. 13269, pp. 230-250. Springer, Cham (2022). doi:10.1007/978-3-031-09234-3_12 |
| [19] | Hadipour, H., Eichlseder, M.: Integral cryptanalysis of WARP based on monomial prediction. IACR Trans. Symmetric Cryptol. 2022(2), 92-112 (2022). doi:10.46586/tosc.v2022.i2.92-112 |
| [20] | Hadipour, H., Nageler, M., Eichlseder, M.: Throwing boomerangs into feistel structures: Application to CLEFIA, WARP, LBlock, LBlock-s and TWINE. IACR Trans. Symmetric Cryptol. 2022(3), 271-302 (2022). doi:10.46586/tosc.v2022.i3.271-302 |
| [21] | Hadipour, H., Sadeghi, S., Eichlseder, M.: Finding the impossible: Automated search for full impossible differential, zero-correlation, and integral attacks. IACR Cryptology ePrint Archive, Report 2022/1147, p. 92 (2022). https://eprint.iacr.org/2022/1147 |
| [22] | Hadipour, H., Sadeghi, S., Niknam, M.M., Song, L., Bagheri, N.: Comprehensive security analysis of CRAFT. IACR Trans. Symmetric Cryptol. 2019(4), 290-317 (2019). doi:10.13154/tosc.v2019.i4.290-317 |
| [23] | Hu, K.; Sun, S.; Wang, M.; Wang, Q.; Moriai, S.; Wang, H., An algebraic formulation of the division property: revisiting degree evaluations, cube attacks, and key-independent sums, Advances in Cryptology - ASIACRYPT 2020, 446-476 (2020), Cham: Springer, Cham · Zbl 1511.94112 · doi:10.1007/978-3-030-64837-4_15 |
| [24] | Jean, J.; Nikolić, I.; Peyrin, T.; Sarkar, P.; Iwata, T., Tweaks and keys for block ciphers: The TWEAKEY framework, Advances in Cryptology - ASIACRYPT 2014, 274-288 (2014), Heidelberg: Springer, Heidelberg · Zbl 1317.94113 · doi:10.1007/978-3-662-45608-8_15 |
| [25] | Knudsen, L.: Deal-a 128-bit block cipher. Complexity 258(2), 216 (1998) |
| [26] | Lai, X.: Higher order derivatives and differential cryptanalysis, pp. 227-233 (1994). doi:10.1007/978-1-4615-2694-0_23 · Zbl 0840.94017 |
| [27] | Liu, G., Ghosh, M., Song, L.: Security analysis of SKINNY under related-tweakey settings. IACR Trans. Symmetric Cryptol. 2017(3), 37-72 (2017). doi:10.13154/tosc.v2017.i3.37-72 |
| [28] | Lu, J.; Dunkelman, O.; Keller, N.; Kim, J.; Chowdhury, DR; Rijmen, V.; Das, A., New impossible differential attacks on AES, Progress in Cryptology - INDOCRYPT 2008, 279-293 (2008), Heidelberg: Springer, Heidelberg · Zbl 1203.94113 · doi:10.1007/978-3-540-89754-5_22 |
| [29] | Lu, J.; Kim, J.; Keller, N.; Dunkelman, O.; Malkin, T., Improving the efficiency of impossible differential cryptanalysis of reduced camellia and MISTY1, Topics in Cryptology - CT-RSA 2008, 370-386 (2008), Heidelberg: Springer, Heidelberg · Zbl 1153.94408 · doi:10.1007/978-3-540-79263-5_24 |
| [30] | Mouha, N.; Wang, Q.; Gu, D.; Preneel, B.; Wu, C-K; Yung, M.; Lin, D., Differential and linear cryptanalysis using mixed-integer linear programming, Information Security and Cryptology, 57-76 (2012), Heidelberg: Springer, Heidelberg · Zbl 1292.94118 · doi:10.1007/978-3-642-34704-7_5 |
| [31] | Naito, Y.; Sasaki, Yu; Sugawara, T.; Canteaut, A.; Ishai, Y., Lightweight authenticated encryption mode suitable for threshold implementation, Advances in Cryptology - EUROCRYPT 2020, 705-735 (2020), Cham: Springer, Cham · Zbl 1492.94150 · doi:10.1007/978-3-030-45724-2_24 |
| [32] | Naito, Y., Sasaki, Y., Sugawara, T.: Secret can be public: Low-memory AEAD mode for high-order masking. In: CRYPTO 2022. LNCS, vol. 13509, pp. 315-345. Springer, Cham (2022). doi:10.1007/978-3-031-15982-4_11 · Zbl 1517.94135 |
| [33] | Nethercote, N.; Stuckey, PJ; Becket, R.; Brand, S.; Duck, GJ; Tack, G.; Bessière, C., MiniZinc: towards a standard CP modelling language, Principles and Practice of Constraint Programming - CP 2007, 529-543 (2007), Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-540-74970-7_38 |
| [34] | Niu, C.; Li, M.; Sun, S.; Wang, M.; Paterson, KG, Zero-correlation linear cryptanalysis with equal treatment for plaintexts and tweakeys, Topics in Cryptology - CT-RSA 2021, 126-147 (2021), Cham: Springer, Cham · Zbl 1479.94238 · doi:10.1007/978-3-030-75539-3_6 |
| [35] | Perron, L., Furnon, V.: OR-Tools. https://developers.google.com/optimization/ |
| [36] | Sadeghi, S., Mohammadi, T., Bagheri, N.: Cryptanalysis of reduced round SKINNY block cipher. IACR Trans. Symmetric Cryptol. 2018(3), 124-162 (2018). doi:10.13154/tosc.v2018.i3.124-162 |
| [37] | Sasaki, Yu; Todo, Y.; Coron, J-S; Nielsen, JB, New impossible differential search tool from design and cryptanalysis aspects, Advances in Cryptology - EUROCRYPT 2017, 185-215 (2017), Cham: Springer, Cham · Zbl 1394.94941 · doi:10.1007/978-3-319-56617-7_7 |
| [38] | Sasaki, Yu; Wang, L.; Knudsen, LR; Wu, H., Meet-in-the-middle technique for integral attacks against feistel ciphers, Selected Areas in Cryptography, 234-251 (2013), Heidelberg: Springer, Heidelberg · Zbl 1327.94073 · doi:10.1007/978-3-642-35999-6_16 |
| [39] | Shi, D.; Sun, S.; Derbez, P.; Todo, Y.; Sun, B.; Hu, L.; Peyrin, T.; Galbraith, S., Programming the Demirci-Selçuk meet-in-the-middle attack with constraints, Advances in Cryptology - ASIACRYPT 2018, 3-34 (2018), Cham: Springer, Cham · Zbl 1446.94157 · doi:10.1007/978-3-030-03329-3_1 |
| [40] | Song, L., et al.: Optimizing rectangle attacks: A unified and generic framework for key recovery. In: ASIACRYPT 2022. LNCS, vol. 13791, pp. 410-440. Springer, Cham (2022). doi:10.1007/978-3-031-22963-3_14 · Zbl 1519.94187 |
| [41] | Sun, B.; Gennaro, R.; Robshaw, M., Links among impossible differential, integral and zero correlation linear cryptanalysis, Advances in Cryptology - CRYPTO 2015, 95-115 (2015), Heidelberg: Springer, Heidelberg · Zbl 1347.94059 · doi:10.1007/978-3-662-47989-6_5 |
| [42] | Sun, L., Gerault, 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). doi:10.13154/tosc.v2020.i3.262-287 |
| [43] | Sun, S., et al.: Analysis of aes, skinny, and others with constraint programming. IACR Trans. Symmetric Cryptol. 2017(1), 281-306 (2017). doi:10.13154/tosc.v2017.i1.281-306 |
| [44] | Todo, Y.: Structural evaluation by generalized integral property. In: EUROCRYPT 2015. LNCS, vol. 9056, pp. 287-314. Springer, Cham (2015). doi:10.1007/978-3-662-46800-5_12 · Zbl 1370.94545 |
| [45] | Tolba, M.; Abdelkhalek, A.; Youssef, AM; Joye, M.; Nitaj, A., Impossible differential cryptanalysis of reduced-round SKINNY, Progress in Cryptology - AFRICACRYPT 2017, 117-134 (2017), Cham: Springer, Cham · Zbl 1408.94969 · doi:10.1007/978-3-319-57339-7_7 |
| [46] | Xiang, Z.; Zhang, W.; Bao, Z.; Lin, D.; Cheon, JH; Takagi, T., Applying MILP Method to Searching Integral Distinguishers Based on Division Property for 6 Lightweight Block Ciphers, Advances in Cryptology - ASIACRYPT 2016, 648-678 (2016), Heidelberg: Springer, Heidelberg · Zbl 1404.94120 · doi:10.1007/978-3-662-53887-6_24 |
| [47] | Yang, D.; Qi, W.; Chen, H., Impossible differential attacks on the SKINNY family of block ciphers, IET Inf. Secur., 11, 6, 377-385 (2017) · doi:10.1049/iet-ifs.2016.0488 |
| [48] | Zhang, Y., Cui, T., Wang, C.: Zero-correlation linear attack on reduced-round SKINNY. Frontiers of Comput. Sci. 17(174808 (2023)), 377-385 (2022). doi:10.1007/s11704-022-2206-2 |
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.
