Is this construction a secure MAC?

Question

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

Answer 1

No, it need not be a secure MAC, as one can devise a hash function that meets the standard hash function properties (preimage resistance, collision resistance), but makes this MAC insecure when used in this mode.

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)