PRF ⇒ MAC (CBC-MAC)

Fully-black-box reduction · standard model · BKR94 · security loss: for a forger making tag queries, the PRF distinguisher makes queries, plus additive

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.