PRF ⇒ MAC (CBC-MAC)
Statement
Let be a PRF on with , write , and fix . CBC-MAC on is
For every efficient making queries there is an efficient making queries with
so CBC-MAC is a PRF on , and with canonical verification is a UF-CMA-secure MAC on — BKR94.
Sketch
runs and computes each CBC value with calls to its own oracle. The remaining term is the advantage of a computationally unbounded -query distinguisher between CBC-MAC over a uniformly random function on and a uniformly random function , which BKR94 bound by .
Notes
- The fixed length in the statement cannot simply be dropped: on , CBC-MAC is forged after one tagging query, since for a one-block message with tag , the two-block message has tag — standard.
- With a block cipher, a PRP in place of , the switching lemma applied to ‘s queries adds at most , so the bound keeps the form — standard.