Paper 2021/732 Original: eprint.iacr.org/2021/732 ↗
Preimage Attacks on 4-round Keccak by Solving Multivariate Quadratic Systems
Abstract
In this paper, we present preimage attacks on 4-round Keccak-224/256 as well as 4-round Keccak[$r = 640,c = 160,l = 80$] in the preimage challenges. We revisit the Crossbred algorithm for solving the Boolean multivariate quadratic (MQ) system, propose a new view for the case $D = 2$ and elaborate the computational complexity. The result shows that the Crossbred algorithm outperforms brute force theoretically and practically with feasible memory costs. In our attacks, we construct Boolean MQ systems in order to make full use of variables. With the help of solving MQ systems, we successfully improve preimage attacks on Keccak-224/256 reduced to 4 rounds. Moreover, we implement the preimage attack on 4-round Keccak[$r = 640,c = 160,l = 80$], an instance in the Keccak preimage challenges, and find 78-bit matched \textit{near preimages}. Due to the fundamental rule of solving MQ systems, the complexity elaboration of Crossbred algorithm is of independent interest.
Metadata
- Available format(s)
PDF- Category
- Secret-key cryptography
- Publication info
- Preprint.
- History
- 2021-06-03: last updated
- 2021-06-03: published
- Short URL
- https://ia.cr/2021/732
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2021/732,
author = {Congming Wei and Chenhao Wu and Ximing Fu and Xiaoyang Dong and Kai He and Jue Hong and Xiaoyun Wang},
title = {Preimage Attacks on 4-round Keccak by Solving Multivariate Quadratic Systems},
howpublished = {Cryptology {ePrint} Archive, Paper 2021/732},
year = {2021},
url = {https://eprint.iacr.org/2021/732}
}