# Mac-sforge motivation for storing pairs

I don't understand why Q keeping pairs of instead of m like mac-forge solves the problem of generating a new tag on a previously authenticated message. Say, a previously authenticated message for "Cat" is tag 90, Adversary can retrieve (Cat, 90) from the query. However, if Adversary is able to successfully forge a new tag (Cat, 138), I almost feel as if sforge weakens the definition. Q has Cat, but it doesn't have 138 as the tag, so this will pass mac-sforge, but not pass mac-forge. Could someone clarify my confusion?

Relevant passage From Katz and Lindell:

"As defined, a secure MAC ensures that an adversary cannot generate a valid tag on a new message that was never previously authenticated. But it does not rule out the possibility that an attacker might be able to generate a new tag on a previously authenticated message. That is, a MAC guarantees that if an attacker learns tags t1, . . . on messages m1, . . ., then it will not be able to forge a valid tag t on any message m ̸∈ {m1, . . .}. However, it may be possible for an adversary to ”forge” a different valid tag t′1 ̸= t1 on the message m1. In general, this type of adversarial behavior is not a concern. Nevertheless, in some settings it is useful to consider a stronger definition of security for MACs where such behavior is ruled out.

Formally, we consider a modified experiment Mac-sforge that is defined in exactly the same way as Mac-forge, except that now the set Q contains pairs of oracle queries and their associated responses. (That is, (m, t) ∈ Q if A queried Mack(m) and received in response the tag t.) The adversary A succeeds (and experiment Mac-sforge evaluates to 1) if and only if A outputs (m,t) such that Vrfyk(m, t) = 1 and (m, t) ∈/ Q.

DEFINITION 4.3 A message authentication code Π = (Gen,Mac,Vrfy) is strongly secure, or a strong MAC, if for all probabilistic polynomial-time adversaries A, there is a negligible function negl such that: Pr[Mac-sforgeA,Π(n) = 1] ≤ negl(n)."

An attacker queries "Cat" and receives the tag "90". It then computes the tag "138" such that $$\mathsf{Vrfy}_k(\text{Cat},138)=1$$ and outputs the pair $$(\text{Cat},138)$$.
The regular $$\mathsf{MAC\text{-}forge}$$ experiment will reject this output. I.e., the attacker does not win, and therefore this security definition does not rule out the existence of said attacker.
The stronger $$\mathsf{MAC\text{-}sforge}$$ experiment will accept this output. I.e., the attacker wins, and therefore this security definition rules out the existence of said attacker.