Confidentiality without authenticity is an illusion: an attacker who cannot decrypt a ciphertext can often tamper with it systematically (via bit-flipping attacks, padding oracles, or cut-and-paste manipulations) to completely subvert the protocol. In modern engineering, unauthenticated encryption is considered a critical security vulnerability. Authenticated Encryption with Associated Data (AEAD) solves this by guaranteeing both ciphertext privacy (IND-CPA) and ciphertext integrity (IND-CCA2).
1. Message Authentication Codes (MAC) & HMAC Security
A Message Authentication Code (MAC) is a symmetric primitive consisting of algorithms (( ext{KeyGen}, ext{Tag}, ext{Verify})). It guarantees Existential Unforgeability under Chosen-Message Attacks (EUF-CMA):
[
Pr left[ mathcal{A}^{ ext{Tag}(K, cdot)} ext{ outputs } (m^*, t^*) ext{ s.t. } ext{Verify}(K, m^*, t^*) = 1 wedge m^*
otin mathcal{Q}
ight] le ext{negl}(n)
]
To construct a provably secure MAC from Merkle-Damgård hash functions without length-extension vulnerabilities, Mihir Bellare developed HMAC:
[
ext{HMAC}_K(m) = HBig( (K oplus opad) parallel Hbig( (K oplus ipad) parallel m big) Big)
]
where (ipad = 0 ext{x}36) and (opad = 0 ext{x}5C) repeated to block length. Bellare (2006) proved that HMAC is a secure PRF as long as the compression function (f) is a PRF when keyed via its chaining input, even if the underlying hash function suffers from weak collision resistance.
2. The Three Composition Paradigms: Why Encrypt-then-MAC Wins
When combining an encryption scheme (mathcal{E}) with a MAC scheme (mathcal{M}), three classical composition paradigms exist:
- Encrypt-and-MAC: (C = E_{K_1}(P), T = M_{K_2}(P)). Flawed because MAC tags are deterministic and can leak plaintext information (used in early SSH).
- MAC-then-Encrypt: (T = M_{K_2}(P), C = E_{K_1}(P parallel T)). Vulnerable to padding oracle attacks (e.g., Vaudenay’s POODLE and Lucky Thirteen in TLS 1.0–1.2).
- Encrypt-then-MAC (EtM): (C = E_{K_1}(P), T = M_{K_2}(C parallel A)). Bellare and Namprempe (2000) proved that Encrypt-then-MAC is unconditionally the only composition that generically guarantees IND-CCA2 security: unauthenticated ciphertexts are rejected before reaching decryption routines, shutting down side-channel oracles completely.
3. AES-GCM: Galois/Counter Mode
Today, the gold standard AEAD cipher across TLS 1.3, IPsec, and Google Cloud is AES-GCM (Galois/Counter Mode). It marries CTR mode encryption with high-speed universal hashing over ( ext{GF}(2^{128})).
For associated data (A) and ciphertext (C), the authentication tag is generated using the GHASH function:
[
ext{GHASH}_H(X) = sum_{i=1}^m X_i cdot H^{m – i + 1} in ext{GF}(2^{128})
]
where (H = E_K(0^{128})) is the hash key, and field multiplication is evaluated modulo the irreducible polynomial (f(x) = x^{128} + x^7 + x^2 + x + 1). The final authentication tag masks GHASH with an encrypted counter:
[
T = ext{GHASH}_H(A, C) oplus E_K( ext{Nonce} parallel 0^{31}1)
]
Because GHASH relies purely on finite field polynomial evaluation, modern CPUs execute it in hardware via dedicated instructions (Intel PCLMULQDQ / ARM PMULL) at blistering speeds exceeding 10 GB/s.
4. The Nonce-Reuse Catastrophe & ChaCha20-Poly1305
A fatal pitfall of AES-GCM is Nonce Reuse. If an encryption key (K) is ever used with the identical Nonce for two different messages, the tag mask (E_K( ext{Nonce} parallel 1)) cancels out:
[
T_1 oplus T_2 = ext{GHASH}_H(A_1, C_1) oplus ext{GHASH}_H(A_2, C_2)
]
This yields a polynomial equation in (H) of degree at most (m) over ( ext{GF}(2^{128})). Finding the roots reveals the secret authentication key (H), permitting total forgery of all subsequent messages. To mitigate this without hardware acceleration, Daniel J. Bernstein engineered ChaCha20-Poly1305: an ARX (Add-Rotate-XOR) stream cipher paired with a Carter-Wegman polynomial authenticator modulo the prime (2^{130} – 5), offering constant-time, cache-timing-immune performance on mobile processors.
