PRNG with onto state update function

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?

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.

• "where the size of the state decreases at each round", this need not be true: if $x, y$ are real values, then $\sin(x)=y$ is onto but the size of $y$ is the size of $x$. So if I understand correctly, if the state update function was $\sin$, then it would not be backtracking resistant because the set $S=\sin^{-1}(y)$ is trivial to compute, even though $|S| = \infty$? – GEG Apr 15 '20 at 15:47
• @GEG Computer state is discrete. $\sin$ is a function on real numbers. A digital computer does not compute $\sin$. It can either compute a symbolic representation or an approximation, neither of which are useful here. Even so the size of the input and output from $\sin$ are the same: both have the cardinal of $\mathbb{R}$. – Gilles 'SO- stop being evil' Apr 15 '20 at 15:51
• Got it, so if we have an onto function where the preimages are easy to compute, it would not be backtracking resistant because the set of preimages are easy to compute, and in a CSPRNG such preimages must be difficult to compute? – GEG Apr 15 '20 at 15:59
• @GEG In a CSPRNG, it must be infeasible (i.e. difficult to the point that it's practically impossible) to calculate (or more generally get meaningful information about) the state from the outputs. It doesn't necessarily have to be infeasible to calculate previous states from the current state: that's no in the definition of a CSPRNG. A good CSPRNG should be backtracking resistant, and that means that it's infeasible to calculate previous states from the current state. – Gilles 'SO- stop being evil' Apr 15 '20 at 16:38