Paper 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.
Note: Fixed typos and improved explanation
Metadata
- Available format(s)
-
PDF
- Publication info
- Published by the IACR in EUROCRYPT 2018
- Keywords
- forgeryWegman-CarterauthenticatorMACGCMuniversal hashpolynomial
- Contact author(s)
-
atul luykx @ esat kuleuven be
bart preneel @ esat kuleuven be - History
- 2018-04-27: revised
- 2018-02-11: received
- See all versions
- Short URL
- https://ia.cr/2018/166
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2018/166,
author = {Atul Luykx and Bart Preneel},
title = {Optimal Forgeries Against Polynomial-Based {MACs} and {GCM}},
howpublished = {Cryptology {ePrint} Archive, Paper 2018/166},
year = {2018},
url = {https://eprint.iacr.org/2018/166}
}
