[Resource Topic] 2017/172: On The Exact Security of Message Authentication Using Pseudorandom Functions

Welcome to the resource topic for 2017/172

On The Exact Security of Message Authentication Using Pseudorandom Functions

Authors: Ashwin Jha, Avradip Mandal, Mridul Nandi


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.

ePrint: https://eprint.iacr.org/2017/172

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .