International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

New Semi-Free-Start Collision Attack Framework for Reduced RIPEMD-160

Authors:
Fukang Liu , Shanghai Key Laboratory of Trustworthy Computing, East China Normal University, Shanghai, China; University of Hyogo, Hyogo, Japan
Christoph Dobraunig , Radboud University, Nijmegen, The Netherlands
Florian Mendel , Infineon Technologies AG, Neubiberg, Germany
Takanori Isobe , National Institute of Information and Communications Technology, Tokyo, Japan; University of Hyogo, Hyogo, Japan
Gaoli Wang , Shanghai Key Laboratory of Trustworthy Computing, East China Normal University, Shanghai, China
Zhenfu Cao , Shanghai Key Laboratory of Trustworthy Computing, East China Normal University, Shanghai, China; Cyberspace Security Research Center, Peng Cheng Laboratory, Shenzhen, China
Download:
DOI: 10.13154/tosc.v2019.i3.169-192
URL: https://tosc.iacr.org/index.php/ToSC/article/view/8362
Search ePrint
Search Google
Abstract: RIPEMD-160 is a hash function published in 1996, which shares similarities with other hash functions designed in this time-period like MD4, MD5 and SHA-1. However, for RIPEMD-160, no (semi-free-start) collision attacks on the full number of steps are known. Hence, it is still used, e.g., to generate Bitcoin addresses together with SHA-256, and is an ISO/IEC standard. Due to its dual-stream structure, even semifree- start collision attacks starting from the first step only reach 36 steps, which were firstly shown by Mendel et al. at Asiacrypt 2013 and later improved by Liu, Mendel and Wang at Asiacrypt 2017. Both of the attacks are based on a similar freedom degree utilization technique as proposed by Landelle and Peyrin at Eurocrypt 2013. However, the best known semi-free-start collision attack on 36 steps of RIPEMD-160 presented at Asiacrypt 2017 still requires 255.1 time and 232 memory. Consequently, a practical semi-free-start collision attack for the first 36 steps of RIPEMD-160 still requires a significant amount of resources. Considering the structure of these previous semi-free-start collision attacks for 36 steps of RIPEMD-160, it seems hard to extend it to more steps. Thus, we develop a different semi-free-start collision attack framework for reduced RIPEMD-160 by carefully investigating the message expansion of RIPEMD-160. Our new framework has several advantages. First of all, it allows to extend the attacks to more steps. Second, the memory complexity of the attacks is negligible. Hence, we were able to mount semi-free-start collision attacks on 36 and 37 steps of RIPEMD-160 with practical time complexity 241 and 249 respectively. Additionally, we describe semi-free-start collision attacks on 38 and 40 (out of 80) steps of RIPEMD-160 with time complexity 252 and 274.6, respectively. To the best of our knowledge, these are the best semi-free-start collision attacks for RIPEMD-160 starting from the first step with respect to the number of steps, including the first practical colliding message pairs for 36 and 37 steps of RIPEMD-160.
Video from TOSC 2019
BibTeX
@article{tosc-2019-29948,
  title={New Semi-Free-Start Collision Attack Framework for Reduced RIPEMD-160},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2019, Issue 3},
  pages={169-192},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/8362},
  doi={10.13154/tosc.v2019.i3.169-192},
  author={Fukang Liu and Christoph Dobraunig and Florian Mendel and Takanori Isobe and Gaoli Wang and Zhenfu Cao},
  year=2019
}