There are a lot of quite elaborate PRNG's out there (e.g. Mersenne Twister et.al.), and they have some important properties, especially when it comes to crypto applications.
So, I was wondering how hash functions like SHA1 or MD5 would perform in such a scenario / compare to actual PRNG's. For instance, one could use the a1 = hash(seed) to generate the first batch of random bits and then a2 = hash(seed + a1) for the next series and so forth.
Mersenne Twister (as an example) is a fast random number generator, and has good properties (long period, good distribution) for most applications of random numbers (like statistics, simulations, modelling).
For cryptographic applications, we need more: We need a cryptographically secure random number generator. Such a function (implemented by an algorithm) has the property that an attacker has no means of to distinguishing the output from a pure random bit sequence, if he does not know the seed.
Such CSPRNGs (cryptographically secure random number generators) can be build from several other cryptographic primitives:
All these primitives effectively need the properties of a "normal" PRNG, thus they are usable as such.
On the other hand, the algorithms implementing such primitives are normally a lot slower than "normal" PRNG - thus don't use iterated SHA-1 when Mersenne Twister is enough for your needs.
It is possible to design a PRNG upon a hash function, but it requires some care, notably because existing hash functions are not random oracles (being collision-resistant and preimage-resistant is not all that can be dreamed of for a hash function).
NIST Special Publication SP 800-90 describes some PRNG designs which are "Approved" (in the bureaucratic sense) for cryptographic purposes. Hash_DRBG and HMAC_DRBG are based upon a hash function (within HMAC for the latter). If you use a hash function with an output of n bits, then Hash_DRBG will require, asymptotically, one hash function invocation (over a small input) per n bits of produced alea (for HMAC_DRBG, this will be two such invocations). This means that on a basic PC, using SHA-256, you will be able to produce, say, about 60 to 70 megabytes of alea per second, using a single core; I am talking about an Intel x86 Core2, with no fancy programming -- one should be able to double that bandwidth with SSE2 instructions (for HMAC_DRBG, divide performance by 2). Depending on your application, this speed can be total overkill, grossly inefficient, or anything in between.
Hash functions are (usually) very good at processing much input data, for which they yield a small output. This is exactly the opposite of what we want for a fast PRNG, which is why performance of a hash-based PRNG may be somewhat low. Some hash functions are designed on a "reversible" core which can accept input data and produce output very efficiently; these are designs which can be used as hash functions or stream ciphers. PANAMA is such a function (very fast, even faster than MD4 as a hash function; unfortunately, it turned out to be very broken too). A more recent reversible design is Skein, a candidate for SHA-3; other hash function designs are amenable to conversion to a stream cipher (e.g. all so-called Sponge functions). Caution should be exercised: hash functions and stream ciphers are not analyzed with the same techniques or goals; that a reversible function looks secure as a hash function does not mean that the corresponding stream cipher is secure, or vice versa. In particular, the SHA-3 process tells very little about use of Skein as anything else than a hash function.
For faster cryptographically secure PRNG, look up stream ciphers, in particular those selected by the eSTREAM project. A good, secure stream cipher should be able to output, say, 750 MB/s worth of alea on a basic PC (that's what I do on my 2.4 GHz Core2, there again with a single core, using SOSEMANUK).
Non-cryptographic RNG can be devilishly fast (more than 1 GB/s), albeit they do so by having detectable biases which may or may not be an issue for any given application. A sure sign of a PRNG not being cryptographically secure is any assertion about how large the "period" is. For cryptography, the period is mostly irrelevant (anything beyond 2128 is good enough); a long period says almost nothing about security.
On a recent enough x86 processor, forget all of the above: the AES-NI instructions should be used to implement an AES-based PRNG (like CTR_DRBG in NIST SP 800-90) which will provide excellent alea (fit for any purpose, including cryptography) at 2 GB/s or so.
In general, cryptographic hash functions make great building blocks for secure PRNGs. In fact, Skein is a third-round contender remaining in the SHA-3 contest. It documents its use as a CSPRNG as a side-effect of its operation.
But as others have mentioned they are slower than a non-CS PRNG function like MT that only needs to appear statistically random.
But watch out, the construction you gave "a1 = hash(seed), a2 = hash(seed + a1), ..." suffers from a problem. If you were to use, say, SHA-1 for the hash function it has an output size of 160 bits. Due to the "birthday bound" on collision resistance, you would expect to see your function enter a cycle after only about 2^80 blocks output.
A better design is to use a "CTR mode" in which you hash the concatenation of the seed and an incrementing block counter. There are still some traps, such as you need to make sure the seed and the counter are delimited. I believe NIST has a standard for this scheme, or a very similar construction using block ciphers.
The variable-length input property of hash functions allows the counter to run forever, so it you get an effectively unlimited output period.
But wait, that's not all! As a bonus, you also get O(1) access to any position in the stream!
hash(seed || counter) and want to increment the counter unlimited (to have an unlimited output period), the counter must grow in length eventually. Of course, the block size of SHA-2 is large enough so this is not really a problem in practice - this is more a theoretical remark.
$\endgroup$
Commented
Aug 3, 2011 at 9:44
Along with the PRNGs, this scheme is repeatable (deterministic) and uniform.
This also has the (mostly desirable) property of having a very large period. This method only falls into a cycle after a hash collision.
However, this is NOT cryptographically secure if the seed could be easily guessed. (e.g. if it were based solely on the clock time or a static hardware identifier.)
This seems like a pretty feasible route for a PRNG, if you are willing to sacrifice a ton of performance for the huge cycle length.
