Cryptology ePrint Archive: Report 2016/161

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

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:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]