Paper 2015/958

Building Single-Key Beyond Birthday Bound Message Authentication Code

Nilanjan Datta, Avijit Dutta, Mridul Nandi, Goutam Paul, and Liting Zhang

Abstract

MACs (Message Authentication Codes) are widely adopted in communication systems to ensure data integrity and data origin authentication, e.g. CBC-MACs in the ISO standard 9797-1. However, all the current designs based on block cipher either suffer from birthday attacks or require long key sizes. In this paper, we focus on designing {\em single keyed block cipher based MAC achieving beyond-birthday-bound (BBB) security (in terms of number of queries) in the standard model}. Here, we develop several tools on sampling distributions which would be quite useful in the analysis of mode of operations. In this paper, we also show that the sum of two dependent pseudorandom permutation with some loss of randomness is still PRF with BBB security. Then, we demonstrate a generic composition (including the single keyed) achieving BBB security provided that the underlying internal construction satisfies some variants of cover-free (we call them {\em extended cover-free} and {\em pseudo-cover-free}) and block-wise universal properties. By applying this result, we finally provide two concrete single keyed constructions which achieve BBB security. These two constructions, called \tx{1kf9} and \tx{1k\_PMAC+}, are basically simple one key variants of \tx{3kf9} and \tx{PMAC\_Plus} respectively. Thus, we solve a long-standing open problem in designing single-keyed BBB-secure MAC.

Note: We have found a flaw in the security proof of 1k_PMAC+ and therefore we have decided to withdraw the paper as we do not want our wrong results to be cited in other works.