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

Qingliang Hou; Xiaoyang Dong; Lingyue Qin; Guoyan Zhang; Xiaoyun Wang

Paper 2023/1359

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

Qingliang Hou

, Shandong University

Xiaoyang Dong, Tsinghua University

Lingyue Qin, Tsinghua University

Guoyan Zhang, Shandong University

Xiaoyun Wang, Tsinghua University

Abstract

Feistel network and its generalizations (GFN) are another important building blocks for constructing hash functions, e.g., Simpira v2, 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 the 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 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 model. 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.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Published by the IACR in ASIACRYPT 2023
Keywords: MitM Automatic Tool Feistel Simpira v2 Lesamnta-LW Areion
Contact author(s): qinglianghou @ mail sdu edu cn
xiaoyangdong @ tsinghua edu cn
qinly @ tsinghua edu cn
guoyanzhang @ sdu edu cn
xiaoyunwang @ tsinghua edu cn
History: 2023-09-14: revised; 2023-09-11: received; See all versions
Short URL: https://ia.cr/2023/1359
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1359,
      author = {Qingliang Hou and Xiaoyang Dong and Lingyue Qin and Guoyan Zhang and Xiaoyun Wang},
      title = {Automated Meet-in-the-Middle Attack Goes to Feistel},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1359},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/1359}},
      url = {https://eprint.iacr.org/2023/1359}
}