# Is this construction a secure MAC?

Let $F:\{ 0,1 \}^n \times \{ 0,1 \}^ n \rightarrow Z^*_q$ is a PRF, and $H:\{ 0,1 \}^{2n} \rightarrow \{ 0,1\}^n$ is a secure hash function. Is the following construction $\Pi=(Gen,Mac,Vrfy)$ is a secure MAC?

(Note that we redefined the condition of the attacker's success for pair $(m=a_1|a_2,~T)$, so that $Vrfy_K(m,T)=1$ ,and also $a_1|a_2$ or $a_2|a_1$ did not asked its oracle).

$K \leftarrow Gen(1^n):\\ ~~~~~~~~~k_1,k_2,k_3 \leftarrow \{ 0,1 \}^n \\ ~~~~~~~~~K=(k_1,k_2,k_3)$ $-----------------------------------$ $T \leftarrow Mac_K(m)\\ ~~~~~~~~~parse~m~as~~a_1|a_2 ~~where~ a_1,a_2 \in \{ 0,1 \}^n \\ ~~~~~~~~~parse~K~as~(k_1,k_2,k_3)\\ ~~~~~~~~~r \leftarrow F_{k_3}(H(a_1 | a_2) \oplus H(a_2 | a_1))\\ ~~~~~~~~~a \leftarrow F_{k_1}(a_1),~~~~s \leftarrow F_{k_2}(a_1)\\ ~~~~~~~~~b \leftarrow F_{k_1}(a_2),~~~~z \leftarrow F_{k_2}(a_2)\\ ~~~~~~~~~t_1 \leftarrow a \cdot (s+r),~~~~t_2 \leftarrow b \cdot (z-r)\\ ~~~~~~~~~T=(t_1,t_2)$ $-----------------------------------$ $b:=Vrfy_K(m,T)\\ ~~~~~~~~~parse~m~as~~a_1|a_2 ~~where~ a_1,a_2 \in \{ 0,1 \}^n \\ ~~~~~~~~~parse~K~as~(k_1,k_2,k_3)\\ ~~~~~~~~~parse~T~as~(t_1,t_2)\\ ~~~~~~~~~a \leftarrow F_{k_1}(a_1),~~~~s \leftarrow F_{k_2}(a_1)\\ ~~~~~~~~~b \leftarrow F_{k_1}(a_2),~~~~z \leftarrow F_{k_2}(a_2)\\ ~~~~~~~~~if ~(a^{-1}\cdot t_1 + b^{-1}\cdot t_2 =s+z) ~then\\ ~~~~~~~~~~~~b=1\\ ~~~~~~~~~else\\ ~~~~~~~~~~~~b=0\\$

If we take $H'$ as a standard secure hash function, we can define the hash function:
$$H(a | b) = \begin{cases} 0 || H'(a | b) & \text{if } a \ge b \\ 1 || H'(b | a) & \text{if } a < b \end{cases}$$
Note that if we find, say, a preimage or collision on $H$, this immediately gives us a preimage or collision on $H'$
And, with this hash function, the value $r$ defined during the MAC generation process is a key dependent constant; other than $r$, the first half of the tag is a function of the first half of the message, and the second half of the tag is a function of the second half of the message. Hence, given the MAC of the two messages $(x, y)$, and $(z, w)$, an adversary could easily predict the MAC the valid generator would produce for $(x, w)$ (which would be accepted, of course)
• Thank you so much. If we change to compute the value r and condition of the attacker's success for pair $(m=a1|a2, T)$ as follows, is this construction secure? $r \leftarrow F_{k_3}(H(a|b))$ where $a \leftarrow F_{k1}(a_1)$ and $b \leftarrow F_{k1}(a_2)$ , and also the condition be VrfyK(m,T)=1 ,and also a1≠a2 and a1|a2 or a2|a1 did not asked its oracle. – Robert Jul 14 '18 at 21:21