Software-optimized universal hashing and message authentication

Abstract

We describe a message authentication algorithm, UMAC, which can authenticate messages in software, on contemporary machines, at a rate faster than one Pentium cycle per byte of authenticated message. This is roughly an order of magnitude faster than current practice (e.g., HMAC-SHA1 or CBC-MAC-RC6). We explore three designs, all variations on the style of Wegman and Carter, which achieve such speeds. As a first step, all three designs utilize NH, a universal hash-function family which allows effective exploitation of SIMD parallelism. Unlike conventional, inherently serial MACs, UMAC will have ever-faster implementation speeds as machines offer up increasing amounts of parallelism. UMAC was designed and analyzed in a “provable-security” framework which has allowed its design to be minimal and therefore conducive to high-speeds. Along with the description of UMAC, we develop some new notions. We introduce “verifier-selectable assurance” for message authentication, where the receiver of a message and authentication tag can verify the message up to a level of their own choosing, trading computation time for assurance level. Also introduced is the notion of “variationally-universal” hash-function families, a relaxation of strongly-universal which measures universal hash-function families in terms of variational distance from the uniform distribution. Also described is an almost-universal hash-function family based on polynomial evaluation that hashes arbitrary-length messages into short strings using short keys.