Paper 2007/032

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Message Authentication Codes
Contact author(s)
mridul nandi @ gmail com
History
2007-02-14: received
Short URL
https://ia.cr/2007/032
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/032,
      author = {Avradip Mandal and Mridul Nandi},
      title = {An improved collision probability for CBC-MAC and PMAC},
      howpublished = {Cryptology ePrint Archive, Paper 2007/032},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/032}},
      url = {https://eprint.iacr.org/2007/032}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.