Paper 2023/518

Weak-Diffusion Structure: Meet-in-the-Middle Attacks on Sponge-based Hashing Revisited

Lingyue Qin, Tsinghua University
Boxin Zhao, Zhongguancun Laboratory
Jialiang Hua, Tsinghua University
Xiaoyang Dong, Tsinghua University
Xiaoyun Wang, Tsinghua University
Abstract

Besides the U.S. NIST standard SHA-3(Keccak), another sponge-based primitive Ascon was selected as the NIST standard for lightweight applications, recently. Exploring the security against attacks on the sponge-based hash functions is very important. At EUROCRYPT 2023, Qin et al. introduced the MitM preimage attack framework and the automatic tools for Keccak, Ascon, and Xoodyak. In this paper, we extend Qin et al.'s MitM attack framework into collision attack and also develop various techniques to improve the automatic tools for both preimage and collision attacks. We introduce a novel initial structure called weak-diffusion structure that enjoys many more degrees of freedom to build the blue/red neutral sets than Qin et al.'s. In addition, a more flexible condition scheme is introduced to reduce the diffusion of variables. To further accelerate the solving of automatic model, we propose a heuristic two-stage searching strategy, which first finds many blue neutral sets with naturally weak-diffusion properties, and then solves different automatic models with different blue neutral sets prefixed. Also symmetry property of Keccak is applied to speed up the search. At last, we introduce the first collision attack on 4-round Keccak-512. Besides, the first MitM-based preimage attack on 4-round Keccak-384 is found that outperforms all previous attacks, while Qin et al. only found attack on Keccak-512. Moreover, we find collision attacks on reduced Xoodyak and Ascon with 1-2 rounds improvements than before. The complexities of preimage attacks on reduced Xoodyak and Ascon are also improved.

Metadata
Available format(s)
-- withdrawn --
Category
Secret-key cryptography
Publication info
Preprint.
Keywords
KeccakMitMAutomatic ToolAsconXoodyak
Contact author(s)
qinly @ tsinghua edu cn
zhaobx @ mail zgclab edu cn
huajl18 @ mails tsinghua edu cn
xiaoyangdong @ tsinghua edu cn
xiaoyunwang @ tsinghua edu cn
History
2024-01-18: withdrawn
2023-04-11: received
See all versions
Short URL
https://ia.cr/2023/518
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.