Collision-Resistant Hashing: Towards Making UOWHFs Practical

Mihir Bellare; Phillip Rogaway

Paper 1997/009

Collision-Resistant Hashing: Towards Making UOWHFs Practical

Mihir Bellare and Phillip Rogaway

Abstract

Recent attacks on the cryptographic hash functions MD4 and MD5 make it clear that (strong) collision-resistance is a hard-to-achieve goal. We look towards a weaker notion, the <i>universal one-way hash functions</i> (UOWHFs) of Naor and Yung, and investigate their practical potential. The goal is to build UOWHFs not based on number theoretic assumptions, but from the primitives underlying current cryptographic hash functions like MD5 and SHA. Pursuing this goal leads us to new questions. The main one is how to extend a compression function to a full-fledged hash function in this new setting. We show that the classic Merkle-Damgard method used in the standard setting fails for these weaker kinds of hash functions, and we present some new methods that work. Our main construction is the "XOR tree." We also consider the problem of input length-variability and present a general solution.

Metadata

Available format(s): PS
Publication info: Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Keywords: Hashing collision-resistance MD5 SHA trees.
Contact author(s): mihir @ cs ucsd edu
History: 1997-07-11: received
Short URL: https://ia.cr/1997/009
License: CC BY

BibTeX

@misc{cryptoeprint:1997/009,
      author = {Mihir Bellare and Phillip Rogaway},
      title = {Collision-Resistant Hashing: Towards Making UOWHFs Practical},
      howpublished = {Cryptology ePrint Archive, Paper 1997/009},
      year = {1997},
      note = {\url{https://eprint.iacr.org/1997/009}},
      url = {https://eprint.iacr.org/1997/009}
}