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

Advances in Cryptology: EUROCRYPT 2005 Proceedings, Springer-Verlag, 2005, pp. 474-490.

**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*work. Using SHA1 as an example, our attack can find a second preimage for a

^{n/2+1}+2^{n-k+1}*2*byte message in

^{60}*2*work, rather than the previously expected

^{106}*2*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.

^{160}[full text - PDF (Acrobat)] [full text - Postscript]

Categories: Algorithm Analyses