## CryptoDB

### Paper: Efficient Collision Attack Frameworks for RIPEMD-160

Authors: Fukang Liu Christoph Dobraunig Florian Mendel Takanori Isobe Gaoli Wang Zhenfu Cao DOI: 10.1007/978-3-030-26951-7_5 (login may be required) Search ePrint Search Google RIPEMD-160 is an ISO/IEC standard and has been applied to generate the Bitcoin address with SHA-256. Due to the complex dual-stream structure, the first collision attack on reduced RIPEMD-160 presented by Liu, Mendel and Wang at Asiacrypt 2017 only reaches 30 steps, having a time complexity of $2^{70}$. Apart from that, several semi-free-start collision attacks have been published for reduced RIPEMD-160 with the start-from-the-middle method. Inspired from such start-from-the middle structures, we propose two novel efficient collision attack frameworks for reduced RIPEMD-160 by making full use of the weakness of its message expansion. Those two frameworks are called dense-left-and-sparse-right (DLSR) framework and sparse-left-and-dense-right (SLDR) framework. As it turns out, the DLSR framework is more efficient than SLDR framework since one more step can be fully controlled, though with extra $2^{32}$ memory complexity. To construct the best differential characteristics for the DLSR framework, we carefully build the linearized part of the characteristics and then solve the corresponding nonlinear part using a guess-and-determine approach. Based on the newly discovered differential characteristics, we provide colliding messages pairs for the first practical collision attacks on 30 and 31 (out of 80) steps of RIPEMD-160 with time complexity $2^{35.9}$ and $2^{41.5}$ respectively. In addition, benefiting from the partial calculation, we can attack 33 and 34 (out of 80) steps of RIPEMD-160 with time complexity $2^{67.1}$ and $2^{74.3}$ respectively. When applying the SLDR framework to the differential characteristic used in the Asiacrypt 2017 paper, we significantly improve the time complexity by a factor of $2^{13}$. However, it still cannot compete with the results obtained from the DLSR framework. To the best of our knowledge, these are the best collision attacks on reduced RIPEMD-160 with respect to the number of steps, including the first colliding message pairs for 30 and 31 steps of RIPEMD-160.
##### BibTeX
@article{crypto-2019-29884,
title={Efficient Collision Attack Frameworks for RIPEMD-160},
booktitle={Advances in Cryptology – CRYPTO 2019},
series={Lecture Notes in Computer Science},
publisher={Springer},
volume={11693},
pages={117-149},
doi={10.1007/978-3-030-26951-7_5},
author={Fukang Liu and Christoph Dobraunig and Florian Mendel and Takanori Isobe and Gaoli Wang and Zhenfu Cao},
year=2019
}