Fortuna is a cryptographically secure pseudo-random number generator (PRNG) devised by Bruce Schneier and Niels Ferguson while writing the book Practical Cryptography. It is named for Fortuna, the Roman goddess of chance.

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

• The generator itself, which once seeded will produce an indefinite quantity of pseudo-random data.
• The entropy accumulator, which collects genuinely random data from various sources and uses it to reseed the generator when enough new randomness has arrived.
• The seed file, which stores enough state to enable the computer to start generating random numbers as soon as it has booted.

The generator is based on any good block cipher. 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, repeated blocks would be generated. Therefore, the key is changed periodically: no more than 1MB 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 PRNG outputs.

The entropy accumulator is designed to be resistant against “injection” attacks, without needing sophisticated and inevitably unreliable estimators of entropy.

There are 32 “pools” of entropy; each entropy source distributes its alleged entropy evenly over the pools; and on the n^th reseeding of the generator, pool k is used only if 2^k divides n. Thus, the k^th pool is used only 1/2^k of the times. Higher-numbered pools, in other words,

1. contribute to reseedings less frequently;
2. collect a larger amount of entropy between reseedings.

Reseeding is performed by hashing the specified entropy pools into the block cipher’s key.

Unless an attacker is able to control all the sources of alleged entropy flowing into the system, there will be some k for which the k^th 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.

Fortuna uses 32 pools, and restricts reseeding to happen at most 10 times per second. Running out of pools would then take about 13 years, which Ferguson and Schneier deem long enough for practical purposes. More paranoid implementors, or ones requiring the generation of random data at a colossal rate and correspondingly frequent reseeding, could use a larger number of pools.

Notes on Clipperz’s implementation

Coming soon …