Let (S,V) be a secure MAC defined over $(K,M,T)$ where $M = \{0,1\}^n$ and $T =\{0,1\}^{128}$. Which of the following is a secure MAC:

  1. $S'(k,m) = S(k,m)[0,\ldots,126]\quad and \quad V'(k,m,t) = \big[V(k,\ m,\ t\big\|0) \ \text{ or }\ V(k,\ m,\ t\big\|1)\ \big] $

  2. $S'(k,m) = S(k,m)\quad and \quad V'(k,m,t) = \big[V(k,\ m,\ t) \text{ or } V(k,\ m \oplus 1^n,\ t)\big] $

  3. $S'(k,\ m) = \big[ t \gets S(k,m),\ \text{output } (t,t)\ \big)\quad and \quad V'\big(k,m,(t_1,t_2)\big) = \begin{cases} V(k,m,t_1) & \text{if } t_1 = t_2 \\ \text{"0"} & \text{otherwise} \end{cases} $

  4. $S'(k, m) = S(k, m \oplus 1^n)\quad and \quad V'(k, m, t) = V(k, m \oplus 1^n, t).$

  5. $ S'(k,m) = S(k,\ \ m[0,\ldots,n-2] \big\| 0)\quad and \quad V'(k,m,t) = V(k,\ \ m[0,\ldots,n-2] \big\| 0,\ \ t) $
  6. $ S'(k,m) = S(k,m \oplus m)\quad and \quad V'(k,m,t) = V(k,\ m \oplus m,\ t) $

The first one I think it's a secure MAC, but I don't now how to prove.

For the 5th one I think that it's not a secure MAC beacuse I can just ask for the tag of 0000...01 and I find out the tag for $0^n$, which is a valid one. So, it's not secure.

For the sixth, I can ask for $S'(k, 1^n)$ and I find out $S(k, 0^n)$, which is $S'(k, 0^n)$, so it's not a secure MAC.

Is my way of thinking correct? how about the others MACs?
thank you!

  • $\begingroup$ Yes, you are heading the right way. But I think 1 is not secure because if someone has found two different messages $m_1, m_2$, whose tags differ only at the last bit, then security is compromised. $\endgroup$ – user110219 May 17 '15 at 17:44
  • $\begingroup$ @user110219: how would security be compromised? Remember, MACs need not be compromised if you find a 'collision'; that are compromised if the attacker finds a new message/tag pair. $\endgroup$ – poncho May 18 '15 at 13:57
  • $\begingroup$ @poncho, I think my statement is not contradictory to yours so if you check 1 and then read my comment. Everything will be clear. $\endgroup$ – user110219 May 18 '15 at 14:21
  • $\begingroup$ Shouldn't the attacker be able to explicitly say which is the pair (m, t) of a message and a valid tag for it? How could he find this pair in the case of the first MAC? $\endgroup$ – KrasivaM May 18 '15 at 14:28
  • $\begingroup$ @KrasivaM, I don't know how to find such a pair. But what we know is that if someone finds two different messages $m_1, m_2$ where they differ only at the last bit, then we are in danger because of the verification algorithm. $\endgroup$ – user110219 May 18 '15 at 14:40

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.