Paper 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 ``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 ``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 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 overlooked certain structure graphs. This invalidates the proofs of the PRF bounds. In ICALP '06, Pietrzak improved the bound for EMAC by showing a 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} $).

Note: Fix for some minor technical and editorial issues.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Minor revision. Journal of Mathematical Cryptology
DOI
10.1515/jmc-2016-0030
Keywords
CBCEMACECBCFCBCstructure graphaccident
Contact author(s)
ashwin jha1991 @ gmail com
History
2020-02-22: last of 2 revisions
2016-02-18: received
See all versions
Short URL
https://ia.cr/2016/161
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/161,
      author = {Ashwin Jha and Mridul Nandi},
      title = {Revisiting Structure Graphs: Applications to CBC-MAC and EMAC},
      howpublished = {Cryptology ePrint Archive, Paper 2016/161},
      year = {2016},
      doi = {10.1515/jmc-2016-0030},
      note = {\url{https://eprint.iacr.org/2016/161}},
      url = {https://eprint.iacr.org/2016/161}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.