Second Preimage Attack on 3-Pass HAVAL and Partial Key-Recovery Attacks on HMAC/NMAC-3-Pass HAVAL

摘要

In 1992, Zheng, Pieprzyk and Seberry proposed a one-way hashing algorithm called HAVAL, which compresses a message of arbitrary length into a digest of 128, 160, 192, 224 or 256 bits. It operates in so called passes where each pass contains 32 steps. The number of passes can be chosen equal to 3, 4 or 5. In this paper, we devise a new differential path of 3-pass HAVAL with probability 2~(-114), which allows us to design a second preimage attack on 3-pass HAVAL and partial key recovery attacks on HMAC/NMAC-3-pass HAVAL. Our partial key-recovery attack works with 2~(122) oracle queries, 5. 2~(32) memory bytes and 2~(96) 3-pass HAVAL computations.