Definition of a CSPRNG

Question

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:

1. It satisfies the next-bit test.
2. 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?

Answer 1

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.

Answer 2

Here's a couple of useful sources for definitions of CSPRNG or DRBGs (Deterministic Random Bit Generator).

Check out the NIST documents for CSPRNG:

• http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf
• http://csrc.nist.gov/publications/drafts/800-90/draft-sp800-90b.pdf
• http://csrc.nist.gov/publications/drafts/800-90/draft-sp800-90c.pdf

B and C are still in draft, but they have some interesting ideas worth considering. Specifically, they have useful ideas on rough estimations of entropy of sources and they add the concept of "Fresh Entropy". By this I mean if the state of the CSPRNG is compromised, the next request for random bits will not be compromised because fresh entropy is always being provided. It's a pretty stringent requirement and debatable about its necessity, but for hardware vendors that can provide it I bet they like to see it in there.

Also, definitely a classic and a must read is

"A model and Architecture for Pseudo-Random Generation and Applications to /dev/random"

• http://www.cs.princeton.edu/~boaz/Papers/devrand.pdf

They define the following properties:

Resilience. The generator’s output looks random to an observer with no knowledge of the internal state. This holds even if that observer has complete control over data that is used to refresh the internal state.

Forward security. Past output of the generator looks random to an observer, even if the observer learns the internal state at a later time.

Backward security/Break-in recovery. Future output of the generator looks random, even to an observer with knowledge of the current state, provided that the generator is refreshed with data of sufficient entropy.

If you can pick up chapter 10 of Niels Ferguson and Bruce Schneier, Practical Cryptography, published by Wiley in 2003, the description of Fortuna is pretty informative and still quite useful, though most people refer to Barak/Halevi.

Another paper worth checking out is this one which adds another concept of "Robustness" for a CSPRNG:

"Security Analysis of Pseudo-Random Number Generators with Input: /dev/random is not Robust ?"

• http://eprint.iacr.org/2013/338.pdf

In this work we extend the BH model to also include a new security property capturing how it should accumulate the entropy of the input data into the internal state after state compromise. This property states that a good PRNG should be able to eventually recover from compromise even if the entropy is injected into the system at a very slow pace, and expresses the real-life expected behavior of existing PRNG designs