Fortuna is a
cryptographically secure pseudorandom number generator
A cryptographically secure pseudorandom number generator (CSPRNG) or cryptographic pseudorandom number generator (CPRNG) is a pseudorandom number generator (PRNG) with properties that make it suitable for use in cryptography. It is also loosely kno ...
(PRNG) devised by
Bruce Schneier
Bruce Schneier (; born January 15, 1963) is an American cryptographer, computer security professional, privacy specialist, and writer. Schneier is a Lecturer in Public Policy at the Harvard Kennedy School and a Fellow at the Berkman Klein Cente ...
and
Niels Ferguson and published in 2003. It is named after
Fortuna
Fortuna ( la, Fortūna, equivalent to the Greek goddess Tyche) is the goddess of fortune and the personification of luck in Roman religion who, largely thanks to the Late Antique author Boethius, remained popular through the Middle Ages until at ...
, the Roman goddess of chance.
FreeBSD uses Fortuna for
/dev/random
In Unix-like operating systems, and are special files that serve as cryptographically secure pseudorandom number generators. They allow access to environmental noise collected from device drivers and other sources. typically blocked if ther ...
and /dev/urandom is symbolically linked to it since FreeBSD 11. Apple OSes have switched to Fortuna since 2020 Q1.
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
seed
A seed is an embryonic plant enclosed in a protective outer covering, along with a food reserve. The formation of the seed is a part of the process of reproduction in seed plants, the spermatophytes, including the gymnosperm and angiospe ...
ed will produce an indefinite quantity of pseudo-random data.
* The
entropy
Entropy is a scientific concept, as well as a measurable physical property, that is most commonly associated with a state of disorder, randomness, or uncertainty. The term and the concept are used in diverse fields, from classical thermodynam ...
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. ''Practical Cryptography'' suggests
AES,
Serpent
Serpent or The Serpent may refer to:
* Snake, a carnivorous reptile of the suborder Serpentes
Mythology and religion
* Sea serpent, a monstrous ocean creature
* Serpent (symbolism), the snake in religious rites and mythological contexts
* Serp ...
or
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 it was not selected for standardization. T ...
. The basic idea is to run the cipher in
counter mode
In cryptography, a block cipher mode of operation is an algorithm that uses a block cipher to provide information security such as confidentiality or authenticity.
A block cipher by itself is only suitable for the secure cryptographic transform ...
, encrypting successive values of an incrementing counter.
With a 128-bit block cipher, this would produce statistically identifiable deviations from randomness; for instance, generating 2
64 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
128 produced by a 128-bit cipher in counter mode. Therefore, the key is changed periodically: no more than 1 MiB of data (2
16 128-bit blocks) is generated without a key change. The book points out that block ciphers with a 256-bit (or greater) block size, which did not enjoy much popularity at the time, do not have this statistical problem.
The key is also changed after every data request (however small), so that a future key compromise doesn't endanger previous generator outputs. This property is sometimes described as "Fast Key Erasure" or
Forward secrecy
In cryptography, forward secrecy (FS), also known as perfect forward secrecy (PFS), is a feature of specific key agreement protocols that gives assurances that session keys will not be compromised even if long-term secrets used in the session key ...
.
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 ''n''th reseeding of the generator, pool ''k'' is used only if ''n'' is a multiple of 2
''k''. Thus, the ''k''th 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
SHA-2 (Secure Hash Algorithm 2) is a set of cryptographic hash functions designed by the United States National Security Agency (NSA) and first published in 2001. They are built using the Merkle–Damgård construction, from a one-way compressi ...
.
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 ''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.
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 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
In cryptography, SHA-1 (Secure Hash Algorithm 1) is a cryptographically broken but still widely used hash function which takes an input and produces a 160-bit (20- byte) hash value known as a message digest – typically rendered as 40 hexadec ...
rather than iterated
SHA-256
SHA-2 (Secure Hash Algorithm 2) is a set of cryptographic hash functions designed by the United States National Security Agency (NSA) and first published in 2001. They are built using the Merkle–Damgård construction, from a one-way compressi ...
.
Analysis
An analysis and a proposed improvement of Fortuna was made in 2014.
[Y. Dodis, A. Shamir, N. Stephens-Davidowitz, D. Wichs, "How to Eat Your Entropy and Have it Too —Optimal Recovery Strategies for Compromised RNGs" ''Cryptology'' ePrint Archive, Report 2014/167, 2014. https://eprint.iacr.org/2014/167.pdf]
See also
*
Blum Blum Shub
Blum Blum Shub (B.B.S.) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub that is derived from Michael O. Rabin's one-way function.
__TOC__
Blum Blum Shub takes the form
:x_ = x_n^2 \bmod M,
where ...
*
CryptGenRandom
CryptGenRandom is a deprecated cryptographically secure pseudorandom number generator function that is included in Microsoft CryptoAPI. In Win32 programs, Microsoft recommends its use anywhere random number generation is needed. A 2007 paper from ...
*
Random number generator attack
The security of cryptographic systems depends on some secret data that is known to authorized persons but unknown and unpredictable to others. To achieve this unpredictability, some randomization is typically employed. Modern cryptographic protoco ...
*
Yarrow algorithm
References
General
* Niels Ferguson and Bruce Schneier, ''Practical Cryptography'', published by Wiley in 2003. .
* John Viega, "Practical Random Number Generation in Software," acsac, pp. 129, 19th Annual Computer Security Applications Conference (ACSAC '03), 2003
External links
*
*
*
*
*
*
*
{{cryptography navbox
Pseudorandom number generators
Cryptographically secure pseudorandom number generators