International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Collision-Resistant Hashing: Towards Making UOWHFs Practical

Authors:
Download:
URL: http://eprint.iacr.org/1997/009
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-1997-11291,
  title={Collision-Resistant Hashing: Towards Making UOWHFs Practical},
  booktitle={IACR Eprint archive},
  keywords={Hashing, collision-resistance, MD5, SHA, trees.},
  url={http://eprint.iacr.org/1997/009},
  note={Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive. mihir@cs.ucsd.edu 10500 Received July 11, 1997.},
  author={},
  year=1997
}