One-key Double-Sum MAC with Beyond-Birthday Security.
Nilanjan Datta, Avijit Dutta, Mridul Nandi, Goutam Paul, Liting Zhang · 2015
Abstract. MACs (Message Authentication Codes) are widely adopted in communication systems to ensure data integrity and data origin au-thentication, e.g. CBC-MACs in the ISO standard 9797-1. However, all the current designs either suffer from birthday attacks or require long key sizes. In this paper, we focus on designing beyond-birthday-bound MAC modes with a single key, and investigate their design principles. First, we review the current proposals, e.g. 3kf9 and PMAC Plus, and identify that the security primarily comes from the construction of a cover-free function and the advantage of the sum of PRPs. The main challenge in reducing their key size is to find a mechanism to carefully separate the block cipher inputs to the cover-free construction and the sum of PRPs that work in cascade with such a construction. Secondly, we develop several tools on sampling distributions that are quite useful in analysis of the MAC mode of operations and by which we unify the proofs for three/two-key beyond-birthday-bound MACs. Thirdly, we establish our main theorem that upper-bounds the PRF security of the one-key con-structions by extended-cover-free, pseudo-cover-free, block-wise universal and the normal PRP assumption on block ciphers. Finally, we apply our main theorem to 3kf9 and PMAC Plus, and successfully reduce their key sizes to the minimum possible. Thus, we solve a long-standing open problem in designing beyond-birthday-bound MAC with a single key.