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 $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.

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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2004/304}},
      url = {https://eprint.iacr.org/2004/304}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.