# Proof that MAC is insecure

I've just started studying MACs and I faced the following challenge:

Let $F$ be a PRF over $(\mathcal{K,R,X})$ where $\mathcal{X} = \{0,1\}^{32}$

Let $\mathrm{CRC32}(m)$ be a function that takes inputs $m \in \{0,1\}^{\le \ell}$ and output a 32-bit string and

$\mathrm{CRC32}(m_1) \oplus \mathrm{CRC32}(m_2) = \mathrm{CRC32}(m_1 \oplus m_2)$.

Let's define a MAC system $(S,V)$ as:

• $\quad S(k,m) = \{r \small\xleftarrow[]{R}\mathcal{R},\quad t \leftarrow F(k,r) \oplus\mathrm{CRC32}(m), \quad \text{output} \;(r,t)\}$
• $\quad V(k,m,(r,t)) = \{ \mathtt{accept} \; \text{if} \;\; t = F(k,r) \oplus\mathrm{CRC32}(m), \quad \mathtt{reject} \; \text{otherwise} \}$

How can I prove that this MAC is insecure?

After thinking a lot about how an attacker could send queries (sending messages $m_i$ and receiving its correspondent tags $t_i$) to find an existential forgery, I read that although the attacker can send several queries, they may not help, so I wonder what else can I try in order to break it.

• Fix $k$, $r$, and $m$. Consider $t = F(k, r) \oplus \operatorname{CRC32}(m)$. Can you relate it to $t' = F(k, r) \oplus \operatorname{CRC32}(m \oplus \delta)$? – Squeamish Ossifrage May 1 '18 at 22:41
• well, $t' = t \oplus \mathrm{CRC32}(\delta)$ by the definition of $\mathrm{CRC32}$ – Daniel May 1 '18 at 22:54
• I think I got it. If I send some $m$, I will get some $t$. Than I can send $m \oplus \delta$ and get $t' = t \oplus \mathrm{CRC32}(\delta)$, so I know that If I send a message $m \oplus \gamma$, the tag will be $t \oplus \mathrm{CRC32}(\gamma)$, and I know both of them, so I get a existential forgery. Is that right? – Daniel May 1 '18 at 23:35
• Indeed, $t' = t \oplus \mathrm{CRC32}(\delta)$ is a valid tag for $m \oplus \delta$, which can be calculated without knowledge of the secret key, hence $(S, V)$ is insecure. – puzzlepalace May 1 '18 at 23:39
• @Daniel There's no need for the $\gamma$ part. Once you know a tag $(r, t)$ on an arbitrary message $m$, you can forge a tag $(r, t')$ with $t' = t \oplus \operatorname{CRC32}(\delta)$ on $m \oplus \delta$ for an arbitrary difference $\delta$. You don't need to know anything else: $t$ and $\delta$ are sufficient for you to compute $t'$, without knowledge of $k$. Not only is it existential, but it's selective and completely arbitrary: you can forge the tag for any message $m'$ of your choice by using $\delta = m \oplus m'$. – Squeamish Ossifrage May 2 '18 at 1:28

Fix $k$, $r$, and $m$. Consider $t = F(k, r) \oplus \operatorname{CRC32}(m)$. Can you relate it to $t' = F(k, r) \oplus \operatorname{CRC32}(m \oplus \delta)$?