An official website of the United States government
Here’s how you know
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.
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 November 14, 2024)