Improved Security Analyses for CBC MACs

Mihir Bellare, Krzysztof Pietrzak, and Phillip Rogaway

Advances in Cryptology — CRYPTO 2005, Lecture Notes in Computer Science, Springer-Verlag, vol. 3621, pp. 527–545, Aug 2005.

We present an improved bound on the advantage of any \mbox{$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 $\ell$ be the block length of the longest query, our bounds are about $\ell q^2/2^n$ for the basic CBC MAC and $\ell^{o(1)}q^2/2^n$ for the encrypted CBC MAC, improving prior bounds of $\ell^2q^2/2^n$. The new bounds translate into improved guarantees on the probability of forging these MACs.

BibTeX Citation

@inproceedings{BePiRo05,
    author       = {Mihir Bellare and Krzysztof Pietrzak and Phillip Rogaway},
    title        = {Improved Security Analyses for {CBC} {MAC}s},
    booktitle    = {Advances in Cryptology --- CRYPTO 2005},
    pages        = 527--545,
    series       = {Lecture Notes in Computer Science},
    volume       = 3621,
    year         = 2005,
    month        = 8,
    publisher    = {Springer-Verlag},
}