Definition of a CSPRNG I am interested in what conditions are necessary and sufficient to define a cryptographically secure pseudo-random number generator (CSPRNG).

Wikipedia lists two defining characteristics:


It satisfies the next-bit test.
It withstands 'state compromise extensions' - part of all of the state being compromised does not allow for reconstruction of the prior stream of random numbers.


I understand that condition 1 is equivalent to saying there does not exist a polynomial-time algorithm which can distinguish the output stream from random (with success probability 1/2 + $\epsilon$), due to Yao (1982). I cannot, however, find any formal justification for the second criteria, which Wikipedia surmises as 'they hold up well under serious attack, even when part of their initial or running state becomes available to an attacker.' Does anyone have a reliable source for this?

Moreover, is this condition even sensible? If you consider something like RC4 (okay, not the best example of a CSPRNG I know), if you know the whole state at any point then it is possible to step the PRGA forward or backwards completely deterministically and independent of knowledge of the key, right? So, this means that RC4 does not satisfy Wikipedia's second condition for being a CSPRNG?
Does anyone have a reliable source for this?


Well, you are asking about the definition of a CSPRNG, and whether this second criteria is a necessary part.

Well, it comes down the to exact definition of the term 'CSPRNG'.  

If we define a CSPRNG as something that generates output which is indistinguishable from random (your first criteria), then a CSPRNG need not meet the second criteria.  This can be seen by the observation that this definition relies only on the output, while the second criteria is also defined in terms of the internal state.  It would be easy to take a CSPRNG (which meets the first criteria), and add internal state that would allow someone to reconstruct previous outputs; this modified generator would continue to meet the first criteria (we haven't changed the output), but it would prevent it from meeting the second criteria.

On the other hand, if the term 'CSPRNG' includes the second criteria, well, that's obviously a necessary part.

When I use the term 'CSPRNG', I personally mean something that meets the first criteria (and if I also need the second criteria, I use an additional term such as 'backtracking resistance' to describe it).

The wikipedia article appears to use this as its source.  I would point out that in its list of standardized CSPRNGs, it includes the X9.31 generator, whose obvious implementation does not meet their criteria (if the attacker recovers the internal key, and has a good guess about previous timestamps).


  Is this condition even sensible?


Of course it is; it is useful if you're in a scenario where there is a danger that, at some point, the internal state may actually be exposed.


  If you consider something like RC4; this means that RC4 does not satisfy Wikipedia's second condition for being a CSPRNG?


Well, RC4 is known not to meet the first criteria, and so it's not the best example.  However, ignoring that point, it is certainly true that the obvious implementation of RC4 would certainly not meet the second criteria; it is conceivable (that is, I don't know of a disproof) that there is an alternate implementation of RC4 that generates the same output, and would meet the second criteria.