Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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