Welcome to the resource topic for 2004/304
Title:
Second Preimages on n-bit Hash Functions for Much Less than 2^n Work
Authors: John Kelsey, 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.
ePrint: https://eprint.iacr.org/2004/304
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .