## Salvaging Merkle-Damgard for Practical Applications

**Authors:**

Yevgeniy Dodis,
Thomas Ristenpart and
Thomas Shrimpton

**Abstract:**

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.

**References:**

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.