Refining Probabilistic-Linearization TIDA for 5-Round SHA3-384 Collision Attacks (Full Version)

Luhan Yan; Zhenzhen Bao; Huina Li

Paper 2026/2090

Refining Probabilistic-Linearization TIDA for 5-Round SHA3-384 Collision Attacks (Full Version)

Luhan Yan, Institute for Network Sciences and Cyberspace, Tsinghua University, Beijing, China

Zhenzhen Bao

, Institute for Network Sciences and Cyberspace, Tsinghua University, Beijing, China, Zhongguancun Laboratory, Beijing, China, State Key Laboratory of Cryptography and Digital Economy Security, Tsinghua University, Beijing, 100084, China

Huina Li

, Institute for Network Sciences and Cyberspace, Tsinghua University, Beijing, China

Abstract

Since the SHA-3 family was standardized by NIST in 2015, its collision resistance has been extensively studied. The previous best-known collision attack on 5-round SHA3-384 is based on internal differentials and the probabilistic-linearization variant of two-block Target Internal Differential Algorithm (TIDA). Its connector replaces deterministic affine restrictions that guarantee S-box differential validity by higher-dimensional affine relaxations, reducing the number of linear constraints and preserving more degrees of freedom. The price is that solutions of the linearized system are only probabilistically valid. In particular, once the first message block fixes the inner part variables, the remaining affine solution space cannot be treated as a set of independent trials; only part of its freedom effectively contributes to the connector probability. This paper refines the probabilistic-linearization framework in two ways. We first propose SA-PIDS, a simulated-annealing-based search for affine-subspace assignments, improving the trade-off among capacity constraints, the product-density estimate, and the remaining solution-space dimension. We then give a structural evaluation of the actual connector probability, explaining how the effective remaining freedom in the solution space after fixing the first block could be used and counted. Using the same target internal differential characteristic as the previous 5-round SHA3-384 attack, our refinements reduce the theoretical complexity from $2^{170.73}$ to $2^{164.11}$.

Note: This is the full version of the paper. The camera-ready version will appear in the Proceedings of SAC 2026. Conference website: https://sacworkshop.org/SAC26/

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Published elsewhere. Minor revision. SAC 2026
Keywords: SHA-3 Collision Attacks Internal Differentials TIDA
Contact author(s): ylh23 @ mails tsinghua edu cn
zzbao @ mail tsinghua edu cn
lihuina @ mail tsinghua edu cn
History: 2026-09-22: approved; 2026-09-18: received; See all versions
Short URL: https://ia.cr/2026/2090
License: CC BY

BibTeX

@misc{cryptoeprint:2026/2090,
      author = {Luhan Yan and Zhenzhen Bao and Huina Li},
      title = {Refining Probabilistic-Linearization {TIDA} for 5-Round {SHA3}-384 Collision Attacks (Full Version)},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2090},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2090}
}