The usual definition of MAC security is (roughly) that there is no \"efficient\"
ID: 653265 • Letter: T
Question
The usual definition of MAC security is (roughly) that there is no "efficient" adversary that has non-negligible advantage in the "MAC game" where the MAC game is as follows: the challenger chooses a random key, the adversary sends some messages to the challenger, the challenger sends the MACs of those messages with the chosen key back to adversary. For the adversary to win, the adversary now has to come up with a forged message-MAC pair. The adversary's advantage is the probability that the adversary can win the game.
Every time the adversary plays, a new key is chosen by the challenger. Does it make a difference if we allow the adversary to have a "memory" of previous plays?
For example, in round 1 of the game the challenger generates a random key k1 and the adversary sends s messages getting back s tags, but has no idea of how to forge a MAC, losing round 1.
In round 2, the challenger generates a new random key k2, the adversary sends the same s messages and, because of some weakness in the MAC algorithm and the fact that keys k1 are k2 are different, in round 2 the adversary can now come up with a forgery. Of course, for this to make sense, the adversary must be allowed to "remember" the results from round 1.
Maybe there are MAC algorithms that are secure against adversaries that do not remember results from round-to-round but insecure against adversaries that are allowed to have some memory.
Adversaries with this sort of memory are at least as strong as adversaries without memory. Are they strictly stronger?
Explanation / Answer
Memory of the first round can't help the attacker win the second round.
If it could: the attacker could simulate the first round on his own (picking his own key, pretending to play the game against himself), and then play the second round against the challenger.
So, adversaries like this are not stronger -- not even if they have memory.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.