Paper 2018/652

Efficient Collision Attack Frameworks for RIPEMD-160

Fukang Liu, Christoph Dobraunig, Florian Mendel, Takanori Isobe, Gaoli Wang, and Zhenfu Cao

Abstract

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.

Note: This is the CRYPTO 2019 version.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published by the IACR in CRYPTO 2019
Keywords
hash functionRIPEMD-160start-from-the-middlecollision attackcollision
Contact author(s)
liufukangs @ 163 com
cdobraunig @ cs ru nl
florian mendel @ gmail com
History
2019-05-28: last of 9 revisions
2018-07-06: received
See all versions
Short URL
https://ia.cr/2018/652
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/652,
      author = {Fukang Liu and Christoph Dobraunig and Florian Mendel and Takanori Isobe and Gaoli Wang and Zhenfu Cao},
      title = {Efficient Collision Attack Frameworks for RIPEMD-160},
      howpublished = {Cryptology ePrint Archive, Paper 2018/652},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/652}},
      url = {https://eprint.iacr.org/2018/652}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.