Paper 2016/185

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

Atul Luykx, Bart Preneel, 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.

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.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in EUROCRYPT 2016
Keywords
unforgeabilityintegrityverificationbirthday boundtagPMACmessage length
Contact author(s)
atul luykx @ esat kuleuven be
History
2016-11-22: revised
2016-02-23: received
See all versions
Short URL
https://ia.cr/2016/185
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/185,
      author = {Atul Luykx and Bart Preneel and Alan Szepieniec and Kan Yasuda},
      title = {On the Influence of Message Length in PMAC's Security Bounds},
      howpublished = {Cryptology ePrint Archive, Paper 2016/185},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/185}},
      url = {https://eprint.iacr.org/2016/185}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.