Salvaging Merkle-Damgard for Practical Applications

Yevgeniy Dodis; Thomas Ristenpart; Thomas Shrimpton

Paper 2009/177

Salvaging Merkle-Damgard for Practical Applications

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.

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

Metadata

Available format(s): PDF
Publication info: Published elsewhere. An initial version of this work appeared at Eurocrypt 2009.
Keywords: hash functions random oracles indifferentiability framework
Contact author(s): tristenp @ cs ucsd edu
History: 2010-06-14: revised; 2009-04-23: received; See all versions
Short URL: https://ia.cr/2009/177
License: CC BY

BibTeX

@misc{cryptoeprint:2009/177,
      author = {Yevgeniy Dodis and Thomas Ristenpart and Thomas Shrimpton},
      title = {Salvaging Merkle-Damgard for Practical Applications},
      howpublished = {Cryptology {ePrint} Archive, Paper 2009/177},
      year = {2009},
      url = {https://eprint.iacr.org/2009/177}
}