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 ``\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} $).
Note: Fixed some typos and attending the editorial comments. Extending the tight bound results to ECBC and FCBC.
Metadata
- Available format(s)
- 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
-
CC BY