Salvaging Merkle-Damgard for Practical Applications

Yevgeniy Dodis, Thomas Ristenpart and Thomas Shrimpton

Many cryptographic applications of hash functions are analyzed in the random oracle model. Unfortunately, most concrete hash functions, including the SHA family, use the iterative (strengthened) Merkle-Damgard transform applied to a corresponding compression function. Moreover, it is well known that the resulting ``structured'' hash function cannot be generically used as a random oracle, even if the compression function is assumed to be ideal. This leaves a large disconnect between theory and practice: although no attack is known for many concrete applications utilizing existing (Merkle-Damgard-based) hash functions, there is no security guarantee either, even by idealizing the compression function. Motivated by this question, we initiate a rigorous and modular study of finding kinds of (still idealized) hash functions which would be (a) elegant and interesting in their own right; (b) still enough to argue security of important applications; and (c) provably instantiable by the (strengthened) Merkle-Damgard transform, applied to a "strong enough" compression function. We develop two such notions which we believe are natural and interesting in their own right: preimage awareness and being indifferentiable from a public-use random oracle.

A preliminary version of this paper appears in Advances in Cryptology -- Eurocrypt '09, Lecture Notes in Computer Science Vol. 5479, A. Joux ed., Springer-Verlag, 2009.

Full Version:
Full version of the paper is available as a pdf.

List of Updates:
June 2010 - Fixed a bug in proof of Thm. 4.1 in full version of paper.
April 2009 - Put up full version of paper.