### On The Exact Security of Message Authentication Using Pseudorandom Functions

Ashwin Jha, Avradip Mandal, and Mridul Nandi

##### Abstract

Traditionally, modes of Message Authentication Codes(MAC) such as Cipher Block Chaining (CBC) are instantiated using block ciphers or keyed Pseudo Random Permutations(PRP). However, one can also use domain preserving keyed Pseudo Random Functions(PRF) to instantiate MAC modes. The very first security proof of CBC-MAC, essentially modeled the PRP as a PRF. Until now very little work has been done to investigate the difference between PRP vs PRF instantiations. Only known result is the rather loose folklore PRP-PRF transition of any PRP based security proof, which looses a factor of $O(\frac{\sigma^2}{2^n})$ (domain of PRF/PRP is $\{0,1\}^n$ and adversary makes $\sigma$ many PRP/PRF calls in total). This loss is significant, considering the fact tight $\Theta(\frac{q^2}{2^n})$ security bounds have been known for PRP based EMAC and ECBC constructions (where $q$ is the total number of adversary queries). In this work, we show for many variations of encrypted CBC MACs (i.e. EMAC, ECBC, FCBC, XCBC and TCBC), random function based instantiation has a security bound $O(\frac{q\sigma}{2^n})$. This is a significant improvement over the folklore PRP/PRF transition. We also show this bound is optimal by providing an attack against the underlying PRF based CBC construction. This shows for EMAC, ECBC and FCBC, PRP instantiations are substantially more secure than PRF instantiations. Where as, for XCBC and TMAC, PRP instantiations are at least as secure as PRF instantiations.

Note: An abridged version of this paper appears in FSE 2017/ToSC Vol 2017. This is the full version. In comparison to the ToSC version, this one has some minor technical and editorial fixes, and a discussion on a relevant previous work.

Available format(s)
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in FSE 2017
Keywords
MACCBCEMACXCBCFCBCTMACdomain preserving PRFPRP
Contact author(s)
ashwin jha1991 @ gmail com
History
2020-06-02: last of 2 revisions
See all versions
Short URL
https://ia.cr/2017/172

CC BY

BibTeX

@misc{cryptoeprint:2017/172,
author = {Ashwin Jha and Avradip Mandal and Mridul Nandi},
title = {On The Exact Security of Message Authentication Using Pseudorandom Functions},
howpublished = {Cryptology ePrint Archive, Paper 2017/172},
year = {2017},
note = {\url{https://eprint.iacr.org/2017/172}},
url = {https://eprint.iacr.org/2017/172}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.