Improved Semi-Free-Start Collision Attacks on RIPEMD-160 (Full Version)

Zhuolong Zhang; Muzhou Li; Haoyang Wang; Shiqi Hou; Wei Wang; Meiqin Wang

Paper 2025/1531

Improved Semi-Free-Start Collision Attacks on RIPEMD-160 (Full Version)

Zhuolong Zhang, School of Cyber Science and Technology, Shandong University, Qingdao, China

Muzhou Li, School of Cyber Science and Technology, Shandong University, Qingdao, China

Haoyang Wang, Shanghai Jiao Tong University, Shanghai, China

Shiqi Hou, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS, Beijing, China

Wei Wang, School of Cyber Science and Technology, Shandong University, Qingdao, China

Meiqin Wang, School of Cyber Science and Technology, Shandong University, Qingdao, China

Abstract

As an ISO/IEC standard, RIPEMD-160 has been extensively studied for (Semi-Free-Start) collision attacks. A significant breakthrough was achieved at FSE 2024 with the first 41-, 42-, and 43-step SFS collision attacks, which leveraged an automatic search model (EUROCRYPT 2023) and a message modification strategy (FSE 2020). However, these attacks are limited by reliance on heuristic objective functions and suboptimal message modification techniques. This paper enhances the existing framework from two perspectives. Firstly, we refine the automatic search model by incorporating a holistic objective function that considers all critical probability components, moving beyond simple Hamming weight. Secondly, we introduce two generic techniques to further improve (SFS) collision attacks: the first application of differential clustering and a dedicated message modification strategy. As a result, we present the first valid SFS collision attack on 44-step RIPEMD-160. Additionally, we significantly reduce the time complexities of existing attacks on 41-, 42-, and 43-step variants, making it feasible to find colliding message pairs for 41- and 42-step versions within practical time for the first time.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: A major revision of an IACR publication in ASIACRYPT 2025
Keywords: SFS Collision Attack RIPEMD-160 Signed Difference SAT/SMT
Contact author(s): zhuolongzhang @ mail sdu edu cn
muzhouli @ mail sdu edu cn
haoyang wang @ sjtu edu cn
houshiqi @ iie ac cn
weiwangsdu @ sdu edu cn
mqwang @ sdu edu cn
History: 2025-09-12: revised; 2025-08-27: received; See all versions
Short URL: https://ia.cr/2025/1531
License: CC BY

BibTeX

@misc{cryptoeprint:2025/1531,
      author = {Zhuolong Zhang and Muzhou Li and Haoyang Wang and Shiqi Hou and Wei Wang and Meiqin Wang},
      title = {Improved Semi-Free-Start Collision Attacks on {RIPEMD}-160 (Full Version)},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1531},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1531}
}