Paper 1997/009 Original: eprint.iacr.org/1997/009 ↗
Collision-Resistant Hashing: Towards Making UOWHFs Practical
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)
PDF- Publication info
- Preprint.
- History
- 1997-07-11: last updated
- 1997-07-11: published
- Short URL
- https://ia.cr/1997/009
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/1997/009}
}