The idea of verifying message integrity is similar to the use of checksum. However, checksum only offers protection against random errors/modifications of message but not against an adversarial tempering.
There are three kinds of attacks, from strongest to weakest:
Total break: adversary can reconstruct key
Universal forgery: adversary can construct a valid tag for every message
Existential forgery: adversary can construct a valid tag for some message
Here we define a security notion that not only renders existential forgery impossible, but does so even the adversary can access to the function to create valid pairs of message-tag , on the condition that no longer counts as a successful existential forgery.
Let define a security game:
Note: there is no encryption here. MAC only protects integrity, not privacy.
Proof. The correctness is immediate. We show the security by a contradiction.
Assume that the scheme is not EUF-CMA-secure, meaning that there is a PPT adversary that wins the game with noticeable probability. We construct an adversary that uses to break the security of . Specifically, plays the game FN-IND defined on while simulating as follows:
For :
receives from and sends to its Cha
receives from its Cha and forwards to
receives from
sends to its Cha and gets back
If then output 1 ( is a pseudorandom function)
Otherwise, output 0 ( is a truly random function).
Observe here that
If is a pseudorandom function then the game that is playing is exactly the EUF-CMA game defined on the MAC scheme given in the theorem statement. This means that, by our assumption, will win this game with noticeable probability.
On the other hand, if is a truly random function, can not do noticeably better than random guess. Then in this case, the probability that output 1 is exactly the probability that guesses correctly, which is and is negligible.
It follows that for some polynomial and . This contradicts the fact that is a PRF family and concludes the proof. ◻