Authenticated encryption, GCM and CCM

The four ways to combine encryption with a MAC, why getting the combination wrong is a common source of vulnerabilities, and the two AEAD constructions, GCM and CCM, that fold both into one operation.

Name the four approaches to combining encryption and message authentication, their formulas, and which protocol uses each.
Explain why authenticated encryption exists as a single primitive rather than composing encryption and a MAC by hand.
Describe GCM's construction, its efficiency, and its brittleness under nonce reuse.
Describe CCM's construction and why it is sequential rather than parallelisable like GCM.

16 min read

Intuition

Confidentiality and integrity have been treated as two separate jobs so far: encryption for one, a MAC for the other. Combining them by hand is where mistakes creep in, get the order wrong, reuse a key incorrectly, or release plaintext before its integrity is checked, and the result can quietly fail even though both pieces work correctly on their own. Authenticated encryption folds both jobs into one operation specifically to close that gap.

Mechanism

There are four ways to combine encryption and a MAC. All but the first need two independent keys, one for each operation:

Hashing followed by Encryption (H → E). Compute $h = H(M)$ , then send $E_K(M \Vert h)$ .

Authentication followed by Encryption (A → E). Compute $T = \text{MAC}_{K_1}(M)$ , then send $E_{K_2}(M \Vert T)$ . This is what SSL/TLS uses.

Encryption followed by Authentication (E → A). Compute $C = E_{K_2}(M)$ , then $T = \text{MAC}_{K_1}(C)$ , sending $(C, T)$ . This is what IPSec uses, and it can withstand stronger attacks than the other three.

Independently Encrypt and Authenticate (E + A). Compute $C = E_{K_2}(M)$ and $T = \text{MAC}_{K_1}(M)$ independently, in either order, sending $(C, T)$ . This is what SSH uses.

Formula

The four AE approaches

\begin{aligned} \text{H} \to \text{E}: &\quad E_K(M \Vert H(M)) \\ \text{A} \to \text{E}: &\quad E_{K_2}(M \Vert \text{MAC}_{K_1}(M)) \\ \text{E} \to \text{A}: &\quad \big(E_{K_2}(M),\ \text{MAC}_{K_1}(E_{K_2}(M))\big) \\ \text{E + A}: &\quad \big(E_{K_2}(M),\ \text{MAC}_{K_1}(M)\big) \end{aligned}

$M$: the plaintext message
$E_K$: encryption under key K
$H(M)$: the message's hash
$\text{MAC}_{K}(x)$: the MAC of x under key K
$K_1, K_2$: two independent keys, one for the MAC and one for encryption, used in every approach except H then E

A->E is used in SSL/TLS, E->A is used in IPSec and is considered the strongest, E+A is used in SSH.

Mechanism

Authenticated Encryption (AE) packages this into a single primitive that provides confidentiality and integrity together, ideally structured so that no plaintext is released until integrity has been verified. Authenticated Encryption with Associated Data (AEAD) extends AE further: some data, such as a packet header, needs to stay readable in plaintext but still needs tamper protection, so AEAD authenticates it without encrypting it. The MAC computation and the encryption can typically run in parallel, which is part of why AEAD schemes are efficient. AEAD is defined for both block ciphers and stream ciphers; two constructions dominate in practice.

Mechanism

GCM (Galois/Counter Mode) is currently the strongest and most widely used block-cipher AEAD mode, and highly efficient because of its parallelism. It follows the Encrypt-then-MAC pattern: the message is encrypted in a variant of CTR mode, and the resulting ciphertext is combined with key material and the message length, multiplied over $GF(2^{128})$ , to produce the authenticator tag. The standard also defines a MAC-only mode built the same way, called Galois MAC. Internally, GCM uses two functions: GHASH, a keyed hash function, and GCTR, CTR mode with counters that simply increment by one each block.

Threat

GCM is very brittle in implementation. Reusing a nonce under the same key can completely break its security, not just weaken it.

Control

Always use a well-vetted cryptographic library for GCM rather than implementing it directly. This is the lecture’s own explicit advice, not a general caution, precisely because nonce management is easy to get wrong by hand.

Mechanism

CCM (Counter with CBC-MAC) is a carefully engineered construction standardised by NIST to meet IEEE 802.11 WiFi’s security requirements. It computes a CBC-MAC over the message first to produce a tag, then encrypts the message and that tag together using CTR mode, which makes it a MAC-then-Encrypt construction structurally, even though it is sometimes summarised as a variant of MAC-and-Encrypt. Because the MAC must finish before encryption can begin, CCM is sequential and therefore less efficient than GCM, but it remains widely used in constrained environments such as IoT devices and 802.11 WiFi. As with GCM, a single key is safely reused for both encryption and the MAC in CCM, because the two uses are cleanly separated by the construction’s design and accounted for in its security proof.

Pitfall

The slides describe CCM two ways in different places: once as “a MAC-then-Encrypt construction” (compute the tag, then encrypt the message and tag together), and later as “a carefully engineered variation of MAC-and-Encrypt.” Both descriptions are of the same operation, compute the tag first, then encrypt message and tag together under CTR mode, which structurally matches MAC-then-Encrypt, not the independent, either-order MAC-and-Encrypt pattern used by SSH. Treat CCM as MAC-then-Encrypt; the second label is the slides’ own loose wording, not a different construction.

Compare

Parallelisable and highly efficient, built from GHASH and GCTR, following an Encrypt-then-MAC pattern. Very brittle: a reused nonce can completely break security, so it should only ever be used through a vetted library.

Sequential and less efficient, since its CBC-MAC tag must be computed before CTR-mode encryption can begin. Widely used in constrained settings such as IoT and 802.11 WiFi, where GCM’s throughput advantage matters less than its implementation risk.

Exam detail

Memorise the protocol pairings exactly: SSL/TLS uses Authentication-then-Encryption (A → E), IPSec uses Encryption-then-Authentication (E → A) and is called the strongest of the four, and SSH uses independent Encrypt-and-Authenticate (E + A). For AEAD specifically, GCM is the general-purpose, high-throughput choice precisely because it parallelises, while CCM trades that throughput for the simpler, sequential construction IEEE 802.11 WiFi and constrained IoT devices standardised on.

Recall

Why does AEAD reduce implementation risk compared to composing an encryption scheme and a MAC by hand?

Composing them manually leaves room for mistakes that break security silently: the wrong ordering, reusing a key across both operations without the guarantees a proper construction provides, or releasing plaintext before its integrity has actually been checked. An AEAD construction like GCM or CCM is specified as one tightly defined operation with its own security proof, removing those decision points from the implementer entirely.

Source

Week 6 slides PDF