Analysis of Authenticated Encryption with Polynomial Evaluation MAC

Abstract

Authenticated Encryption (AE) is a block cipher mode of operation which simultaneously provides confidentiality, integrity and authenticity assurances on the data in a single processing step. In this thesis, we mainly consider the integrity part and focus on the polynomial evaluation MAC, where the authentication tag is derived from the polynomial evaluation over a finite field. The examples which use the authentication tag of this type are Poly1305, GCM(Galois/Counter mode), and CWC(Carter Wegman + CTR mode). Among these, GCM which is standardized by a NIST(National Institute of Standards and Technology), is being highly recommended to many network protocols.

In recent, the cycling attack for the authentication tag of GCM, was introduced. Since GCM uses a finite filed of $GF(2^{128})$, the order of multiplicative group becomes $2^{128}-1$, but this is factorized into nine factors. This leads to a cycle of short length for some weak keys and the attacker can modify the corresponding coefficients i.e. associated data and the ciphertext, with same value of tag. The success probability for this attack is impractically low but sufficiently higher than the expected value, $2^{128}$ where the block length of cipher is 128 bits.

We analyze the cycling attack. We compute the success probability of the attack when the order of multiplicative group $N$ and the number of authenticated message blocks $L$ are given. We also consider the optimal choices for the order of cycles with minimal times of trial. These are analyzed on the general polynomial evaluation MACs (Message Authentication Code). And then we focus on GCM and the application on the several network protocols for security including SSH (Secure SHell) and IPSec (Internet Protocol Security). We also suggest how we can avoid the cycling attack. At the last chapter, we apply GCM to the meter reading transmission protocol for Power Line Communication (PLC) as a tool for efficient authenticated encryption mechanism. By these researches we contribute to the way of applying polynomial evaluation MACs securely on the practical protocols.