Preimage Attacks on up to 5 Rounds of SHA-3 Using Internal Differentials

Zhongyi Zhang; Chengan Hou; Meicheng Liu

Paper 2025/439

Preimage Attacks on up to 5 Rounds of SHA-3 Using Internal Differentials

Zhongyi Zhang

, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, School of Cyber Security, University of Chinese Academy of Sciences

Chengan Hou

, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, School of Cyber Security, University of Chinese Academy of Sciences

Meicheng Liu

, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, School of Cyber Security, University of Chinese Academy of Sciences

Abstract

In this paper, we study preimage resistance of the SHA-3 standard. We propose a squeeze meet-in-the-middle attack as a new preimage attack method for the sponge functions. This attack combines the squeeze attack and meet-in-the-middle attack, and is implemented by internal differentials. We analyze the inverse operation of the SHA-3 round function, and develop a new target internal differential algorithm as well as a linearization technique for the Sbox in the backward phase. In addition, we propose the concept of a value-difference distribution table (VDDT) to optimize the attack complexity. These techniques lead to faster preimage attacks on five (out of six) SHA-3 functions reduced to 4 rounds, and also bring preimage attacks on 5 rounds of four SHA-3 instances. The attack techniques are verified by performing practical preimage attack on a small variant of 4-round Keccak.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: A major revision of an IACR publication in EUROCRYPT 2025
Keywords: Hash Function SHA-3 Preimage Attack Internal Differentials Linearization Meet-in-the-Middle
Contact author(s): zhangzhongyi0714 @ iie ac cn
houchengan @ iie ac cn
liumeicheng @ iie ac cn
History: 2025-03-10: approved; 2025-03-07: received; See all versions
Short URL: https://ia.cr/2025/439
License: CC BY

BibTeX

@misc{cryptoeprint:2025/439,
      author = {Zhongyi Zhang and Chengan Hou and Meicheng Liu},
      title = {Preimage Attacks on up to 5 Rounds of {SHA}-3 Using Internal Differentials},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/439},
      year = {2025},
      url = {https://eprint.iacr.org/2025/439}
}