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.

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

Your Answer

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

Browse other questions tagged or ask your own question.