How does MAC verification work with CBC-MAC, and what probability guarantees does it provide?

Both sender and receiver compute the MAC independently using the same shared key; if the MACs match, the message is authentic — with near-certainty but not 100%.

Verification process:

1. Sender: Computes $MAC = CBC\text{-}MAC_K(\text{message})$ using shared key $K$
2. Sender: Transmits message + MAC over the channel
3. Receiver: Computes $MAC' = CBC\text{-}MAC_K(\text{received message})$ using the same key $K$
4. Compare: If $MAC = MAC'$ → message is authentic

Probability guarantees:

• If MACs match → authentic to 99.99...9% (not quite 100%, since collisions theoretically exist)
• If MACs don't match → 100% tampered (or transmission error)

Why not 100% certainty for match? Because hash functions compress — infinitely many inputs map to $2^n$ outputs. By pigeonhole principle, collisions exist. But for a well-designed MAC with a sufficiently large output (e.g., 128+ bits), the probability of an accidental or intentional collision is negligible ($\approx 2^{-128}$).

Key requirement: Both parties must possess the same secret key — this is why MAC is a symmetric (shared-secret) mechanism.