International Association for Cryptologic Research

International Association
for Cryptologic Research


Ted Krovetz


VHASH Security
Wei Dai Ted Krovetz
VHASH is an almost-delta-universal hash family, designed for exceptional performance on computers that multiply 64-bit quantities efficiently. Changes to the algorithm detailed in this note improve both security and performance over the original 2006 version. Speed is improved through a newly analyzed hash construction which allows the use of lower-degree polynomials. Claimed security is higher due primarily to improved analysis and a change in prime modulus. The result is a hash family capable of hashing cache-resident one kilobyte messages on the Intel Core 2 architecture at a rate of about one-half processor cycle per byte of message with a collision probability of less than $1/2^{61}$.
Message Authentication on 64-bit Architectures
Ted Krovetz
This paper takes UMAC --- a message authentication algorithm (MAC) optimized for performance on 32-bit architectures --- as its starting point, and adapts its strategies for optimum performance on 64-bit architectures. The resulting MAC, called UMAC8, achieves per message forgery probabilities of about $2^{-60}$ and $2^{-120}$ for tags of length 64 and 128 bits. The UMAC strategies are discussed at length and adapted for 64-bit environments, but are also modified to address several UMAC shortcomings, particularly key-agility and susceptibility to timing attacks. UMAC achieved peak throughput rates, when generating 64-bit tags, of 1.0 CPU cycle per byte of message authenticated, while UMAC8 achieves 0.5 cycles per byte.
OCB Mode
This paper was prepared for NIST, which is considering new block-cipher modes of operation. It describes a parallelizable mode of operation that simultaneously provides both privacy and authenticity. "OCB mode" encrypts-and-authenticates an arbitrary message $M\in\bits^*$ using only $\lceil |M|/n\rceil + 2$ block-cipher invocations, where $n$ is the block length of the underlying block cipher. Additional overhead is small. OCB refines a scheme, IAPM, suggested by Jutla [IACR-2000/39], who was the first to devise an authenticated-encryption mode with minimal overhead compared to standard modes. Desirable new properties of OCB include: very cheap offset calculations; operating on an arbitrary message $M\in\bits^*$; producing ciphertexts of minimal length; using a single underlying cryptographic key; making a nearly optimal number of block-cipher calls; avoiding the need for a random IV; and rendering it infeasible for an adversary to find "pretag collisions". The paper provides a full proof of security for OCB.