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 functionsrandom oraclesindifferentiability 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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2009/177}},
      url = {https://eprint.iacr.org/2009/177}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.