0
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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)$? $\endgroup$
    – Squeamish Ossifrage
    May 1 '18 at 22:41
  • $\begingroup$ well, $t' = t \oplus \mathrm{CRC32}(\delta)$ by the definition of $\mathrm{CRC32}$ $\endgroup$
    – Daniel
    May 1 '18 at 22:54
  • $\begingroup$ 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? $\endgroup$
    – Daniel
    May 1 '18 at 23:35
  • 1
    $\begingroup$ 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. $\endgroup$
    – puzzlepalace
    May 1 '18 at 23:39
  • 1
    $\begingroup$ @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'$. $\endgroup$
    – Squeamish Ossifrage
    May 2 '18 at 1:28
0
$\begingroup$

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)$?

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.