Breaking AES GCM part 2

In the first part I discussed some background on why AES GCM exists. GCM stands for Galois Counter Mode. Now we will take a dive into the Galois part!

Galois Field

Galois field, or finite field is a set in which the basic math operations are defined - addition, subtraction, multiplication and division. There is obviously a lot of rules for a field, but a major one is that the field must be isomorphic, i.e all elements in the field must have an inverse. Therefore Galois Fields are only defined with the order of (number of elements) p. Where p is a prime or a prime power, p^k, where k is a positive integer.

GCM and Galois

GCM works in GF(2^128) with the irreducible polynom.


In a Galois Field the irreducible polynom is like a prime number, i.e it has no factors (in that field).

Here is a python implementation of addition, multiplication and division in GF(2^k).

# Returns the degree of the polynomial
def deg(a):
    deg = len(bin(a)[2:])-1
    return deg

# Add and subtract is the same. Since it's GF(2^k)
def add(a,b):
    return a^b

def divmod(a, b):
    q, r = 0, a

    while deg(r) >= deg(b):
        d = deg(r) - deg(b)
        q = q ^ (1 << d)
        r = r ^ (b << d)

    return q, r

# Multiplicative over GF(2^k)
def gf_mul(a,b,m):
    # Peasant multiplication from wikipedia
    p = 0
    while a > 0:
        if a & 1:
            p = p^b
        a = a >> 1
        b = b << 1
	# Modulus the polynomial m
        if deg(b) == deg(m):
            b = b^m

    return p

Now when we can do math in GF(2^k), let’s implement the GHASH


  1. Pick the MAC secret. Which is a block of zero bytes encrypted with your AES key.

  2. Zero pad the ciphertext and additional data block by block, so it’s divisible by the block length (AES-128=16). Then concatenate the blocks.

  3. Add a block which concatenates the bit length of the ciphertext and AD.

  4. For each of the concatenated blocks, do:

tag += block
tag *= MAC secret
  1. Mask the tag with a nonce-derived secret
mask = AES(nonce || 1)
tag += mask

Now you have derived a hash from the ciphertext, additional data, nonce and AES-key. Cool!

Here’s my GHASH implemenation in Python3.

import struct
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes, bytes_to_long

# The code shown above...
from galois import *

# GF(2^128)
# p = x^128+x^7+x^2+x+1

def convert_to_field_element(a):
    p = 340282366920938463463374607431768211591
    if deg(a) >= deg(p):
        return a^p
        return a

class GHASH():
    def __init__(self, K, nonce, CT, AD=None):
        self.K = K
        self.nonce = nonce
        self.CT = CT
	self.AD = AD
	# MAC secret
        self.H = convert_to_field_element(bytes_to_long(self.E_K(b'\x00'*AES.block_size)))
        # Calculate Length block
        AD_len = 0 if AD==None else len(AD)
        len_block = struct.pack('<Q', AD_len*8)+struct.pack('<Q', len(CT)*8)
        # Pad CT and AD :-)
        # Concatenate stuff = self.CT+len_block if self.AD == None else self.AD+self.CT+len_block

    def E_K(self, data):
        cipher =
        return cipher.encrypt(data)
    def pad(self):
        if len(self.CT) % AES.block_size != 0:
            self.CT = self.CT+b'\x00'*(AES.block_size-(len(self.CT) % AES.block_size))
        if self.AD != None:
            if len(self.AD) % AES.block_size != 0:
                self.AD = self.AD+b'\x00'*(AES.block_size-(len(self.AD) % AES.block_size))

    def round(self):
        g = 0
        for b in
            b = convert_to_field_element(bytes_to_long(b))
            g ^= b
            g = gf_mul(g,self.H,340282366920938463463374607431768211591)

        return g

    def derive(self):
        # Calculate the rounds
        g = self.round()

        # Mask tag
        s = bytes_to_long(self.E_K(self.nonce+struct.pack('<i',4)))
        self.tag = g^s

        return self.tag

Tag structure

Basically what the tag looks like is this (MS is MAC secret):

tag = (((((block1*MS)+block2)*MS)+len)*MS)+mask

Which becomes

tag = block1*MS^3+block2*MS^2+len*MS+mask


Now we know how the tag is calculated. Say that we accidentally repeat a nonce using the same AES key. What could possibly go wrong? Well, let’s look at it.

tag1 = b1*MS^3+b2*MS^2+len1*MS+mask

tag2 = d1*MS^3+d2*MS^2+len2*MS+mask

What do they have in common? MS, of course, since it’s AES(key, ‘\x00’*block_length). What else?

The mask!

Since we work in GF(2^k) where addition and subtraction is the same, we can add the two tags together to remove the mask.

tag1+2 = (b1^d1)*MS^3+(b2^d2)*MS^2+(len1^len2)*MS

The validation of the tag is that we plug in the mac secret into the polynomial and check if the result equals zero. So the mac secret is a root to tag.

tag = f(MS) = 0

The attack is then to factor the polynomial tag1+2 to find the mac secret. If we find the MAC secret, we can fake the authentication tags for all ciphertexts under the same AES key.

alt text

Next post will be to implement AES GCM, factoring tag1+2 and successfully fake a ciphertext.