# Forgery attack for Merkle–Damgård MAC scheme with prefix method

Consider a hash function $H$ based on an iterated hash function $H_0$ with $l$-bit block messages an the Merkle–Damgård strenghtening pad. That is, $m||pad(m)$ has a length multiple of $l$ and $H(m) =H_0(m||pad(m))$ We consider the MAC algorithm defined given a $l$-bit secret key K and a message m as $MAC_K(m) = H_0(K||m||pad(m))$ where || denotes the concatenation operation.

Show that given the MAC of a known message m the adversary is able to output a forgery on a message $m' \neq m$

The solution of the exercise forges MAC for message $m′ = m || pad(m) || m^⋆$ for arbitrary $m^*$. It hashes $m^*$ and uses $IV = MAC_K(m)$.

The problem is that I don't understand how this scheme works. First, what is the $f$ function of the drawing? Is it $H_0$? But then how is it that it is taking two parameters, namely, and $l-block$ and an IV? Also, can you do some math that show that this construction works?

A lot of this is explained well on the wikipedia article.

The function $f$ is called the compression function. It is a function $$f:\left\{0,1\right\}^n\times\left\{0,1\right\}^\ell\to\left\{0,1\right\}^n.$$

That is, it takes as input an $n$-bit value and an $\ell$-bit value, and outputs an $n$-bit value. This function is a building block for the function $H_0$. This function $H_0$ is called a hash function, with the restriction that its input is a multiple of $\ell$ bits. So we can think of it as a function $$H_0:\left(\left\{0,1\right\}^\ell\right)^*\to\left\{0,1\right\}^n.$$ By definition, $H_0$ is defined as \begin{align*} H_0(M_0||\cdots||M_t) &= f(\cdots f(f(f(IV,M_0),M_1),M_2)\cdots,M_t).\\ \end{align*} So we compute $f(IV,M_0)$, followed by $f(f(IV,M_0),M_1)$, etc.

The function $H$ is a hash function without the length restriction. We build it on top of $H_0$, so to do so we may have to pad the message to have length a multiple of $\ell$. That is, $H$ is a function $$H:\left\{0,1\right\}^*\to\left\{0,1\right\}^n$$ defined by $H(M)=H_0(M||pad(M))$.

So what is the relation between $f$ and $H$? Well, it can be shown that if $f$ is a collision-resistant one-way function, then $H$ is a collision-resistant hash function. So the idea of the Merkle-Damgard construction is that we can build collision-resistant hash functions from collision-resistant one-way functions.

You can make this hash function into a MAC function by prepending a key, so defining ${\tt MAC}_K(M)=H(K||M)$. The exercise asks you to show that this is not a good idea, i.e. for this MAC we can find forge a signature.

Constructing a forgery:

I feel this is the type of question that becomes hard by overload of notation. The best way (in my opinion) to get through this is to calmly figure out what all this notation means (which the above should help with), and then figure out what the question is asking. This is not always easy.

Show that given the MAC of a known message m the adversary is able to output a forgery on a message m′≠m

So, what does this mean? We are given a MAC of known message $m$, and are asked to output the MAC of any other message $m'$, as long as $m'\neq m$. Thus, the question can be rewritten as

Given ${\tt MAC}_K(m)$, compute ${\tt MAC}_K(m')$ for some $m'\neq m$.

Assume for simplicity of the argument that $K$ has length a multiple of $\ell$. By definition, we have \begin{align*} {\tt MAC}_K(m) &= f(\cdots f(f(f(IV,K),m_0),m_1)\cdots, ..||pad(m)). \end{align*}

From this, we see that the key is used only once. Moreover, it is used right at the start of the computation. The idea should thus be to choose $m'$ in such a way that the start overlaps with $m$. For example, take some $\ell$-bit message $m'_0$ and take $m'=m || pad(m) || m'_0$. By definition, \begin{align*} {\tt MAC}_K(m') &= f(f(\cdots f(f(f(IV,K),m_0),m_1)\cdots, ..||pad(m)),m'_0) \\ &= f({\tt MAC}_K(m),m'_0). \end{align*}

Hence we know ${\tt MAC}_K(m')$, and $m'\neq m$ since $m'$ is longer. The crux of the argument was appending $m'_0$ to $m$, which is a so-called length-extension attack. You can generalize this to appending any message of any length.

• I added some details on the forgery. Again, try to look past notation. Once you grasp the idea it should be much easier. – CurveEnthusiast Dec 1 '16 at 7:32