PRNG with onto state update function

Question

Consider a (hypothetical) PRNG where the state update function is onto, but it is easy to find the set of preimages (so not one-way). That is, if an attacker is given the internal state of the system, say state $s_n, s_{n+1}, ..., s_{n+m}$, the "true" previous state $s_{n-1}$ obtained by the user could be any one of multiple states in an infinite set $S$. So the attacker knows $s_{n-1} \in S$, but assume $|S|$ is large or infinite, so the attacker must guess the "true" $s_{n-1}$ state. Does such a PRNG exist? And, would one be able to call such a PRNG "backtracking resistant"?

Something I am unsure of is whether such a PRNG would by default be cryptographically secure: because the state update function is onto, the "true" previous state could have been, with equal probability, any one of the states in $S$, so the previous state would almost be trivially unpredictable, implying such a PRNG would be cryptographically secure. Where does my logic go wrong here?

Answer 1

The state of a stateful algorithm is its “memory”. One round of the algorithm can be modeled as a function from $S \times I$ to $S \times O$ where $I$ is the input to one round and $O$ is the output from one round. For a PRNG, $I$ would either be a singleton (i.e. no input, just a request to generate more output), or a small amount of information such as the requested output size, or some additional entropy to inject. $O$ is the chunk of pseudorandom output.

The size of the state before and after the round is the same. So for a given input, the state update function is onto (surjective) if and only if it is one-to-one (injective).

If you have a state update function that is onto but not one-to-one, it means you're working in a different model where the size of the state decreases at each round. Your PRNG would have a limited lifetime since the size would eventually shrink to near-zero (near-zero being any size where the adversary can realistically enumerate the possible states). That would limit its usefulness.

In such a case, just because the knowledge of the current state alone doesn't allow the attacker to be certain what the previous state was doesn't particularly confer any security. Security is not plausible deniability. To make a system secure, it isn't enough to make it so that the adversary cannot prove beyond a doubt that they've broken it! You actually need to make it effectively impossible to break. It is very common that the adversary has some partial information and not just the one piece of knowledge that you're focusing on. For example, suppose that in the previous round, the PRNG was used to generate 32 bytes of data, out of which 16 bytes were used as a key and 16 bytes were used as an IV, and the adversary has been able to see the encrypted message and now wants to decrypt it. The adversary knows the IV, i.e. they know half of the output of the PRNG, and they're looking for the other half which is the key. In order for the PRNG to have backtracking resistance, you need to ensure that the knowledge of the current PRNG state plus the knowledge of the IV is not enough to reconstruct the previous PRNG state. Maybe the knowledge of the current PRNG state alone is not enough, but that is not at all helpful in the actual scenario where the adversary also knows half of the output.

There are real-world PRNG where it's trivial to inverse the state update function, i.e. to find the previous state if you know the current state (and possibly the corresponding output). But by definition, they are not backtracking resistant.