Probabilistic Linearization: Internal Differential Collisions in up to 6 Rounds of SHA-3

Zhongyi Zhang; Chengan Hou; Meicheng Liu

Paper 2024/1136

Probabilistic Linearization: Internal Differential Collisions in up to 6 Rounds of SHA-3

Zhongyi Zhang

, Institute of Information Engineering, Chinese Academy of Sciences, School of Cyber Security, University of Chinese Academy of Sciences

Chengan Hou

, Institute of Information Engineering, Chinese Academy of Sciences, School of Cyber Security, University of Chinese Academy of Sciences

Meicheng Liu

, Institute of Information Engineering, Chinese Academy of Sciences, School of Cyber Security, University of Chinese Academy of Sciences

Abstract

The SHA-3 standard consists of four cryptographic hash functions, called SHA3-224, SHA3-256, SHA3-384 and SHA3-512, and two extendable-output functions (XOFs), called SHAKE128 and SHAKE256. In this paper, we study the collision resistance of the SHA-3 instances. By analyzing the nonlinear layer, we introduce the concept of maximum difference density subspace, and develop a new target internal difference algorithm by probabilistic linearization. We also exploit new strategies for optimizing the internal differential characteristic. Further more, we figure out the expected size of collision subsets in internal differentials, by analyzing the collision probability of the digests rather than the intermediate states input to the last nonlinear layer. These techniques enhance the analysis of internal differentials, leading to the best collision attacks on four round-reduced variants of the SHA-3 instances. In particular, the number of attacked rounds is extended to 5 from 4 for SHA3-384, and to 6 from 5 for SHAKE256.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: A minor revision of an IACR publication in CRYPTO 2024
Keywords: Hash Functions SHA-3 Collision Attacks Internal Differentials Linearization
Contact author(s): liumeicheng @ iie ac cn
History: 2024-07-15: approved; 2024-07-12: received; See all versions
Short URL: https://ia.cr/2024/1136
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1136,
      author = {Zhongyi Zhang and Chengan Hou and Meicheng Liu},
      title = {Probabilistic Linearization: Internal Differential Collisions in up to 6 Rounds of {SHA}-3},
      howpublished = {Cryptology ePrint Archive, Paper 2024/1136},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/1136}},
      url = {https://eprint.iacr.org/2024/1136}
}