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.