# Is following MAC schemes formed by MAC schemes secure?

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?

• Hint: What if $\Pi_1=\Pi_2$? – SEJPM Apr 18 '17 at 16:07
• 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$? – poncho Apr 18 '17 at 16:18
• $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? – Artjom B. Apr 18 '17 at 21:54
• @SEJPM, if $\Pi_1=\Pi_2$, then how it is possible to construct $\Pi_3$ that is ever secure? – Bango Apr 22 '17 at 22:30
• 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. – SEJPM Apr 23 '17 at 17:51

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$$.

• 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). – Maarten Bodewes Apr 28 at 23:29