VMac

VMAC is a block cipher-based message authentication code (MAC) algorithm using a universal hash proposed by Ted Krovetz and Wei Dai in April 2007. The algorithm was designed for high performance backed by a formal analysis.

VMAC is designed to have exceptional performance in software on 64-bit CPU architectures while still performing well on 32-bit architectures. Measured speeds are as fast as one-half CPU cycle per byte (cpb) on 64-bit architectures, under five cpb on desktop 32-bit processors, and around ten cpb on embedded 32-bit architectures. A closely related variant of VMAC that is optimized for 32-bit architectures is given by UMAC.

VMAC is a MAC in the style of Wegman and Carter. A fast "universal" hash function is used to hash an input message M into a short string. This short string is then combined by addition with a pseudorandom pad, resulting in the VMAC tag. Security depends on the sender and receiver sharing a randomly chosen secret hash function and pseudorandom pad. This is achieved by using keyed hash function H and pseudorandom function F. A tag is generated by performing the computation

where K1 and K2 are secret random keys shared by sender and receiver, and Nonce is a value that changes with each generated tag. The receiver needs to know which nonce was used by the sender, so some method of synchronizing nonces needs to be used. This can be done by explicitly sending the nonce along with the message and tag, or agreeing upon the use of some other non-repeating value such as a sequence number. The nonce need not be kept secret, but care needs to be taken to ensure that, over the lifetime of a VMAC key, a different nonce is used with each message.

VMAC uses a function, called VHASH (also specified in this document), as the keyed hash function H and uses a pseudorandom function F whose default implementation uses the AES block cipher. VMAC allows for tag lengths of any 64-bit multiple up to the block size of the block cipher in use. When using AES, this means VMAC can produce 64- or 128-bit tags.

The theory of Wegman-Carter MACs and the analysis of VMAC show that if one "instantiates" VMAC with truly random keys and pads then the probability that an attacker (even a computationally unbounded one) produces a correct tag for messages of its choosing is less than 1/2⁶⁰ or 1/2¹²⁰ when the tags are of length 64 or 128 bits, respectively. When an attacker makes N forgery attempts the probability of getting one or more tags right increases linearly to less than N/2⁶⁰ or N/2¹²⁰. In an applied implementation of VMAC, using AES to produce keys and pads, these forgery probabilities increase by a small amount related to the security of AES. As long as AES is secure, this small additive term is insignificant for any practical attack. See specification for more details. Analysis of VMAC security has been carried out by authors Wei Dai and Ted Krovetz.

...
Wikipedia