The AES-CCM Algorithm

The AES-CCM Algorithm

Introduction

Encryption alone hides a message, but it does not stop anyone from changing it. Authenticated encryption with associated data, or AEAD, solves both problems at once. It encrypts the message, and it adds a short tag that lets the receiver detect any change to the ciphertext. It can also cover associated data, such as a packet header, that must stay readable but must not be altered.

AES-CCM is one of the standard AEAD modes. Its name stands for Counter with CBC-MAC. It builds the whole thing from one tool, the AES block cipher, used in two ways. A CBC-MAC over the data produces the tag, and counter mode encrypts the data and hides the tag.

Table of Contents

• History and Standards
• The Two Halves of CCM
• Parameters
• Formatting the CBC-MAC Input
• Encryption and the Tag
• Decryption and Verification
• A Worked Example
• Python Implementation
• Limitations
• Security Status
• FAQ
• References

History and Standards

Russ Housley, Doug Whiting, and Niels Ferguson developed CCM. It was published as RFC 3610 in September 2003, and NIST standardized it as SP 800-38C in May 2004. Wikipedia notes that it was developed as a patent-free alternative to OCB mode for the IEEE 802.11i standard.

CCM is used in many places. The Wi-Fi security protocol WPA2 uses it under the name CCMP. Bluetooth Low Energy uses it, and so do IPsec and TLS, and ZigBee uses a variant called CCM*. CCM needs only a block cipher in the forward direction, which suits small hardware.

The Two Halves of CCM

CCM runs two passes over the data with the same AES key:

1. Authentication. The cipher builds a sequence of blocks from the nonce, the lengths, the associated data, and the plaintext. It runs CBC-MAC over them. The result is a tag T.
2. Encryption. It encrypts the plaintext in counter mode, using blocks built from the nonce and a counter. A special counter block, number 0, also encrypts the tag T.

The output is the ciphertext followed by the encrypted tag. Using the same key twice is safe here because the block formatting keeps the two passes apart. The section on encryption explains how.

Interactive Visualizer

The visualizer above runs this exact algorithm. Pick a tag and nonce size, then enter an AES key, a nonce, associated data, and a message in hex. Click Encrypt to see the CBC-MAC states, the counter blocks, and the keystream. To decrypt, paste the ciphertext and tag into the message box and click Decrypt. Change one hex digit first, and the tag check fails.

Parameters

CCM has two size parameters. They trade off how long a message can be against how long the nonce is:

Name	Meaning	Values
M	Tag length in bytes	4, 6, 8, 10, 12, 14, or 16
L	Size of the length field in bytes	2 to 8
N	Nonce length in bytes	15 - L, so 7 to 13

A larger L allows longer messages, and a smaller L allows a longer nonce. The message length must fit in L bytes, so it is below 2^(8L) bytes. TLS 1.3 uses a 12-byte nonce for every AEAD, which gives L = 3 for CCM. The nonce must never repeat under the same key.

Formatting the CBC-MAC Input

The CBC-MAC runs over a list of blocks. The first block, B0, packs the parameters:

B0 = flags || nonce || message length
flags = 64 * Adata + 8 * ((M - 2) / 2) + (L - 1)

Adata is 1 if there is associated data, and 0 if there is none. The message length takes L bytes, written big-endian. In the RFC example, the flags are 59, which is 01011001 in binary. Assuming there is associated data, tag length 4 with L = 3 gives flags 4a, and tag length 16 with L = 3 gives 7a. Without associated data, the same settings give 0a and 3a.

If there is associated data, it follows B0. It is preceded by its length, encoded in two bytes when it is shorter than 2^16 - 2^8 bytes. Longer data uses a six-byte or ten-byte prefix. The prefix and the data are then padded with zeros to a whole number of 16-byte blocks. The plaintext follows, padded with zeros in the same way.

Encryption and the Tag

CBC-MAC. Start with a state X of 16 zero bytes. For each block B, compute X = AES(X ^ B). The first M bytes of the final state are the tag T.

Counter mode. Build counter blocks A_i, each made of a flags byte L - 1, the nonce, and the counter i in L bytes. For i = 1, 2, ..., compute the keystream S_i = AES(A_i) and XOR it with the plaintext block. The counter starts at 1 for the data.

Hiding the tag. Counter block 0 is reserved for the tag. The first M bytes of S_0 = AES(A_0) are XORed with T, which gives the encrypted tag U. The final output is the ciphertext followed by U.

Keeping the passes apart. Both passes use one key, so a B0 block must never equal a counter block. In B0, bits 5 to 3 of the flags hold (M - 2) / 2. Because M is at least 4, that value is at least 1, so those bits are never all zero. In a counter block A_i, the flags byte is only L - 1, so the same bits are always zero. The two kinds of block can never match.

Encrypting the tag matters. A raw CBC-MAC value would let an attacker test guesses against known data. With the tag hidden under a fresh counter value, the tag leaks no information about the CBC-MAC state.

Decryption and Verification

The receiver cannot check the tag before decrypting, because the tag is computed over the plaintext. Decryption therefore runs the same steps in a different order:

1. Decrypt the ciphertext with counter mode to get the candidate plaintext.
2. Recompute the CBC-MAC over the associated data and the candidate plaintext.
3. Compute T XOR S_0 and compare it with the received tag.

RFC 3610 says the recipient must verify the tag before releasing any information, such as the plaintext. If the tags differ, the receiver must destroy all information except the fact that verification failed. A good implementation compares the two tags in constant time.

This rule exists because the tag covers the plaintext, not the ciphertext. The receiver must decrypt first, so unverified plaintext exists in memory before the check. Passing it to the application early is called the release of unverified plaintext. Buffer the whole message and release it only after the tag matches.

A Worked Example

This is Packet Vector 1 from RFC 3610. The key is c0c1c2c3c4c5c6c7c8c9cacbcccdcecf, the nonce is 00000003020100a0a1a2a3a4a5 (13 bytes, so L = 2), the associated data is the 8-byte header 0001020304050607, and the plaintext is the 23-byte message 08090a0b0c0d0e0f101112131415161718191a1b1c1d1e. The tag is 8 bytes long.

Formatting. The first block is B0 = 5900000003020100a0a1a2a3a4a50017. It holds the flags 59, the nonce, and the message length 0017, which is 23. The header is encoded with the length prefix 0008 and padded to 00080001020304050607000000000000. The message becomes two blocks, 08090a0b0c0d0e0f1011121314151617 and 18191a1b1c1d1e000000000000000000, the second padded with zeros.

CBC-MAC. Encrypting B0 gives X = eb9d5547730955ab231e0a2dfe4b90d6. The header block is XORed in, giving eb955546710a51ae25190a2dfe4b90d6, and AES turns it into cdb6411e3cdc9b4f5d9258b69ee7f091. The first message block gives c5bf4b1530d195404d834aa58af2e686, then 9c38405ea03c1bc904b58b40c76ca2eb. The last gives 84215a45bc2105c904b58b40c76ca2eb, then 2dc697e411ca83a860c2c406ccaa542f. The tag is the first 8 bytes of that: T = 2dc697e411ca83a8.

Counter mode. Counter block 1 is 0100000003020100a0a1a2a3a4a50001, and AES turns it into the keystream 50859d916dcb6ddde077c2d1d4ec9f97. Counter block 2 is 0100000003020100a0a1a2a3a4a50002, with keystream 7546717ac6de9aff640c9c06de6d0d8f. XORing these with the message gives the ciphertext:

588c979a61c663d2f066d0c2c0f98980
6d5f6b61dac384

The tag. Counter block 0 is 0100000003020100a0a1a2a3a4a50000. The first 8 bytes of its AES output are 3a2e46c8ec33a548. XORing with T gives the encrypted tag 17e8d12cfdf926e0. The complete output is the ciphertext followed by that tag. Every intermediate value above matches the RFC’s own listing.

Tampering. Change the first ciphertext byte and decrypt. The recomputed tag no longer matches, and the receiver reports: authentication failed.

Python Implementation

This is a complete AES-CCM, with a small AES included. It supports every tag and nonce size. Decryption refuses to return any data if the tag does not match.

# ccm.py
#
# AES-CCM, Counter with CBC-MAC (RFC 3610, NIST SP 800-38C).
# One AES key does two jobs. CBC-MAC over a specially formatted message makes
# the authentication tag, and CTR mode with the same key encrypts the data and
# hides the tag. The nonce has 7 to 13 bytes, the tag has 4 to 16 bytes (even
# lengths only), and the length of the message must fit in L = 15 - nonce
# length bytes.

from aes_core import AES


def xor(a, b):
    return bytes(x ^ y for x, y in zip(a, b))


def check_parameters(nonce, tag_len):
    if not 7 <= len(nonce) <= 13:
        raise ValueError("a CCM nonce is 7 to 13 bytes")
    if tag_len not in (4, 6, 8, 10, 12, 14, 16):
        raise ValueError("a CCM tag is 4, 6, 8, 10, 12, 14 or 16 bytes")


def format_b0(nonce, tag_len, aad_len, message_len):
    """The first CBC-MAC block: flags, nonce, and the message length."""
    length_bytes = 15 - len(nonce)
    if message_len >= 1 << (8 * length_bytes):
        raise ValueError("the message is too long for this nonce length")
    flags = (64 if aad_len else 0) | (((tag_len - 2) // 2) << 3) | (length_bytes - 1)
    return bytes([flags]) + nonce + message_len.to_bytes(length_bytes, "big")


def encode_aad(aad):
    """The length prefix of the associated data, then the data, padded with zeros to whole blocks."""
    if not aad:
        return b""
    n = len(aad)
    if n < 0xFF00:
        prefix = n.to_bytes(2, "big")
    elif n < 1 << 32:
        prefix = b"\xff\xfe" + n.to_bytes(4, "big")
    else:
        prefix = b"\xff\xff" + n.to_bytes(8, "big")
    data = prefix + aad
    return data + bytes(-len(data) % 16)


def pad16(data):
    return data + bytes(-len(data) % 16)


def cbc_mac_blocks(nonce, tag_len, aad, message):
    blocks = [format_b0(nonce, tag_len, len(aad), len(message))]
    for source in (encode_aad(aad), pad16(message)):
        blocks += [source[i:i + 16] for i in range(0, len(source), 16)]
    return blocks


def counter_block(nonce, index):
    length_bytes = 15 - len(nonce)
    return bytes([length_bytes - 1]) + nonce + index.to_bytes(length_bytes, "big")


def compute_tag(aes, nonce, tag_len, aad, message):
    x = bytes(16)
    for block in cbc_mac_blocks(nonce, tag_len, aad, message):
        x = aes.encrypt_block(xor(x, block))
    return x[:tag_len]


def ctr_crypt(aes, nonce, data):
    out = bytearray()
    for i in range(0, len(data), 16):
        stream = aes.encrypt_block(counter_block(nonce, 1 + i // 16))
        out += xor(data[i:i + 16], stream)
    return bytes(out)


def encrypt(key, nonce, plaintext, aad=b"", tag_len=16):
    """Return ciphertext followed by the tag."""
    check_parameters(nonce, tag_len)
    aes = AES(key)
    tag = compute_tag(aes, nonce, tag_len, aad, plaintext)
    ciphertext = ctr_crypt(aes, nonce, plaintext)
    s0 = aes.encrypt_block(counter_block(nonce, 0))
    return ciphertext + xor(tag, s0[:tag_len])


def decrypt(key, nonce, data, aad=b"", tag_len=16):
    """Return the plaintext, or raise ValueError if the tag does not match."""
    check_parameters(nonce, tag_len)
    if len(data) < tag_len:
        raise ValueError("the input is shorter than the tag")
    aes = AES(key)
    ciphertext, received = data[:-tag_len], data[-tag_len:]
    plaintext = ctr_crypt(aes, nonce, ciphertext)
    expected = xor(compute_tag(aes, nonce, tag_len, aad, plaintext), aes.encrypt_block(counter_block(nonce, 0))[:tag_len])
    difference = 0
    for a, b in zip(expected, received):
        difference |= a ^ b
    if difference:
        raise ValueError("authentication failed")
    return plaintext


if __name__ == "__main__":
    key = bytes.fromhex("c0c1c2c3c4c5c6c7c8c9cacbcccdcecf")
    nonce = bytes.fromhex("00000003020100a0a1a2a3a4a5")
    header = bytes.fromhex("0001020304050607")
    message = bytes.fromhex("08090a0b0c0d0e0f101112131415161718191a1b1c1d1e")
    sealed = encrypt(key, nonce, message, header, 8)
    print("Key:        " + key.hex())
    print("Nonce:      " + nonce.hex())
    print("Header:     " + header.hex())
    print("Plaintext:  " + message.hex())
    print("Sealed:     " + sealed.hex())
    print("Recovered:  " + decrypt(key, nonce, sealed, header, 8).hex())
    try:
        decrypt(key, nonce, bytes([sealed[0] ^ 1]) + sealed[1:], header, 8)
    except ValueError as error:
        print("Tampered:   " + str(error))

Running it produces this output:

Key:        c0c1c2c3c4c5c6c7c8c9cacbcccdcecf
Nonce:      00000003020100a0a1a2a3a4a5
Header:     0001020304050607
Plaintext:  08090a0b0c0d0e0f101112131415161718191a1b1c1d1e
Sealed:     588c979a61c663d2f066d0c2c0f989806d5f6b61dac38417e8d12cfdf926e0
Recovered:  08090a0b0c0d0e0f101112131415161718191a1b1c1d1e
Tampered:   authentication failed

The code above imports a small AES from a file named aes_core.py. It is a plain implementation of FIPS 197, written for clarity.

# aes_core.py
#
# A small AES block cipher (FIPS 197) used by the AEAD modes in this guide.
# Only encryption of one 16-byte block is needed: CCM, SIV, and OCB all use
# AES in the forward direction for the parts shown here, except OCB, which
# also needs decryption of a block in its own decrypt path.


def xtime(a):
    a <<= 1
    if a & 0x100:
        a ^= 0x11B
    return a


def gmul(a, b):
    result = 0
    while b:
        if b & 1:
            result ^= a
        a = xtime(a)
        b >>= 1
    return result


def build_sbox():
    """The AES S-box: inversion in GF(2^8) followed by an affine map."""
    inverse = [0] * 256
    for a in range(1, 256):
        for b in range(1, 256):
            if gmul(a, b) == 1:
                inverse[a] = b
                break
    box = []
    for a in range(256):
        x = inverse[a]
        y = x ^ ((x << 1) | (x >> 7)) & 0xFF ^ ((x << 2) | (x >> 6)) & 0xFF ^ ((x << 3) | (x >> 5)) & 0xFF ^ ((x << 4) | (x >> 4)) & 0xFF ^ 0x63
        box.append(y & 0xFF)
    return box


SBOX = build_sbox()
INV_SBOX = [0] * 256
for _i, _v in enumerate(SBOX):
    INV_SBOX[_v] = _i


def expand_key(key):
    if len(key) not in (16, 24, 32):
        raise ValueError("AES keys are 16, 24 or 32 bytes")
    nk = len(key) // 4
    rounds = nk + 6
    words = [list(key[4 * i:4 * i + 4]) for i in range(nk)]
    rcon = 1
    for i in range(nk, 4 * (rounds + 1)):
        temp = list(words[i - 1])
        if i % nk == 0:
            temp = temp[1:] + temp[:1]
            temp = [SBOX[b] for b in temp]
            temp[0] ^= rcon
            rcon = xtime(rcon)
        elif nk > 6 and i % nk == 4:
            temp = [SBOX[b] for b in temp]
        words.append([a ^ b for a, b in zip(words[i - nk], temp)])
    return [sum(words[4 * r:4 * r + 4], []) for r in range(rounds + 1)]


def sub_bytes(s, box):
    return [box[b] for b in s]


def shift_rows(s):
    return [s[(i + 4 * (i % 4)) % 16] for i in range(16)]


def inv_shift_rows(s):
    return [s[(i - 4 * (i % 4)) % 16] for i in range(16)]


def mix_columns(s):
    out = []
    for c in range(4):
        a = s[4 * c:4 * c + 4]
        out += [gmul(a[0], 2) ^ gmul(a[1], 3) ^ a[2] ^ a[3],
                a[0] ^ gmul(a[1], 2) ^ gmul(a[2], 3) ^ a[3],
                a[0] ^ a[1] ^ gmul(a[2], 2) ^ gmul(a[3], 3),
                gmul(a[0], 3) ^ a[1] ^ a[2] ^ gmul(a[3], 2)]
    return out


def inv_mix_columns(s):
    out = []
    for c in range(4):
        a = s[4 * c:4 * c + 4]
        out += [gmul(a[0], 14) ^ gmul(a[1], 11) ^ gmul(a[2], 13) ^ gmul(a[3], 9),
                gmul(a[0], 9) ^ gmul(a[1], 14) ^ gmul(a[2], 11) ^ gmul(a[3], 13),
                gmul(a[0], 13) ^ gmul(a[1], 9) ^ gmul(a[2], 14) ^ gmul(a[3], 11),
                gmul(a[0], 11) ^ gmul(a[1], 13) ^ gmul(a[2], 9) ^ gmul(a[3], 14)]
    return out


def add_round_key(s, k):
    return [a ^ b for a, b in zip(s, k)]


class AES:
    def __init__(self, key):
        self.round_keys = expand_key(key)

    def encrypt_block(self, block):
        if len(block) != 16:
            raise ValueError("a block is 16 bytes")
        s = add_round_key(list(block), self.round_keys[0])
        for r in range(1, len(self.round_keys) - 1):
            s = add_round_key(mix_columns(shift_rows(sub_bytes(s, SBOX))), self.round_keys[r])
        s = add_round_key(shift_rows(sub_bytes(s, SBOX)), self.round_keys[-1])
        return bytes(s)

    def decrypt_block(self, block):
        if len(block) != 16:
            raise ValueError("a block is 16 bytes")
        s = add_round_key(list(block), self.round_keys[-1])
        for r in range(len(self.round_keys) - 2, 0, -1):
            s = inv_mix_columns(add_round_key(sub_bytes(inv_shift_rows(s), INV_SBOX), self.round_keys[r]))
        s = add_round_key(sub_bytes(inv_shift_rows(s), INV_SBOX), self.round_keys[0])
        return bytes(s)


if __name__ == "__main__":
    key = bytes.fromhex("000102030405060708090a0b0c0d0e0f")
    block = bytes.fromhex("00112233445566778899aabbccddeeff")
    aes = AES(key)
    ciphertext = aes.encrypt_block(block)
    print("Key:        " + key.hex())
    print("Plaintext:  " + block.hex())
    print("Ciphertext: " + ciphertext.hex())
    print("Recovered:  " + aes.decrypt_block(ciphertext).hex())

It prints the FIPS 197 example:

Key:        000102030405060708090a0b0c0d0e0f
Plaintext:  00112233445566778899aabbccddeeff
Ciphertext: 69c4e0d86a7b0430d8cdb78070b4c55a
Recovered:  00112233445566778899aabbccddeeff

I checked this code in three ways before writing it up. The AES itself matches the FIPS 197 example and Node’s OpenSSL on 120 random blocks of all three key sizes. It reproduces all 24 packet vectors of RFC 3610, including B0, every CBC-MAC step, and every counter block, which is 72 MAC steps. It passes the AES-128 AES-CCM cases of the Wycheproof test suite that fit its parameters, 135 valid and 27 invalid. It also agrees with the OpenSSL that ships inside Node.js on 300 random cases, covering AES-128, AES-192, and AES-256 and every tag and nonce size. Changing any byte of the ciphertext or the associated data makes decryption fail.

Limitations

This is a faithful teaching version of the mode, not a production one:

• Never reuse a nonce. The code does not track nonces. Reusing one under the same key breaks both secrecy and authenticity.
• Not constant-time. The AES here uses table lookups on secret data, and Python is not suitable for real encryption.
• Whole messages only. CCM needs the message length before it starts, so this code works on complete messages in memory.
• Not parallel. Counter mode can run on many blocks at once, but the CBC-MAC cannot, because each block waits for the previous state. On modern CPUs, CCM is often slower than GCM or OCB for this reason.
• Short tags are risky. A 4-byte tag leaves an attacker with a chance of about one in four billion per forgery attempt. Use 16 bytes where you can. NIST SP 800-38C, Appendix B, says a tag shorter than 64 bits should not be used unless the protocol limits how often verification can fail under one key. The rule is Tlen >= lg(MaxErrs / Risk). Here Tlen is the tag length in bits, MaxErrs is the number of failures allowed before the key is retired, and Risk is the acceptable chance of accepting a forgery. NIST’s own example allows a 32-bit tag with at most 1,024 failures and a one-in-a-million risk.

Security Status

CCM has a security proof that ties its strength to that of the underlying block cipher. Jakob Jonsson presented the proof at the SAC 2002 conference, and the paper is titled “On the Security of CTR + CBC-MAC”. No practical attack on AES-CCM is known, as long as nonces are never reused and the tag is long enough.

The main practical risk is misuse. A repeated nonce under one key lets an attacker recover the XOR of two plaintexts, because counter mode leaks the XOR when a keystream repeats. CCM also shares the design drawbacks of a two-pass mode: it is not online, so the length must be known in advance, and it runs two AES calls for each block. Where speed and streaming matter, AES-GCM, ChaCha20-Poly1305, and OCB are common alternatives.

FAQ

What is the difference between CCM and GCM?

Both are AEAD modes with counter-mode encryption. CCM authenticates with a CBC-MAC and needs two AES calls per block. GCM authenticates with a Galois-field multiplication and can run in a single pass. CCM needs only the forward AES direction and no multiplier, which helps on tiny hardware.

Why must the message length be known in advance?

The very first block, B0, contains the message length. The CBC-MAC cannot start until the length is known, so CCM cannot process an unbounded stream. This is the meaning of “not online”.

What does the associated data do?

It is authenticated but not encrypted. A packet header is a typical example: routers need to read it, but nobody should be able to change it without detection. Changing one bit of the associated data changes the tag.

How long should the tag be?

Use 16 bytes if you can, and at least 8. Some protocols use 4 or 8 bytes to save space in each packet, but a short tag raises the chance that a forged message passes.

Why is the tag encrypted?

The raw CBC-MAC value would leak information about the internal state. XORing it with the first bytes of AES(counter 0) hides it, and counter 0 is never used for data.

References

1. Whiting, D., Housley, R., and Ferguson, N. “Counter with CBC-MAC (CCM).” RFC 3610, 2003. Available at: https://www.rfc-editor.org/rfc/rfc3610

2. Dworkin, M. “Recommendation for Block Cipher Modes of Operation: The CCM Mode for Authentication and Confidentiality.” NIST Special Publication 800-38C, 2004.

3. Jonsson, J. “On the Security of CTR + CBC-MAC.” Selected Areas in Cryptography (SAC) 2002, Lecture Notes in Computer Science 2595, Springer, 2003.

4. Google. “Project Wycheproof: AES-CCM test vectors.” Available at: https://github.com/C2SP/wycheproof

5. Wikipedia. “CCM mode.” Available at: https://en.wikipedia.org/wiki/CCM_mode