Paper 2012/049

2-Dimension Sums: Distinguishers Beyond Three Rounds of RIPEMD-128 and RIPEMD-160

Yu Sasaki and Lei Wang

Abstract

This paper presents differential-based distinguishers against ISO standard hash functions RIPEMD-128 and RIPEMD-160. The compression functions of RIPEMD-128/-160 adopt the double-branch structure, which updates a chaining variable by computing two functions and merging their outputs. Due to the double size of the internal state and difficulties of controlling two functions simultaneously, only few results were published before. In this paper, second-order differential paths are constructed on reduced RIPEMD-128 and -160. This leads to a practical 4-sum attack on 47 steps (out of 64 steps) of RIPEMD-128 and 40 steps (out of 80 steps) of RIPEMD-160. We then extend the distinguished property from the 4-sum to other properties, which we call \emph{a 2-dimension sum} and \emph{a partial 2-dimension sum}. As a result, the practical partial 2-dimension sum is generated on 48 steps of RIPEMD-128 and 42 steps of RIPEMD-160, with a complexity of $2^{35}$ and $2^{36}$, respectively. Theoretically, $2$-dimension sums are generated faster than the exhaustive search up to 52 steps of RIPEMD-128 and 51 steps of RIPEMD-160, with a complexity of $2^{101}$ and $2^{158}$, respectively. The practical attacks are implemented, and examples of generated (partial) 2-dimension sums are presented.

Note: The manuscript was submitted to FSE 2012. No change from the submitted manuscript is made in this version. The review comments will be reflected in the future revised version.