# Forgery of the Carter-Wegman MAC

Consider the nonce-based Carter-Wegman MAC which works on key space $$K=\{0,1\}^n \times \{0,1\}^n,$$ message space $$M=\{0,1\}^{mn}$$, nonce space $$N=\{0,1\}^n$$ and the tag space $$T=\{0,1\}^n$$ as follows:

$$cwMAC_{h,k}(x,n)=H_h(x) \oplus E_k(n),$$

where $$x \in M$$, $$(h,k) \in K, n \in N, \{H_h\}_{h \in \{0,1\}^n}$$ is a AXU family where each $$H_h: M \rightarrow T$$ and $$\{E_k\}_{k \in \{0,1\}^n}$$ is a PEP family of block length $$n$$.

Suppose that when using $$cwMAC$$, an implementation error causes the system to re-use a nonce more than once. Let us show that the nonce-based Carter-Wegman MAC falls apart if this ever happens.

(a) Consider the nonce-based Carter-Wegman MAC where the AXU function H is instantiated by $$xPoly$$ defined as:

$$xPoly_h(x_1||x_2||\dots||x_m)= x_1h \oplus x_2h^2 \oplus \dots \oplus x_mh^m,$$

where additions and multiplications are in $$\mathbb{F_n}$$. Show that if the adversary obtains the tag on some one-block message $$m_1$$ using nonce $$n$$ and the tag on a different one-block message $$m_2$$ using the same nonce $$n$$, then the $$MAC$$ s becomes insecure: the adversary can forge the $$MAC$$ on any message of his choice with high probability.

(b) Consider the nonce-based Carter-Wegman $$MAC$$ with an arbitrary AXU hash function. Suppose that an adversary is free to re-use nonces at will. Show how to create a forgery.

This is what I have tried:

(a) Let $$(m_1,n)$$ be a message nonce pair and $$(m_2,n)$$ be another pair.

$$cwMAC_{(h,k)}(m_1,n)=xpoly_h(m_1) \oplus E_k(n)$$ = $$m_1h \oplus E_k(n)=t_1$$

$$cwMAC_{(h,k)}(m_2,n)=xpoly_h(m_2) \oplus E_k(n)$$ = $$m_2h \oplus E_k(n)=t_2$$

$$m_1h \oplus E_k(n) \oplus m_2h \oplus E_k(n) = t_1 \oplus t_2$$

$$\implies (m_1 \oplus m_2)h= t_1 \oplus t_2$$

Hence we can get the value of $$h$$ by solving the above equation:

$$E_k(n)=m_1h \oplus t_1$$

Now let $$m$$ be a one-block message and nonce $$n$$.

$$t=mh \oplus E_k(n)$$

$$(m,t)$$ is a valid forgery.

Therefore, the $$MAC$$ is not secure.

I am unsure about my approach. I have no idea about Part b.

• The attack for a) works out, though the conclusion is a bit too general. – SEJPM Feb 13 at 13:45
• Can you please write what needs to be added to make it precise? Thanks – Sayantan Feb 13 at 17:02
• You can't conclude "the MAC is insecure" from an attack that is outside most attack models. – SEJPM Feb 13 at 23:42
• Okay, I am very new to this, Can you please help me in solving this? – Sayantan Feb 13 at 23:49