The Security of the Cipher Block Chaining Message Authentication Code

Author: Mihir Bellare and Phillip Rogaway

Reference: Journal of Computer and System Sciences, vol. 61, no. 3, December 2000, pp. 362-399. Earlier version in: Advances in Cryptology - CRYPTO 94, Lecture Notes in Computer Science, Vol. 839, Y. Desmedt, ed., Springer-Verlag, 1994.

Abstract: The Cipher Block Chaining Message Authentication Code (CBC MAC) specifies that a message x=x1 ... xm be authenticated among parties who share a secret key a by tagging x with a prefix of

fam(x) = fa(fa(... fa(fa(x1) xor x2) xor ... xor xm-1) xor xm) ,
where f is some underlying block cipher (e.g., the Data Encryption Standard) and a is its key. This method is a pervasively used international and U.S. standard. We provide its first formal justification, showing the following general lemma: that cipher block chaining a pseudorandom function gives a pseudorandom function. Underlying our results is a technical lemma of independent interest, bounding the success probability of a computationally unbounded adversary in distinguishing between a random mL-bit to L-bit function and the CBC MAC of a random L-bit to L-bit function.

Full version available in PostScript or gzipped PostScript or pdf

Rogaway's home page.