Cryptology ePrint Archive: Report 2015/958

One-key Double-Sum MAC with Beyond-Birthday Security

Nilanjan Datta and Avijit Dutta and Mridul Nandi and 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 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 constructions 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.

Category / Keywords: secret-key cryptography / Beyond Birthday, 3kf9, PMAC\_Plus, MAC, Sum of PRP, Cover-free, Rank, Strucutre Graph

Date: received 1 Oct 2015, last revised 3 Oct 2015

Contact author: avirocks dutta13 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20151003:061914 (All versions of this report)

Short URL: ia.cr/2015/958

Discussion forum: Show discussion | Start new discussion