3
$\begingroup$

I'm currently discussing a security topic with some of my classmates.

A cryptographic PRNG typically provides backtracking resistance if an adversary that compromises the internal PRNG state cannot distinguish previously generated values from random values.

Let's assume I use an invertible PRF as PRNG (e.g. AES in CTR mode with a true random key). Then this in general does not provide backtracking resistance since, after obtaining the internal state, I can calculate the previous output using the inverted PRF.

Now let's assume that I regularly reseed my PRNG, like for example every second. Does it then provide backtracking resistance or not?

We have now two opinions:

  1. The PRNG does not provide backtracking resistance since it is possible to recover previous values within the compromised reseed interval.

  2. The PRNG provides backtracking resistance since values beyond the reseed interval can only be guessed with negligible probability

Can someone explain who is right and why?

Best regards, Matt

Improve this question
$\endgroup$
5
  • $\begingroup$ How do you use knowledge of $\operatorname{AES}_k(0)$ to compute $\operatorname{AES}_k(1)$? Inverting the PRF like knowing that 0 is the preimage under $\operatorname{AES}_k$ of $\operatorname{AES}_k(0)$—even if it is a PRP—doesn't mean recovering the key so that you can predict its value at other inputs. $\endgroup$
    – Squeamish Ossifrage
    May 20, 2019 at 15:00
  • $\begingroup$ According to NIST SP 800-90A it is assumed that an adversary can obtain the complete internal state of the PRNG. Assuming that we use AES in CTR mode this means he can obtain the current counter value and the key. This then allows him to encrypt all previous counter values and hence to recover all previous random numbers, which violates backtracking resistance. $\endgroup$
    – Matt
    May 20, 2019 at 15:16
  • $\begingroup$ So when you say ‘inverting the PRF’ you're really talking about state compromise? What I read when I see ‘inverting the PRF’ is solving $y = F_k(x)$ for $x$ given $y$ but not $k$. $\endgroup$
    – Squeamish Ossifrage
    May 20, 2019 at 15:17
  • $\begingroup$ Yes, I mean a state compromise (and sorry I hit "Enter" too early). I didn't mean that someone can invert the AES without knowing the key. $\endgroup$
    – Matt
    May 20, 2019 at 15:19
  • $\begingroup$ Where does the reseed come from? $\endgroup$
    – Swashbuckler
    May 20, 2019 at 15:35

1 Answer 1

Reset to default
2
$\begingroup$

Here's a perhaps better way to frame it that won't lead to tedious semantic disputes:

  1. Consider a PRNG with 256-bit seed $s$ that, on each request, produces $\operatorname{AES}_s(2) \mathbin\| \operatorname{AES}_s(3) \mathbin\| \cdots$ as output, and updates its seed by $s' = \operatorname{AES}_s(0) \mathbin\| \operatorname{AES}_s(1)$. This PRNG erases its key after every request.

  2. Consider a PRNG with 256-bit seed $s$ that, on each request, produces $\operatorname{AES}_s(0) \mathbin\| \operatorname{AES}_s(1) \mathbin\| \operatorname{AES}_s(2) \cdots$ as output. If you schedule a timer event to reseed it every second, then this PRNG erases its key after every second.

    Of course, in this case, you need some source from which to reseed it, so the story doesn't end here and is necessarily more complicated than the story in (1) for prompt key erasure.

The terms backtracking resistance and forward secrecy are not as helpful because they don't emphasize when the keys are erased. Both PRNGs could be construed to provide backtracking resistance in some sense, but PRNG (1) is largely a better engineering choice than PRNG (2) because it doesn't need reseeding at all (so fewer things to wire up, fewer things that can go wrong) and it provides even prompter key erasure.

The question, as stated, is essentially about PRNG (2):

We have now two opinions:

  1. The PRNG does not provide backtracking resistance since it is possible to recover previous values within the compromised reseed interval.

  2. The PRNG provides backtracking resistance since values beyond the reseed interval can only be guessed with negligible probability

Can someone explain who is right and why?

You're both right: it provides backtracking resistance every second, but not every request, so there is a window of time in which state compromise could reveal future outputs, but it's small. It's arguable, not a priori clear, which of these ‘backtracking resistance’ means, which is why I recommend emphasizing when keys are erased.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I think that your answer is more about neat design than it is about mathematical properties of said problem. Also it only mentions key rotation/change and says nothing about CTR initialization vector change. I'm not sure you answered the question $\endgroup$
    – user1687327
    May 20, 2019 at 17:21
  • $\begingroup$ @user1687327 The specific details I gave were there just to make what I understood from your description a little more concrete. If you want to start the counter at 1923748 instead of 0, that's fine; it doesn't change security; it doesn't change the question of when keys are erased, which is the real crux of the issue that is phrased in your question as whether the scheme provides backtracking resistance or not. $\endgroup$
    – Squeamish Ossifrage
    May 20, 2019 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.