1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Mikero Dec 11 '18 at 1:28
1
$\begingroup$

No. The construction is not secure!

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.

$\endgroup$

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.