AES-GCM, in depth: counter mode plus GHASH, the GF(2^128) multiply, a tested implementation, nonce rules, what nonce reuse breaks and how to use it safely

The AEAD contract

An AEAD has two functions. Seal(K, N, A, P) takes a key, a nonce, associated data and plaintext and returns ciphertext plus a tag. Open(K, N, A, C, T) returns the plaintext only if the tag verifies over exactly that nonce, associated data and ciphertext; otherwise it fails and returns nothing. Associated data is authenticated but not encrypted: a record header, row ID, tenant ID or key version the receiver must read in clear.

The caller owns one precondition: a (key, nonce) pair must never be used for two different messages. GCM does not detect a repeat, and everything about operational safety comes back to it.

The construction, step by step

With the standard 96-bit nonce, GCM runs as follows:

1. Derive the hash key H = AES_K(0^128), one block encryption of zeros.
2. Form the pre-counter block J0 = N || 0x00000001. Other nonce lengths are hashed through GHASH first; use 96 bits.
3. Encrypt: for block i, compute keystream AES_K(inc32^i(J0)) starting at i = 1 and XOR it with the plaintext. inc32 increments only the low 32 bits.
4. Authenticate: run GHASH over the zero-padded AAD, the zero-padded ciphertext and one final block holding the bit lengths of each as two 64-bit integers.
5. Tag: T = AES_K(J0) XOR GHASH, truncated to the tag length (128 bits unless you have a very good reason).

Counter 1 is reserved for the tag mask, so keystream starts at counter 2. Because the counter field is 32 bits, one message can use at most 2^32 - 2 keystream blocks, which is where the per-message limit of 2^39 - 256 bits (just under 64 GiB) comes from. Every block of both paths is independent, which is why GCM parallelises and pipelines so well in hardware.

GHASH and the field GF(2^128)

GHASH treats each 16-byte block as an element of the finite field GF(2^128), defined by the polynomial x^128 + x^7 + x^2 + x + 1. Addition is XOR. Multiplication is carry-less multiplication of polynomials followed by reduction modulo that polynomial. GHASH evaluates a polynomial in H whose coefficients are the data blocks: for blocks X1..Xm, the result is X1 H^m + X2 H^(m-1) + ... + Xm H, computed with Horner's rule as Y = (Y XOR Xi) * H.

One detail trips up everyone who implements it: GCM uses a reflected bit order. The leftmost bit of the block is the coefficient of x^0, so the reduction constant appears as 0xE1 followed by fifteen zero bytes, and the shift goes right instead of left. Get this wrong and your tags will be self-consistent and match no other implementation, which is why test vectors matter.

GHASH is a universal hash: two different inputs collide for a random H with probability at most (number of blocks) / 2^128. Masking it with a fresh AES output per nonce makes a one-time MAC. The word carrying the whole argument is fresh.

A reference implementation

The implementation below is about sixty lines and is meant for reading, not production: it uses the cryptography package only for a raw AES block, does bit-by-bit field multiplication and has no constant-time guarantees. It does have the right shape, including the one property production code must keep: decryption checks the tag, with a constant-time comparison, before it produces a single byte of plaintext.

import hmac, struct
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes

R = 0xE1000000000000000000000000000000   # x^128 + x^7 + x^2 + x + 1, reflected

def gf_mul(x, y):
    """GF(2^128) multiply in GCM bit order (SP 800-38D, Algorithm 1)."""
    z, v = 0, y
    for i in range(127, -1, -1):
        if (x >> i) & 1:
            z ^= v
        v = (v >> 1) ^ R if v & 1 else v >> 1
    return z

def ghash(h, data):
    y = 0
    for i in range(0, len(data), 16):
        y = gf_mul(y ^ int.from_bytes(data[i:i+16], "big"), h)
    return y

def pad16(b):
    return b + b"\x00" * (-len(b) % 16)

def aes_block(key, block):              # teaching only: raw AES on one block
    enc = Cipher(algorithms.AES(key), modes.ECB()).encryptor()
    return enc.update(block) + enc.finalize()

def inc32(cb):
    ctr = (int.from_bytes(cb[12:], "big") + 1) & 0xFFFFFFFF
    return cb[:12] + ctr.to_bytes(4, "big")

def ctr_xor(key, j0, data):
    out, cb = bytearray(), j0
    for i in range(0, len(data), 16):
        cb = inc32(cb)
        out += bytes(a ^ b for a, b in zip(data[i:i+16], aes_block(key, cb)))
    return bytes(out)

def tag_for(key, j0, aad, ct):
    h = int.from_bytes(aes_block(key, bytes(16)), "big")
    lens = struct.pack(">QQ", len(aad) * 8, len(ct) * 8)
    s = ghash(h, pad16(aad) + pad16(ct) + lens)
    return (int.from_bytes(aes_block(key, j0), "big") ^ s).to_bytes(16, "big")

def gcm_encrypt(key, nonce, plaintext, aad=b""):
    assert len(nonce) == 12, "use 96-bit nonces"
    j0 = nonce + b"\x00\x00\x00\x01"
    ct = ctr_xor(key, j0, plaintext)
    return ct, tag_for(key, j0, aad, ct)

class InvalidTag(Exception):
    pass

def gcm_decrypt(key, nonce, ct, tag, aad=b""):
    j0 = nonce + b"\x00\x00\x00\x01"
    if not hmac.compare_digest(tag_for(key, j0, aad, ct), tag):
        raise InvalidTag()             # verify BEFORE producing any plaintext
    return ctr_xor(key, j0, ct)

Test it three ways: the NIST vectors in the next section; a differential test over a few hundred random keys, nonces and lengths (including zero and non-multiples of 16) against AESGCM(key).encrypt(nonce, p, aad), which appends the 16-byte tag; and a negative test that flips one bit of ciphertext, AAD or tag and expects decrypt to raise. All three pass.

Worked example: the NIST test vectors

NIST's original GCM test cases use a 128-bit all-zero key and an all-zero 96-bit nonce. They are small enough to trace and catch most bit-order mistakes immediately.

The empty-message case is instructive. With no AAD and no ciphertext, the lengths block is all zeros, GHASH returns zero, and the tag is just AES_K(J0). If that vector passes and the one-block tag fails, the bug is in GHASH, almost always the bit order or the lengths encoding (bits, not bytes).

Nonces: the rule that cannot bend

There are two sound ways to pick 96-bit nonces under one key.

• Deterministic: a counter, or a fixed per-device field plus a counter, that never repeats. SP 800-38D calls this the deterministic construction. It allows far more messages per key, but the counter must survive crashes, restores from snapshot and cloned VMs. A counter in memory that restarts at zero after a reboot is a nonce reuse bug.
• Random: 12 bytes from the OS CSPRNG per message. Simple and stateless, but birthday collisions limit it: SP 800-38D caps a key at 2^32 invocations when nonces are random, which keeps the collision probability below 2^-32.

TLS 1.3 shows the deterministic pattern done well. RFC 8446 forms each record's nonce by left-padding the 64-bit record sequence number to the IV length and XORing it with a per-direction static IV derived during the handshake, so no nonce is ever transmitted and none can repeat within a connection. Section 5.5 then limits AES-GCM to about 2^24.5 full-size records per key before a KeyUpdate, which keeps the AE safety margin near 2^-57. That limit comes from the block cipher's bounds, not from nonces, and it is a reminder that every key has a budget. The TLS handshake article shows where those keys and IVs come from.

What nonce reuse actually breaks

Reuse a nonce once and two things fail. The obvious one is secrecy: both messages were XORed with the same keystream, so the XOR of the ciphertexts equals the XOR of the plaintexts.

import os
from cryptography.hazmat.primitives.ciphers.aead import AESGCM

aead = AESGCM(AESGCM.generate_key(bit_length=256))
n = os.urandom(12)
p1 = b"transfer $100 to alice"
c1 = aead.encrypt(n, p1, None)
c2 = aead.encrypt(n, b"transfer $999 to mallo", None)   # BUG: same nonce

x = bytes(a ^ b for a, b in zip(c1, c2))      # = p1 XOR p2
print(bytes(a ^ b for a, b in zip(x, p1)))    # attacker who knows p1 reads p2

The worse failure is integrity. Under a repeated nonce, both tags are masked with the same AES_K(J0). XOR the two tags and the mask cancels, leaving the difference of two GHASH polynomials in the unknown H, with coefficients the attacker can read off the wire. Finding the roots of that polynomial yields a short list of candidates for H. This is Joux's "forbidden attack". With H known, the attacker derives the mask from either tag and forges valid tags for any AAD and ciphertext under that nonce. H depends only on the key, so the key must be retired.

Short tags are a related trap. SP 800-38D permits truncation, but Ferguson showed in 2005 that with short tags a successful forgery leaks information about H, making the next forgeries easier. Keep 128-bit tags; never go below 96 without a specific analysis.

Using it correctly in production

In application code, use a vetted library and design the envelope. The pattern below stores a key version and the nonce with each ciphertext and binds the row ID as AAD, so a valid ciphertext copied into another row fails to decrypt instead of silently moving data between users.

import os, struct
from cryptography.hazmat.primitives.ciphers.aead import AESGCM
from cryptography.exceptions import InvalidTag

KEYS = {1: AESGCM(AESGCM.generate_key(bit_length=256))}   # from your KMS in reality
CURRENT = 1

def seal(row_id: int, plaintext: bytes) -> bytes:
    version = struct.pack(">B", CURRENT)
    nonce = os.urandom(12)                       # random nonce: stay far below 2^32 per key
    aad = version + struct.pack(">Q", row_id)    # bind ciphertext to its row and key version
    return version + nonce + KEYS[CURRENT].encrypt(nonce, plaintext, aad)

def open_(row_id: int, blob: bytes) -> bytes:
    version, nonce, body = blob[:1], blob[1:13], blob[13:]
    aad = version + struct.pack(">Q", row_id)
    return KEYS[version[0]].decrypt(nonce, body, aad)  # raises InvalidTag on any change

The version byte makes rotation possible: new writes use the new key, old rows still decrypt, and a background job re-seals them. Count encryptions per key and rotate well before any limit. For large files, split into chunks with their own nonces and put the chunk index and a final-chunk flag in the AAD, so chunks cannot be reordered or truncated and no plaintext is released before its tag is checked.

Performance comes from hardware: AES instructions for the counter path and carry-less multiply (PCLMULQDQ on x86, PMULL on Armv8) for GHASH. On those CPUs GCM runs at several gigabytes per second per core. Without them, table-driven GHASH and AES leak timing through the cache, and ChaCha20-Poly1305 is the safer choice.

Failure modes

• Nonce reuse after restart or VM clone. Counters reset and snapshots replay state.
• Releasing unverified plaintext from streaming decrypt before the tag check.
• Missing AAD binding. Without it, valid ciphertexts can be swapped between rows, tenants or fields and still decrypt.
• Non-constant-time tag comparison. == on bytes can leak how many leading bytes matched; use hmac.compare_digest or let the library compare.
• Exceeding key budgets. Billions of random-nonce messages under one long-lived key drift toward collisions unnoticed.

Choosing an AEAD

The keys feeding any of these should come from a key exchange such as Diffie-Hellman plus a KDF built on a hash from the SHA family, or from a KMS. Never use a password directly as an AEAD key; stretch it with a password hash as described in password hashing with bcrypt.

What to do next

1. Type in the reference implementation and reproduce all four rows of the NIST vector table.
2. Run the differential test against AESGCM with zero-length and odd-length inputs, then break the bit order on purpose and watch it fail.
3. Audit every place your code generates a GCM nonce: write down whether it is random or a counter, and what happens to it on restart, restore and clone.
4. Add a key version and AAD binding to your ciphertext envelope if it lacks them.
5. Add a per-key encryption counter metric and a rotation alert set well below 2^32 for random nonces.
6. Where nonce uniqueness cannot be guaranteed, evaluate AES-GCM-SIV.