CMAC & Poly1305: Block-Cipher MACs

A Message Authentication Code (MAC) takes a key and a message and produces a tag. The tag proves the message has not been tampered with and was produced by someone who holds the key.

HMAC uses a hash function as its primitive. CMAC and Poly1305 instead use block ciphers or polynomial arithmetic. Block-cipher MACs avoid hash-function dependency and integrate naturally with AES hardware.

CMAC (Cipher-based MAC) is defined in NIST SP 800-38B. It pads the message to a block boundary, derives two subkeys K1/K2 from the cipher, XORs them into the final block, then runs CBC mode without storing intermediate ciphertext.

K1 = AES_K(0^128) left-shifted by 1 bit, XORed with a constant if the MSB was 1. K2 = K1 similarly shifted. These subkeys bind the final partial block securely against length-extension.

Poly1305 is a one-time authenticator designed by Daniel Bernstein. It evaluates a polynomial over the prime 2^130-5, treating the message as polynomial coefficients and using a one-time key pair (r, s).

Tag = (sum of (m_i * r^i) mod 2^130-5) + s mod 2^128. The key r is clamped to 22 specific bits to prevent timing attacks. s is a 16-byte one-time addition mask.

Poly1305 is almost always paired with ChaCha20. ChaCha20 generates the one-time (r, s) from the stream cipher keystream, making the combined AEAD scheme provably secure and extremely fast on ARM/mobile CPUs.

AES-GCM authenticates using GHASH, a polynomial MAC over GF(2^128). AES-CMAC is simpler and used in IEEE 802.11i (WPA2) and TLS 1.2 cipher suites. GCM provides both encryption and authentication in one pass.

Poly1305 on ARM Cortex-A achieves ~1 cycle/byte using NEON intrinsics. AES-CMAC requires one AES block operation per 16-byte block. For bulk data, Poly1305 outperforms CMAC on hardware without AES-NI.

CMAC is existentially unforgeable under chosen-message attack assuming AES is a pseudorandom permutation. Poly1305 is information-theoretically secure given a truly random one-time key — forgery probability is at most 8*ceil(L/16)/2^106.

CMAC: WPA2, S/MIME, filesystem integrity. Poly1305: TLS 1.3 via ChaCha20-Poly1305, WireGuard VPN, Signal Protocol, Noise Protocol Framework. Both are widely deployed in high-security modern systems.

You have learned CMAC's CBC-based construction and Poly1305's polynomial arithmetic. Both are constant-time, secure MACs used in real-world protocols. Next: TLS/HTTPS and how all these primitives compose.