CCM: Combining a MAC and a Counter Inside One Mode

CCM is not a new primitive. It is a prescription for combining two familiar ones — CTR mode for encryption and CBC-MAC for authentication — so precisely that the combination is both provably sound and implementable from a single block cipher core. It exists because the obvious combination, encrypt then MAC with independent keys, requires two keys and two passes over a mode implementation, and the obvious reuse of one key for both invites collisions between the two structures.

The specification is unusual among modes in that it fixes almost every framing detail: where the nonce goes, how the length is encoded, what is MACed, and in what order. That rigidity is the design. CCM’s security argument depends on the MAC input being a uniquely encoded concatenation of the header and the message, and any deviation from the encoding is a deviation from the argument.

One key, two roles, and the separation problem

CCM uses a single block cipher key for both the MAC and the counter. This is a deliberate choice, and it is why the nonce and the counters must be structured to keep the two uses apart.

The counter blocks are built from a fixed flag byte, a nonce of 7 to 13 bytes, and a counter of 15 minus the nonce length bytes. The CBC-MAC blocks are built from a different flag byte, a different layout, and — crucially — the first MAC block includes the message length. The two structures are never the same block in a well-formed scheme, and the specification’s constraints exist to guarantee that: the nonce length is fixed per key, and the message length is bounded so that the counter never reaches the value used to build the MAC’s initial block.

The block cipher is applied to different inputs in the two passes, and the security proof treats the cipher as a pseudorandom permutation, so that distinct inputs produce unrelated outputs. This is the same reasoning that lets GCM use $E_K(0)$ as a hash key while also using $E_K$ for CTR, and it is restricted in the same way: each distinct input may be used for one purpose only, and the mode’s framing must prevent accidental overlap.

The authentication header, byte by byte

The MAC input begins with a block that encodes the parameters, and every field in it is there to prevent a specific ambiguity.

The flag byte holds the number of associated-data length octets, the tag length, and the nonce length. The next field is the nonce. The remaining bytes hold the message length in $15 - n$ bytes, where $n$ is the nonce length — that is, the message length field is sized so the block is exactly 16 bytes. The message length is required to be at most $2^{8(15-n)} - 1$ bytes, which for a 13-byte nonce is 255 bytes and for a 7-byte nonce is $2^{64}-1$ bytes. This is the trade at the centre of CCM: a longer nonce means a shorter counter and a shorter maximum message.

Associated data follows, prefixed by a length encoding whose width is itself variable. A two-byte encoding covers lengths under $2^{16} - 2^{8}$, a four-byte encoding covers lengths under $2^{32}$, and a six-byte encoding covers the rest, with the size class signalled in the encoded value. The associated data is then zero-padded to a block boundary.

Then the message itself, zero-padded to a block boundary, and that is the end of the MAC input. The zero padding is unambiguous because the message length is already in the first block: an attacker cannot append zero bytes to the message without changing the encoded length and therefore every subsequent MAC block.

/* First CBC-MAC block: flags, nonce, and the length field sized so the
   whole block is 16 bytes. Padding of the AD and message follows. */
static void ccm_b0(unsigned char b0[16], int ad_len_bytes, int tag_bytes,
                   int nonce_len, unsigned long long msg_len,
                   const unsigned char *nonce)
{
    /* ad_len_bytes is shown as the raw 1/2/3 encoding; 0 means no AD. */
    b0[0] = (unsigned char)((ad_len_bytes ? (ad_len_bytes - 1) : 0) << 6);
    b0[0] |= (unsigned char)(((tag_bytes - 2) / 2) << 3);
    b0[0] |= (unsigned char)(nonce_len - 1);
    memcpy(b0 + 1, nonce, (size_t)nonce_len);
    for (int i = 0; i < 15 - nonce_len; i++)      /* big-endian length */
        b0[15 - i] = (unsigned char)(msg_len >> (8 * i));
}

The declaration of memcpy is omitted from the snippet; the point is the layout, not the includes.

Encrypt then MAC, authentically

CCM computes the tag first and encrypts second, but the tag is computed over the plaintext. This is the opposite order from encrypt-then-MAC as usually described, and the reason it is safe is that the tag is then encrypted together with the message, under the CTR keystream starting at counter zero.

Specifically, CTR encryption uses counter block 0 to encrypt the MAC value, and counter blocks $1, 2, \dots$ to encrypt the message. The transmitted ciphertext is the encrypted message followed by the encrypted tag. The receiver decrypts the message, decapsulates the tag, recomputes the MAC over the plaintext, and compares.

The construction is equivalent to MAC-then-encrypt in the naive sense, which is the composition that fails for CBC because of the padding oracle. CCM avoids that failure because it has no padding check. The CTR decryption is defined for any byte length, and the tag is a fixed number of bytes, so a modified ciphertext always decrypts to something of the correct length and the only check the receiver performs is the tag comparison. There is no intermediate validity signal to leak, which is why the ordering is safe here and unsafe there — the earlier article on CBC padding oracles sets out the difference in detail.

The remaining hazard is the same one that affects every AEAD: the receiver must not act on the decrypted message before the tag comparison succeeds, and it must compare the tag in constant time. Those requirements are the subject of releasing unverified plaintext.

The two-pass cost and the block size dependency

CCM requires two passes over the message: one to compute the CBC-MAC, one to encrypt. The MAC pass is inherently sequential — each block depends on the previous CBC output — so unlike GCM, CCM gains nothing from parallel hardware. The encryption pass is CTR and parallelises, but it starts only after the MAC is complete, so the total cost is the sum rather than the maximum.

The nonce length trade compounds with this. A 13-byte nonce leaves two bytes of counter and a 255-byte message limit, sufficient for 802.11 frames and similar constrained settings but not for bulk data. A 7-byte nonce leaves eight counter bytes and a message limit of $2^{64}-1$ bytes, but a nonce space of only $2^{56}$ per key. Choosing the nonce length is choosing which side of that trade the deployment needs, and the choice is fixed for the lifetime of the key by the specification.

CCM is also restricted to block ciphers with a 128-bit block. The block size is baked into the layouts, and the constructions do not port to a 64-bit block cipher without redesign. That restriction is the price of the compactness: the whole mode is defined in terms of 16-byte block operations, and every field width derives from that.

Where CCM earns its place

The mode’s advantages are its small implementation footprint, its single key, and the fact that its security rests on well-understood components. An implementation needs a block cipher, a CBC-MAC loop, and a CTR loop, all of which are shared with the non-AEAD modes. There is no field arithmetic and no carry-less multiply, which matters on microcontrollers and on hardware accelerators that expose only a block cipher.

Its disadvantages are the two passes, the serial MAC, the 128-bit block requirement, and the small message limits implied by long nonces. Those constraints are why GCM — one pass, parallel, with a 96-bit nonce and a $2^{39}-256$ bit message limit — became the default choice in protocols with larger payloads, and why the two modes coexist in TLS cipher suites and in hardware security modules rather than one displacing the other.

Both modes share the same fragility, though: the nonce must be unique per key, and a repeat is a total loss. CCM’s MAC is a CBC-MAC over a plaintext that includes the nonce in its first block, so a repeated nonce with different plaintexts produces different MAC values and does not expose the MAC key the way GCM’s polynomial does, but the CTR keystream is reused exactly as in any other counter mode, so the plaintexts XOR together. The counter block in CCM’s CTR pass contains the nonce, which is the same structure described in the CTR counter layout, and the uniqueness requirement comes with it unchanged.

For deployments that cannot guarantee freshness — key wrapping, encrypted backups, replicated state machines — the synthetic-IV constructions in SIV and deterministic authenticated encryption are the alternative, and they pay for their tolerance with the same two-pass structure CCM already has.