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


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)

  • $\begingroup$ 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. $\endgroup$ – Robert Jul 14 '18 at 21:21
  • $\begingroup$ A modified version of this question was raised in the form of a new question. You can access this question through the link crypto.stackexchange.com/q/60801/50330 . $\endgroup$ – Robert Jul 14 '18 at 22:22

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.