Multi-collision Attack on the Compression Functions of MD4 and 3-Pass HAVAL

摘要

In this paper, we present a new type of multi-collision attack on the compression functions of both MD4 and 3-Pass HAVAL. Different from Joux's multi-collision attack, our method focuses on the multi-collision of the compression function. For MD4, we utilize two different feasible collision differential paths to find a 4-collision with about 2~(21) MD4 computations. For 3-Pass HAVAL, we can find a 4-collision with complexity about 2~(30) and a 8-near-collision with complexity 2~9.