# Is this MAC correct and secure?

Let $$m \in \{0, 1\}^{2n} = m_1 || m_2$$. Let's also assume that $$F_k$$ is a PRF and $$G$$ is a PRG defined as $$G: \{0, 1\}^n \rightarrow \{0, 1\}^n$$. Now, Let's define the $$MAC$$ scheme as follows:

$$MAC(m) = F_{m_1}(k \oplus G(k\oplus m_2))$$

Where $$k \in \{0, 1\}^n$$. I think it's correct, but I have not seen much examples of using the message itself as PRF's key. That is why I am getting confused. Is it correct and/or secure?

• Hint: $G$ can have the property that $G(x\|0) = G(x\|1)$ (i.e., insensitive to the last bit of its input) and still be a secure PRG. – Mikero Dec 11 '18 at 1:28

The security property of MAC says that, every poly-time adversary who has access to a MAC oracle (the oracle outputs MAC on input message) cannot come up with a MAC on a message of his choice (without querying the oracle) with non-negligible probability. In your construction, suppose you know that $$G(x) = G(x')$$ for some known values $$x, x'$$. Then an adversary can query for MAC on $$m_1 || x$$ (for any message $$m_1$$) and then obtain MAC for $$m_1 || x'$$.
Note: It's easy to construct a PRG $$G$$ such that $$G(x) = G(x')$$. Take any PRG $$G'$$ and pick any two values $$x,x'$$. Construct $$G$$ as follows. $$G(y) = G'(y)$$ if $$y \neq x$$. $$G(y) = G'(x')$$ if $$y = x$$. Note that $$G$$ is a PRG if $$G'$$ is a PRG.