Cryptology ePrint Archive: Report 2009/177

Salvaging Merkle-Damgard for Practical Applications

Yevgeniy Dodis and 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.

Category / Keywords: hash functions, random oracles, indifferentiability framework

Publication Info: An initial version of this work appeared at Eurocrypt 2009.

Date: received 22 Apr 2009, last revised 14 Jun 2010

Contact author: tristenp at cs ucsd edu

Available format(s): PDF | BibTeX Citation

Note: New version fixes a bug in the proof of Theorem 4.1

Version: 20100614:211401 (All versions of this report)

Short URL: ia.cr/2009/177

Discussion forum: Show discussion | Start new discussion