International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Automating Collision Attacks on RIPEMD-160

Authors:
Yingxin Li , Shanghai Key Laboratory of Trustworthy Computing, East China Normal University, Shanghai, China
Fukang Liu , Tokyo Institute of Technology, Tokyo, Japan
Gaoli Wang , Shanghai Key Laboratory of Trustworthy Computing, East China Normal University, Shanghai, China
Download:
DOI: 10.46586/tosc.v2023.i4.112-142
URL: https://tosc.iacr.org/index.php/ToSC/article/view/11282
Search ePrint
Search Google
Abstract: As an ISO/IEC standard, the hash function RIPEMD-160 has been used to generate the Bitcoin address with SHA-256. However, due to the complex doublebranch structure of RIPEMD-160, the best collision attack only reaches 36 out of 80 steps of RIPEMD-160, and the best semi-free-start (SFS) collision attack only reaches 40 steps. To improve the 36-step collision attack proposed at EUROCRYPT 2023, we explored the possibility of using different message differences to increase the number of attacked steps, and we finally identified one choice allowing a 40-step collision attack. To find the corresponding 40-step differential characteristic, we re-implement the MILP-based method to search for signed differential characteristics with SAT/SMT. As a result, we can find a colliding message pair for 40-step RIPEMD-160 in practical time, which significantly improves the best collision attack on RIPEMD-160. For the best SFS collision attack published at ToSC 2019, we observe that the bottleneck is the probability of the right-branch differential characteristics as they are fully uncontrolled in the message modification. To address this issue, we utilize our SAT/SMT-based tool to search for high-probability differential characteristics for the right branch. Consequently, we can mount successful SFS collision attacks on 41, 42 and 43 steps of RIPEMD-160, thus significantly improving the SFS collision attacks. In addition, we also searched for a 44-step differential characteristic, but the differential probability is too low to allow a meaningful SFS collision attack.
BibTeX
@article{tosc-2023-33684,
  title={Automating Collision Attacks on RIPEMD-160},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={023 No. 4},
  pages={112-142},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/11282},
  doi={10.46586/tosc.v2023.i4.112-142},
  author={Yingxin Li and Fukang Liu and Gaoli Wang},
  year=2023
}