Meet-in-the-Middle Preimage Attacks on Sponge-based Hashing

Lingyue Qin; Jialiang Hua; Xiaoyang Dong; Hailun Yan; Xiaoyun Wang

Paper 2022/1714

Meet-in-the-Middle Preimage Attacks on Sponge-based Hashing

Lingyue Qin

, Tsinghua University

Jialiang Hua

, Tsinghua University

Xiaoyang Dong

, Tsinghua University

Hailun Yan

, University of Chinese Academy of Sciences

Xiaoyun Wang

, Tsinghua University

Abstract

The Meet-in-the-Middle (MitM) attack has been widely applied to preimage attacks on Merkle-Damg{\aa}rd (MD) hashing. In this paper, we introduce a generic framework of the MitM attack on sponge-based hashing. We find certain bit conditions can significantly reduce the diffusion of the unknown bits and lead to longer MitM characteristics. To find good or optimal configurations of MitM attacks, e.g., the bit conditions, the neutral sets, and the matching points, we introduce the bit-level MILP-based automatic tools on Keccak, Ascon and Xoodyak. To reduce the scale of bit-level models and make them solvable in reasonable time, a series of properties of the targeted hashing are considered in the modelling, such as the linear structure and CP-kernel for Keccak, the Boolean expression of Sbox for Ascon. Finally, we give an improved 4-round preimage attack on Keccak-512/SHA3, and break a nearly 10 years’ cryptanalysis record. We also give the first preimage attacks on 3-/4-round Ascon-XOF and 3-round Xoodyak-XOF.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: A major revision of an IACR publication in EUROCRYPT 2023
Keywords: MitM Automatic Tool Keccak/SHA3 Ascon Xoodyak
Contact author(s): qinly @ tsinghua edu cn
huajl18 @ mails tsinghua edu cn
xiaoyangdong @ tsinghua edu cn
hailun yan @ ucas ac cn
xiaoyunwang @ tsinghua edu cn
History: 2023-02-21: last of 3 revisions; 2022-12-11: received; See all versions
Short URL: https://ia.cr/2022/1714
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1714,
      author = {Lingyue Qin and Jialiang Hua and Xiaoyang Dong and Hailun Yan and Xiaoyun Wang},
      title = {Meet-in-the-Middle Preimage Attacks on Sponge-based Hashing},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1714},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1714}},
      url = {https://eprint.iacr.org/2022/1714}
}