You are looking at a specific version 20140115:152424 of this paper. See the latest version.

Paper 2013/144

On Weak Keys and Forgery Attacks against Polynomial-based MAC Schemes

Gordon Procter and Carlos Cid

Abstract

Universal hash functions are commonly used primitives for fast and secure message authentication in the form of Message Authentication Codes (MACs) or Authenticated Encryption with Associated Data (AEAD) schemes. These schemes are widely used and standardised, the most well known being McGrew and Viega's Galois/Counter Mode (GCM). In this paper we identify some properties of hash functions based on polynomial evaluation that arise from the underlying algebraic structure. As a result we are able to describe a general forgery attack, of which Saarinen's cycling attack from FSE 2012 is a special case. Our attack removes the requirement for long messages and applies regardless of the field in which the hash function is evaluated. Furthermore we provide a common description of all published attacks against GCM, by showing that the existing attacks are the result of these algebraic properties of the polynomial-based hash function. We also greatly expand the number of known weak GCM keys and show that almost every subset of the keyspace is a weak key class. Finally, we demonstrate that these algebraic properties and corresponding attacks are highly relevant to GCM/2+, a variant of GCM designed to increase the efficiency in software.

Note: Final version, to appear in the Journal of Cryptology. A short version of this paper was presented at Fast Software Encryption 2013.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. A short version of this paper was presented at Fast Software Encryption 2013
Keywords
Universal HashingMACGaloisCounter ModeCycling AttacksWeak Keys
Contact author(s)
gordon procter 2011 @ rhul ac uk
History
2014-01-15: last of 2 revisions
2013-03-13: received
See all versions
Short URL
https://ia.cr/2013/144
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.