Paper 2010/519

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

Matthias Krause, Frederik Armknecht, and Ewan Fleischmann

Abstract

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.