**An improved collision probability for CBC-MAC and PMAC**

*Avradip Mandal and Mridul Nandi*

**Abstract: **In this paper we compute the collision probability of
CBC-MAC for suitably chosen messages. We show
that the probability is $\Omega(\ell q^2/N)$ where $\ell$ is the
number of message block, $N$ is the size of the domain and $q$ is
the total number of queries. For random oracle the probability is
$O(q^2/N)$. This improved collision probability will help us to have
an efficient distinguishing attack and MAC-forgery attack. We also
show collision probability for PMAC with collision probability
$\Omega(q^2/N)$ (strictly more than birth day bound). We have used a
purely combinatorial approach to obtain this bound. The similar
analysis can be made for other MAC like XCBC,
TMAC, OMAC etc. We hope
this approach will help us to calculate related probabilities.

**Category / Keywords: **secret-key cryptography / Message Authentication Codes

**Date: **received 1 Feb 2007

**Contact author: **mridul nandi at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20070214:102350 (All versions of this report)

**Short URL: **ia.cr/2007/032

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]