AES-GCM, spelled out

Authenticated encryption, every step

Duc V. Le

Study notes · October 2026

Roadmap

Two halves

Fundamental concepts. Why confidentiality and authentication are separate goals, the three ways to combine them, and what "AE-secure" means.
AES-GCM. CTR mode, arithmetic in $\mathrm{GF}(2^{128})$, GMAC, the forgery bound, and why the IV must never repeat.

Fundamental concepts

Confidentiality and authentication are different goals

Encryption hides content. A MAC binds content to a key.
Having one gives you nothing about the other.

Fundamental concepts

Encryption alone does not authenticate

In CTR mode the ciphertext is the plaintext XOR a keystream.
So flipping a ciphertext bit flips exactly the matching plaintext bit.
Bob has no way to notice. This is why a MAC is a separate requirement.

Generic composition 1 of 3

Encrypt-and-MAC: the tag is computed over the plaintext

Alice sends $(c, t)$ with $c = E_{k_1}(m)$ and $t = \mathrm{MAC}_{k_2}(m)$.
Bob decrypts $c$, then checks $t$ against the recovered $m$.
Not secure as a generic method.

Generic composition 3 of 3

Encrypt-then-MAC: the tag is computed over the ciphertext

Alice sends $(c, t)$ with $c = E_{k_1}(m)$ and $t = \mathrm{MAC}_{k_2}(c)$.
Bob verifies first, and decrypts only if the tag checks out.
Proven secure whenever $E$ and the MAC are each secure.

Generic composition · summary

Only one of the three is generically secure

"Generic" means: secure for every secure $E$ and MAC, not just some.
Encrypt-then-MAC is the one to reach for.

Fundamental concepts

What "AE-secure" asks for

Confidentiality: she cannot tell which plaintext she got.
Integrity: she cannot produce a new valid ciphertext.

Fundamental concepts

Some data must be authenticated but not encrypted

Routing and version fields must stay readable, but must not be changeable.
Schemes that support this take additional authenticated data, $A$.

Part two

AES-GCM

CTR mode for secrecy, GMAC for the tag

AES-GCM

Two parts, one key

CTR mode turns AES into a stream cipher and encrypts the payload.
GMAC is a custom MAC built from arithmetic in $\mathrm{GF}(2^{128})$, and produces the tag.

Designed by David McGrew and John Viega, 2004. NIST standard SP 800-38D, 2007.

Both parts are driven by the same AES key $k$ and the same nonce.
This is not a generic composition: GMAC alone is not a secure MAC.

AES-GCM · encryption

CTR mode encrypts counters, not data

$C_i = \mathrm{AES}_k(J_i) \oplus M_i$, one block at a time.
The columns do not depend on each other, so this parallelizes.
Decryption runs the same circuit: $M_i = \mathrm{AES}_k(J_i) \oplus C_i$.

AES-GCM · encryption

Where the counters come from

$J_0 = IV \,\|\, 0^{31} \,\|\, 1$ when the IV is 96 bits.
Encryption starts at $\mathrm{inc32}(J_0)$ — counter 2, not counter 1.
$J_0$ is held back to mask the tag.

AES-GCM · encryption

Why the payload stops at $2^{32}-2$ blocks

The counter is only 32 bits wide, and $J_0$ takes one value.
The standard caps the plaintext so the counter can never wrap back to $J_0$.
A wrap would repeat a keystream block — the same break as reusing an IV.

AES-GCM · encryption

Six things to remember about CTR

It is a stream cipher. The keystream depends only on the key and the counters, never on the data.
Different IVs give different ciphertexts for the same plaintext, as with CBC.
The IV must never repeat under one key. The standard says this is hard to achieve in practice, and it is the sharpest edge in the whole mode.
It parallelizes, unlike CBC encryption: every block is independent.
$\mathrm{AES}^{-1}$ is never needed, in either direction.
The key may be 128, 192 or 256 bits. The block, and $H$, stay 128 bits.

AES-GCM · the tag

Arithmetic in $\mathrm{GF}(2^{128})$

What it means to multiply two 128-bit blocks

GF(2^128)

A block is a polynomial

Bit $a_i$ is the coefficient of $x^i$, so $a_0$ is the constant term.
Coefficients live in $\mathbb{Z}_2$: addition is XOR, and $1+1=0$.

GF(2^128)

Multiply, then reduce — worked all the way through

$c = a \cdot b$ means $c(x) = a(x)\,b(x) \bmod f(x)$.
Shown in the toy field $\mathrm{GF}(2^4)$ so every step fits; GCM uses the same recipe.

Definition and the real modulus: Menezes V5 p.13, $f(x) = 1 + x + x^2 + x^7 + x^{128}$.
The worked example is this deck's own, in $\mathrm{GF}(2^4)$ with $f(x) = 1 + x + x^4$, because the 128-bit case cannot be shown by hand. computed
Full check: $a(x)b(x) = (1+x+x^3)(1+x) = 1 + x + x + x^2 + x^3 + x^4$. The two $x$ terms cancel, leaving $1 + x^2 + x^3 + x^4$. From $f(x)=0$ we get $x^4 = 1+x$, so the sum becomes $1 + x^2 + x^3 + 1 + x = x + x^2 + x^3$ after $1+1=0$. In bits, $a_0a_1a_2a_3 = 0111$.
Why "mod $f$": the product of two degree-$<$128 polynomials can reach degree 254, so it must be folded back into 128 bits. $f$ is irreducible, which is what makes the result a field — every nonzero block has an inverse, and a nonzero polynomial has at most its degree many roots. That last fact is what the forgery bound rests on.
Hardware does this with the PCLMUL instruction (Menezes V5 p.20, point 3).

Recap

GMAC packs the message into one polynomial

Each 128-bit block of $A$ becomes one coefficient; the length block $L$ is the last one.
The secret evaluation point is $H = \mathrm{AES}_k(0^{128})$.
The tag is $t = \mathrm{AES}_k(J_0) \oplus f_A(H)$.

AES-GCM · the tag

Evaluating $f_A(H)$ without ever forming a power

Nesting turns powers of $H$ into one multiply per coefficient.
For blocklength $v$: $v$ additions and $v+1$ multiplications.

Security argument · the simplified tag

First attack: guess the tag outright

1Drop the one-time pad for now and consider the simplified tag $t' = f_A(H)$. It is a single 128-bit value.
2She submits one guess. Exactly one of the $2^{128}$ values is accepted, so $\Pr[\text{success}] = 1/2^{128}$.
3A rejected guess teaches her nothing: the verifier answers only accept or reject, and every other value stays equally likely.

Security argument · the simplified tag

Guessing $H$ succeeds with probability at most $\frac{v+1}{2^{128}}$

1Strip the one-time pad and look at $t' = f_A(H)$ alone. The adversary wants $t'$ for a message $A$ of her choice, without knowing $H$.
2She picks one guess $H'$ and outputs $t' = f_A(H')$. She wins exactly when $f_A(H') = f_A(H)$.
3Put everything on one side: $g(x) = f_A(x) + f_A(H')$. In characteristic 2 subtraction is addition, so she wins iff $g(H) = 0$.
4$g$ is not the zero polynomial and $\deg g = v+1$: adding the constant $f_A(H')$ changes only the $x^0$ term, and the leading term $A_1x^{v+1}$ survives.
5A nonzero degree-$d$ polynomial over a field has at most $d$ roots. So at most $v+1$ of the $2^{128}$ elements are roots of $g$.
6$H = \mathrm{AES}_k(0^{128})$ is unknown and uniform, and she chose $H'$ before seeing it. So $\Pr[g(H) = 0] \le \dfrac{v+1}{2^{128}}$.

Menezes V5 p.16 states the bound; this slide is the derivation spelled out.
Why "at most". A nonzero degree-$d$ polynomial over a field has at most $d$ roots in that field; $g$ may well have fewer than $v+1$. So the count of winning $H$ values is an upper bound, which is exactly what a security claim needs.
Why the leading term survives. $f_A(H')$ is a constant, i.e. a degree-0 term. $f_A(x)$ has no constant term at all (its lowest term is $Lx$), so $g(x) = A_1x^{v+1} + \cdots + Lx + f_A(H')$. Nothing can cancel $A_1x^{v+1}$, assuming $A_1 \ne 0$.
Order of quantifiers matters. She commits to $H'$ first, then $H$ is drawn. If she could pick $H'$ after seeing $H$ the probability would be 1. This is why the bound is over the randomness of $H$ (i.e. of the AES key).
Compare: guessing the 128-bit tag directly succeeds with probability $1/2^{128}$ (Menezes V5 p.16). Guessing $H$ is better by a factor of up to $v+1$, because many different $H$ values can produce the same tag for this particular $A$. Longer messages give the adversary more roots to hit.

Security argument · the simplified tag

Third attack: one valid pair, and the guessing stops

$A$ and $t'$ are both known. $H$ is the only unknown.
That makes it an equation to solve, not a value to guess.

Menezes V5 p.16, third bullet: "if the adversary sees a single valid message-tag pair $(A, t')$, she can solve the polynomial equation $f_A(H) = t'$ for $H$."
This is the punchline of the whole security slide. The first two attacks are bounded by $1/2^{128}$ and $(v+1)/2^{128}$ — both negligible. This one is not a probability at all. It is why the simplified tag $t' = f_A(H)$ cannot be used as a MAC.
Root-finding over $\mathrm{GF}(2^{128})$ runs in polynomial time (Cantor–Zassenhaus and friends). The degree is $v+1$, so she gets at most $v+1$ candidate values for $H$ and can test each against the pair she holds. That candidate count is this deck's note, not the source's.
Nothing about AES is broken here. $H = \mathrm{AES}_k(0^{128})$ is still unknown as a function of the key — but she does not need the key, only $H$ itself.

Security argument · the fix

Hide the polynomial value behind a one-time pad

$t = \mathrm{AES}_k(J_0) \oplus f_A(H)$ — the real GMAC tag.
$\mathrm{AES}_k(J_0)$ is a second secret, fresh per nonce.
She sees $t$, never $f_A(H)$, so there is no equation in $H$.

AES-GCM · the full scheme

What goes in and what comes out

Input

name	what	limit
$A$	authenticated, not encrypted	$\le 2^{64}-1$ bits
$M$	encrypted and authenticated	$\le 2^{39}-256$ bits
$IV$	the nonce	96 bits recommended
$k$	the AES key	128, 192 or 256 bits

Output

name	what	size
$IV$	echoed back	96 bits
$A$	in the clear	unchanged
$C$	the ciphertext	same length as $M$
$t$	the tag	128 bits

AES-GCM · the full scheme

Encryption and authentication, side by side

The tag covers $A$ and $C$ — this is Encrypt-then-MAC in spirit.
$H$ and the pad both come from the same key $k$.

AES-GCM · the full scheme

One polynomial over the header and the ciphertext

$A$ takes the top exponents, then $C$, then $L$ on $x^1$.
Degree $u+v+1$, so the forgery bound becomes $(u+v+1)/2^{128}$.

Menezes V5 p.18, the note at the bottom: $f_{A,C}(x) = A_1x^{u+v+1} + A_2x^{u+v} + \cdots + A_vx^{u+2} + C_1x^{u+1} + C_2x^{u} + \cdots + C_ux^{2} + Lx$.
The bound on slide 22 was stated for $f_A$ with degree $v+1$. The same argument applies verbatim to $f_{A,C}$ with degree $u+v+1$ — longer messages, slightly weaker bound. computed: the source states the bound only for the $f_A$ case.
SP 800-38D builds the same value as $\mathrm{GHASH}_H(A \| 0^v \| C \| 0^u \| [\mathrm{len}(A)]_{64} \| [\mathrm{len}(C)]_{64})$, where the zero strings are padding to a block boundary. Careful: in the standard $u$ and $v$ are the padding lengths, while Menezes uses $u$ and $v$ for the blocklengths of $M$ and $A$. Same letters, different meaning — see the notation backup slide.

AES-GCM · the full scheme

Verify first, decrypt second

Bob recomputes the tag from what he received, then compares.
On mismatch he rejects, and the decryption never runs.

AES-GCM · the sharpest edge

Reusing one IV hands over the key material

The same IV gives the same $J_0$, so the same pad twice.
XOR the two tags and the pad cancels.
What is left is the equation in $H$ that the pad existed to prevent.

Menezes V5 p.22, all four bullets, in the source's order. The source assumes $M_1$ and $M_2$ have the same blocklength and that the eavesdropper knows $M_1$.
Two separate disasters follow from one repeat. Confidentiality: the keystream repeats, so $C_1 \oplus C_2 = M_1 \oplus M_2$ and knowing $M_1$ gives $M_2$ — the slide-4 malleability, now for free. Integrity: the derivation on this slide gives $H$ and then the pad, so she can forge.
Why this is worse than it sounds: a 96-bit random IV collides after about $2^{48}$ messages by the birthday bound, which is reachable for a busy key. Counter-based IVs avoid it but break on VM snapshots, restarts and config cloning.
This is why AES-GCM-SIV exists: it derives the pad from the message as well, so a repeated nonce leaks only whether two messages were equal. Out of scope for the source deck; noted on the last backup slide.

AES-GCM · in practice

Seven properties worth knowing

It does both jobs — authentication and encryption — in one pass.
Authentication only is available by passing an empty $M$. That is GMAC.
Very fast on Intel and AMD, thanks to the AES-NI and PCLMUL instructions.
Both directions parallelize.
It can stream, processing data as it arrives.
Keys of 128, 192 or 256 bits.
It has a security proof — eventually. See the next slide.

AES-GCM · in practice

The special instructions are worth about 14×

algorithm	block (bits)	key (bits)	digest (bits)	speed (MB/s)
ChaCha20	—	256	—	323
Triple-DES	64	168	—	21
AES-128	128	128	—	170
AES-128-NI	128	128	—	2426
AES-256	128	256	—	129
AES-256-NI	128	256	—	1830
GMAC	128	128	128	247
GMAC-PCLMUL	128	128	128	1741

Intel Xeon E3-1220 V2 at 3.10 GHz, 64-bit mode, 2018. Source: bearssl.org/speed.html, via Menezes V5 p.21.

GMAC: 247 → 1741 MB/s with PCLMUL. computed about 7.0×.
AES-128: 170 → 2426 MB/s with AES-NI. computed about 14.3×.

AES-GCM · in practice

The proof took eight years to get right

NIST standardised the mode in 2007 — on a proof that was wrong.
The mode itself survived; only the argument needed repair.

Summary

Five things to carry away

Confidentiality and authentication are separate; encryption alone is malleable.
Of the three generic compositions, only Encrypt-then-MAC is generically secure.
GMAC packs the message into a polynomial and evaluates it at a secret point $H$.
Guessing $H$ wins with probability at most $\frac{v+1}{2^{128}}$ — but one valid unmasked pair gives $H$ outright. The one-time pad $\mathrm{AES}_k(J_0)$ is what stops that.
Therefore: never repeat an IV. It cancels the pad and ends the key.

Backup

Backup slides

Notation, and what this deck leaves out

Backup

Notation reference

symbol	meaning	size
$k$	the AES key	128, 192 or 256 bits
$IV$	the nonce, never repeated under one $k$	96 bits (recommended)
$J_0$	$IV \\| 0^{31} \\| 1$; its AES value masks the tag	128 bits
$J_i$	$\mathrm{inc32}(J_{i-1})$, the counter blocks	128 bits
$H$	$\mathrm{AES}_k(0^{128})$, the secret evaluation point	128 bits
$A$	additional authenticated data, $v$ blocks	$\le 2^{64}-1$ bits
$M$, $C$	plaintext and ciphertext, $u$ blocks	$\le 2^{39}-256$ bits
$L$	$L_A \\| L_M$, the two lengths as 64-bit integers	128 bits
$f_{A,C}$	the message polynomial	degree $u+v+1$
$t$	$\mathrm{AES}_k(J_0) \oplus f_{A,C}(H)$, the tag	128 bits

Menezes V5 p.11, 14, 17, 18. Length bounds from NIST SP 800-38D §5.2.1.1.

Backup

What this deck leaves out

The repaired security bound. Iwata–Ohashi–Minematsu (2012) fixed the proof; this deck states only that it happened, because the bound itself needs the paper, not the source deck. not sourced here
Nonce-misuse resistance. AES-GCM-SIV (RFC 8452) derives the pad from the message too, so a repeated nonce leaks only message equality instead of the key material. beyond the source
Tag truncation. SP 800-38D Appendix C allows 96–120 bit tags, and 32 or 64 bits only in restricted applications. Shorter tags weaken the forgery bound directly. beyond the source
Key commitment. A GCM ciphertext can be made to decrypt validly under two different keys. This matters for some protocols and is not part of the AE definition on slide 8. beyond the source
IVs that are not 96 bits. SP 800-38D hashes those through GHASH to form $J_0$. Only the 96-bit case is shown here.
Multi-user and multi-key bounds, and the cost of rekeying before the birthday limit.