Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Designs, Codes and Cryptography
Published in: Designs, Codes and Cryptography 9/2023

22-05-2023

Meet-in-the-middle attack with splice-and-cut technique and a general automatic framework

Authors: Kai Zhang, Xuejia Lai, Lei Wang, Jie Guan, Bin Hu, Senpeng Wang, Tairong Shi

Published in: Designs, Codes and Cryptography | Issue 9/2023

Login to get access

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Computer aided cryptanalysis has been popular for recent several years, however, most of these automations are semi-automations which leave cryptographers to complete the remaining parts of the attack. This paper proposes an automatic framework towards optimal meet-in-the-middle attack with splice-and-cut technique(MITM-SCT). Compared with other automations on MITM attack, our framework is fully automatic which can take all the procedures of the attack into consideration. Firstly, with a newly introduced matrix-based method, a general framework is proposed to calculate the correlated states and illustrate the differential diffusion property in a MITM attack. Alongside, all the procedures of a typical MITM-SCT attack are reduced to three types of matrices. These matrices can be uniquely determined by the round function and the construction methods are presented. Secondly, based on the framework, a fully automatic searching method on MITM-SCT attack is proposed. Thirdly, an optimal searching strategy on MITM-SCT attack is proposed and the bound for the time complexity is illustrated. Based on our method, if the computing capability is large enough, we can search all the possible attack scenarios and the least upper bound for the target block cipher against MITM-SCT attack can be derived. That is to say, we cannot only find some better attack scenarios, but also try all the possible attack scenarios simultaneously to find the optimal ones for some cases. Finally, we apply our method to HIGHT, CHAM, WARP and derive some currently best-known MITM attacks on these ciphers. For HIGHT, we exhaustively search about 2.1 billion attack scenarios and derive 76.8 thousand 23-round MITM attacks on HIGHT, which is 4 rounds more than the current best MITM attack. For the CHAM family ciphers, some MITM attacks are proposed on 30-round, 19-round, 30-round CHAM-64/128, CHAM-128/128 and CHAM-128/256 respectively. These results can exceed most of the attacks in the single key setting proposed by the designers. For WARP, a concrete 19-round MITM attack is proposed. Our automatic method is proposed on solving the problem of MITM attacks on ARX ciphers, however, the successful attack on WARP indicates that our method can also be applied to Sbox-based block ciphers.
previous article Several families of irreducible constacyclic and cyclic codes
next article The proportion of non-degenerate complementary subspaces in classical spaces
Appendix
Available only for authorised users
Literature
1.
Aoki K., Sasaki Y.: Meet-in-the-middle preimage attacks against reduced SHA-0 and SHA-1. CRYPTO 5677, 70–89 (2009).MathSciNetMATH
2.
Aoki, K., Sasaki, Y.: Preimage attacks on one-block MD4, 63-step MD5 and more. In: Selected Areas in Cryptography: 15th International Workshop, SAC: Sackville, New Brunswick, Canada, August 14–15, Revised Selected Papers 15, pp. 103–119. Springer, Berlin Heidelberg (2008)
3.
Banik, S., Bao, Z., Isobe, T., Kubo, H., Liu, F., Minematsu, K., et. al.: WARP: Revisiting GFN for lightweight 128-bit block cipher. In: Selected Areas in Cryptography: 27th International Conference, Halifax, NS, Canada (Virtual Event), October 21–23, 2020, Revised Selected Papers 27, pp. 535–564. Springer International Publishing (2021)
4.
Bao, Z., Dong, X., Guo, J., Li, Z., Shi, D., Sun, S., Wang, X.: Automatic search of meet-in-the-middle preimage attacks on AES-like hashing. In Advances in Cryptology-EUROCRYPT 2021: 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17–21, 2021, Proceedings, Part I vol. 40, pp. 771–804. Springer International Publishing (2021)
5.
Cui T., Chen S., Fu K., Wang M., Jia K.: New automatic tool for finding impossible differentials and zero-correlation linear approximations. Sci. China Inf. Sci. 64, 1–3 (2021).CrossRef
6.
Canteaut, A., Naya-Plasencia, M., Vayssiere, B.: Sieve-in-the-middle: improved MITM attacks. In: Proceedings of Advances in Cryptology-CRYPTO 2013: 33rd Annual Cryptology Conference, August 18–22. Part I, pp. 222–240. Springer Berlin Heidelberg, Santa Barbara, CA, USA (2013)
7.
Chen, J., Wang, M., Preneel, B.: Impossible differential cryptanalysis of the lightweight block ciphers TEA, XTEA and HIGHT. In: Proceedings of the Progress in Cryptology-AFRICACRYPT 2012: 5th International Conference on Cryptology in Africa, Ifrance, Morocco, July 10–12, vol. 5, pp. 117–137. Springer Berlin Heidelberg (2012)
8.
Derbez, P., Fouque, P.A.: Exhausting Demirci-Selçuk meet-in-the-middle attacks against reduced-round AES. In: Fast Software Encryption: 20th International Workshop, FSE 2013, Singapore, March 11–13: Revised Selected Papers 20, pp. 541–560. Springer, Berlin Heidelberg (2014)
9.
Derbez, P., Fouque, P.A.: Automatic search of meet-in-the-middle and impossible differential attacks. In: Proceedings of the Advances in Cryptology-CRYPTO 2016: 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14–18, 2016, vol. Part II 36, pp. 157–184. Springer Berlin Heidelberg (2016)
10.
Derbez, P., Fouque, P.A., Jean, J.: Improved key recovery attacks on reduced-round AES in the single-key setting. In: Proceedings of the Advances in Cryptology-EUROCRYPT 2013: 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26–30, vol. 32, pp. 371–387. Springer Berlin Heidelberg (2013)
11.
Diffie W., Hellman M.E.: Special feature exhaustive cryptanalysis of the NBS data encryption standard. Computer 10(6), 74–84 (1977).CrossRef
12.
Dong X., Hua J., Sun S., Li Z., Wang X., Hu L.: Meet-in-the-middle attacks revisited: focusing on key-recovery and collision attacks. IACR Cryptol. ePrint Arch. 2021, 427 (2021).MATH
13.
Demirci, H., Selçuk, A.A.: A meet-in-the-middle attack on 8-round AES. In: Fast Software Encryption: 15th International Workshop, FSE: Lausanne, Switzerland, February 10–13, 2008, Revised Selected Papers 15, pp. 116–126. Springer, Berlin Heidelberg (2008)
14.
Fuhr, T., Minaud, B.: Match box meet-in-the-middle attack against KATAN. In: Fast Software Encryption: 21st International Workshop, FSE 2014, London, UK, March 3–5: Revised Selected Papers 21, pp. 61–81. Springer, Berlin Heidelberg (2015)
15.
Fu, K., Wang, M., Guo, Y., Sun, S., Hu, L.: MILP-based automatic search algorithms for differential and linear trails for speck. In: Fast Software Encryption: 23rd International Conference, FSE: Bochum, Germany, March 20–23, Revised Selected Papers 23, pp. 268–288. Springer, Berlin Heidelberg (2016)
16.
Gerault, D., Minier, M., Solnon, C.: Constraint programming models for chosen key differential cryptanalysis. In: Proceedings of the Principles and Practice of Constraint Programming: 22nd International Conference, CP 2016, Toulouse, France, September 5–9, vol. 22, pp. 584–601. Springer International Publishing (2016)
17.
Hong, D., Sung, J., Hong, S., Lim, J., Lee, S., Koo, B.S., et. al. (2006). HIGHT: A new block cipher suitable for low-resource device. In: Proceedings of the Cryptographic Hardware and Embedded Systems-CHES 2006: 8th International Workshop, Yokohama, Japan, October 10–13, vol. 8, pp. 46–59. Springer Berlin Heidelberg (2006)
18.
Hadipour H., Eichlseder M.: Integral cryptanalysis of WARP based on monomial prediction. IACR Trans. Sym. Cryptol. 2022(2), 92–112 (2022).CrossRef
19.
Hu K., Sun S., Wang M., Wang Q.: An algebraic formulation of the division property: Revisiting degree evaluations, cube attacks, and key-independent sums. In: Proceedings of the Advances in Cryptology-ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7–11, Part I, pp. 446–476. Springer International Publishing, Cham (2020)
20.
Igarashi, Y., Sueyoshi, R., Kaneko, T., Fuchida, T.: Meet-in-the-middle attack with splice-and-cut technique on the 19-round variant of block cipher HIGHT. In: Information Science and Applications, pp. 423–429. Springer Berlin Heidelberg (2015)
21.
22.
Kim, J., Hong, S., Sung, J., Lee, S., Lim, J., Sung, S.: Impossible differential cryptanalysis for block cipher structures. In: Proceedings of the Progress in Cryptology-INDOCRYPT 2003: 4th International Conference on Cryptology in India, New Delhi, India, December 8–10, vol. 4, pp. 82–96. Springer Berlin Heidelberg (2003)
23.
Khovratovich, D., Rechberger, C., Savelieva, A.: Bicliques for preimages: attacks on Skein-512 and the SHA-2 family. In: Fast Software Encryption: 19th International Workshop, FSE 2012, Washington, DC, USA, March 19–21: Revised Selected Papers, pp. 244–263. Springer, Berlin Heidelberg (2012)
24.
Le Gall, F.: Powers of tensors and fast matrix multiplication. In: Proceedings of the 39th international symposium on symbolic and algebraic computation, pp. 296–303 (2014)
25.
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).CrossRefMATH
26.
Liu, Y., Wang, Q., Rijmen, V.: Automatic search of linear trails in ARX with applications to SPECK and Chaskey. In: Proceeding of the Applied Cryptography and Network Security: 14th International Conference, ACNS, Guildford, UK, June 19–22, vol. 14, pp. 485–499. Springer International Publishing (2016)
27.
Lallemand, V., Minier, M., Rouquette, L.: Automatic search of rectangle attacks on feistel ciphers: Application to WARP. IACR Transactions on Symmetric Cryptology, pp. 113–140 (2022)
28.
Lin, L., Wu, W., Wang, Y., Zhang, L.: General model of the single-key meet-in-the-middle distinguisher on the word-oriented block cipher. In Information Security and Cryptology–ICISC 2013: 16th International Conference, Seoul, Korea, November 27–29, 2013, Revised Selected Papers 16, pp. 203–223. Springer International Publishing (2014)
29.
Mouha, N., Preneel, B.: Towards finding optimal differential characteristics for ARX: Application to Salsa20. Cryptology ePrint Archive (2013)
30.
Mouha, N., Wang, Q., Gu, D., Preneel, B.: Differential and linear cryptanalysis using mixed-integer linear programming. In: Information Security and Cryptology: 7th International Conference, Inscrypt 2011, Beijing, China, November 30–December 3: Revised Selected Papers 7, pp. 57–76. Springer, Berlin Heidelberg (2012)
31.
Qin, L., Dong, X., Wang, X., Jia, K., Liu, Y.: Automated search oriented to key recovery on ciphers with linear key schedule: applications to boomerangs in SKINNY and ForkSkinny. In: IACR Transactions on Symmetric Cryptology, pp. 249–291 (2021)
32.
Roh, D., Koo, B., Jung, Y., Jeong, I.W., Lee, D.G., Kwon, D., Kim, W.H.: Revised version of block cipher CHAM. In: Information Security and Cryptology-ICISC 2019: 22nd International Conference, Seoul, South Korea, December 4–6, 2019, Revised Selected Papers 22, pp. 1–19. Springer International Publishing (2020)
33.
Sasaki, Y., Aoki, K.: Finding preimages in full MD5 faster than exhaustive search. In: Proceedings of the Advances in Cryptology-EUROCRYPT 2009: 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cologne, Germany, April 26–30, vol. 28, pp. 134–152. Springer Berlin Heidelberg (2009)
34.
Sasaki, Y.: Integer linear programming for three-subset meet-in-the-middle attacks: application to gift. In: Advances in Information and Computer Security: 13th International Workshop on Security, IWSEC 2018, Sendai, Japan, September 3–5, vol. 13, pp. 227–243. Springer International Publishing (2018)
35.
Sun S., Gerault D., Lafourcade P., Yang Q., Todo Y., Qiao K., Hu L.: Analysis of AES, SKINNY, and others with constraint programming. IACR Trans. Sym. Cryptol. 2017(1), 281–306 (2017).CrossRef
36.
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: Proceedings of the Advances in Cryptology-ASIACRYPT 2014: 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, ROC, December 7–11, vol. Part I 20, pp. 158–178. Springer Berlin Heidelberg (2014)
37.
Shi D., Sun S., Derbez P., Todo Y., Sun B., Hu, L.: Programming the Demirci-Selçuk meet-in-the-middle attack with constraints. In: Proceedings of the Advances in Cryptology-ASIACRYPT 2018: 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2–6, vol. Part II, pp. 3–34. Springer International Publishing, Cham (2018)
38.
Sasaki, Y., Todo, Y.: New impossible differential search tool from design and cryptanalysis aspects: revealing structural properties of several ciphers. In: Proceedings of the Advances in Cryptology-EUROCRYPT 2017: 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30–May 4, vol. Part III 36, pp. 185–215. Springer International Publishing (2017)
39.
Sasaki, Y., Wang, L.: Meet-in-the-middle technique for integral attacks against feistel ciphers. In: Selected Areas in Cryptography: 19th International Conference, SAC: Windsor, ON, Canada, August 15–16, 2012, Revised Selected Papers 19, pp. 234–251. Springer, Berlin Heidelberg (2013)
40.
Teh J.S., Biryukov A.: Differential cryptanalysis of WARP. J. Inf. Secur. Appl. 70, 103316 (2022).
41.
Wei, L., Rechberger, C., Guo, J., Wu, H., Wang, H., Ling, S.: Improved meet-in-the-middle cryptanalysis of KTANTAN (poster). In: Proceedings of the Information Security and Privacy: 16th Australasian Conference, ACISP 2011, Melbourne, Australia, July 11–13, vol. 16, pp. 433–438. Springer Berlin Heidelberg (2011)
42.
Wen L., Wang M., Bogdanov A., Chen H.: Multidimensional zero-correlation attacks on lightweight block cipher HIGHT: improved cryptanalysis of an ISO standard. Inf. Process. Lett. 114(6), 322–330 (2014).CrossRefMATH
43.
Xiang, Z., Zhang, W., Bao, Z., Lin, D.: Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers. In: Proceedings of the Advances in Cryptology-ASIACRYPT 2016: 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4–8, vol. Part I 22, pp. 648–678. Springer Berlin Heidelberg (2016)
44.
Zong, R., Dong, X., Chen, H., Luo, Y., Wang, S., Li, Z.: Towards key-recovery-attack friendly distinguishers: application to GIFT-128. IACR Transactions on Symmetric Cryptology, pp. 156–184 (2021)
45.
Zhu B., Gong G.: Multidimensional meet-in-the-middle attack and its applications to KATAN32/48/64. Cryptogr. Commun. 6, 313–333 (2014).MathSciNetCrossRefMATH
46.
Zhang K., Guan J., Hu B.: Automatic search of impossible differentials and zero-correlation linear hulls for ARX ciphers. China Commun. 15(2), 54–66 (2018).CrossRef
47.
Zhang K., Lai X., Wang L., Guan J., Hu B., Wang S., Shi T.: Rotational-XOR differential cryptanalysis and an automatic framework for AND-RX ciphers. IEEE Trans. Inf. Theory 69(2), 1282–1294 (2023).MathSciNetCrossRef
Metadata
Title
Meet-in-the-middle attack with splice-and-cut technique and a general automatic framework
Authors
Kai Zhang
Xuejia Lai
Lei Wang
Jie Guan
Bin Hu
Senpeng Wang
Tairong Shi
Publication date
22-05-2023
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 9/2023
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-023-01226-4

Other articles of this Issue 9/2023

Designs, Codes and Cryptography 9/2023 Go to the issue

OriginalPaper

Characterizing subgroup perfect codes by 2-subgroups

OriginalPaper

(Compact) Adaptively secure FE for attribute-weighted sums from k-Lin

OriginalPaper

On the algebraic immunity—resiliency trade-off, implications for Goldreich’s pseudorandom generator

OriginalPaper

The proportion of non-degenerate complementary subspaces in classical spaces

OriginalPaper

Several families of irreducible constacyclic and cyclic codes

OriginalPaper

Hiding the input-size in multi-party private set intersection

Premium Partner

    Image Credits