Cryptology ePrint Archive: Report 2019/668

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

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

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 semi-free-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 $2^{55.1}$ time and $2^{32}$ 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 give a practical semi-free-start collision attack on 36 steps of RIPEMD-160 with time complexity $2^{41}$. Additionally, we describe semi-free-start collision attacks on 37, 38 and 40 (out of 80) steps of RIPEMD-160 with time complexity $2^{49}$, $2^{53}$ and $2^{74.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 steps of RIPEMD-160.

Category / Keywords: secret-key cryptography / hash function, RIPEMD-160, freedom degree utilization, semi-free-start collision attack

Date: received 5 Jun 2019

Contact author: liufukangs at 163 com,cdobraunig@cs ru nl,florian mendel@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20190606:113545 (All versions of this report)

Short URL: ia.cr/2019/668


[ Cryptology ePrint archive ]