You are looking at a specific version 20110308:143653 of this paper. See the latest version.

Paper 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.

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

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Hash FunctionPreimage ResistanceBlock CipherBeyond Birthday BoundFoundations
Contact author(s)
armknecht @ informatik uni-mannheim de
History
2011-03-08: revised
2010-10-12: received
See all versions
Short URL
https://ia.cr/2010/519
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.