CBC MACs for Arbitrary-Length Messages: The Three-Key Constructions

Authors: John Black and Phillip Rogaway.

Reference: J. of Cryptology, vol. 18, no. 2, pp. 111-131, 2005. Prior version: Advances in Cryptology - CRYPTO '00. . Lecture Notes in Computer Science, vol. 1880, pp. 197-215, M. Bellare, editor, Springer-Verlag, 2000.

Abstract: We suggest some simple variants of the CBC MAC that let you efficiently MAC messages of arbitrary lengths. Our constructions use three keys, K1, K2, K3, to avoid unnecessary padding and MAC any binary string M in the larger of 1 and the ceiling of |M|/n applications of the underlying n-bit block cipher. Our favorite construction, XCBC, works like this: if |M| is a positive multiple of n then XOR the n-bit key K2 with the last block of M and compute the CBC MAC keyed with K1; otherwise, extend M's length to the next multiple of n by appending minimal 10^i padding (i>=0), XOR the n-bit key K3 with the last block of the padded message, and compute the CBC MAC keyed with K1. We prove the security of this and other constructions, giving concrete bounds on an adversary's inability to forge in terms of her inability to distinguish the block cipher from a random permutation. Our analysis exploits new ideas which simplify proofs compared to prior work.

Availability: Paper available as pdf or ps


A Suggestion for Handling Arbitrary-Length Messages to with the CBC MAC

Authors: John Black and Phillip Rogaway.

Publication notes: This is an unpublished submission to NIST corresponding to the paper above. Also available from the NIST web site.

Availability: Paper available as pdf or ps


Rogaway's home page.