The Security of Cipher Block Chaining

The Cipher Block Chaining — Message Authentication Code (CBC MAC) specifies that a message x = x₁ . . . x_m be authenticated among parties who share a secret key a by tagging x with a prefix of $$ f_a^{(m)} (x)\mathop = \limits^{def} f_a (f_a ( \ldots f_a (f_a (x_1 ) \oplus x_2 ) \oplus \ldots \oplus x_{m - 1} ) \oplus x_m ) $$ where f is some underlying block cipher (eg. 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.