International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Analysis of RIPEMD-160: New Collision Attacks and Finding Characteristics with MILP

Authors:
Fukang Liu , Tokyo Institute of Technology; University of Hyogo
Gaoli Wang , East China Normal University; State Key Laboratory of Cryptology
Santanu Sarkar , Indian Institute of Technology Madras
Ravi Anand , University of Hyogo
Willi Meier , FHNW
Yingxin Li , East China Normal University
Takanori Isobe , University of Hyogo; NICT
Download:
DOI: 10.1007/978-3-031-30634-1_7 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2023
Abstract: The hash function RIPEMD-160 is an ISO/IEC standard and is being used to generate the bitcoin address together with SHA-256. Despite the fact that many hash functions in the MD-SHA hash family have been broken, RIPEMD-160 remains secure and the best collision attack could only reach up to 34 out of 80 rounds, which was published at CRYPTO 2019. In this paper, we propose a new collision attack on RIPEMD-160 that can reach up to 36 rounds with time complexity $2^{64.5}$. This new attack is facilitated by a new strategy to choose the message differences and new techniques to simultaneously handle the differential conditions on both branches. Moreover, different from all the previous work on RIPEMD-160, we utilize a MILP-based method to search for differential characteristics, where we construct a model to accurately describe the signed difference transitions through its round function. As far as we know, this is the first model targeting the signed difference transitions for the MD-SHA hash family. Indeed, we are more motivated to design this model by the fact that many automatic tools to search for such differential characteristics are not publicly available and implementing them from scratch is too time-consuming and difficult. Hence, we expect that this can be an alternative easy tool for future research, which only requires to write down some simple linear inequalities.
BibTeX
@inproceedings{eurocrypt-2023-32824,
  title={Analysis of RIPEMD-160: New Collision Attacks and Finding Characteristics with MILP},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-30634-1_7},
  author={Fukang Liu and Gaoli Wang and Santanu Sarkar and Ravi Anand and Willi Meier and Yingxin Li and Takanori Isobe},
  year=2023
}