Efficient collision attack frameworks for RIPEMD-160

F Liu, C Dobraunig, F Mendel, T Isobe, G Wang… - Annual International …, 2019 - Springer
Annual International Cryptology Conference, 2019Springer
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 …
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 . 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 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 and respectively. In addition, benefiting from the partial calculation, we can attack 33 and 34 (out of 80) steps of RIPEMD-160 with time complexity and 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 . 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.
Springer
Showing the best result for this search. See all results