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

J. Kelsey and B. Schneier

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 2k-message-block message with about k times 2n/2+1+2n-k+1 work. Using SHA1 as an example, our attack can find a second preimage for a 260 byte message in 2106 work, rather than the previously expected 2160 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.

[full text – PDF (Acrobat)] [full text – Postscript]

Categories: Algorithm Analyses

Sidebar photo of Bruce Schneier by Joe MacInnis.