Message authentication codes (HMAC, CMAC, Poly1305, KMAC)

Deep dive

How it works

In: random key (at least 128 bit), message (plus a unique nonce for Poly1305, GMAC) · Out: tag of 4-32 B · State: none, or cached key-derived values · Cost: O(n); short-message HMAC-SHA256 is 2 compressions cached, 4 uncached.

1. Sender computes t = MAC(K, m) over a canonical encoding of m (version, purpose, length-prefixed fields) and sends (m, t).
2. Receiver recomputes t' from the received m and compares with t in constant time.
3. On mismatch, reject before parsing or acting on m.

Constructions (checked against the texts in Sources):

• HMAC (RFC 2104): K0 = K zero-padded to the block size B (64 B for SHA-256, 128 B for SHA-512); a K longer than B is first replaced by H(K). Tag = H((K0 ⊕ opad) ‖ H((K0 ⊕ ipad) ‖ m)), ipad = 0x36 and opad = 0x5C repeated B times. The outer hash hides the inner state, blocking length extension; collision resistance of H is not needed (Bellare 2006).
• CMAC (SP 800-38B): L = E_K(0^128); K1 = L·x, K2 = K1·x in GF(2^128) (shift left, XOR 0x87 on carry-out; 0x1B for 64-bit blocks). CBC-MAC the blocks, XORing K1 into a complete last block or K2 into a 10*-padded partial one, which repairs raw CBC-MAC's length forgery.
• Poly1305 and GMAC (RFC 8439, SP 800-38D): evaluate a polynomial of the message at a secret point, then add a one-time mask. Poly1305: 32 B key (r, s), r clamped, mod 2^130 - 5, tag (acc + s) mod 2^128; in ChaCha20-Poly1305 the key is ChaCha20 block 0 of the same (key, nonce). GMAC is GCM with empty plaintext. A repeated nonce repeats the one-time key, which leaks the plaintext XOR (RFC 8439) and enables forgeries. Forgery probability about n/2^102 for n 16 B blocks.
• KMAC (SP 800-185): KMAC128(K, X, L, S) = cSHAKE128(bytepad(encode_string(K), 168) ‖ X ‖ right_encode(L), L, "KMAC", S). L is in the input, so tags of different lengths are unrelated.
• BLAKE3 keyed_hash: the 256-bit key replaces the IV words and a KEYED_HASH flag is set in every compression: no extra compressions (HMAC needs three, per the spec).
• SipHash-2-4: 128-bit key, 64-bit output, built for short inputs. A 64-bit tag suits hash tables, not remote authentication under unbounded guessing.

Why H(key ‖ msg) is wrong. SHA-256 and SHA-512 output their final chaining state, so from H(k ‖ m) and |k| an attacker computes H(k ‖ m ‖ padding ‖ x) without k. H(m ‖ k) turns any collision of H into a forgery under every key.

Code

Rust, sha2 = "0.11" (0.10 works too), dev-dependency hmac = "0.13". RFC 2104 HMAC on the direct Sha256 API with cached pad states, RFC 4231 vectors, constant-time compare; passes cargo test.

use sha2::{Digest, Sha256};

const B: usize = 64; // SHA-256 block size, RFC 2104 "B"

#[derive(Clone)]
pub struct HmacSha256 {
    inner: Sha256, // state after absorbing K0 ^ ipad
    outer: Sha256, // state after absorbing K0 ^ opad
}

impl HmacSha256 {
    pub fn new(key: &[u8]) -> Self {
        let mut k0 = [0u8; B]; // zero padded
        if key.len() > B {
            k0[..32].copy_from_slice(&Sha256::digest(key)); // long key: hash first
        } else {
            k0[..key.len()].copy_from_slice(key);
        }
        let (mut ipad, mut opad) = ([0x36u8; B], [0x5cu8; B]);
        for i in 0..B {
            ipad[i] ^= k0[i];
            opad[i] ^= k0[i];
        }
        let (mut inner, mut outer) = (Sha256::new(), Sha256::new());
        inner.update(ipad);
        outer.update(opad);
        Self { inner, outer }
    }

    // H((K0^opad) || H((K0^ipad) || msg)); cloning skips 2 compressions per call
    pub fn mac(&self, msg: &[u8]) -> [u8; 32] {
        let mut i = self.inner.clone();
        i.update(msg);
        let mut o = self.outer.clone();
        o.update(i.finalize());
        o.finalize().into()
    }

    // accepts truncations of at least 4 B (SP 800-107r1)
    pub fn verify(&self, msg: &[u8], tag: &[u8]) -> bool {
        (4..=32).contains(&tag.len()) && ct_eq(&self.mac(msg)[..tag.len()], tag)
    }
}

// no early exit; the length is public
pub fn ct_eq(a: &[u8], b: &[u8]) -> bool {
    if a.len() != b.len() {
        return false;
    }
    let mut diff = 0u8;
    for (x, y) in a.iter().zip(b) {
        diff |= x ^ y;
    }
    std::hint::black_box(diff) == 0
}

#[cfg(test)]
mod tests {
    use super::*;
    fn hex(s: &str) -> Vec<u8> {
        (0..s.len() / 2).map(|i| u8::from_str_radix(&s[2 * i..2 * i + 2], 16).unwrap()).collect()
    }

    #[test]
    fn rfc4231() {
        // test cases 6 (131 B key > block size) and 5 (truncated to 128 bit)
        let t6 = HmacSha256::new(&[0xaa; 131]).mac(b"Test Using Larger Than Block-Size Key - Hash Key First");
        assert_eq!(t6.to_vec(), hex("60e431591ee0b67f0d8a26aacbf5b77f8e0bc6213728c5140546040f0ee37f54"));
        let h = HmacSha256::new(&[0x0c; 20]);
        let tag = hex("a3b6167473100ee06e0c796c2955552b");
        assert!(h.verify(b"Test With Truncation", &tag));
        assert!(!h.verify(b"Test With Truncation", &tag[..3])); // under 32 bit refused
        let mut bad = tag.clone();
        bad[15] ^= 1;
        assert!(!h.verify(b"Test With Truncation", &bad));
        assert!(ct_eq(b"abc", b"abc") && !ct_eq(b"abc", b"abd"));
    }

    #[test]
    fn matches_hmac_crate() {
        use hmac::{Hmac, KeyInit, Mac};
        for (klen, mlen) in [(0usize, 0usize), (64, 56), (65, 1000), (131, 3)] {
            let key: Vec<u8> = (0..klen).map(|i| (i * 7 + 3) as u8).collect();
            let msg: Vec<u8> = (0..mlen).map(|i| (i * 13 + 1) as u8).collect();
            let mut m = Hmac::<Sha256>::new_from_slice(&key).unwrap();
            m.update(&msg);
            assert_eq!(HmacSha256::new(&key).mac(&msg), <[u8; 32]>::from(m.finalize().into_bytes()));
        }
    }
}

Complexity and constants

• Time O(n). HMAC-SHA256: ceil((n+9)/64) inner compressions, 1 outer, plus 2 pad blocks unless cached; a 16 B message costs 4 compressions uncached, 2 cached.
• Tags: HMAC-SHA256 32 B, CMAC-AES and Poly1305 16 B, SipHash 8 B; cached key state order of 100 B (SP 800-38B caps a CMAC key at 2^48 messages).
• Drivers: compressions, key setup per call, allocation; constant-time compare of 32 B about 2 ns here.

Efficiency

• Cost: measured, Apple M4 Pro, Rust 1.99.1, best of 5, noisy 10-20 %. 16 B message, sha2 0.11.1: hand HMAC about 98 ns uncached, 54-63 ns cached; hmac crate 98 and 52 ns; BLAKE3 keyed about 51 ns; SipHash-2-4 about 9 ns. 64 B: HMAC 111 and 70-73 ns; BLAKE3 about 52 ns; SipHash about 23 ns. Bound: compression count.
• Levers:
  • Cache ipad/opad states — about 1.8x measured (98 to 54 ns, 16 B; RFC 2104 section 4) — many short messages, one key.
  • Hardware SHA-256 — about 4.5x measured (127 ns per block with sha2 0.10.9, 28 ns with 0.11.1; presumably SHA extensions) — verify your crate version uses them.
  • Keyed native modes (BLAKE3, KMAC) — no extra compressions (specs); on par with cached HMAC here — CPUs without SHA instructions.
  • One tag per batch (hash chain, Merkle root) — one MAC for many messages — partial delivery acceptable.
  • Truncate tags — saves wire bytes, not CPU — constrained links.
• Naive → standard → state of the art:
  • Naive · HMAC rebuilt per message, software SHA, ==; about 500 ns (measured, 16 B, sha2 0.10)
  • Standard · cached HMAC-SHA256, hardware SHA, constant-time verify; about 55 ns
  • State of the art · the AEAD's own tag if encrypting anyway; BLAKE3 keyed; SipHash for hash tables

Implementation notes

• Truncation keeps the leftmost bits. RFC 2104: at least half the hash length and 80 bits. SP 800-107r1: at least 32 bits, retiring the key before 2^t failed verifications (forgery chance per attempt about 2^-(λ-t)). SP 800-38B: Tlen at least 64 unless failed verifications are bounded, then Tlen at least lg(MaxInvalids/Risk). IPsec uses HMAC-SHA-256-128 (RFC 4868), SRTP an 80-bit HMAC-SHA1 tag (RFC 3711). Default here: 16 B; under 8 B only with rate-limited verification.
• Constant time: full-tag compare, no early exit (verify_slice, ring::hmac::verify, subtle); reject wrong lengths first.
• Key separation: a random key of at least 32 B per purpose and direction, from HKDF with distinct info, plus a purpose label in the MAC input. The BLAKE3 spec's warning: HKDF-Expand equals one HMAC call, so a key shared by both can collide.
• Length-prefix fields so ("ab","c") and ("a","bc") differ. A MAC proves origin, not freshness: add a counter or timestamp and check it after the tag.

Pitfalls

• == or memcmp on tags: timing leaks the tag byte by byte.
• H(key ‖ msg) with SHA-256 or SHA-512: length extension.
• One key for MAC and encryption, or for HMAC and HKDF.
• Poly1305 or GMAC under a repeated nonce.
• 32-bit tags with unlimited verification attempts.
• Handing the key to a verifier you do not trust: they can forge.

Variants and alternatives

In production

• Payments and cloud: webhook signatures (GitHub X-Hub-Signature-256, Stripe), AWS Signature V4.
• Web: JWT HS256 (RFC 7518), SSH hmac-sha2-256 (RFC 6668), TLS 1.3 Finished and HKDF.
• Telecom and media: IPsec (RFC 4868), SRTP voice and video (RFC 3711).
• Hash tables: Rust HashMap uses SipHash 1-3 (std docs); also Linux, WireGuard, Bitcoin (author's list).

Implementations

Sources

• Krawczyk, Bellare, Canetti, RFC 2104: HMAC, 1997. RFC; Nystrom, RFC 4231, 2005. RFC
• Nir, Langley, RFC 8439: ChaCha20 and Poly1305 for IETF Protocols, 2018. RFC; Bernstein, The Poly1305-AES Message-Authentication Code, FSE 2005. paper
• Dworkin, NIST SP 800-38B: CMAC, 2016. spec; SP 800-38D: GCM and GMAC, 2007. spec
• Kelsey, Chang, Perlner, NIST SP 800-185, 2016. spec; SP 800-107 Rev. 1, 2012, section 5.3.3. spec
• Bellare, New Proofs for NMAC and HMAC: Security Without Collision-Resistance, CRYPTO 2006. paper
• Aumasson, Bernstein, SipHash: A Fast Short-Input PRF, Indocrypt 2012. paper · code
• O'Connor et al., BLAKE3: one function, fast everywhere, 2020, section 6.1. paper
• Kelly, Frankel, RFC 4868, 2007. RFC; Baugher et al., RFC 3711: SRTP, 2004. RFC