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

$\endgroup$
  • $\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 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 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 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 at 15:19
  • $\begingroup$ Where does the reseed come from? $\endgroup$ – Swashbuckler May 20 at 15:35
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.

$\endgroup$
  • 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 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 at 18:13
-5
$\begingroup$

I would suggest that this all hinges on "Let's assume I use an invertible PRF(sic) as PRNG (e.g. AES in CTR mode with a true random key). " Our current knowledge is insufficient to invert an AES-CTR RNG. Information theory suggests that inversion can't be ruled out, but we can't do it as yet. See P=NP. If we could, that would be a cropper for a lot of modern encryption. So by this paradigm, your RNG is backtracking resistant.

If your RNG is not based on a currently approved cryptographic primitive or mathematically hard problem (eg. quadratic residues), then it will be invertible and not backtracking resistant. A Mersenne Twister for example, or even now RC4.

We could summarise as: backtracking resistance = non inverability. The one second reseeding is a bit of a red herring. A modern PC can easily generate hundreds of megabytes of pseudo random numbers in one second between reseeds. The reseeding can't offer any security to those if it only takes say, 627 words to compromise the internal state.


Also see PRF v PRP. One collides, one doesn't.

$\endgroup$
  • 2
    $\begingroup$ This doesn't seem to address the question about the distinction in backtracking resistance between the two PRNGs. $\endgroup$ – Squeamish Ossifrage May 20 at 14:57

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.