The Security of the Cipher Block Chaining Message Authentication Code

✍ Scribed by Mihir Bellare; Joe Kilian; Phillip Rogaway

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 286 KB
• Volume: 61
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1999.1694

✦ Synopsis

Let F be some block cipher (eg., DES) with block length l. The cipher block chaining message authentication code (CBC MAC) specifies that an m-block message x=x 1 } } } x m be authenticated among parties who share a secret key a for the block cipher by tagging x with a prefix of y m , where y 0 =0 l and y i =F a (m i Ä y i&1 ) for i=1, 2, ..., m. This method is a pervasively used international and U.S. standard. We provide its first formal justification, showing the following general lemma: cipher block chaining a pseudorandom function yields 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.