I found a theorem that says:

Let $MAC = (S,V)$ be a MAC for short messages over $(K,M,T)$.
Let $H: M^{big} → M$.
Define $MAC^{big} = (S^{big},V^{big})$ over $(K,M^{big},T)$ as:
$S^{big}(k,m) = S(k,H(m))$ and $V^{big}(k,m,t) = V(k,H(m),t)$.

Theorem: If $MAC$ is a secure mac and $H$ is a collision-resistant hash function then $MAC^{big}$ is a secure MAC.

But I have not found the proof. How can we prove this fact?


1 Answer 1


The generic model for a MAC is the following: the attacker is given access to a block box which implements the $S$ function with a key $k$ that the attacker does not know of. The attacker is allowed to make $q$ requests to the box on messages that he can choose arbitrarily. The goal of the attacker is to make a forgery, i.e. produce values $m$ and $t$ such that $V(k,m,t) = \mathbf{true}$ but $m$ is distinct from all the $q$ messages sent as requests. In other words, the attacker obtains $q+1$ valid message+MAC pairs from only $q$ requests.

Now, suppose that a forgery is possible on $S^{big}$. This means that the attacker can send $m_1$, $m_2$,... $m_q$ to the box implementing $S^{big}$, obtain $t_1$, $t_2$,... $t_q$, and somehow compute $m$ and $t$ where $m$ is distinct from all the $m_i$, and $V^{big}(k,m,t) = \mathbf{true}$. Then look at $H(m)$ and compare it to all the $H(m_i)$; exactly one of the two following must hold:

  • If $H(m) = H(m_i)$ for some $i$, then, by construction, the attacker found a collision on $H$.
  • If $H(m) \ne H(m_i)$ for all $i$, then the attacker implicitly made $q$ requests to $S$ (for all $H(m_i)$) and then computed $m$, which means that $H(m)$ and $t$ are such that $V(k,H(m),t) = \mathbf{true}$. The attacker then succeeded at a forgery attack on $S$: he computed a pair containing a short message ($H(m)$) and a token $t$ which are accepted by $V$, and yet at no point was that exact $H(m)$ sent to the box implementing $S$.

It follows that if $S$ is strong against forgeries and $H$ is collision-resistant, then $S^{big}$ must also be strong against forgeries.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.