2012-10-27
The difference between cryptographic and normal random number generators
This is something I was looking into today and I want to write stuff down before it falls out of my head again. I'll start with the premise: suppose that you want to generate unpredictable random numbers to avoid attempts to predict your actions. Do you need a cryptographically secure (pseudo) random number generator, or is your language's normal PRNG good enough?
All (pseudo) random number generators (and hashes) have some amount of internal state that is manipulated and permuted to generate their sequence of random numbers. If an outside observer can fully recreate this internal state (and knows the algorithm), they can work out the future values that the PRNG function will generate (because they can just run their own copy of the PRNG). In some cases they can also run the PRNG backwards, working out all previous random values. There are a number of technical requirements for cryptographically secure PRNGs, but a significant part of it is that a CSPRNG is designed to not reveal this internal state whereas a normal PRNG may well leak this state if you watch a long enough sequence of its random numbers (see eg the quick mention of this in the Wikipedia page about the Mersenne twister).
(This resistance to state discovery is not stated explicitly in the Wikipedia page on CSPRNGs, but it is implied by the next-bit test. If you can discover the internal PRNG state from past bits, you have a clear polynomial-time algorithm for 100% accurate predictions of the next bits.)
In a strict sense, a CSPRNG is more random and less predictable than a normal PRNG even in non-cryptographic situations. In a practical sense the difference between a CSPRNG and a good PRNG (one that passes strong tests for statistical randomness and so on) is likely to be very small. If you're generating random numbers for ordinary use and you have a CSPRNG handy (and it runs fast enough), you might as well use it. But if you don't, there's almost certainly no need to implement one just to get 'sufficiently unpredictable' random numbers; the output of a good normal PRNG is good enough for pretty much any use.
(While a normal PRNG can be reverse engineered and predicted, this requires someone (or some code) that is actively and explicitly attempting to do so. This is extremely unlikely in general situations, so good statistical randomness is all you need.)
It would be handy if everyone's language runtime and standard libraries contained a CSPRNG implementation, but I'm not holding my breath on that. In practice I'm happy if everyone has a high-quality PRNG like the Mersenne twister.