iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://unpaywall.org/10.1007/S11128-024-04349-2
New Demiric–Selçuk meet-in-the-middle attacks on Misty and Feistel schemes | Quantum Information Processing Skip to main content
Springer Nature Link
Log in

New Demiric–Selçuk meet-in-the-middle attacks on Misty and Feistel schemes

  • Published:
Quantum Information Processing Aims and scope Submit manuscript

Abstract

In this paper, we present some new key-recovery attacks on Misty L-KF, Misty R-KF, and generalized Feistel schemes. Firstly, we propose a new 5-round distinguisher on Misty L-KF structure. Based on our new distinguisher attack, we propose a new 6-round Demiric–Selçuk meet-in-the-middle attack (DS-MITM attack) against Misty L-KF structure. Secondly, we extend our classical DS-MITM attack to a new quantum DS-MITM attack on Misty L-KF structure by using the quantum claw finding algorithm. In addition, we apply the above method to attack Misty R-KF and generalized Feistel schemes. To sum up, we construct our classical key-recovery attacks on the 6-round Misty L-KF structure and Misty R-KF structure with \( O (2^{3n/4}) \) time and \( O (2^{n/2}) \) memory cost. By using a quantum computer, our new quantum key-recovery attacks on the 6-round Misty L-KF structures and Misty R-KF structures can be constructed with \( {\tilde{O}}(2^{n/2}) \) time and \( O (2^{n/2}) \) memory cost. Furthermore, we can construct our new quantum \((5d-4)\)-round key-recovery attacks on the d-branch contracting Feistels with \({\tilde{O}}(2^{(d-1)n/d})\) time and \(O (2^{(d-1)n/d})\) memory cost. In the end, we can construct our new quantum \((4d-3)\)-round and \((5d-4)\)-round key-recovery attacks on the two types of d-branch expanding Feistels with \({\tilde{O}}(2^{(d-1)n/d})\) time and \(O (2^{(d-1)n/d})\) memory cost.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Algorithm 1
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Algorithm 2
Fig. 10

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Data availability

The datasets generated during and/or analyzed during the current study are available from the corresponding author on reasonable request.

References

  1. Matsui, M.: New block encryption algorithm MISTY. In Biham, E. (ed.), Fast Software Encryption, 4th International Workshop, FSE ’97, Haifa, Israel, January 20–22, 1997, Proceedings, vol. 1267, pp. 54–68. Springer (1997)

  2. Feistel, H.: Cryptography and computer privacy. Sci. Am. 228(5), 15–23 (1973)

    Article  ADS  Google Scholar 

  3. Nyberg, K.: Generalized feistel networks. In Kim, K., Matsumoto, T. (eds Advances in Cryptology - ASIACRYPT ’96, International Conference on the Theory and Applications of Cryptology and Information Security, Kyongju, Korea, November 3–7, 1996, Proceedings, vol. 1163, pp. 91–104. Springer (1996)

  4. Coppersmith, Don: The data encryption standard (DES) and its strength against attacks. IBM J. Res. Dev. 38(3), 243–250 (1994)

    Article  Google Scholar 

  5. Aoki, K., Ichikawa, T., Kanda, M., Matsui, M., Moriai, S., Nakajima, J., Tokita, T.: Camellia: a 128-bit block cipher suitable for multiple platforms - design and analysis. In Stinson, D.R., Tavares, S.E. (eds.) Selected Areas in Cryptography, 7th Annual International Workshop, SAC 2000, Waterloo, Ontario, Canada, August 14–15, 2000, Proceedings, vol. 2012, pp. 39–56. Springer (2000)

  6. Rivest, Ron: A description of the rc2(r) encryption algorithm. RFC 2268, 1–11 (1998)

    Google Scholar 

  7. Peyravian, O.M., Burwick, C., Gennaro, R., Halevi, S., Zunic, N.: Mars—a candidate cipher for aes. nist aes proposal, (1999)

  8. Isobe, T., Shibutani, K.: Generic key recovery attack on feistel scheme. In Advances in Cryptology - ASIACRYPT 2013—19th International Conference on the Theory and Application of Cryptology and Information Security, Bengaluru, India, December 1–5, 2013, Proceedings, Part I, vol. 8269, pp. 464–485. Springer (2013)

  9. Dinur, I., Dunkelman, O., Keller, N., Shamir, A.: New attacks on feistel structures with improved memory complexities. In Gennaro, R., Robshaw, M. (eds.), Advances in Cryptology—CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part I, vol. 9215, pp. 433–454. Springer (2015)

  10. Boyer, M., Brassard, G., Hoyer, P., Tappa, A.: Tight Bounds on Quantum Searching, vol. 46 (2005)

  11. Dong, Xiaoyang, Wang, Xiaoyun: Quantum key-recovery attack on Feistel structures. Sci. China Inf. Sci. 61(10), 102501:1-102501:7 (2018)

    Article  Google Scholar 

  12. Gouget, A., Patarin, J., Toulemonde, A.: (quantum) cryptanalysis of misty schemes. In Hong, D. (ed.), Information Security and Cryptology—ICISC 2020—23rd International Conference, Seoul, South Korea, December 2-4, 2020, Proceedings, vol. 12593, pp. 43–57. Springer (2020)

  13. Cui, Jingyi, Guo, Jiansheng, Ding, Shuzhen: Applications of Simon’s algorithm in quantum attacks on Feistel variants. Quantum Inf. Process. 20(3), 117 (2021)

    Article  ADS  MathSciNet  Google Scholar 

  14. Kaplan, Marc, Leurent, Gaëtan., Leverrier, Anthony, Naya-Plasencia, María: Quantum differential and linear cryptanalysis. IACR Trans. Symmetric Cryptol. 2016(1), 71–94 (2016)

    Article  Google Scholar 

  15. Kaplan, M.: Quantum attacks against iterated block ciphers (2014) CoRR, arXiv:1410.1434

  16. Hosoyamada, A., Sasaki, Y.: Cryptanalysis against symmetric-key schemes with online classical queries and offline quantum computations. In Smart, N.P. (ed.), Topics in Cryptology—CT-RSA 2018—The Cryptographers’ Track at the RSA Conference 2018, San Francisco, CA, USA, April 16-20, 2018, Proceedings, vol. 10808, pp. 198–218. Springer (2018)

  17. Hosoyamada, A., Sasaki, Y.: Quantum demiric-selçuk meet-in-the-middle attacks: applications to 6-round generic feistel constructions. In Catalano, D., De Prisco, R. (ed.), Security and Cryptography for Networks—11th International Conference, SCN 2018, Amalfi, Italy, September 5–7, 2018, Proceedings, vol. 11035, pp. 386–403. Springer (2018)

  18. Canteaut, Anne, Duval, Sébastien., Leurent, Gaëtan., Naya-Plasencia, María, Perrin, Léo., Pornin, Thomas, Schrottenloher, André: Saturnin: a suite of lightweight symmetric algorithms for post-quantum security. IACR Trans. Symmetric Cryptol. 2020(S1), 160–207 (2020)

    Article  Google Scholar 

  19. Bonnetain, X.: Quantum key-recovery on full AEZ. In Adams, C., Camenisch, J. (eds.), Selected Areas in Cryptography—SAC 2017—24th International Conference, Ottawa, ON, Canada, August 16–18, 2017, Revised Selected Papers, vol. 10719, pp. 394–406. Springer (2017)

  20. Zhandry, Mark: How to construct quantum random functions. J. ACM 68(5), 33:1-33:43 (2021)

    Article  MathSciNet  Google Scholar 

  21. Boneh, D., Dagdelen, Ö., Fischlin, M., Lehmann, A., Schaffner, C., Zhandry, M.: Random oracles in a quantum world. In Lee, D.H., Wang, X. (eds.), Advances in Cryptology—ASIACRYPT 2011—17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4–8, 2011. Proceedings, vol. 7073, pp. 41–69. Springer (2011)

  22. Kaplan, M., Leurent, G., Leverrier, A., Naya-Plasencia, M.: Breaking symmetric cryptosystems using quantum period finding. In Robshaw, M., Katz, J. (ed.), Advances in Cryptology—CRYPTO 2016—36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14–18, 2016, Proceedings, Part II, vol. 9815, pp. 207–237. Springer (2016)

  23. Demirci, H., Selçuk, A.A.: A meet-in-the-middle attack on 8-round AES. In Nyberg, K. (ed.), Fast Software Encryption, 15th International Workshop, FSE 2008, Lausanne, Switzerland, February 10–13, 2008, Revised Selected Papers, vol. 5086, pp. 116–126. Springer (2008)

  24. Derbez, P., Fouque, P.-A., Jean, J.: Improved key recovery attacks on reduced-round AES in the single-key setting. In Johansson, T., Nguyen, P.Q. (eds.), Advances in Cryptology—EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26–30, 2013. Proceedings, vol. 7881, pp. 371–387. Springer (2013)

  25. Guo, J., Jean, J., Nikolic, I., Sasaki, Y.: Meet-in-the-middle attacks on generic Feistel constructions. In Palash Sarkar and Tetsu Iwata, editors, Advances in Cryptology—ASIACRYPT 2014—20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7–11, 2014. Proceedings, Part I, vol. 8873, pp. 458–477. Springer (2014)

  26. Guo, Jian, Jean, Jérémy., Nikolic, Ivica, Sasaki, Yu.: Meet-in-the-middle attacks on classes of contracting and expanding Feistel constructions. IACR Trans. Symmetric Cryptol. 2016(2), 307–337 (2016)

    Google Scholar 

  27. Nachef, V., Patarin, J., Treger, J.: Generic attacks on misty schemes -5 rounds is not enough-. IACR Cryptol. ePrint Arch., p. 405 (2009)

  28. Grover, L.K.: A fast quantum mechanical algorithm for database search. In Miller, G.L. (ed.), Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22–24, 1996, pp. 212–219. ACM, (1996)

  29. Brassard, G., Høyer, P., Tapp, A.: Quantum algorithm for the collision problem. In Encyclopedia of Algorithms (1997)

  30. Buhrman, H., Dürr, C., Heiligman, M., Høyer, P., Magniez, F., Santha, M., de Wolf, R.: Quantum algorithms for element distinctness. In Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18–21, 2001, pp. 131–137. IEEE Computer Society (2001)

  31. Xu, Y., Yuan, Z.: Quantum meet-in-the-middle attack on 7-round feistel construction (2021) CoRR, arXiv:2107.12724

  32. Ambainis, Andris: Quantum walk algorithm for element distinctness. SIAM J. Comput. 37(1), 210–239 (2007)

    Article  MathSciNet  Google Scholar 

  33. Schrottenloher, A.: Improved quantum algorithms for the k-xor problem. In Al-Tawy, R., Hülsing, A. (eds.), Selected Areas in Cryptography—28th International Conference, SAC 2021, Virtual Event, September 29–October 1, 2021, Revised Selected Papers, vol. 13203, pp. 311–331. Springer (2021)

  34. Guo, J., Sasaki, Y., Wang, L., Wang, M., Wen, L.: Equivalent key recovery attacks against HMAC and NMAC with whirlpool reduced to 7 rounds. IACR Cryptol. ePrint Arch., p. 75, (2015)

Download references

Author information

Authors and Affiliations

  1. College of Computer and Data Science, Fuzhou University, Fuzhou, 350108, China

    Jian Zou, Kairong Huang, Min Zhu, Hongkai Zou & Qian Liu

  2. Key Lab of Information Security of Network Systems, Fuzhou University, Fuzhou, 350108, China

    Jian Zou, Kairong Huang, Min Zhu, Hongkai Zou & Qian Liu

  3. School of Information Sciences and Technology, Huizhou University, Huizhou, China

    Yiyuan Luo

Authors
  1. Jian Zou
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kairong Huang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Min Zhu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Hongkai Zou
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Yiyuan Luo
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Qian Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

Conceptualization and methodology were done by JZ, KH, and MZ; validation, investigation, and formal analysis were done by JZ, MZ, HZ, and YL; writing—original draft preparation was done by MZ and KH; writing—review and editing was done by HZ, KH, and QL. All authors have read and agreed to the published version of the manuscript.

Corresponding author

Correspondence to Jian Zou.

Ethics declarations

Conflict of interest

The authors declare no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix

Appendix

See Figs. 11, 12, 13.

Fig. 11
figure 11

13-round distinguisher on the contracting Feistel

Full size image
Fig. 12
figure 12

10-round distinguisher on the expanding Feistel-F

Full size image
Fig. 13
figure 13

13-round distinguisher on the expanding Feistel-FL

Full size image

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zou, J., Huang, K., Zhu, M. et al. New Demiric–Selçuk meet-in-the-middle attacks on Misty and Feistel schemes. Quantum Inf Process 23, 136 (2024). https://doi.org/10.1007/s11128-024-04349-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s11128-024-04349-2

Keywords

Search

Navigation