Skip to main content
SpringerLink
Log in

Diving Deep into the Preimage Security of AES-Like Hashing

  • Conference paper
  • First Online:
Advances in Cryptology – EUROCRYPT 2024 (EUROCRYPT 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14651))

  • 718 Accesses

Abstract

Since the seminal works by Sasaki and Aoki, Meet-in-the-Middle (MITM) attacks are recognized as an effective technique for preimage and collision attacks on hash functions. At Eurocrypt 2021, Bao et al. automated MITM attacks on AES-like hashing and improved upon the best manual result. The attack framework has been furnished by subsequent works, yet far from complete. This paper introduces three key contributions dedicated to further generalizing the idea of MITM and refining the automatic model on AES-like hashing. (1) We introduce S-box linearization to MITM pseudo-preimage attacks on AES-like hashing. The technique works well with superposition states to preserve information after S-boxes at affordable cost. (2) We propose distributed initial structures, an extension on the original concept of initial states, that selects initial degrees of freedom in a more versatile manner to enlarge the search space. (3) We exploit the structural similarities between encryption and key schedule in constructions (e.g., Whirlpool and Streebog) to model propagations more accurately and avoid repeated costs. Weaponed with these innovative techniques, we further empower the MITM framework and improve the attack results on AES-like designs for preimage and collision. We obtain the first preimage attacks on 10-round AES-192, 10-round Rijndael-192/256, and 7.75-round Whirlpool, reduced time and/or memory complexities for preimage attacks on 5-, 6-round Whirlpool and 7.5-, 8.5-round Streebog, as well as improved collision attacks on 6- and 6.5-round Whirlpool.

Eik List - visiting independent researcher at Nanyang Technological University, Singapore.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 25167
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 18589
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Notes

  1. 1.

    We ran our MILP models with Gurobi 9.5.2 on a desktop computer with 3.6 GHz Intel Core i9 and 16GB 2667 MHz DDR4.

  2. 2.

    The AddRoundConstant in the key schedule of Whirlpool is the last operation for each round (SB, SR, MC, AC), that is the subkey added into the encryption already involved with the round constant. When using the SIM technique, the corresponding cells related to the XOR compensation here will be canceled to all zero constants.

  3. 3.

    For comparisons, we directly use the calculation method in [8] to provide the time complexity for Whirlpool.

References

  1. Federal Agency on Technical Regulation and Metrology, Information technology - Cryptographic data security - Hash-function, National Standard of the Russian Federation, GOST R 34.11-2012 (2012)

    Google Scholar 

  2. ZigBee Alliance. zigbee Specification Revision 22 1.0. Technical report, ZigBee Alliance, April 19 2017 (2017)

    Google Scholar 

  3. AlTawy, R., Youssef, A.M.: Preimage attacks on reduced-round Stribog. In: Pointcheval, D., Vergnaud, D. (eds.) AFRICACRYPT 2014. LNCS, vol. 8469, pp. 109–125. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-06734-6_7

    Chapter  Google Scholar 

  4. Aoki, K., Sasaki, Yu.: Preimage attacks on one-block MD4, 63-step MD5 and more. In: Avanzi, R.M., Keliher, L., Sica, F. (eds.) SAC 2008. LNCS, vol. 5381, pp. 103–119. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04159-4_7

    Chapter  Google Scholar 

  5. Aoki, K., Sasaki, Yu.: Meet-in-the-middle preimage attacks against reduced SHA-0 and SHA-1. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 70–89. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03356-8_5

    Chapter  Google Scholar 

  6. Bao, Z., Ding, L., Guo, J., Wang, H., Zhang, W.: Improved meet-in-the-middle preimage attacks against AES hashing modes. IACR Trans. Symmetric Cryptol. 2019(4), 318–347 (2019)

    Google Scholar 

  7. Bao, Z., et al.: Automatic search of meet-in-the-middle preimage attacks on AES-like hashing. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12696, pp. 771–804. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77870-5_27

    Chapter  Google Scholar 

  8. Bao, Z., Guo, J., Shi, D., Yi, T.: Superposition meet-in-the-middle attacks: updates on fundamental security of AES-like hashing. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022. LNCS, vol. 13507. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-15802-5_3

    Chapter  Google Scholar 

  9. Barreto, P.S.L.M., Rijmen, V.: The WHIRLPOOL hashing function. In: First open NESSIE Workshop, Leuven, Belgium, vol. 13, p. 14. Citeseer (2000)

    Google Scholar 

  10. Bogdanov, A., Rechberger, C.: A 3-subset meet-in-the-middle attack: cryptanalysis of the lightweight block cipher KTANTAN. In: Biryukov, A., Gong, G., Stinson, D.R. (eds.) SAC 2010. LNCS, vol. 6544, pp. 229–240. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19574-7_16

    Chapter  Google Scholar 

  11. Canteaut, A., Naya-Plasencia, M., Vayssière, B.: Sieve-in-the-middle: improved MITM attacks. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 222–240. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_13

    Chapter  Google Scholar 

  12. Chen, S., Guo, J., List, E., Shi, D., Zhang, T.: Diving deep into the preimage security of aes-like hashing. Cryptology ePrint Archive, Paper 2024/300 (2024). https://eprint.iacr.org/2024/300

  13. Daemen, J., Rijmen, V.: The Design of Rijndael: AES - The Advanced Encryption Standard Information Security and Cryptography. Springer, Heidelberg (2002). https://doi.org/10.1007/978-3-662-04722-4

    Book  Google Scholar 

  14. Diffie, W., Hellman, M.E.: Special feature exhaustive cryptanalysis of the NBS data encryption standard. IEEE Comput. 10(6), 74–84 (1977)

    Article  Google Scholar 

  15. Dolmatov, V., Degtyarev, A.: GOST R 34.11-2012: Hash Function. RFC 6986, August 2013 (2013)

    Google Scholar 

  16. Dong, X., Hua, J., Sun, S., Li, Z., Wang, X., Hu, L.: Meet-in-the-middle attacks revisited: key-recovery, collision, and preimage attacks. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12827, pp. 278–308. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84252-9_10

    Chapter  Google Scholar 

  17. Fuhr, T., Minaud, B.: Match box meet-in-the-middle attack against KATAN. In: Cid, C., Rechberger, C. (eds.) FSE 2014. LNCS, vol. 8540, pp. 61–81. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46706-0_4

    Chapter  Google Scholar 

  18. Gilbert, H., Peyrin, T.: Super-Sbox cryptanalysis: improved attacks for AES-like permutations. In: FSE, pp. 365–383 (2010)

    Google Scholar 

  19. Guo, J., Ling, S., Rechberger, C., Wang, H.: Advanced meet-in-the-middle preimage attacks: first results on full tiger, and improved results on MD4 and SHA-2. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 56–75. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17373-8_4

    Chapter  Google Scholar 

  20. Hosoyamada, A., Sasaki, Yu.: Finding hash collisions with quantum computers by using differential trails with smaller probability than birthday bound. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12106, pp. 249–279. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45724-2_9

    Chapter  Google Scholar 

  21. Hou, Q., Dong, X., Qin, L., Zhang, G., Wang, X.: Automated meet-in-the-middle attack goes to feistel. In: Guo, J., Steinfeld, R. (eds.) ASIACRYPT 2023, Part III. LNCS, pp. 370–404. Springer, Cham (2023). https://doi.org/10.1007/978-981-99-8727-6_13

    Chapter  Google Scholar 

  22. Hua, J., Dong, X., Sun, S., Zhang, Z., Lei, H., Wang, X.: Improved MITM cryptanalysis on streebog. IACR Trans. Symmetric Cryptol. 2022(2), 63–91 (2022)

    Article  Google Scholar 

  23. ISO/IEC. ISO/IEC 10118-3: 2004. IT Security techniques - Hash-functions - Part 3: Dedicated hash-functions (2004)

    Google Scholar 

  24. ISO/IEC. ISO/IEC 10118-2: 2010. IT Security techniques - Hash-functions - Part 2: Hash-functions using an n-bit block cipher (2010)

    Google Scholar 

  25. ISO/IEC. ISO/IEC 10118-3: 2018. IT Security techniques - Hash-functions - Part 3: Dedicated hash-functions (2018)

    Google Scholar 

  26. 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, 2012. Revised Selected Papers, pp. 244–263 (2012)

    Google Scholar 

  27. Lamberger, M., Mendel, F., Rechberger, C., Rijmen, V., Schläffer, M.: Rebound distinguishers: results on the full whirlpool compression function. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 126–143. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10366-7_8

    Chapter  Google Scholar 

  28. Lamberger, M., Mendel, F., Schläffer, M., Rechberger, C., Rijmen, V.: The rebound attack and subspace distinguishers: application to whirlpool. J. Cryptol. 28(2), 257–296 (2015)

    Article  MathSciNet  Google Scholar 

  29. Liu, F., Mahzoun, M., Øygarden, M., Meier, W.: Algebraic attacks on RAIN and AIM using equivalent representations. IACR Trans. Symmetric Cryptol. 2023(4), 166–186 (2023)

    Article  Google Scholar 

  30. Ma, B., Li, B., Hao, R., Li, X.: Improved (Pseudo) preimage attacks on reduced-round GOST and Grøstl-256 and studies on several truncation patterns for AES-like compression functions. In: IWSEC, pp. 79–96 (2015)

    Google Scholar 

  31. Mendel, F., Rechberger, C., Schläffer, M., Thomsen, S.S.: The rebound attack: cryptanalysis of reduced whirlpool and grøstl. In: Dunkelman, O. (ed.) FSE 2009. LNCS, vol. 5665, pp. 260–276. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03317-9_16

    Chapter  Google Scholar 

  32. Menezes, A., van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press (1996)

    Google Scholar 

  33. Preneel, B., Govaerts, R., Vandewalle, J.: Hash functions based on block ciphers: a synthetic approach. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 368–378. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48329-2_31

    Chapter  Google Scholar 

  34. Qin, L., Hua, J., Dong, X., Yan, H., Wang, X.: Meet-in-the-middle preimage attacks on sponge-based hashing. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, IV. LNCS, vol. 14007, pp. 158–188. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-30634-1_6

    Chapter  Google Scholar 

  35. Sasaki, Yu.: Meet-in-the-middle preimage attacks on AES hashing modes and an application to whirlpool. In: Joux, A. (ed.) FSE 2011. LNCS, vol. 6733, pp. 378–396. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21702-9_22

    Chapter  Google Scholar 

  36. Sasaki, Yu., Aoki, K.: Preimage Attacks on 3, 4, and 5-Pass HAVAL. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 253–271. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-89255-7_16

    Chapter  Google Scholar 

  37. Sasaki, Yu., Aoki, K.: Finding preimages in full MD5 faster than exhaustive search. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 134–152. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01001-9_8

    Chapter  Google Scholar 

  38. Sasaki, Yu., Wang, L., Wu, S., Wu, W.: Investigating fundamental security requirements on whirlpool: improved preimage and collision attacks. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 562–579. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34961-4_34

    Chapter  Google Scholar 

  39. Schrottenloher, A., Stevens, M.: Simplified MITM modeling for permutations: new (quantum) attacks. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022, Part III. Lecture Notes in Computer Science, vol. 13509, pp. 717–747. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-15982-4_24

    Chapter  Google Scholar 

  40. Schrottenloher, A., Stevens, M.: Simplified modeling of MITM attacks for block ciphers: New (quantum) attacks. IACR Trans. Symmetric Cryptol. 2023(3), 146–183 (2023)

    Article  Google Scholar 

  41. 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.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 158–178. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45611-8_9

    Chapter  Google Scholar 

  42. Zhang, K., Qingju Wang, Y.Y., Guo, C., Cui, H.: Algebraic attacks on round-reduced rain and full AIM-III. In: Guo, J., Steinfeld, R. (eds.) ASIACRYPT 2023, Part III. LNCS, vol. 14440, pp. 285–310. Springer, Singapore (2023). https://doi.org/10.1007/978-981-99-8727-6_10

    Chapter  Google Scholar 

  43. Zhang, T.: Comprehensive preimage security evaluations on rijndael-based hashing. In: Zhou, J., et al. (eds.) ACNS 2023. LNCS, vol. 13907, pp. 23–42. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-41181-6_2

    Chapter  Google Scholar 

Download references

Acknowledgements

We would like to thank all anonymous reviewers for their detailed and valuable comments.

This research is supported by the National Key R &D Program of China (Grants No. 2022YFB2701900), the National Natural Science Foundation of China (Grants No. 62172410), the Youth Innovation Promotion Association of Chinese Academy of Sciences, the National Research Foundation, Singapore and Infocomm Media Development Authority under its Trust Tech Funding Initiative and Strategic Capability Research Centres Funding Initiative, the Ministry of Education in Singapore under Grant RG93/23, and the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – LI 4223/1-1. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not reflect the views of National Research Foundation, Singapore and Infocomm Media Development Authority.

Author information

Authors and Affiliations

  1. Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China

    Danping Shi

  2. School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

    Danping Shi

  3. Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, Singapore

    Jian Guo & Tianyu Zhang

  4. Strategic Centre for Research in Privacy-Preserving Technologies and Systems, Nanyang Technological University, Singapore, Singapore

    Shiyao Chen

  5. Digital Trust Centre, Nanyang Technological University, Singapore, Singapore

    Shiyao Chen

  6. Weimar, Germany

    Eik List

Authors
  1. Shiyao Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jian Guo
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Eik List
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Danping Shi
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Tianyu Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Danping Shi .

Editor information

Editors and Affiliations

  1. Zama, Paris, France

    Marc Joye

  2. Ruhr University Bochum, Bochum, Germany

    Gregor Leander

Rights and permissions

Reprints and permissions

Copyright information

© 2024 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Chen, S., Guo, J., List, E., Shi, D., Zhang, T. (2024). Diving Deep into the Preimage Security of AES-Like Hashing. In: Joye, M., Leander, G. (eds) Advances in Cryptology – EUROCRYPT 2024. EUROCRYPT 2024. Lecture Notes in Computer Science, vol 14651. Springer, Cham. https://doi.org/10.1007/978-3-031-58716-0_14

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-58716-0_14

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-58715-3

  • Online ISBN: 978-3-031-58716-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation