Meet-in-the-Middle (Second) Preimage Attacks on Two Double- Branch Hash Functions RIPEMD and RIPEMD-128

摘要

Even though meet-in-the-middle preimage attack framework has been successfully applied to attack most of narrow-pipe hash functions, it seems difficult to apply this framework to attack double-branch hash functions. Only few results have been published on this research. This paper proposes a refined strategy of applying meet-in-the-middle attack framework to double-branch hash functions. The main novelty is a new local-collision approach named one-message-word local collision. We have applied our strategy to two double-branch hash functions RIPEMD and RIPEMD-128, and obtain the following results. 1.On RIPEMD. We find a pseudo-preimage attack on 47-step compression function, where the full version has 48 steps, with a complexity of 2~(119). It can be converted to a second preimage attack on 47-step hash function with a complexity of 2~(124.5). Moreover, we also im-prove previous preimage attacks on (intermediate) 35-step RIPEMD, and reduce the complexity from 2~(113) to 2~(96). 2.On RIPEMD-128. We find a pseudo-preimage on (intermediate) 36-step compression function, where the full version has 64 steps, with a complexity of 2123. It canl be converted to a preimage attack on (intermediate) 36-step hash function with a complexity of 2~(126.5). Both RIPEMD and RIPEMD-128 produce 128-bit digests. Therefore our attacks are faster than the brute-force attack, which means that our attacks break the theoretical security bound of the above step-reduced variants of those two hash functions in the sense of (second) preimage resistance. The maximum number of the attacked steps on both those two hash functions is 35 among previous works based to our best knowledge. Therefore we have successfully increased the number of the attacked steps. We stress that our attacks does not break the security of full-version RIPEMD and RIPEMD-128. But the security mergin of RIPEMD becomes very narrow. On the other hand, RIPEMD-128 still has enough security margin.