This website does readability filtering of other pages. All styles, scripts, forms and ads are stripped. If you want your website excluded or have other feedback, use this form.

Cryptology ePrint Archive: Report 2004/304

Cryptology ePrint Archive: Report 2004/304

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

John Kelsey and Bruce Schneier

Abstract: We provide a second preimage attack on all $n$-bit iterated hash functions with Damgard-Merkle strengthening and $n$-bit itermediate states, allowing a second preimage to be found for a $2^k$-message-block message with about $k \times 2^{n/2+1}+2^{n-k+1}$ work. Using SHA1 as an example, our attack can find a second preimage for a $2^{60}$ byte message in $2^{106}$ work, rather than the previously expected $2^{160}$ work. We also provide slightly cheaper ways to find multicollisions than the method of Joux. 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 also provide algorithms for finding expandable messages for a hash function, using only a small multiple of the work done to find a single collision in the hash function.

Category / Keywords: secret-key cryptography / hash functions

Date: received 14 Nov 2004, last revised 29 Nov 2004

Contact author: john kelsey at nist gov

Available format(s): PDF | BibTeX Citation

Note: Fixed typos

Version: 20041129:150807 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]