Second Primages on n-bit Hash Functions for Much Less than 2n Work

Published

May 1, 2005

Author(s)

John M. Kelsey, B Schneier

Abstract

We expand a previous result of Dean[Dea99] to provide a second preimage attack on all n-bit iterated hash functions with Damgard-Merkle strengthening and n-bit intermediate states, allowing a second preimage to be found for a 2k-message-block message with about k x 2n/2+1 + 2n-k+1 work. Using RIPE-MD160 as an example, our attack can find a second preimage for a 260 byte message in about 2106 work, rather than the previously expected 2160 work. We also provide slightly cheaper ways to find multicollisions than the method of Joux[Jou04]. Both of these results are based on expandable messages--patterns for producing messages of varying length, which all collide on the intermediate hash result immediately after processing the message. We provide an algorithm for finding expandable messages for any n-bit hash function built using the Damgard-Merkle construction, which requires only a small multiple of the work done to find a single collision in the hash function.

Proceedings Title

Proceedings of Eurocrypt 2005

Conference Location

Lecture Notes in Computer Science, USA

Conference Title

Margrethepladsen 1, DK-8000 Aarhus (May 21-28, 2005)

Pub Type

Conferences

Citation

Kelsey, J. and Schneier, B. (2005), Second Primages on n-bit Hash Functions for Much Less than 2n Work, Proceedings of Eurocrypt 2005, Lecture Notes in Computer Science, USA (Accessed October 13, 2025)