International Association for Cryptologic Research

International Association
for Cryptologic Research


Automated Meet-in-the-Middle Attack Goes to Feistel

Qingliang Hou , Shandong University
Lingyue Qin , Tsinghua University
Xiaoyang Dong , Tsinghua University
Guoyan Zhang , Shandong University
Xiaoyun Wang , Tsinghua University
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2023
Abstract: Feistel network and its generalizations (GFN) are another important building blocks for constructing hash functions, e.g., Simpiravb, Areion, and the ISO standard Lesamnta-lw. The Meet-in-the-Middle (MitM) is a general paradigm to build preimage and collision attacks on hash functions, which has been automated in several papers. However, those automatic tools mostly focus on hash function with Substitution–Permutation network (SPN) as building blocks, and only one for Feistel network by Schrottenloher and Stevens (at CRYPTO 2022). In this paper, we introduce a new automatic model for MitM attacks on Feistel networks by generalizing the traditional {\em direct or indirect partial matching strategies} and also Sasaki's multi-round matching strategy. Besides, we find the equivalent transformations of Feistel and GFN can significantly simplify the MILP modellings. Based on our automatic model, we improve the preimage attacks on Feistel-SP-MMO, Simpira-2/-4-DM, Areion-256/-512-DM by 1-2 rounds or significantly reduce the complexities. Furthermore, we fill in the gap left by Schrottenloher and Stevens at CRYPTO 2022 on the large branch ($b>4$) Simpira-$b$'s attack and propose the first 11-round attack on Simpira-6. Besides, we significantly improve the collision attack on the ISO standard hash Lesamnta-lw by increasing the attacked round number from previous 11 to ours 17 rounds.
  title={Automated Meet-in-the-Middle Attack Goes to Feistel},
  author={Qingliang Hou and Lingyue Qin and Xiaoyang Dong and Guoyan Zhang and Xiaoyun Wang},