Cryptology ePrint Archive: Report 2010/519

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

Matthias Krause and 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.

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 format(s): PDF | BibTeX Citation

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

Version: 20110308:143653 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]