Twisted Polynomials and Forgery Attacks on GCM

Mohamed Ahmed A. M. A. Abdelraheem, Peter Beelen, Andrey Bogdanov, Elmar Wolfgang Tischhauser

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


Polynomial hashing as an instantiation of universal hashing is a widely employed method for the construction of MACs and authenticated encryption (AE) schemes, the ubiquitous GCM being a prominent example. It is also used in recent AE proposals within the CAESAR competition which aim at providing nonce misuse resistance, such as POET. The algebraic structure of polynomial hashing has given rise to security concerns: At CRYPTO 2008, Handschuh and Preneel describe key recovery attacks, and at FSE 2013, Procter and Cid provide a comprehensive framework for forgery attacks. Both approaches rely heavily on the ability to construct forgery polynomials having disjoint sets of roots, with many roots (“weak keys”) each. Constructing such polynomials beyond naïve approaches is crucial for these attacks, but still an open problem.

In this paper, we comprehensively address this issue. We propose to use twisted polynomials from Ore rings as forgery polynomials. We show how to construct sparse forgery polynomials with full control over the sets of roots. We also achieve complete and explicit disjoint coverage of the key space by these polynomials. We furthermore leverage this new construction in an improved key recovery algorithm.

As cryptanalytic applications of our twisted polynomials, we develop the first universal forgery attacks on GCM in the weak-key model that do not require nonce reuse. Moreover, we present universal weak-key forgeries for the nonce-misuse resistant AE scheme POET, which is a CAESAR candidate.
Original languageEnglish
Title of host publicationAdvances in Cryptology – EUROCRYPT 2015 : Proceedings of the 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Part 1
EditorsElisabeth v, Marc Fischlin
Publication date2015
ISBN (Print)978-3-662-46799-2
ISBN (Electronic)978-3-662-46800-5
Publication statusPublished - 2015
Event34th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2015) - Sofia, Bulgaria
Duration: 26 Apr 201530 Apr 2015
Conference number: 34


Conference34th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2015)
Internet address
SeriesLecture Notes in Computer Science


  • Authenticated encryption
  • Polynomial hashing
  • Twisted polynomial ring (Ore ring)
  • Weak keys
  • GCM
  • POET

Fingerprint Dive into the research topics of 'Twisted Polynomials and Forgery Attacks on GCM'. Together they form a unique fingerprint.

Cite this