Abstract
Recent attacks on the cryptographic hash functions MD4 and MD5 make it clear that (strong) collision-resistance is a hard-toachieve goal. We look towards a weaker notion, the universal one-way hash functions (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-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.
Chapter PDF
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
M. Bellare, R. Canetti and H. Krawczyk, Keying hash functions for message authentication. Advances in Cryptology — Crypto 96 Proceedings, Lecture Notes in Computer Science Vol. 1109, N. Koblitz ed., Springer-Verlag, 1996.
M. Bellare, R. Canetti and H. Krawczyk, Pseudorandom functions revisited: the cascade construction and its concrete security. Proceedings of the 37th Symposium on Foundations of Computer Science, IEEE, 1996.
M. Bellare, J. Kilian and P. Rogaway, The security of cipher block chaining. Advances in Cryptology — Crypto 94 Proceedings, Lecture Notes in Computer Science Vol. 839, Y. Desmedt ed., Springer-Verlag, 1994.
M. Bellare and P. Rogaway, Collision-Resistant Hashing: Towards Making UOWHFs Practical. Full version of this paper, available via http://www-cse.ucsd.edu/users/mihir.
T. Cormen, C. Leiserson and R. Rivest, Introduction to Algorithms. McGraw-Hill, 1992.
I. Damgård, Collision Free Hash Functions and Public Key Signature Schemes. Advances in Cryptology — Eurocrypt 87 Proceedings, Lecture Notes in Computer Science Vol. 304, D. Chaum ed., Springer-Verlag, 1987.
I. Damgård, A Design Principle for Hash Functions. Advances in Cryptology — Crypto 89 Proceedings, Lecture Notes in Computer Science Vol. 435, G. Brassard ed., Springer-Verlag, 1989.
B. den Boer and A. Bosselaers, An attack on the last two rounds of MD4. Advances in Cryptology — Crypto 91 Proceedings, Lecture Notes in Computer Science Vol. 576, J. Feigenbaum ed., Springer-Verlag, 1991.
B. den Boer and A. Bosselaers, Collisions for the compression function of MD5. Advances in Cryptology — Eurocrypt 93 Proceedings, Lecture Notes in Computer Science Vol. 765, T. Helleseth ed., Springer-Verlag, 1993.
H. Dobbertin, Cryptanalysis of MD4. Fast Software Encryption—Cambridge Workshop, Lecture Notes in Computer Science, vol. 1039, D. Gollman, ed., Springer-Verlag, 1996.
H. Dobbertin, Cryptanalysis of MD5. Rump Session of Eurocrypt 96, May 1996, http://www.iacr.org/conferences/ec96/rump/index.html.
H. Dobbertin, A. Bosselaers and B. Preneel, RIPEMD-160: A strengthened version of RIPEMD, Fast Software Encryption, Lecture Notes in Computer Science 1039, D. Gollmann, ed., Springer-Verlag, 1996.
R. Impagliazzo and M. Naor, Efficient cryptographic schemes provably as secure as subset sum. Journal of Cryptology, Vol. 9, No. 4, Autumn 1996.
B. Kaliski and M. Robshaw, Message Authentication with MD5. RSA Labs' CryptoBytes, Vol. 1 No. 1, Spring 1995.
R. Merkle, One way hash functions and DES. Advances in Cryptology — Crypto 89 Proceedings, Lecture Notes in Computer Science Vol. 435, G. Brassard ed., Springer-Verlag, 1989
M. Naor and M. Yung, Universal one-way hash functions and their cryptographic applications. Proceedings of the 21st Annual Symposium on Theory of Computing, ACM, 1989.
National Institute of Standards, FIPS 180–1, Secure hash standard. April 1995.
B. Preneel and P. van Oorschot, MD-x MAC and building fast MACs from hash functions. Advances in Cryptology — Crypto 95 Proceedings, Lecture Notes in Computer Science Vol. 963, D. Coppersmith ed., Springer-Verlag, 1995.
RIPE Consortium, Ripe Integrity primitives —Final report of RACE integrity primitives evaluation (R1040). Lecture Notes in Computer Science, vol. 1007, Springer-Verlag, 1995.
R. Rivest, The MD4 message-digest algorithm, Advances in Cryptology — Crypto 90 Proceedings, Lecture Notes in Computer Science Vol. 537, A. J. Menezes and S. Vanstone ed., Springer-Verlag, 1990, pp. 303–311. Also IETF RFC 1320 (April 1992).
R. Rivest, The MD5 message-digest algorithm. IETF RFC 1321 (April 1992).
J. Rompel, One-way functions are necessary and sufficient for digital signatures. Proceedings of the 22nd Annual Symposium on Theory of Computing, ACM, 1990.
G. Tsudik, Message authentication with one-way hash functions, Proceedings of Infocom 92, IEEE Press, 1992.
S. Vaudenay, On the need for multipermutations: cryptanalysis of MD4 and SAFER. Fast Software Encryption —Leuven Workshop, Lecture Notes in Computer Science, vol. 1008, Springer-Verlag, 1995, 286–297.
Wegman and Carter, New hash functions and their use in authentication and set equality, Journal of Computer and System Sciences, Vol. 22, 1981, pp. 265–279.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag
About this paper
Cite this paper
Bellare, M., Rogaway, P. (1997). Collision-Resistant hashing: Towards making UOWHFs practical. In: Kaliski, B.S. (eds) Advances in Cryptology — CRYPTO '97. CRYPTO 1997. Lecture Notes in Computer Science, vol 1294. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0052256
Download citation
DOI: https://doi.org/10.1007/BFb0052256
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63384-6
Online ISBN: 978-3-540-69528-8
eBook Packages: Springer Book Archive