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: ia.cr/2004/304
[ Cryptology ePrint archive ]