If a PRG is constructed by iterating a PRF, is it backtracking-resistant? Say we construct a pseudo-random generator from a pseudo-random function $f$ (using some constant key $k$ and some initial value $v_0$). We do this by feeding the output block of the PRF back into the PRF to produce a new block of pseudo-random bits. That is, $B_{i+1} = f_k(B_i)$. Is that backtracking-resistant?

I thought it would be backtracking resistant because if we compromise the internal state of the PRG at time $t+1$ (meaning the adversary gets $k$ and $B_{i+1}$), then we can't find any of the previous blocks $B_i$ (for $i &lt; t+1$), since the PRF is hard to invert.
That is, $B_{i+1} = f_k(B_i)$, so we want to find $B_i$ by doing $B_i = f^{-1}_k(B_{i+1})$, but we can't invert it.

Am I missing something? Apparently it's not backtracking-resistant because the key isn't being changed, whereas other PRGs such as HMAC-DRBG are, because they update the key.
Is that backtracking-resistant?


No, as mentioned in the comments, if the PRF itself can be inverted when you know the key, the PRG is not backtracking resistant.


  I thought it would be backtracking resistant because if we compromise the internal state of the PRG at time $t+1$ (meaning the adversary gets $k$ and $B_{i+1}$), then we can't find any of the previous blocks $B_i$ (for $i &lt; t+1$), since the PRF is hard to invert.


Being hard to invert when the key is known is not a required property of a PRF and many practical PRF constructions (like block ciphers) lack it.


  Apparently it's not backtracking-resistant because the key isn't being changed, whereas other PRGs such as HMAC-DRBG are, because they update the key.


Indeed. If you overwrite the key with data generated using the old key, there is no way to backtrack unless the PRF is invertible (to state and key) by those without the (old) key.