Practical Preimage Attacks on 3-Round Keccak-256 and 4-Round Keccak[r=640, c=160]

Xiaoen Lin; Le He; Hongbo Yu

Paper 2023/101

Practical Preimage Attacks on 3-Round Keccak-256 and 4-Round Keccak[r=640, c=160]

Xiaoen Lin, Department of Computer Science and Technology, Tsinghua University, Beijing, 100084, People’s Republic of China

Le He

, School of Cyber Engineering, Xidian University, Xi’an, 710126, People’s Republic of China

Hongbo Yu, Department of Computer Science and Technology, Tsinghua University, Beijing, 100084, People’s Republic of China, Zhongguancun Laboratory, Beijing, People’s Republic of China, State Key Laboratory of Cryptography and Digital Economy Security, Tsinghua University, Beijing, 100084, People’s Republic of China

Abstract

Recently, linear structures and algebraic attacks have been widely used in preimage attacks on round-reduced Keccak. Inherited by pioneers' work, we make some improvements for 3-round Keccak-256 and 4-round Keccak[r=640, c=160]. For 3-round Keccak-256, we introduce a three-stage model to deal with the unsatisfied restrictions while bringing more degrees of freedom at the same time. Besides, we show that guessing values for different variables will result in different complexity of solving time. With these techniques, the guessing times can be decreased to 2^{52}, and the solving time for each guess can be decreased to around 2^{5.2} 3-round Keccak calls. As a result, the complexity of finding a preimage for 3-round Keccak-256 can be decreased to around 2^{57.2}. For 4-round Keccak[r=640, c=160], an instance of the Crunchy Contest, we use some techniques to save degrees of freedom and make better linearization. Based on these techniques, we build an MILP model and obtain an attack with better complexity of around 2^{60.9}. The results of 3-round Keccak-256 and 4-round Keccak[r=640, c=160] are verified with real examples.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Published by the IACR in TOSC 2025
Keywords: Keccak SHA-3 Preimage attack Linear structure
Contact author(s): lxe21 @ mails tsinghua edu cn
hele @ xidian edu cn
yuhongbo @ mail tsinghua edu cn
History: 2025-03-08: revised; 2023-01-27: received; See all versions
Short URL: https://ia.cr/2023/101
License: CC BY

BibTeX

@misc{cryptoeprint:2023/101,
      author = {Xiaoen Lin and Le He and Hongbo Yu},
      title = {Practical Preimage Attacks on 3-Round Keccak-256 and 4-Round Keccak[r=640, c=160]},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/101},
      year = {2023},
      url = {https://eprint.iacr.org/2023/101}
}