The security of the cipher block chaining message authentication
Authors: M. Bellare, J. Kilian and
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
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.
Ref: Journal of
Computer and System Sciences, Vol. 61, No. 3, Dec 2000, pp. 362--399.
Extended abstract in Advances in Cryptology - Crypto 94 Proceedings,
Lecture Notes in Computer Science Vol. 839, Y. Desmedt ed,
Springer-Verlag, 1994. Full paper available below.
Full paper: Available as compressed
postscript, postscript, or pdf
( Help if this doesn't work).