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

Second Preimages on n-bit Hash Functions for Much Less than 2ⁿ 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 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⁶⁰ byte message in 2¹⁰⁶ work, rather than the previously expected 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.

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

Categories: Algorithm Analyses