Paper 2018/166

Optimal Forgeries Against Polynomial-Based MACs and GCM

Atul Luykx and Bart Preneel


Polynomial-based authentication algorithms, such as GCM and Poly1305, have seen widespread adoption in practice. Due to their importance, a significant amount of attention has been given to understanding and improving both proofs and attacks against such schemes. At EUROCRYPT 2005, Bernstein published the best known analysis of the schemes when instantiated with PRPs, thereby establishing the most lenient limits on the amount of data the schemes can process per key. A long line of work, initiated by Handschuh and Preneel at CRYPTO 2008, finds the best known attacks, advancing our understanding of the fragility of the schemes. Yet surprisingly, no known attacks perform as well as the predicted worst-case attacks allowed by Bernstein's analysis, nor has there been any advancement in proofs improving Bernstein's bounds, and the gap between attacks and analysis is significant. We settle the issue by finding a novel attack against polynomial-based authentication algorithms using PRPs, and combine it with new analysis, to show that Bernstein's bound, and our attacks, are optimal.

Note: Fixed typos and improved explanation

Available format(s)
Publication info
Published by the IACR in EUROCRYPT 2018
forgeryWegman-CarterauthenticatorMACGCMuniversal hashpolynomial
Contact author(s)
atul luykx @ esat kuleuven be
bart preneel @ esat kuleuven be
2018-04-27: revised
2018-02-11: received
See all versions
Short URL
Creative Commons Attribution


      author = {Atul Luykx and Bart Preneel},
      title = {Optimal Forgeries Against Polynomial-Based MACs and GCM},
      howpublished = {Cryptology ePrint Archive, Paper 2018/166},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.