aes-gcm-authentication.ipynb

Kernel: SageMath 10.0

Connect: AES-GCM Authenticated Encryption

Module 03 | Real-World Connections

AES-GCM combines AES encryption with Galois field authentication --- two fields, one protocol.

Introduction

Encryption alone is not enough. If an attacker can modify the ciphertext and the receiver decrypts the modified version without detecting the tampering, the attacker wins. This is the malleability problem.

AES-GCM (Galois/Counter Mode) solves this by combining:

1. AES-CTR for encryption (confidentiality)

2. GHASH for authentication (integrity)

The "G" in GCM stands for Galois --- the authentication tag is computed using polynomial evaluation in GF($2^{128}$). This is the same kind of Galois field arithmetic from Module 03, just in a bigger field.

The GCM Construction

AES-GCM processes a message in three phases:

1. Derive the hash key: $H = \text{AES}_K(0^{128})$ (encrypt a block of zeros)

2. Encrypt with AES-CTR: $C_i = P_i \oplus \text{AES}_K(\text{IV} \| \text{counter}_i)$

3. Authenticate with GHASH: compute a polynomial in GF($2^{128}$) evaluated at $H$

The output is $(C_1, C_2, \ldots, C_n, T)$ where $T$ is the 128-bit authentication tag.

$$T = \text{GHASH}_H(A, C) \oplus \text{AES}_K(\text{IV} \| 0^{31} \| 1)$$

where $A$ is optional associated data (authenticated but not encrypted).

# === Setup: AES primitives from Module 03 ===
R.<x> = GF(2)[]
F8.<a> = GF(2^8, modulus=x^8 + x^4 + x^3 + x + 1)

# Build S-box (same as Module 03d)
def byte_to_gf8(b):
    return sum(GF(2)((b >> i) & 1) * a^i for i in range(8))

def gf8_to_byte(elem):
    p = elem.polynomial()
    return sum(int(p[i]) << i for i in range(8))

A_mat = matrix(GF(2), [
    [1,0,0,0,1,1,1,1],[1,1,0,0,0,1,1,1],[1,1,1,0,0,0,1,1],[1,1,1,1,0,0,0,1],
    [1,1,1,1,1,0,0,0],[0,1,1,1,1,1,0,0],[0,0,1,1,1,1,1,0],[0,0,0,1,1,1,1,1]
])
c_vec = vector(GF(2), [(0x63 >> i) & 1 for i in range(8)])

SBOX = [0] * 256
for b in range(256):
    if b == 0:
        inv_bits = vector(GF(2), [0]*8)
    else:
        inv_byte = gf8_to_byte(byte_to_gf8(b)^(-1))
        inv_bits = vector(GF(2), [(inv_byte >> i) & 1 for i in range(8)])
    result_bits = A_mat * inv_bits + c_vec
    SBOX[b] = sum(int(result_bits[i]) << i for i in range(8))

def xtime(b):
    r = b << 1
    if r & 0x100: r ^^= 0x11B
    return r & 0xFF

def gf256_mul(a_val, b_val):
    result = 0; temp = a_val
    for i in range(8):
        if b_val & (1 << i): result ^^= temp
        temp = xtime(temp)
    return result

# Simplified AES-128 round (for toy demonstration)
MC = [[0x02,0x03,0x01,0x01],[0x01,0x02,0x03,0x01],
      [0x01,0x01,0x02,0x03],[0x03,0x01,0x01,0x02]]

def sub_bytes(s): return [[SBOX[s[r][c]] for c in range(4)] for r in range(4)]
def shift_rows(s):
    res = [row[:] for row in s]
    for i in range(1,4): res[i] = s[i][i:] + s[i][:i]
    return res
def mix_columns(s):
    res = [[0]*4 for _ in range(4)]
    for col in range(4):
        for row in range(4):
            for k in range(4): res[row][col] ^^= gf256_mul(MC[row][k], s[k][col])
    return res
def add_rk(s, rk): return [[s[r][c] ^^ rk[r][c] for c in range(4)] for r in range(4)]
def bytes_to_state(d):
    s = [[0]*4 for _ in range(4)]
    for i in range(16): s[i%4][i//4] = d[i]
    return s
def state_to_bytes(s): return [s[i%4][i//4] for i in range(16)]

print('AES primitives loaded (from Module 03).')
print(f'S-box[0x53] = 0x{SBOX[0x53]:02X}')

GHASH: Polynomial Evaluation in GF($2^{128}$)

The authentication in GCM uses the field $\text{GF}(2^{128})$ constructed as:

$$\text{GF}(2^{128}) = \text{GF}(2)[x] \;/\; \langle x^{128} + x^7 + x^2 + x + 1 \rangle$$

This is the same construction as GF($2^8$) in Module 03, just with a degree-128 irreducible polynomial instead of degree 8.

	Module 03 (AES bytes)	GCM (auth tags)
Field	GF($2^8$)	GF($2^{128}$)
Modulus	$x^8+x^4+x^3+x+1$	$x^{128}+x^7+x^2+x+1$
Element =	8-bit byte	128-bit block
Addition =	XOR of bytes	XOR of blocks
Multiplication =	polynomial product mod $m(x)$	polynomial product mod $p(x)$

# Build GF(2^128) for GHASH
# The GCM irreducible polynomial: x^128 + x^7 + x^2 + x + 1
S.<y> = GF(2)[]
p128 = y^128 + y^7 + y^2 + y + 1
print(f'GCM polynomial: {p128}')
print(f'Irreducible? {p128.is_irreducible()}')
print()

# Build the field
F128.<g> = GF(2^128, modulus=p128)
print(f'GF(2^128) constructed.')
print(f'Field order: 2^128 = {2^128}')
print(f'Number of nonzero elements: 2^128 - 1 = {2^128 - 1}')
print()

# Compare with Module 03's GF(2^8)
print('Comparison:')
print(f'  GF(2^8):   {2^8} elements, each element = 8 bits (1 byte)')
print(f'  GF(2^128): {2^128} elements, each element = 128 bits (16 bytes = 1 AES block)')
print()
print('Same algebraic structure, different size. Addition = XOR, multiplication = ')
print('polynomial product mod an irreducible polynomial.')

# Helper: convert a list of 16 bytes to a GF(2^128) element and back
def bytes_to_gf128(byte_list):
    """Convert 16 bytes to a GF(2^128) element (MSB first, as per GCM spec)."""
    bits = []
    for b in byte_list:
        for i in range(7, -1, -1):
            bits.append(GF(2)((b >> i) & 1))
    return sum(bits[i] * g^i for i in range(128))

def gf128_to_bytes(elem):
    """Convert a GF(2^128) element back to 16 bytes."""
    p = elem.polynomial()
    result = [0] * 16
    for i in range(128):
        byte_idx = i // 8
        bit_idx = 7 - (i % 8)
        if p[i] == 1:
            result[byte_idx] |= (1 << bit_idx)
    return result

# Test: round-trip
test_bytes = [0x01, 0x23, 0x45, 0x67, 0x89, 0xAB, 0xCD, 0xEF,
              0xFE, 0xDC, 0xBA, 0x98, 0x76, 0x54, 0x32, 0x10]
elem = bytes_to_gf128(test_bytes)
recovered = gf128_to_bytes(elem)
print(f'Input:     {" ".join(f"{b:02X}" for b in test_bytes)}')
print(f'Recovered: {" ".join(f"{b:02X}" for b in recovered)}')
print(f'Round-trip correct: {test_bytes == recovered}')
print()

# Demonstrate GF(2^128) multiplication
a_bytes = [0x00]*15 + [0x03]  # A small element for clarity
b_bytes = [0x00]*15 + [0x05]
a_elem = bytes_to_gf128(a_bytes)
b_elem = bytes_to_gf128(b_bytes)
prod = a_elem * b_elem
prod_bytes = gf128_to_bytes(prod)
print(f'GF(2^128) multiplication:')
print(f'  A = ...03 (as polynomial: {a_elem})')
print(f'  B = ...05 (as polynomial: {b_elem})')
print(f'  A * B = {" ".join(f"{b:02X}" for b in prod_bytes)}')

Step-by-Step Toy Example: AES-GCM

Let's walk through a complete AES-GCM encryption on a toy-sized message. We'll use a simplified AES (just a single round for demonstration) so the focus stays on the GCM structure.

Phase 1: Derive the Hash Key $H$

Encrypt a block of zeros: $H = \text{AES}_K(0^{128})$.

# For the toy example, we'll use the S-box as a simplified "block cipher"
# to keep things transparent. In real GCM, this would be full AES-128.

def toy_aes_encrypt(block_16bytes, key_16bytes):
    """Simplified AES: one round only (for pedagogical clarity)."""
    state = bytes_to_state(block_16bytes)
    rk = bytes_to_state(key_16bytes)
    state = add_rk(state, rk)      # AddRoundKey (pre-whitening)
    state = sub_bytes(state)         # SubBytes
    state = shift_rows(state)        # ShiftRows
    state = mix_columns(state)       # MixColumns
    state = add_rk(state, rk)        # AddRoundKey (simplified: reuse key)
    return state_to_bytes(state)

# Key and IV
KEY = [0x2B, 0x7E, 0x15, 0x16, 0x28, 0xAE, 0xD2, 0xA6,
       0xAB, 0xF7, 0x15, 0x88, 0x09, 0xCF, 0x4F, 0x3C]
IV  = [0xCA, 0xFE, 0xBA, 0xBE, 0xFA, 0xCE, 0xDB, 0xAD,
       0xDE, 0xCA, 0xF8, 0x88]

# Phase 1: Derive hash key H = AES_K(0...0)
zero_block = [0x00] * 16
H_bytes = toy_aes_encrypt(zero_block, KEY)
H = bytes_to_gf128(H_bytes)

print('Phase 1: Derive hash key')
print(f'  H = AES_K(0) = {" ".join(f"{b:02X}" for b in H_bytes)}')
print(f'  H as GF(2^128) element: (128-bit value, used in GHASH)')

# Phase 2: Encrypt with AES-CTR

# Build counter blocks: IV || counter (4 bytes)
def make_counter_block(iv_12bytes, counter):
    """IV (12 bytes) || counter (4 bytes, big-endian)."""
    return iv_12bytes + [(counter >> 24) & 0xFF, (counter >> 16) & 0xFF,
                         (counter >> 8) & 0xFF, counter & 0xFF]

# Our plaintext: two 16-byte blocks
plaintext = [0x48, 0x65, 0x6C, 0x6C, 0x6F, 0x20, 0x57, 0x6F,  # "Hello Wo"
             0x72, 0x6C, 0x64, 0x21, 0x00, 0x00, 0x00, 0x00,  # "rld!...."
             0x54, 0x68, 0x69, 0x73, 0x20, 0x69, 0x73, 0x20,  # "This is "
             0x47, 0x43, 0x4D, 0x21, 0x00, 0x00, 0x00, 0x00]  # "GCM!...."

# CTR encryption: C_i = P_i XOR AES_K(IV || counter_i)
# Counter starts at 2 (counter=1 is reserved for the final tag encryption)
ciphertext = []
num_blocks = len(plaintext) // 16

print('Phase 2: AES-CTR Encryption')
for i in range(num_blocks):
    ctr_block = make_counter_block(IV, i + 2)  # counter starts at 2
    keystream = toy_aes_encrypt(ctr_block, KEY)
    
    pt_block = plaintext[i*16:(i+1)*16]
    ct_block = [p ^^ k for p, k in zip(pt_block, keystream)]
    ciphertext.extend(ct_block)
    
    print(f'  Block {i+1}:')
    print(f'    Counter: {" ".join(f"{b:02X}" for b in ctr_block)}')
    print(f'    PT:      {" ".join(f"{b:02X}" for b in pt_block)}')
    print(f'    CT:      {" ".join(f"{b:02X}" for b in ct_block)}')

print()
print(f'Full ciphertext ({len(ciphertext)} bytes):')
print(f'  {" ".join(f"{b:02X}" for b in ciphertext)}')

Phase 3: GHASH Authentication

GHASH computes a polynomial in GF($2^{128}$):

$$\text{GHASH}_H(X_1, X_2, \ldots, X_m) = X_1 \cdot H^m \oplus X_2 \cdot H^{m-1} \oplus \cdots \oplus X_m \cdot H$$

This is polynomial evaluation --- the same concept as evaluating $f(x) = a_n x^n + \cdots + a_1 x + a_0$, but in GF($2^{128}$) instead of the integers.

The inputs $X_i$ are the ciphertext blocks (and optionally, associated data blocks), plus a final length block.

# Phase 3: GHASH
# GHASH_H(X_1, ..., X_m) = X_1 * H^m + X_2 * H^(m-1) + ... + X_m * H
# Equivalently, using Horner's method: ((X_1 * H + X_2) * H + X_3) * H + ...

def ghash(h_elem, data_blocks):
    """Compute GHASH using Horner's method in GF(2^128).
    data_blocks: list of 16-byte lists."""
    result = F128(0)
    for block in data_blocks:
        x_i = bytes_to_gf128(block)
        result = (result + x_i) * h_elem
    return result

# Build GHASH inputs:
# 1. Associated data blocks (we'll use empty AAD for simplicity)
# 2. Ciphertext blocks
# 3. Length block: len(AAD) || len(C) in bits, each as 64-bit big-endian

aad = []  # no associated data
ct_blocks = [ciphertext[i*16:(i+1)*16] for i in range(num_blocks)]

# Length block: 0 bits of AAD, len(ciphertext)*8 bits of ciphertext
aad_len_bits = 0
ct_len_bits = len(ciphertext) * 8
len_block = [0]*8  # AAD length = 0
for i in range(7, -1, -1):
    len_block.append((ct_len_bits >> (8*i)) & 0xFF)
len_block = len_block[:16]

# GHASH input: AAD blocks (none) + CT blocks + length block
ghash_input = ct_blocks + [len_block]

print('GHASH computation (polynomial evaluation in GF(2^128)):')
print()
for i, block in enumerate(ghash_input):
    label = f'C_{i+1}' if i < len(ct_blocks) else 'len_block'
    print(f'  X_{i+1} ({label}): {" ".join(f"{b:02X}" for b in block)}')
print()

# Compute GHASH step by step
print('Horner\'s method:')
accum = F128(0)
for i, block in enumerate(ghash_input):
    x_i = bytes_to_gf128(block)
    accum = (accum + x_i) * H
    accum_bytes = gf128_to_bytes(accum)
    print(f'  Step {i+1}: ({" ".join(f"{b:02X}" for b in accum_bytes[:4])}...)')

ghash_result = accum
ghash_bytes = gf128_to_bytes(ghash_result)
print()
print(f'GHASH result: {" ".join(f"{b:02X}" for b in ghash_bytes)}')

# Final tag: T = GHASH_H(A, C) XOR AES_K(IV || 0...01)
ctr0_block = make_counter_block(IV, 1)  # counter = 1 for the tag
encrypted_ctr0 = toy_aes_encrypt(ctr0_block, KEY)

tag = [g ^^ e for g, e in zip(ghash_bytes, encrypted_ctr0)]

print('=== Complete AES-GCM Output ===')
print()
print(f'Ciphertext: {" ".join(f"{b:02X}" for b in ciphertext)}')
print(f'Auth Tag:   {" ".join(f"{b:02X}" for b in tag)}')
print()
print('The tag is a 128-bit fingerprint of the ciphertext.')
print('If ANY bit of the ciphertext is modified, the tag will not match on decryption.')

Why Authenticated Encryption Matters

Without the authentication tag, an attacker can flip ciphertext bits and the decryption will succeed, producing a corrupted plaintext that the receiver accepts as genuine.

In CTR mode, flipping bit $j$ of ciphertext block $C_i$ flips bit $j$ of the corresponding plaintext block $P_i$. This is called malleability --- the attacker can make targeted changes to the plaintext without knowing the key.

The GHASH tag detects this because changing even one ciphertext bit changes the polynomial inputs, producing a completely different tag.

# Demonstrate bit-flipping attack on CTR (without authentication)
print('=== Bit-Flipping Attack on CTR Without Authentication ===')
print()

# Original plaintext
print(f'Original PT: {bytes(plaintext[:16])}')

# Attacker flips one bit in the ciphertext
tampered_ct = ciphertext[:]
tampered_ct[0] ^^= 0x20  # flip bit 5 of first byte: 'H' (0x48) -> 'h' (0x68)

# Decrypt the tampered ciphertext (CTR decryption = same as encryption)
tampered_pt = []
for i in range(num_blocks):
    ctr_block = make_counter_block(IV, i + 2)
    keystream = toy_aes_encrypt(ctr_block, KEY)
    ct_block = tampered_ct[i*16:(i+1)*16]
    pt_block = [c ^^ k for c, k in zip(ct_block, keystream)]
    tampered_pt.extend(pt_block)

print(f'Tampered PT: {bytes(tampered_pt[:16])}')
print()
print(f'The attacker changed "H" to "h" without knowing the key!')
print(f'CTR XOR property: flipping ciphertext bit = flipping plaintext bit.')
print()

# But GHASH catches the tampering
tampered_ct_blocks = [tampered_ct[i*16:(i+1)*16] for i in range(num_blocks)]
tampered_ghash_input = tampered_ct_blocks + [len_block]
tampered_ghash_result = ghash(H, tampered_ghash_input)
tampered_ghash_bytes = gf128_to_bytes(tampered_ghash_result)
tampered_tag = [tg ^^ e for tg, e in zip(tampered_ghash_bytes, encrypted_ctr0)]

print(f'Original tag:  {" ".join(f"{b:02X}" for b in tag)}')
print(f'Tampered tag:  {" ".join(f"{b:02X}" for b in tampered_tag)}')
print(f'Tags match: {tag == tampered_tag}')
print()
print('GCM detects the tampering! The receiver rejects the message.')

Concept Map: Two Galois Fields, One Protocol

Component	Field	Role
AES SubBytes	GF($2^8$)	Byte-level non-linearity via field inversion
AES MixColumns	GF($2^8$)	Column-level diffusion via matrix multiplication
AES-CTR keystream	GF($2^8$) internally	Generates pseudo-random blocks for encryption
GHASH	GF($2^{128}$)	Computes authentication tag via polynomial evaluation
Tag computation	Both	AES encrypts the GHASH output to produce the final tag

The field arithmetic from Module 03 appears at two different scales:

• GF($2^8$): inside AES, operating on individual bytes

• GF($2^{128}$): in GHASH, operating on entire 128-bit blocks

Both are constructed the same way: $\text{GF}(2)[x] / \langle \text{irreducible polynomial} \rangle$.

# Side-by-side: GF(2^8) vs GF(2^128)
print('=== GF(2^8) vs GF(2^128): Same Construction, Different Scale ===')
print()

# GF(2^8)
m8 = x^8 + x^4 + x^3 + x + 1
a8 = byte_to_gf8(0x57)
b8 = byte_to_gf8(0x83)
prod8 = a8 * b8
inv8 = a8^(-1)
print(f'GF(2^8):')
print(f'  Modulus: {m8}')
print(f'  0x57 * 0x83 = 0x{gf8_to_byte(prod8):02X}')
print(f'  0x57^(-1)   = 0x{gf8_to_byte(inv8):02X}')
print(f'  Verify: 0x57 * 0x{gf8_to_byte(inv8):02X} = 0x{gf8_to_byte(a8 * inv8):02X}')
print()

# GF(2^128)
print(f'GF(2^128):')
print(f'  Modulus: {p128}')
a128 = bytes_to_gf128([0x00]*14 + [0x00, 0x57])
b128 = bytes_to_gf128([0x00]*14 + [0x00, 0x83])
prod128 = a128 * b128
inv128 = a128^(-1)
prod128_bytes = gf128_to_bytes(prod128)
inv128_bytes = gf128_to_bytes(inv128)
print(f'  ...0057 * ...0083 = ...{" ".join(f"{b:02X}" for b in prod128_bytes[-2:])}')
print(f'  ...0057^(-1)      = {" ".join(f"{b:02X}" for b in inv128_bytes)}')
verify = a128 * inv128
print(f'  Verify: ...0057 * inv = {" ".join(f"{b:02X}" for b in gf128_to_bytes(verify)[-2:])}')
print()
print('Same operations, same structure, different polynomial degree.')

Summary

Concept	Key idea
AES-GCM	The gold standard for authenticated encryption in TLS 1.3, combining AES-CTR for confidentiality with GHASH for integrity
GHASH	Polynomial evaluation in GF($2^{128}$), constructed the same way as GF($2^8$) but with a degree-128 irreducible polynomial
Two Galois fields	AES-CTR uses GF($2^8$) internally (S-box and MixColumns), while GHASH uses GF($2^{128}$) for authentication
Malleability without auth	CTR mode alone is malleable. Flipping a ciphertext bit flips the corresponding plaintext bit, and the receiver cannot detect it
Tag detects tampering	The GHASH tag catches any modification, because changing even one ciphertext bit produces a completely different polynomial evaluation
Same construction, different scale	GF($2^8$) and GF($2^{128}$) are both built as GF(2)$[x] / \langle \text{irreducible polynomial} \rangle$, with the same operations at different sizes

The field theory from Module 03 is not just about AES bytes. It extends to 128-bit blocks, authentication tags, and the security of every HTTPS connection.

---

Back to Module 03: Galois Fields and AES