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.