4
$\begingroup$

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 < 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.

$\endgroup$
  • 1
    $\begingroup$ Yes. ​ Who is a PRF hard to invert for? ​ ​ ​ ​ $\endgroup$ – user991 Nov 14 '15 at 4:36
  • $\begingroup$ I might have mixed up PRF with one-way function (I don't quite understand the relationship between them). $\endgroup$ – user29077 Nov 14 '15 at 4:40
  • 1
    $\begingroup$ A PRF with large domain is hard to invert for parties/people who don't know the key. ​ ​ $\endgroup$ – user991 Nov 14 '15 at 4:41
  • $\begingroup$ A PRF may also be hard to invert for someone who knows the key, as there is no requirement for an efficient inverting algorithm. However, since a PRF is normally constructed from a PRG, I don't see the point of doing it the other way... $\endgroup$ – fkraiem Nov 14 '15 at 4:47
  • $\begingroup$ Could you give an example of a PRF that is hard to invert for someone who doesn't know the key, but easy to invert for someone who knows the key? $\endgroup$ – user29077 Nov 14 '15 at 4:58
1
$\begingroup$

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 < 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.

$\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.