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

John Kelsey; Bruce Schneier

Paper 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 byte message in work, rather than the previously expected 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.

Note: Fixed typos

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: hash functions
Contact author(s): john kelsey @ nist gov
History: 2004-11-29: revised; 2004-11-16: received; See all versions
Short URL: https://ia.cr/2004/304
License: CC BY

BibTeX

@misc{cryptoeprint:2004/304,
      author = {John Kelsey and Bruce Schneier},
      title = {Second Preimages on n-bit Hash Functions for Much Less than 2^n Work},
      howpublished = {Cryptology {ePrint} Archive, Paper 2004/304},
      year = {2004},
      url = {https://eprint.iacr.org/2004/304}
}