# Why this isn't a secure PRF?

Given that F is a secure PRF in the example $$F'(k,x)= F(k,x)\mathbin\|F(k,F(k,x))$$ I'm not sure why this isn't a secure PRF? Under what condition $$F(k, F(k,x))$$ when concatenated to $$F(k,x)$$ the adversary will be able to distinguish between $$F'$$ and true random function?

• What happens if a second query to F can depend on the output of a first query? How would this allow you to break this? – SEJPM Oct 26 '20 at 19:39
• A related question Is $f(K, f(K, x))$ a pseudorandom function? – kelalaka Oct 26 '20 at 20:06
• What's the relationship between input/output domains of $F$ for the definition to make sense? Then what's $F'$ input/output domains? Now assume you have a black box that implements $F'$ for a fixed unknown $k$, and made a first query with some $x$ of $\ell\gg1$ bits, and got some answer $y$. How do you craft the second query to confirm beyond reasonable doubt that the blackbox implements $F'$? Note: the question is easier than for $F(k,F(k,x))$. – fgrieu Oct 26 '20 at 20:13
• @Alex: you are on good tracks, but you need to reformulate that in the framework of an attack/adversary/algorithm in a position to use an oracle/block box/API that (sometime) implements $F'$ without giving a direct access to $F$, since the question is about $F'$ being a PRF. That oracle/block box/API is assumed to sometime use, in the manner defined by $F'(k,x)= F(k,x)\mathbin\|F(k,F(k,x))$, a sub-oracle/block box/API implementing $F$; and sometime implement a true PRF. The goal of the attack/adversary/algorithm is to distinguish between the two cases. – fgrieu Oct 27 '20 at 6:48
• @Alex: Yes, you got it. Depending on the academic context, this is a correct answer; or it needs more formalization, like: stating what you described as an algorithm, called the distinguisher, invoking $F'$ as a sub-function, producing an output 1 if it concludes $F'$ is of the form $F(k,x)\mathbin\|F(k,F(k,x))$; computing the (or a minimum) advantage of that distinguisher w.r.t. an algorithm that outputs 1 or 0 at random, and show that it is non-vanishing when the parameter controlling the width of things increases. You could do this and make an answer out of it. – fgrieu Oct 30 '20 at 6:45