Cryptology ePrint Archive: Report 2016/185

On the Influence of Message Length in PMAC's Security Bounds

Atul Luykx and Bart Preneel and Alan Szepieniec and Kan Yasuda

Abstract: Many MAC (Message Authentication Code) algorithms have security bounds which degrade linearly with the message length. Often there are attacks that confirm the linear dependence on the message length, yet PMAC has remained without attacks. Our results show that PMAC's message length dependence in security bounds is non-trivial. We start by studying a generalization of PMAC in order to focus on PMAC's basic structure. By abstracting away details, we are able to show that there are two possibilities: either there are infinitely many instantiations of generic PMAC with security bounds independent of the message length, or finding an attack against generic PMAC which establishes message length dependence is computationally hard. The latter statement relies on a conjecture on the difficulty of finding subsets of a finite field summing to zero or satisfying a binary quadratic form. Using the insights gained from studying PMAC's basic structure, we then shift our attention to the original instantiation of PMAC, namely, with Gray codes. Despite the initial results on generic PMAC, we show that PMAC with Gray codes is one of the more insecure instantiations of PMAC, by illustrating an attack which roughly establishes a linear dependence on the message length.

Category / Keywords: unforgeability, integrity, verification, birthday bound, tag, PMAC, message length

Original Publication (with minor differences): IACR-EUROCRYPT-2016

Date: received 22 Feb 2016, last revised 21 Nov 2016

Contact author: atul luykx at esat kuleuven be

Available format(s): PDF | BibTeX Citation

Note: As pointed out by Peter Vandendriessche, the conjecture in the paper is false. A paragraph has been added to the end of the introduction explaining the implications.

Version: 20161122:013708 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]