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.
Category / Keywords: secret-key cryptography / Hash Function, Preimage Resistance, Block Cipher, Beyond Birthday Bound, Foundations Date: received 8 Oct 2010, last revised 8 Mar 2011 Contact author: armknecht at informatik uni-mannheim de Available formats: PDF | BibTeX Citation Note: First technique has been revised, yielding a better bound. Version: 20110308:143653 (All versions of this report) Discussion forum: Show discussion | Start new discussion