## CryptoDB

### Avradip Mandal

#### Affiliation: Fujitsu Laboratories of America, INC

#### Publications

**Year**

**Venue**

**Title**

2017

TOSC

On The Exact Security of Message Authentication Using Pseudorandom Functions
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 [BKR00], 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 Ο( σ2/2n ) (domain of PRF/PRP is {0, 1}n and adversary makes σ many PRP/PRF calls in total). This loss is significant, considering the fact tight Θ( q2/2n ) 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 Ο( qσ/2n ). 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.

2015

CRYPTO

2012

TCC

2007

EPRINT

Improved Security Analysis of PMAC
Abstract

In this paper we provide a simple, concrete and improved security
analysis of {\bf PMAC}, a Parallelizable Message Authentication
Code. We show that the advantage of any distinguisher for {\bf PMAC}
based on a random permutation is at most $\mathbf{\frac{5q\sigma -
3.5 q^2}{2^n}}$, where $\sigma$ is the total number of message
blocks in all $q$ queries made by the distinguisher. In the original
paper by Black and Rogaway in Eurocrypt-2002, the bound was
$\frac{(\sigma+1)^2}{2^{n-1}}$. Very recently, Minematsu and
Matsushima in FSE-2007, have provided a bound $\frac{10\ell
q^2}{2^n}$ where $\ell$ is the maximum block length of all messages
queried by the distinguisher. Our new bound is better than both
original and recently proposed bound and guarantees much more
security of PMAC. We also have provided a complete, independent and
simple combinatorial proof. This proof idea may help us to find a
similar result for other MAC algorithms.

2007

EPRINT

An improved collision probability for CBC-MAC and PMAC
Abstract

In this paper we compute the collision probability of
CBC-MAC for suitably chosen messages. We show
that the probability is $\Omega(\ell q^2/N)$ where $\ell$ is the
number of message block, $N$ is the size of the domain and $q$ is
the total number of queries. For random oracle the probability is
$O(q^2/N)$. This improved collision probability will help us to have
an efficient distinguishing attack and MAC-forgery attack. We also
show collision probability for PMAC with collision probability
$\Omega(q^2/N)$ (strictly more than birth day bound). We have used a
purely combinatorial approach to obtain this bound. The similar
analysis can be made for other MAC like XCBC,
TMAC, OMAC etc. We hope
this approach will help us to calculate related probabilities.

#### Coauthors

- Rishiraj Bhattacharyya (2)
- Jean-Sébastien Coron (4)
- Yevgeniy Dodis (1)
- Ashwin Jha (1)
- Antoine Joux (1)
- David Naccache (2)
- Mridul Nandi (4)
- Jacques Patarin (1)
- Arnab Roy (2)
- Yannick Seurin (2)
- Mehdi Tibouchi (2)