Improved (semi-free-start/near-) collision and distinguishing attacks on round-reduced RIPEMD-160

Gaoli Wang*, Fukang Liu, Binbin Cui, Florian Mendel, Christoph Erwin Dobraunig

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

In this paper, we present an improved cryptanalysis of the double-branch hash function RIPEMD-160 standardized by ISO/IEC. First, how to theoretically calculate the step differential probability of RIPEMD-160 is solved, which was stated as an open problem by Mendel et al. at ASIACRYPT 2013. Then, we apply the start-from-the-middle framework to a newly discovered 32-step differential path of RIPEMD-160. Compared with the collision attack on 30 steps of RIPEMD-160 at ASIACRYPT 2017, two steps are extended and the time complexity is 2 71.9. We propose a new start-from-the-middle near-collision attack framework, and achieve a near-collision attack on 39 steps of RIPEMD-160 with a time complexity of 2 65. For the semi-free-start collision attack on 36 steps of RIPEMD-160 at ASIACRYPT 2013, by a different choice of the message words to merge two branches, adding some conditions on the starting point as well as solving the equation T⋘S0⊞C0=(T⊞C1)⋘S1 (T is the variable) in an optimized way, the time complexity of this semi-free-start collision attack is reduced by a factor of 2 15.3 to 2 55.1. Finally, we present a 2-dimension sum distinguisher on 52 steps of RIPEMD-160 by using other message differences compared to ACNS 2012, which improves the best 2-dimension sum distinguisher on RIPEMD-160 by one step. Our attack takes into consideration the modular difference of the internal states when doing message modification in the first part of the differential path, and evaluating the probability of the last part of differential paths by experiment.

Original languageEnglish
Pages (from-to)887-930
Number of pages44
JournalDesigns, Codes and Cryptography
Volume88
Issue number5
DOIs
Publication statusPublished - 1 May 2020

Fingerprint

Dive into the research topics of 'Improved (semi-free-start/near-) collision and distinguishing attacks on round-reduced RIPEMD-160'. Together they form a unique fingerprint.

Cite this