DIMACS Special Year on Networks Seminar


MMH: Software Message Authentication in the Gbit/second Rates


Shai Halevi


AT&T Murray Hill Building, Room: 2A-435
Note: Visitors not from the MH building should use the east side entrance "stairway 9", and call Rebecca Wright, phone 5484, to let them in. Since entering the MH building takes time, visitors are requested to arrive no latter than 2:15 pm.
AT&T Host: Rebecca Wright


2:30 - 3:30 p.m
Friday, December 20, 1996

We describe a construction of almost universal hash functions suitable for very fast software implementation and applicable to the hashing of bulk 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/second, 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 is 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 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.

Joint work with Hugo Krawczyk

Document last modified on December 12, 1996