MAC Constructions: Security Bounds and Distinguishing Attacks

Cryptography;MAC;Security;Distinguishing Attack;Combinatorics and Optimization

Mandal, Avradip

University of Waterloo

关键词: Cryptography;    MAC;    Security;    Distinguishing Attack;    Combinatorics and Optimization;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/3058/1/ThesisD4.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

We provide a simple and improved security analysis of PMAC, aParallelizable MAC (Message Authentication Code) defined overarbitrary messages. A similar kind of result was shown by Bellare,Pietrzak and Rogaway at Crypto 2005, where they have provided animproved bound for CBC (Cipher Block Chaining) MAC, which wasintroduced by Bellare, Killan and Rogaway at Crypto 1994. Ouranalysis idea is much more simpler to understand and is borrowedfrom the work by Nandi for proving Indistinguishability atIndocrypt 2005 and work by Bernstein. It shows that the advantagefor any distinguishing attack for n-bit PMAC based on a randomfunction is bounded by O(σq / 2^n), whereσ is the total number of blocks in all q queries made bythe attacker. In the original paper by Black and Rogaway atEurocrypt 2002 where PMAC was introduced, the bound isO(σ^2 / 2^n).We also compute the collision probability of CBC MAC for suitablychosen messages. We show that the probability is Ω( lq^2 / N) where l is the number of message blocks, N is thesize of the domain and q is the total number of queries. Forrandom oracles the probability is O(q^2 / N). This improvedcollision probability will help us to have an efficientdistinguishing attack and MAC-forgery attack. We also show that thecollision probability for PMAC is Ω(q^2 / N) (strictly greaterthan the birthday bound). We have used a purely combinatorialapproach to obtain this bound. Similar analysis can be made forother CBC MAC extensions like XCBC, TMAC and OMAC.