Search

This paper shows that the advantage of any q-query adversary (which makes at most q queries) for distinguishing OMAC from a uniform random function is roughly Lq2/2n. Here L is the number of blocks of the longest query and n is the output size of the uniform random function. The so far best bound is roughly σ2/2n = O(L2q2/2n) and hence our new bound is an improved bound. Our improved security analysis also works for OMAC1 and CMAC which has been recommended by NIST as a candidate of blockcipher based MAC.

In this paper we provide a simple, concrete and improved security analysis of PMAC, a Parallelizable Message Authentication Code. We show that the advantage of any distinguisher forPMAC based on a random permutation is at most 5qσ−3.5q 2 2n , where σ 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 (σ+1) 2 2n−1 . Very recently, Minematsu and Matsushima in FSE-2007, have provided a bound 10`q 2 2n where ` 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.