4
$\begingroup$

Given two MAC schemes $\prod_1 = (keyGen_1, S_1, V_1)$ and $\prod_2=(keyGen_2, S_2, V_2)$.

$\prod_3$ runs $keyGen$ from $\prod_1$ and $\prod_2$, respectively, to obtain $(k_1, k_2)$. $\prod_3$, where $S_3 = ((k_1,k_2), (m_1,m_2))$ then runs $S_1(k_1,m_1)\rightarrow t_1$ and $S_2(k_2,m_2)\rightarrow t_2$. And obtain $t_3 := t_1||t_2$. Would $\prod_3$ be a secure MAC?

And the follow up is when $t_3:= t_1 \oplus t_2 $, would this also be a secure MAC?

My guess is that the concatenation is secure because attackers would have no way of knowing how $t_1$ and $t_2$ is generated. For the second one, my intuition tells me that adversary can somehow swap the messages and produce a valid (m,t) pair?

|improve this question
$\endgroup$
  • 3
    $\begingroup$ Hint: What if $\Pi_1=\Pi_2$? $\endgroup$ – SEJPM♦ Apr 18 '17 at 16:07
  • $\begingroup$ Hint: for either definition of $\Pi_3$, suppose we had a way to break the security of $\Pi_3$, would that allow us to break the security assumptions of $\Pi_1$? $\endgroup$ – poncho Apr 18 '17 at 16:18
  • $\begingroup$ $S_3$ has a different input message domain than $S_1$ or $S_2$. How exactly are $m_1$ and $m_2$ created when some message $m$ is to be signed? $\endgroup$ – Artjom B. Apr 18 '17 at 21:54
  • $\begingroup$ @SEJPM, if $\Pi_1=\Pi_2$, then how it is possible to construct $\Pi_3$ that is ever secure? $\endgroup$ – Bango Apr 22 '17 at 22:30
  • 1
    $\begingroup$ Actually, my previous comments were wrong. I thought that if $\Pi_1=\Pi_2$ then you would sample the very same $k_1=k_2$ (which would lead to $t_3=0$). This is obviously wrong because you call the agorithms independently. $\endgroup$ – SEJPM♦ Apr 23 '17 at 17:51
4
$\begingroup$

In the first case, $\Pi_3$ is not secure.

We can use $(m_1, m_2)$ and $(m_3, m_4)$ to query the adversary $A$.

$t_1||t_2 = A(m_1, m_2)$

$t_3||t_4 = A(m_3, m_4)$

The forged MAC would be $t_1||t_4: Verify(t_1||t_4, (m_1, m_4)) \rightarrow Accept$.

In the second case, $\Pi_3$ is not secure.

We can use $(m_1, m_2)$ and $(m_1, m_3)$ to query the adversary $A$.

$t = t_1 \oplus t_2 = A(m_1, m_2)$

$t' = t_1 \oplus t_3 = A(m_1, m_3)$

$t_f = t \oplus t' = t_2 \oplus t_3$

The forged MAC would be $t_f: Verify(t_f, (m_2, m_3)) \rightarrow Accept$.

Another way to break the scheme is to reverse the message pair. $Verify(t, (m_2, m_1)) \rightarrow Accept$.

|improve this answer
$\endgroup$
  • $\begingroup$ Nice, another question without any answer off the list. Welcome to cryptography! Bango, if you're still around, could you have a look if this answers your old question as it may help others (even if it may be a bit late for yourself). $\endgroup$ – Maarten - reinstate Monica♦ Apr 28 at 23:29

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.