Cryptology ePrint Archive: Report 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.
Category / Keywords: Hashing, collision-resistance, MD5, SHA, trees.
Publication Info: Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Date: Received July 11, 1997.
Contact author: mihir at cs ucsd edu
Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]