International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
John Kelsey
Bruce Schneier
Download:
URL: http://eprint.iacr.org/2004/304
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2004-12270,
  title={Second Preimages on n-bit Hash Functions for Much Less than 2^n Work},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / hash functions},
  url={http://eprint.iacr.org/2004/304},
  note={ john.kelsey@nist.gov 12751 received 14 Nov 2004, last revised 29 Nov 2004},
  author={John Kelsey and Bruce Schneier},
  year=2004
}