Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

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

Published

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)

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 May 23, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created April 30, 2005, Updated October 12, 2021