zbMATH — the first resource for mathematics

Collision-resistant hashing: Towards making UOWHFs practical. (English) Zbl 0882.94015
Kaliski, Burton S. jun. (ed.), Advances in Cryptology - CRYPTO ’97. 17th annual international cryptology conference. Santa Barbara, CA, USA. August 17–21, 1997. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1294, 470-484 (1997).
Summary: 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 universal one-way hash functions (UOWHFs) of M. Naor and M. Yung, 21st ACM STOC (1989) 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-1. 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-Damgård 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.
For the entire collection see [Zbl 0870.00047].

94A60 Cryptography
68P25 Data encryption (aspects in computer science)