MAC Constructions from PRFs
Stub. Beyond the MAC definition and basic CBC-MAC (already covered): why MAC verification queries don't help an attacker, the prefix-free-PRF framework for authenticating variable-length messages (CBC and cascade constructions), the extension attacks that break naive CBC/cascade as MACs, and the three standard fixes — ECBC/NMAC (encrypted PRF), prefix-free encodings, and CMAC — plus converting a block-wise PRF to a bit-wise one, the ANSI CBC-MAC/CMAC/PMAC case studies, and searching on encrypted data as a fun application.
Corresponds to Chapter 6 (the MAC definition and the basic idea of CBC-MAC are already covered in message-authentication-and-hash-functions). The subtlety this note covers is authenticating variable-length messages: a PRF is only secure as a MAC directly if the message space has fixed length, or if it’s prefix-free (no message is a prefix of another), which CBC and cascade constructions achieve by construction — but naive CBC/cascade MACs are still vulnerable to extension attacks when prefix-freeness is violated by an attacker appending blocks. Covers the three standard remedies: ECBC/NMAC (encrypt the PRF’s output with a second, independent key), prefix-free encodings (prepend the message length), and CMAC (XOR a derived subkey into the last block) — plus converting a block-wise PRF into a bit-wise one for arbitrary bit-length messages, and the ANSI CBC-MAC/CMAC/PMAC (parallelizable) standards as case studies.
Outline (TODO — flesh out each)
- MAC verification queries do not help the attacker
- Prefix-free PRFs for long messages — CBC and cascade constructions
- Extension attacks: why CBC and cascade are insecure MACs directly
- ECBC and NMAC — encrypted PRF
- Prefix-free encodings
- CMAC
- Converting a block-wise PRF to a bit-wise PRF
- Case studies: ANSI CBC-MAC, CMAC, PMAC
- Fun application: searching on encrypted data