Fortuna (PRNG)

Fortuna is a cryptographically secure pseudorandom number generator (PRNG) devised by Bruce Schneier and Niels Ferguson and published in 2003. It is named after Fortuna, the Roman goddess of chance.

Fortuna is a family of secure PRNGs; its design leaves some choices open to implementors. It is composed of the following pieces:

The generator is based on any good block cipher. Practical Cryptography suggests AES, Serpent or Twofish. The basic idea is to run the cipher in counter mode, encrypting successive values of an incrementing counter. On its own, this would produce statistically identifiable deviations from randomness; for instance, generating 2⁶⁴ genuinely random 128-bit blocks would produce on average about one pair of identical blocks, but there are no repeated blocks at all among the first 2¹²⁸ produced by a 128-bit cipher in counter mode. Therefore, the key is changed periodically: no more than 1 MiB of data is generated without a key change. The key is also changed after every data request (however small), so that a key compromise doesn't endanger old RNG outputs.

The entropy accumulator is designed to be resistant against "injection" attacks, without needing sophisticated (and inevitably unreliable) estimators of entropy. There are several "pools" of entropy; each entropy source distributes its alleged entropy evenly over the pools; and (here is the key idea) on the nth reseeding of the generator, pool k is used only if 2^k divides n. Thus, the kth pool is used only 1/2^k of the time. Higher-numbered pools, in other words, (1) contribute to reseedings less frequently but (2) collect a larger amount of entropy between reseedings. Reseeding is performed by hashing the specified entropy pools into the block cipher's key using two iterations of SHA-256.

Unless an attacker is able to control all the sources of alleged entropy flowing into the system (in which case no algorithm can save it from compromise), there will be some k for which the kth pool collects enough entropy between reseedings that a reseeding with that pool ensures security. And that pool will be used at an interval proportional to the amount of entropy in question. Therefore, the system will always recover from an injection attack, and the time it takes to do so is at most a constant factor greater than the theoretical time it could take if we were able to identify which sources of entropy were corrupt and which not.

...
Wikipedia