Improved security analyses for CBC MACs

Abstract

We present an improved bound on the advantage of any q-query adversary at distinguishing between the CBC MAC over a random n-bit permutation and a random function outputting n bits. The result assumes that no message queried is a prefix of any other, as is the case when all messages to be MACed have the same length: We go on to give an improved analysis of the encrypted CBC MAC, where there is no restriction on queried messages. Letting m be the block length of the longest query, our bounds are about mq2/2nfor the basic CBC MAC and m°(1)q2/2nfor the encrypted CBC MAC, improving prior bounds of m2q2/2n. The new bounds translate into improved guarantees on the probability of forging these MACs. © International Association for Cryptologic Research 2005.