Paper 2017/800

Collisions and Semi-Free-Start Collisions for Round-Reduced RIPEMD-160

Fukang Liu, Florian Mendel, and Gaoli Wang

Abstract

In this paper, we propose an improved cryptanalysis of the double-branch hash function RIPEMD-160 standardized by ISO/IEC. Firstly, we show how to theoretically calculate the step differential probability of RIPEMD-160, which was stated as an open problem by Mendel $et$ $al.$ at ASIACRYPT 2013. Secondly, based on the method proposed by Mendel $et$ $al.$ to automatically find a differential path of RIPEMD-160, we construct a 30-step differential path where the left branch is sparse and the right branch is controlled as sparse as possible. To ensure the message modification techniques can be applied to RIPEMD-160, some extra bit conditions should be pre-deduced and well controlled. These extra bit conditions are used to ensure that the modular difference can be correctly propagated. This way, we can find a collision of 30-step RIPEMD-160 with complexity $2^{70}$. This is the first collision attack on round-reduced RIPEMD-160. Moreover, by a different choice of the message words to merge two branches and adding some conditions to the starting point, the semi-free-start collision attack on the first 36-step RIPEMD-160 from ASIACRYPT 2013 can be improved. However, the previous way to pre-compute the equation $T^{\lll S_0}\boxplus C_0=(T\boxplus C_1)^{\lll S_1}$ costs too much. To overcome this obstacle, we are inspired by Daum's $et~al$. work on MD5 and describe a method to reduce the time complexity and memory complexity to pre-compute that equation. Combining all these techniques, the time complexity of the semi-free-start collision attack on the first 36-step RIPEMD-160 can be reduced by a factor of $2^{15.3}$ to $2^{55.1}$.

Note: 1. We negelect three uncontrolled bit conditions on the right branch when mounting collision attack by mistake. Therefore, the time complexity shoule become $2^{70}$. 2. We also correct the probability that $\Delta X_4$ = 0 for the semi-free-start collision attack. But this will not influence the original cpmlexity or probability of the 36-step semi-free-start collision attack.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in ASIACRYPT 2017
Keywords
RIPEMD-160semi-free-start collisioncollisionhash functioncompression function
Contact author(s)
1152049805 @ qq com
History
2018-05-27: last of 2 revisions
2017-08-28: received
See all versions
Short URL
https://ia.cr/2017/800
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/800,
      author = {Fukang Liu and Florian Mendel and Gaoli Wang},
      title = {Collisions and Semi-Free-Start Collisions for Round-Reduced RIPEMD-160},
      howpublished = {Cryptology ePrint Archive, Paper 2017/800},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/800}},
      url = {https://eprint.iacr.org/2017/800}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.