**Improved security analysis of OMAC**

*Mridul Nandi*

**Abstract: **We present an improved security analysis of OMAC, the construction
is widely used as a candidate of MAC or Pseudo Random Function (or
PRF). In this direction, the first result was given in Crypto-05
where an improved security analysis of CBC (for fixed length or for
arbitrary length prefix-free messages) had provided. Followed by
this work, improved bounds for XCBC, TMAC and PMAC were found. The
improved bounds are of the form $\mathrm{O}(\frac{Lq^2}{2^n})$ where
the original bounds are $\mathrm{O}(\frac{\sigma^2}{2^n})$ which is
roughly $\mathrm{O}(\frac{L^2q^2}{2^n})$. Here, a distinguisher can
make at most $q$ queries having at most $\sigma$ many blocks with
$L$ as the maximum block size. The original bound for OMAC was
roughly $\frac{5L^2q^2}{2^n}$ shown in FSE-03 and the next improved
bound was $\frac{4\sigma^2}{2^n}$ shown in Indocrypt-03. In this
paper we have provided an improved bound (a similar form as provided
for others) for OMAC and the bound we show is roughly
$\frac{4q\sigma}{2^n} = \mathrm{O}(\frac{Lq^2}{2^n})$.

**Category / Keywords: **secret-key cryptography /

**Date: **received 29 Jul 2007

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

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

**Version: **20070807:153839 (All versions of this report)

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

[ Cryptology ePrint archive ]