Paper 2021/732

Preimage Attacks on 4-round Keccak by Solving Multivariate Quadratic Systems

Congming Wei, Chenhao Wu, Ximing Fu, Xiaoyang Dong, Kai He, Jue Hong, and Xiaoyun Wang


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.

Available format(s)
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Contact author(s)
wcm16 @ mails tsinghua edu cn
2021-06-03: received
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.