Tight Security of PMAC-type and CBC-type Message Authentication Codes

Abstract

Message Authentication Codes (or MACs) are symmetric-key primitives that ensure the authenticity as well as the integrity of messages. The sender generates an authen- tication tag (based on a message and a secret key) which can be verified on the re- ceiver’s end. Two paradigms for building block cipher based MACs of the form Hash- then-PRP: 1) Parallelizable or PMAC-type, 2) Sequential or CBC-type. PMAC, sPMAC, PMAC1, LightMAC etc. are examples of PMAC-type MACs. Whereas OMAC, XCBC, TMAC, GCBC are examples of CBC-type MACs. Obtaining length independent (tight) bounds for these constructions has been a challenging problem. The goal of this thesis is to obtain length independent (tight) bounds for as many important constructions as possible and devise a novel technique that can be employed for various constructions and has a scope of generalization. PMAC-TYPE MACS: Firstly, in chapter 3, we demonstrate why a claim about tight se- curity of a PMAC variant proposed by Naito is wrong. Together with that, we state a necessary and sufficient condition to correctly establish that claim. Secondly, in the same chapter, we propose a variant of PMAC1 which has tight security for a rea- sonable range of message lengths. Then we prove the tight security of sPMAC for a weaker notion of independence (of hash). Next, in chapter 4, we analyze secu- rity bounds for LightMAC: We show tight security of 1k-LightMAC (single-key version of the original LightMAC) which holds for a range of lengths (both upper and lower bounded). Moreover, we show an attack on 1k-LightMAC for sufficiently small-length messages. Besides we propose two new variants of 1k-LightMAC, namely, LightMAC- swp and LightMAC-ds, both of which achieve length independent tight security for a fairly good range of lengths. Here we employ a novel sampling technique, dubbed “Reset-sampling”, as a subroutine of H-coefficient setup. It helps get tight bounds. Then, in the last chapter (5) of this part, we try to get a generalized view of the PMAC family. We develop technical concepts necessary to cover a large class of parallelizable MACs of the form hash-then-PRP. As the main results of this chapter, we prove the se- curity bound in terms of the collision probability of the underlying hash function, both for independent keys and single-keyed versions of a generic member of the PMAC family. As a corollary to this, we apply this result to get birthday-bound security for a simplified version of PMAC+, under some assumptions. Moreover, a similar bound for 1k-LightMAC as well follows directly from the main result. CBC-TYPE MACS: In chapter 6, we obtain O( q2 2n + qℓ2 2n ) bound for OMAC using reset- sampling . This is the best-known bound for it. Although it is not “length independent” in an exact sense, it behaves almost like a birthday bound with some consideration. We obtain similar bounds for XCBC and TMAC also. In this way, we become successful in establishing tight security for all CBC-MAC variants, except the original one.