Abstract
We describe a construction of almost universal hash functions suitable for very fast software implementation and applicable to the hashing of variable size data and fast cryptographic message authentication. Our construction uses fast single precision arithmetic which is increasingly supported by modern processors due to the growing needs for fast arithmetic posed by multimedia applications.
We report on hand-optimized assembly implementations on a 150 MHz PowerPC 604 and a 150 MHz Pentium-Pro, which achieve hashing speeds of 350 to 820 Mbit/sec, depending on the desired level of security (or collision probability), and a rate of more than 1 Gbit/sec on a 200 MHz Pentium-Pro. This represents a significant speed-up over current software implementations of universal hashing and other message authentication techniques (e.g., MD5-based). Moreover, our construction is specifically designed to take advantage of emerging microprocessor technologies (such as Intel’s MMX, 64-bit architectures and others) and then best suited to accommodate the growing performance needs of cryptographic (and other universal hashing) applications.
The construction is based on techniques due to Carter and Wegman for universal hashing using modular multilinear functions that we carefully modify to allow for fast software implementation. We prove the resultant construction to retain the necessary mathematical properties required for its use in hashing and message authentication.
Work was done while the author was visiting the IBM Watson Research Center.
Chapter PDF
Similar content being viewed by others
References
V. Afanassiev, C. Gehrmann and B. Smeets. Fast Message Authentication using Efficient Polynomial Evaluation Appeares in these proceedings.
M. Atici and D. Stinson. Universal Hashing and Multiple Authentication Advances in Cryptology — CRYPTO ’96 Proceedings, Lecture Notes in Computer Science Vol. 1109, N. Koblitz, ed., Springer-Verlag, 1996. pp. 16–30.
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. pp. 1–15.
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. pp. 341–358.
A. Bosselaers, R. Govaerts, J. Vandewalle. Fast Hashing on the Pentium, Advances in Cryptology — CRYPTO ’96 Proceedings Lecture Notes in Computer Science Vol. 1109, N. Koblitz, ed., Springer-Verlag, 1996. pp. 298–312.
G. Brassard. On computationally secure authentication tags requiring short secret shared keys, Advances in Cryptology — CRYPTO ’82 Proceedings, Springer-Verlag, 1983, pp. 79–86.
L. Carter and M. Wegman. Universal Hash Functions. J. of Computer and System Science 18, 1979, pp. 143–154.
L. Carter and M. Wegman. Private Communication.
S. Goldwasser, S. Micali and R. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal of Computing, vol. 17, 2 (April 1988), pp. 281–308.
T. Helleseth and T. Johansson. Universal Hash Functions from Exponential Sums over Finite Fields Advances in Cryptology — CRYPTO ’96 Proceedings, Lecture Notes in Computer Science Vol. 1109, N. Koblitz, ed., Springer-Verlag, 1996. pp. 31–44.
H. Krawczyk. LFSR-based Hashing and Authentication. Proceedings of CRYPTO ’94, Lecture Notes in Computer Science, vol. 839, Springer-Verlag, 1994, pp. 129–139.
H. Krawczyk. New Hash Functions for Message Authentication. Proceedings of EUROCRYPT ’95, Lecture Notes in Computer Science, vol. 921, Springer-Verlag, 1995, pp. 301–310.
Rabin, M.O., “Fingerprinting by Random Polynomials≓, Tech. Rep. TR-15-81, Center for Research in Computing Technology, Harvard Univ., Cambridge, Mass., 1981.
P. Rogaway. Bucket Hashing and its application to Fast Message Authentication. Proceedings of CRYPTO ’95, Lecture Notes in Computer Science, vol. 963, Springer-Verlag, 1995, pp. 15–25.
V. Shoup. On Fast and Provably Secure Message Authentication Based on Universal Hashing Advances in Cryptology — CRYPTO ’96 Proceedings, Lecture Notes in Computer Science Vol. 1109, N. Koblitz, ed., Springer-Verlag, 1996. pp. 313–328.
D. Stinson. Universal Hashing and Authentication Codes. Designs, Codes and Cryptography, vol. 4, 1994, pp. 369–380.
J. Touch. Performance Analysis of MD5. Proc. Sigcomm ’95, Boston, pp. 77–86.
D. Stinson. On the Connection Between Universal Hashing, Combinatorial Designs and Error-Correcting Codes. TR95-052, Electronic Colloquium on Computational Complexity, 1995.
M. Wegman and L. Carter. New hash functions and their use in authentication and set equality. J. 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
Halevi, S., Krawczyk, H. (1997). MMH: Software message authentication in the Gbit/second rates. In: Biham, E. (eds) Fast Software Encryption. FSE 1997. Lecture Notes in Computer Science, vol 1267. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0052345
Download citation
DOI: https://doi.org/10.1007/BFb0052345
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63247-4
Online ISBN: 978-3-540-69243-0
eBook Packages: Springer Book Archive
Keywords
- Hash Function
- Collision Probability
- Message Authentication Code
- Message Authentication
- Pseudorandom Generator
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.