Fortuna is a cryptographically secure pseudorandom number generator

Cryptographically secure pseudorandom number generator

A cryptographically secure pseudo-random number generator is a pseudo-random number generator with properties that make it suitable for use in cryptography.Many aspects of cryptography require random numbers, for example:...

 (PRNG) devised by Bruce Schneier

Bruce Schneier

Bruce Schneier is an American cryptographer, computer security specialist, and writer. He is the author of several books on general security topics, computer security and cryptography, and is the founder and chief technology officer of BT Managed Security Solutions, formerly Counterpane Internet...

 and Niels Ferguson

Niels Ferguson

Niels T. Ferguson is a Dutch cryptographer and consultant who currently works for Microsoft. He has worked with others, including Bruce Schneier, designing cryptographic algorithms, testing algorithms and protocols, and writing papers and books...

. It is named after Fortuna, the Roman goddess of chance.

Design

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.

Generator

The generator is based on any good block cipher

Block cipher

In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...

. Practical Cryptography suggests AES

Advanced Encryption Standard

Advanced Encryption Standard is a specification for the encryption of electronic data. It has been adopted by the U.S. government and is now used worldwide. It supersedes DES...

, Serpent

Serpent (cipher)

Serpent is a symmetric key block cipher which was a finalist in the Advanced Encryption Standard contest, where it came second to Rijndael. Serpent was designed by Ross Anderson, Eli Biham, and Lars Knudsen....

 or Twofish

Twofish

In cryptography, Twofish is a symmetric key block cipher with a block size of 128 bits and key sizes up to 256 bits. It was one of the five finalists of the Advanced Encryption Standard contest, but was not selected for standardisation...

. 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.

Entropy accumulator

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.

Seeding

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.

This conclusion depends on there being enough pools. 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.

Alternatives

Fortuna differs from the earlier Yarrow

Yarrow algorithm

The Yarrow algorithm is a cryptographically secure pseudorandom number generator. The name is taken from the yarrow plant, the stalks of which are dried and used as a randomising agent in I Ching divination....

 algorithm family of Schneier, Kelsey and Ferguson mostly in its handling of the entropy accumulator. Yarrow required each source of entropy to be accompanied by a mechanism for estimating the actual entropy supplied, and used only two pools; and its suggested embodiment (called Yarrow-160) used SHA-1 rather than iterated SHA-256.

See also

• Blum Blum Shub
• CryptGenRandom
  CryptGenRandom
  CryptGenRandom is a cryptographically secure pseudorandom number generator function that is included in Microsoft's Cryptographic Application Programming Interface. In Win32 programs, Microsoft recommends its use anywhere random number generation is needed...
  
  
• Cryptographically secure pseudorandom number generator
  Cryptographically secure pseudorandom number generator
  A cryptographically secure pseudo-random number generator is a pseudo-random number generator with properties that make it suitable for use in cryptography.Many aspects of cryptography require random numbers, for example:...
  
  
• Mersenne Twister
• Yarrow algorithm
  Yarrow algorithm
  The Yarrow algorithm is a cryptographically secure pseudorandom number generator. The name is taken from the yarrow plant, the stalks of which are dried and used as a randomising agent in I Ching divination....
  
  

External links

• The Javascript Crypto Library includes a Javascript implementation of Fortuna PRNG, open source, AGPL licensed.
• Patch adding an implementation of Fortuna to the Linux kernel, seems to still do some Yarrow-style entropy estimation
• Fortuna implementation in C++
• Fortuna implementation in Python, part of the Python Cryptography Toolkit