New Records in Collision Attacks on RIPEMD-160 and SHA-256

Yingxin Li; Fukang Liu; Gaoli Wang

Paper 2023/285

New Records in Collision Attacks on RIPEMD-160 and SHA-256

Yingxin Li, East China Normal University

Fukang Liu, Tokyo Institute of Technology, University of Hyogo

Gaoli Wang, East China Normal University

Abstract

RIPEMD-160 and SHA-256 are two hash functions used to generate the bitcoin address. In particular, RIPEMD-160 is an ISO/IEC standard and SHA-256 has been widely used in the world. Due to their complex designs, the progress to find (semi-free-start) collisions for the two hash functions is slow. Recently at EUROCRYPT 2023, Liu et al. presented the first collision attack on 36 steps of RIPEMD-160 and the first MILP-based method to find collision-generating signed differential characteristics. We continue this line of research and implement the MILP-based method with a SAT/SMT-based method. Furthermore, we observe that the collision attack on RIPEMD-160 can be improved to 40 steps with different message differences. We have practically found a colliding message pair for 40-step RIPEMD-160 in 16 hours with 115 threads. Moreover, we also report the first semi-free-start (SFS) colliding message pair for 39-step SHA-256, which can be found in about 3 hours with 120 threads. These results update the best (SFS) collision attacks on RIPEMD-160 and SHA-256. Especially, we have made some progress on SHA-256 since the last update on (SFS) collision attacks on it at EUROCRYPT 2013, where the first practical SFS collision attack on 38-step SHA-256 was found.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: practical collisions RIPEMD-160 SHA-256 SAT/SMT
Contact author(s): liyx1140 @ 163 com
liufukangs @ gmail com
glwang @ sei ecnu edu cn
History: 2023-02-28: revised; 2023-02-25: received; See all versions
Short URL: https://ia.cr/2023/285
License: CC BY

BibTeX

@misc{cryptoeprint:2023/285,
      author = {Yingxin Li and Fukang Liu and Gaoli Wang},
      title = {New Records in Collision Attacks on RIPEMD-160 and SHA-256},
      howpublished = {Cryptology ePrint Archive, Paper 2023/285},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/285}},
      url = {https://eprint.iacr.org/2023/285}
}