Cryptology ePrint Archive: Report 2018/166

Optimal Forgeries Against Polynomial-Based MACs and GCM

Atul Luykx and Bart Preneel

Abstract: 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.

Category / Keywords: forgery, Wegman-Carter, authenticator, MAC, GCM, universal hash, polynomial

Original Publication (in the same form): IACR-EUROCRYPT-2018

Date: received 8 Feb 2018, last revised 27 Apr 2018

Contact author: atul luykx at esat kuleuven be, bart preneel@esat kuleuven be

Available format(s): PDF | BibTeX Citation

Note: Fixed typos and improved explanation

Version: 20180427:234840 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]