TY - GEN

T1 - Collisions and Semi-Free-Start Collisions for Round-Reduced RIPEMD-160

AU - Liu, Fukang

AU - Mendel, Florian

AU - Wang, Gaoli

PY - 2017

Y1 - 2017

N2 - In this paper, we propose an improved cryptanalysis of the double-branch hash function RIPEMD-160 standardized by ISO/IEC. Firstly, we show how to theoretically calculate the step differential probability of RIPEMD-160, which was stated as an open problem by Mendel et al. at ASIACRYPT 2013. Secondly, based on the method proposed by Mendel et al. to automatically find a differential path of RIPEMD-160, we construct a 30-step differential path where the left branch is sparse and the right branch is controlled as sparse as possible. To ensure the message modification techniques can be applied to RIPEMD-160, some extra bit conditions should be pre-deduced and well controlled. These extra bit conditions are used to ensure that the modular difference can be correctly propagated. This way, we can find a collision of 30-step RIPEMD-160 with complexity 267. This is the first collision attack on round-reduced RIPEMD-160. Moreover, by a different choice of the message words to merge two branches and adding some conditions to the starting point, the semi-free-start collision attack on the first 36-step RIPEMD-160 from ASIACRYPT 2013 can be improved. However, the previous way to pre-compute the equation T⋘S0⊞C0=(T⊞C1)⋘S1 costs too much. To overcome this obstacle, we are inspired by Daum’s et al. work on MD5 and describe a method to reduce the time complexity and memory complexity to pre-compute that equation. Combining all these techniques, the time complexity of the semi-free-start collision attack on the first 36-step RIPEMD-160 can be reduced by a factor of 215.3 to 255.1.

AB - In this paper, we propose an improved cryptanalysis of the double-branch hash function RIPEMD-160 standardized by ISO/IEC. Firstly, we show how to theoretically calculate the step differential probability of RIPEMD-160, which was stated as an open problem by Mendel et al. at ASIACRYPT 2013. Secondly, based on the method proposed by Mendel et al. to automatically find a differential path of RIPEMD-160, we construct a 30-step differential path where the left branch is sparse and the right branch is controlled as sparse as possible. To ensure the message modification techniques can be applied to RIPEMD-160, some extra bit conditions should be pre-deduced and well controlled. These extra bit conditions are used to ensure that the modular difference can be correctly propagated. This way, we can find a collision of 30-step RIPEMD-160 with complexity 267. This is the first collision attack on round-reduced RIPEMD-160. Moreover, by a different choice of the message words to merge two branches and adding some conditions to the starting point, the semi-free-start collision attack on the first 36-step RIPEMD-160 from ASIACRYPT 2013 can be improved. However, the previous way to pre-compute the equation T⋘S0⊞C0=(T⊞C1)⋘S1 costs too much. To overcome this obstacle, we are inspired by Daum’s et al. work on MD5 and describe a method to reduce the time complexity and memory complexity to pre-compute that equation. Combining all these techniques, the time complexity of the semi-free-start collision attack on the first 36-step RIPEMD-160 can be reduced by a factor of 215.3 to 255.1.

U2 - 10.1007/978-3-319-70694-8_6

DO - 10.1007/978-3-319-70694-8_6

M3 - Conference paper

SN - 978-3-319-70693-1

T3 - Lecture Notes in Computer Science

SP - 158

EP - 186

BT - Advances in Cryptology - ASIACRYPT 2017

A2 - Takagi, T.

A2 - Peyrin, T.

PB - Springer

CY - Cham

T2 - 23rd International Conference on the Theory and Application of Cryptology and Information Security

Y2 - 3 December 2017 through 7 December 2017

ER -