The security of cipher block chaining

M. Bellare, J. Kilian, P. Rogaway

The Cipher Block Chaining-Message Authentication Code (CBC MAC)
specifies that a message x=x/sub 1/...x/sub m/ be authenticated among
parties who share a secret key a by tagging x with a prefix of fa/sup
(m)/(x)=/sup def/fa(fa(...fa(fa(x/sub 1/)(+)x/sub 2/)(+)...(+)x/sub
m-1/)(+)x/sub m/), where f is some underlying block cipher (e.g. f=DES).
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.