CBC-MAC Ends at the Last Block, and That Is the Problem

Cipher block chaining is a confidentiality mode: each plaintext block is XORed with the previous ciphertext block before encryption, so identical plaintext blocks at different positions produce different ciphertext. The same structure can be run as an authentication function by taking the final ciphertext block as the tag and discarding the rest. This is CBC-MAC, and it is correct only under a condition that is easy to miss: every message must have the same length.

The chaining state is the tag

Encryption under CBC-MAC proceeds block by block. With a block cipher $E_k$, a message split into blocks $M_1, \dots, M_n$, and an initial vector fixed at zero, the computation is

$$C_1 = E_k(M_1 \oplus 0), \qquad C_i = E_k(M_i \oplus C_{i-1}), \qquad t = C_n$$

The final chaining value is the tag. The intermediate values are discarded, which is the point: an attacker who sees only $t$ has no information about the chaining states along the way.

Consider what happens when two messages of different lengths are authenticated under the same key. Take a one-block message $M_1$ with tag $C_1$. Now take the two-block message $M_1 ,|, (M_2 \oplus C_1)$, which the attacker can construct from $M_1$, $M_2$, and the observed tag $C_1$. Its first block produces $C_1$, so its second block is encrypted with $C_1$ XORed against $M_2 \oplus C_1$, giving $E_k(M_2)$ as the new chaining value. The attacker therefore obtains a valid tag for a longer message without knowing the key, as long as the receiver accepts variable lengths.

The attack is a splicing operation. The tag of a message becomes the IV for a chosen continuation, and since the IV is supposed to be zero and is not transmitted, nothing in the verification procedure detects that the chain was started mid-way. The receiver recomputes from the start and gets the same final value, because the attacker arranged the blocks so that the recomputation passes through the same states.

Length-prefixing fixes the simple case

The textbook repair is to put the message length in the first block: $t = \mathrm{CBCMAC}_k(\mathrm{len}(M) ,|, M)$. Now the two messages have different first blocks, so the splicing construction no longer lines up, because the attacker would need the tag of a message whose first block is the length encoding rather than the original $M_1$. The length field must be unambiguous and must cover the whole message, including any padding.

Length-prefixing has a cost and a limitation. It consumes a full block, so a message of exactly one block becomes two, and it requires the receiver to know the length before it starts processing, which rules out streaming verification unless the length is transmitted ahead of the body. It also fixes the length in blocks, so the encoding must be exact: a length field measured in bytes but processed in blocks, with padding applied after the length is computed, creates an ambiguity the attacker can exploit.

CMAC’s two subkeys

CMAC, standardised as NIST SP 800-38B, avoids the length block by deriving two subkeys from the cipher key and using them to mask the final block. The derivation uses the block cipher itself:

$$L = E_k(0^{128}), \qquad K_1 = \mathrm{dbl}(L), \qquad K_2 = \mathrm{dbl}(K_1)$$

where $\mathrm{dbl}$ is multiplication by the constant $x$ in the field $\mathrm{GF}(2^{128})$: a left shift by one bit, followed by a conditional XOR with the reduction polynomial $0x87$ when the shifted-out bit was one. The two subkeys depend only on the key, so they can be computed once and cached.

The message is padded with a single 1 bit followed by zeros to a block boundary. The final block is then XORed with $K_1$ if the message length was an exact multiple of the block size and no padding was added, or with $K_2$ if padding was added. The chaining runs as in CBC-MAC, and the final ciphertext block is the tag.

The distinction between the two cases is what makes the construction secure without a length field. A padded message and an unpadded message that happen to produce the same final block before masking are masked differently, so their tags differ. An attacker trying to splice a continuation onto a known tag faces a final block masked with a subkey it does not know, and cannot compute the resulting tag. The subkeys are secret because they are derived from the key through the cipher, and an attacker who could compute them could invert the cipher.

def dbl(block: int) -> int:
    # Multiply by x in GF(2^128) with the GCM/CMAC reduction polynomial
    carry = block >> 127
    block = (block << 1) & ((1 << 128) - 1)
    return block ^ (0x87 if carry else 0)

def cmac_subkeys(key: bytes) -> tuple[int, int]:
    from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
    enc = Cipher(algorithms.AES(key), modes.ECB()).encryptor()
    L = int.from_bytes(enc.update(b"\x00" * 16), "big")
    k1 = dbl(L)
    return k1, dbl(k1)

The subkey derivation requires a single block encryption per key, which is why implementations compute it at key setup rather than per message.

The one-block message and the empty message

Two boundary cases deserve attention because they are where implementations diverge.

An empty message has zero blocks. CMAC pads it to a single block consisting of a 1 bit followed by 127 zero bits, then masks with $K_2$. There is no ambiguity with a message consisting of 16 zero bytes, because that message is unpadded and masked with $K_1$. An implementation that treats an empty input as “nothing to process” and returns the zero chaining value produces a tag that is independent of the key, which is a complete break for that input.

A message of exactly one block is unpadded and masked with $K_1$. The chaining is $C_1 = E_k(M_1 \oplus K_1)$, and the tag is $C_1$. Note that the subkey enters before encryption, not after, so the tag is not simply the encryption of the masked block in a way that allows precomputation across messages; it depends on the message.

Truncation follows the same rule as HMAC: the leftmost bits of the tag are kept, and the security level is bounded by the truncated length. SP 800-38B permits tag lengths in whole bytes down to 32 bits, and short tags appear in constrained protocols. The bound is direct: a 32-bit tag gives a random forgery attempt one chance in $2^{32}$, and a 64-bit tag one in $2^{64}$, per attempt, with no per-message cost to the attacker beyond submitting the message.

Why not just use HMAC

CMAC exists because some environments have a block cipher and no hash function, particularly in hardware where an AES engine is present and a SHA-256 engine is not, or where a single primitive is preferred for certification and code size. Its cost is one block encryption per 16-byte message block, plus one encryption at key setup to derive the two subkeys. A hash-based MAC processes 64 bytes of message per compression with SHA-256, so the two are not directly comparable per byte; the choice follows the primitive the platform accelerates, and the block cipher’s 16-byte granularity makes CMAC relatively expensive for long messages on general-purpose hardware.

The security assumptions differ. HMAC’s proof rests on the compression function behaving like a PRF under a secret prefix. CMAC’s proof rests on the block cipher being a PRP, which is a stronger assumption and one that AES is designed to satisfy. In practice both are sound with their respective primitives, and the choice is usually made by what the platform accelerates.

One property CMAC shares with every MAC in this cluster is that verification requires the key, so it cannot settle a dispute, as the verification split explains. Another it shares with CBC-mode constructions generally is that it is sequential: the tag of a message cannot be computed in parallel across blocks, because each block depends on the previous chaining value. For long messages on multi-core hardware this matters, and it is one reason tree-based constructions and parallel modes exist. CMAC’s final-block masking has no analogue in those constructions, which authenticate blocks independently and combine their tags; the trade is parallelism against a more complex proof and a larger tag.

The construction also assumes the message is available in blocks. Streaming implementations must buffer the final block, because whether padding was applied is not known until the end. An implementation that flushes eagerly and masks with $K_1$ will produce a wrong tag for any message whose length is not a multiple of the block size, and the error appears only at the boundary, which is exactly the case that tests tend to miss. The safe pattern is to hold back the last block until the input ends, then decide which subkey applies, which is also how Poly1305 handles its own final partial block.