CryptoDB

Publications

Year
Venue
Title
2017
TOSC
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
2014
EPRINT
2012
TCC
2011
PKC
2011
PKC
2011
CRYPTO
2010
TCC
2010
FSE
2009
ASIACRYPT
2007
EPRINT
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
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.