Building adversary to show a PRF is not secure Let $F(k,x)$ be a secure PRF over $(\mathcal{K},\mathcal{X},\mathcal{Y})$ where $\mathcal{K} = \mathcal{X} = \mathcal{Y} = \{0,1\}^n$.

Let $F'(k, x) = F(F(k, 0^n), x) \; \Vert \; F(k, x)$.

$a \; \Vert \; b$ means $a$ concatenated to $b$.

How can I show that $F'$ is not a secure PRF? I've been trying to build an adversary that could find some pattern but I couldn't. My  best guess was to initially use $x = 0^n$, so the output would be something like $F(k', 0^n) \; \Vert \; k'$ (where $k' = F(k, 0^n)$, which is the key of the left side) and I would be able to use $k'$ for the next calculations, but it didn't seem to be enought to find any pattern in the sequence of outputs.
Query $0^n$ to your oracle, receive $a\Vert b$ as a response.
If $F(b,0^n) = a$ output $1$, otherwise output $0$.

In the case that the oracle is $F'$, since $F'(k,x)$ is defined as $F(F(k,0^n),x)\Vert F(k,x)$ your response will be $a\Vert b = F(F(k,0^n),0^n)\Vert F(k,0^n) = F(k',0^n)\Vert k'$, it will always be true that $F(b,0^n) = a$. I.e.
$$\Pr_k[\mathcal{A}^{F'(k,\cdot)}(1^n)=1] = 1.$$

In the case that the oracle is a truly random function $g : \{0,1\}^n \times \{0,1\}^n  \to \{0,1\}^n$, $a$ is distributed uniformly and independently of $b$. Therefore the probability of $F(b,0^n) = a$ is $2^{-n}$. Thus,
$$\Pr_g[\mathcal{A}^{g(\cdot)}(1^n)=1] = 2^{-n}.$$

And therefore

$$\left|\Pr_k[\mathcal{A}^{F'(k,\cdot)}(1^n)=1]-\Pr_g[\mathcal{A}^{g(\cdot)}(1^n)=1]\right|=1-2^{-n},$$
which is clearly non-negligible.