Paper 2015/1224

Twisted Polynomials and Forgery Attacks on GCM

Mohamed Ahmed Abdelraheem, Peter Beelen, Andrey Bogdanov, and Elmar Tischhauser

Abstract

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 \emph{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 \emph{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 forgery attacks for the recently proposed nonce-misuse resistant AE schemes POET, Julius, and COBRA.

Note: Corrected some text in the introduction regarding Ferguson's GCM attack and referred to a recent paper estimating its complexity and improving it.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in EUROCRYPT 2015
Keywords
Authenticated encryptionpolynomial hashingtwisted polynomial ring (Ore ring)weak keysGCMPOETJuliusCOBRA
Contact author(s)
moh ahm abdelraheem @ gmail com
History
2017-04-26: revised
2015-12-23: received
See all versions
Short URL
https://ia.cr/2015/1224
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1224,
      author = {Mohamed Ahmed Abdelraheem and Peter Beelen and Andrey Bogdanov and Elmar Tischhauser},
      title = {Twisted Polynomials and Forgery Attacks on GCM},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1224},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1224}},
      url = {https://eprint.iacr.org/2015/1224}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.