Paper 2010/519

Preimage Resistance Beyond the Birthday Bound: Double-Length Hashing Revisited

Matthias Krause, Frederik Armknecht, and Ewan Fleischmann


Security proofs are an essential part of modern cryptography. Often the challenge is not to come up with appropriate schemes but rather to technically prove that these satisfy the desired security properties. We provide for the first time techniques for proving asymptotically optimal preimage resistance bounds for block cipher based double length, double call hash functions. More precisely, we consider for some $\keylength>\blocklength$ compression functions $H:\{0,1\}^{\keylength+\blocklength} \rightarrow \{0,1\}^{2\blocklength}$ using two calls to an ideal block cipher with an $\blocklength$-bit block size. Optimally, an adversary trying to find a preimage for $H$ should require $\Omega(2^{2\blocklength})$ queries to the underlying block cipher. As a matter of fact there have been several attempts to prove the preimage resistance of such compression functions, but no proof did go beyond the $\Omega(2^{\blocklength})$ barrier, therefore leaving a huge gap when compared to the optimal bound. In this paper, we introduce two new techniques on how to lift this bound to $\Omega(2^{2\blocklength})$. We demonstrate our new techniques for a simple and natural design of $H$, being the concatenation of two instances of the well-known Davies-Meyer compression function.

Note: First technique has been revised, yielding a better bound.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Hash FunctionPreimage ResistanceBlock CipherBeyond Birthday BoundFoundations
Contact author(s)
armknecht @ informatik uni-mannheim de
2011-03-08: revised
2010-10-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Matthias Krause and Frederik Armknecht and Ewan Fleischmann},
      title = {Preimage Resistance Beyond the Birthday Bound: Double-Length Hashing Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2010/519},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.