**Revisiting Structure Graphs: Applications to CBC-MAC and EMAC**

*Ashwin Jha and Mridul Nandi*

**Abstract: **In Crypto'05, Bellare et al. proved an $O(\ell q^2 /2^n)$ bound for the PRF (pseudorandom function) security of the CBC-MAC based on an $n$-bit random permutation $\Pi$, provided $\ell < 2^{n/3}$. Here an adversary can make at most $q$ prefix-free queries each having at most $\ell$ many ``\emph{blocks}'' (elements of $\{0,1\}^n$). In the same paper an $O(\ell^{o(1)} q^2 /2^n)$ bound for EMAC (or encrypted CBC-MAC) was proved, provided $\ell < 2^{n/4}$. Both proofs are based on {\bf structure graphs} representing all collisions among ``\emph{intermediate inputs}'' to $\Pi$ during the computation of CBC. The problem of bounding PRF-advantage is shown to be reduced to bounding the number of structure graphs satisfying certain collision patterns. In the present paper, we show that \emph{the Lemma 10 in the Crypto '05 paper, stating an important result on structure graphs, is incorrect}. This is due to the fact that the authors {\bf overlooked certain structure graphs}. This invalidates the proofs of the PRF bounds. In ICALP '06, Pietrzak improved the bound for EMAC by showing a \emph{tight bound} $O(q^2/2^n)$ under the restriction that $\ell < 2^{n/8}$. As he used the same flawed lemma, this proof also becomes invalid. In this paper, we have revised and sometimes simplified these proofs. We revisit structure graphs in a slightly different mathematical language and provide a complete characterization of certain types of structure graphs. Using this characterization, we show that PRF security of CBC-MAC is about $\sigma q /2^n$ provided $\ell < 2^{n/3}$ where $ \sigma $ is the total number of blocks in all queries. We also recover tight bound for PRF security of EMAC with a much relaxed constraint ($ \ell < 2^{n/4} $) than the original ($ \ell < 2^{n/8} $).

**Category / Keywords: **CBC, EMAC, ECBC, FCBC, structure graph, accident

**Original Publication**** (with minor differences): **Journal of Mathematical Cryptology
**DOI: **10.1515/jmc-2016-0030

**Date: **received 18 Feb 2016, last revised 11 Mar 2017

**Contact author: **ashwin jha1991 at gmail com

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

**Note: **Fixed some typos and attending the editorial comments. Extending the tight bound results to ECBC and FCBC.

**Version: **20170311:071025 (All versions of this report)

**Short URL: **ia.cr/2016/161

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

[ Cryptology ePrint archive ]