UMAC: Fast and secure message authentication

Reference: Advances in Cryptology - CRYPTO '99. . Lecture Notes in Computer Science, vol. 1666, M. Wiener, ed., Springer-Verlag, pp. 215-233.

Abstract: We describe a message authentication algorithm, UMAC, which authenticates messages (in software, on contemporary machines) roughly an order of magnitude faster than current practice (eg, HMAC-SHA1). To achieve such speeds UMAC uses a variant of the Carter-Wegman paradigm, employing a new universal-hash-function, NH, as well as a new way to use such a family to construct a MAC. The "cryptographic" work of UMAC is done using standard primitives of the user's choice, such as a block cipher or cryptographic hash function; no new heuristic primitives are developed here. Instead, the security of UMAC is rigorously proven, in the sense of giving exact and quantitatively strong results which demonstrate an inability to forge UMAC-authenticated messages assuming an inability to break the underlying cryptographic primitive. Unlike conventional, inherently serial MACs, {\name} is parallelizable, and will have ever-faster implementation speeds as machines offer up increasing amounts of parallelism. We envision UMAC as a practical and desirable algorithm for next-generation message authentication.