Let $(Mac, Vrfy)$ be a safe defined $MAC$ over $(K,M,T)$ where $ M = \{0,1\}^n$ and $T = \{0,1\}^{128}$.
Is the following $MAC$ safe? Show your proof.

$Mac'(k,m) = Mac(k, m ⊕ m)$
$Vrfy'(k,m,t) = Vrfy(k,m ⊕ m, t)$

I have no idea how I can prove this, please help. How would I go about proving this? Thank you for your help.

So I tried something, I don't know if it is correct tho, can you please confirm it?
So, because $m⊕m = 0$ the $Mac'(k,m) = Mac(k, m ⊕ m)$ produces a tag $t$ for $0$ and $k$ key, it means that $Vrfy'(k,m,t) = Vrfy(k,m ⊕ m, t)$ will always return $true$ because it verifies the same $m⊕m$ message which is $0$ and $k$ key, which is equal to the returned $t$ ? is that correct?

  • $\begingroup$ Is there an efficient attack on it? ​ If no, why? ​ ​ ​ ​ $\endgroup$ – user991 Jun 7 '16 at 12:15
  • 2
    $\begingroup$ Hint: what is $m \oplus m$? $\endgroup$ – poncho Jun 7 '16 at 12:17
  • $\begingroup$ @poncho the sent message XOR sent message ? What exactly do you mean by that question? Sorry, I really don't understand what I have to be looking for, I am a newbie and I have an exam in 3 days and I need to understand this type of problems. $\endgroup$ – southpaw22 Jun 7 '16 at 12:25
  • $\begingroup$ And when you xor anything with itself, what is the result? $\endgroup$ – poncho Jun 7 '16 at 12:29
  • $\begingroup$ @poncho XOR-ing something with itself gives you $0$, right? so $m⊕m = 0$ ? Is that right ? $\endgroup$ – southpaw22 Jun 7 '16 at 12:45

I think you have the right idea; here's a more formal way of saying it.

A MAC is secure if an attacker who, given an Oracle that can generate MACs for messages (with a secret random key), cannot (with nontrivial probability) generate a valid Message, MAC pair for a Message he has not queried the Oracle.

For $Mac'$, what the attacker could do is select a message (for example, the string $0$), and query the Oracle for the corresponding tag $T$. So, the attacker knows that $0, T$ is a valid message/tag pair (but that doesn't count for the goal, as he asked for that message).

So, the attacker selects a different message for the same length (for example, the string $1$), and form the message pair $1, T$ (where $T$ is the tag he got previously). As $Vrfy'(k, 1, T) = Vrfy(k, 1 \oplus 1, T) = Vrfy(k, 0 \oplus 0, T) = Vrfy'(k, 0, T)$ evaluates to true (as $0, T$ is a valid pair), so is $1, T$ as well (and so the attacker wins, as he has found the MAC for a message he didn't ask for)

| improve this answer | |
  • $\begingroup$ I see now, wow I would have never thought using the previous tag with a new message to see if it evaluates true, amazing, I understand now, thank you! $\endgroup$ – southpaw22 Jun 7 '16 at 14:03

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.