On hash functions using checksums

摘要

We analyse the security of iterated hash functionsthat compute an input dependent checksum which is pro-cessed as part of the hash computation. We show that a largeclass of such schemes, including those using non-linear oreven one-way checksum functions, is not secure against thesecond preimage attack of Kelsey and Schneier, the herdingattack of Kelsey and Kohno and the multicollision attack ofJoux. Our attacks also apply to a large class of cascaded hashfunctions. Our second preimage attacks on the cascaded hashfunctions improve the results of Joux presented at Crypto'04.We also apply our attacks to the MD2 and GOST hash func-tions. Our second preimage attacks on the MD2 and GOSThash functions improve the previous best known short-cutsecond preimage attacks on these hash functions by factors ofat least 226 and 254, respectively. Our herding and multicolli-sion attacks on the hash functions based on generic checksumfunctions (e.g., one-way) are a special case of the attacks onthe cascaded iterated hash functions previously analysed byDunkelman and Preneel and are not better than their attacks.On hash functions with easily invertible checksums, our mul-ticollision and herding attacks (if the hash value is short as in MD2) are more efficient than those of Dunkelman andPreneel.