Twisted Polynomials and Forgery Attacks on GCM

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

doi:10.1007/978-3-662-46800-5_29

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 proceeding › Article in proceedings › Research › peer-review

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 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 language	English
Title of host publication	Advances in Cryptology – EUROCRYPT 2015 : Proceedings of the 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Part 1
Editors	Elisabeth v, Marc Fischlin
Publisher	Springer
Publication date	2015
Pages	762-786
ISBN (Print)	978-3-662-46799-2
ISBN (Electronic)	978-3-662-46800-5
DOIs	https://doi.org/10.1007/978-3-662-46800-5_29
Publication status	Published - 2015
Event	34th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2015) - Sofia, Bulgaria Duration: 26 Apr 2015 → 30 Apr 2015 Conference number: 34 https://www.cosic.esat.kuleuven.be/eurocrypt_2015/

Conference

Conference	34th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2015)
Number	34
Country/Territory	Bulgaria
City	Sofia
Period	26/04/2015 → 30/04/2015
Internet address	https://www.cosic.esat.kuleuven.be/eurocrypt_2015/

Series	Lecture Notes in Computer Science
Volume	9056
ISSN	0302-9743

Keywords

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

Access to Document

10.1007/978-3-662-46800-5_29

OpenUrl availability

Full text

Cite this

Abdelraheem, M. A. A. M. A., Beelen, P., Bogdanov, A., & Tischhauser, E. W. (2015). Twisted Polynomials and Forgery Attacks on GCM. In E. v, & M. Fischlin (Eds.), Advances in Cryptology – EUROCRYPT 2015: Proceedings of the 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Part 1 (pp. 762-786). Springer. https://doi.org/10.1007/978-3-662-46800-5_29

Abdelraheem, Mohamed Ahmed A. M. A. ; Beelen, Peter ; Bogdanov, Andrey et al. / Twisted Polynomials and Forgery Attacks on GCM. Advances in Cryptology – EUROCRYPT 2015: Proceedings of the 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Part 1. editor / Elisabeth v ; Marc Fischlin. Springer, 2015. pp. 762-786 (Lecture Notes in Computer Science, Vol. 9056).

@inproceedings{87c01f0148d44a9a90ec8daa5f495ecd,

title = "Twisted Polynomials and Forgery Attacks on GCM",

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 forgery polynomials having disjoint sets of roots, with many roots (“weak keys”) each. Constructing such polynomials beyond na{\"i}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.",

keywords = "Authenticated encryption, Polynomial hashing, Twisted polynomial ring (Ore ring), Weak keys, GCM, POET",

author = "Abdelraheem, {Mohamed Ahmed A. M. A.} and Peter Beelen and Andrey Bogdanov and Tischhauser, {Elmar Wolfgang}",

year = "2015",

doi = "10.1007/978-3-662-46800-5_29",

language = "English",

isbn = "978-3-662-46799-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "762--786",

editor = "v, {Elisabeth } and Fischlin, {Marc }",

booktitle = "Advances in Cryptology – EUROCRYPT 2015",

note = "34th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2015), EUROCRYPT ; Conference date: 26-04-2015 Through 30-04-2015",

url = "https://www.cosic.esat.kuleuven.be/eurocrypt_2015/",

}

Abdelraheem, MAAMA, Beelen, P, Bogdanov, A & Tischhauser, EW 2015, Twisted Polynomials and Forgery Attacks on GCM. in E v & M Fischlin (eds), Advances in Cryptology – EUROCRYPT 2015: Proceedings of the 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Part 1. Springer, Lecture Notes in Computer Science, vol. 9056, pp. 762-786, 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2015), Sofia, Bulgaria, 26/04/2015. https://doi.org/10.1007/978-3-662-46800-5_29

Twisted Polynomials and Forgery Attacks on GCM. / Abdelraheem, Mohamed Ahmed A. M. A.; Beelen, Peter ; Bogdanov, Andrey et al.
Advances in Cryptology – EUROCRYPT 2015: Proceedings of the 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Part 1. ed. / Elisabeth v; Marc Fischlin. Springer, 2015. p. 762-786 (Lecture Notes in Computer Science, Vol. 9056).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Twisted Polynomials and Forgery Attacks on GCM

AU - Abdelraheem, Mohamed Ahmed A. M. A.

AU - Beelen, Peter

AU - Bogdanov, Andrey

AU - Tischhauser, Elmar Wolfgang

N1 - Conference code: 34

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

KW - Authenticated encryption

KW - Polynomial hashing

KW - Twisted polynomial ring (Ore ring)

KW - Weak keys

KW - GCM

KW - POET

U2 - 10.1007/978-3-662-46800-5_29

DO - 10.1007/978-3-662-46800-5_29

M3 - Article in proceedings

SN - 978-3-662-46799-2

T3 - Lecture Notes in Computer Science

SP - 762

EP - 786

BT - Advances in Cryptology – EUROCRYPT 2015

A2 - v, Elisabeth

A2 - Fischlin, Marc

PB - Springer

T2 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2015)

Y2 - 26 April 2015 through 30 April 2015

ER -

Abdelraheem MAAMA, Beelen P, Bogdanov A, Tischhauser EW. Twisted Polynomials and Forgery Attacks on GCM. In v E, Fischlin M, editors, Advances in Cryptology – EUROCRYPT 2015: Proceedings of the 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Part 1. Springer. 2015. p. 762-786. (Lecture Notes in Computer Science, Vol. 9056). doi: 10.1007/978-3-662-46800-5_29

Twisted Polynomials and Forgery Attacks on GCM

Abstract

Conference

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this