[8 May 2001]
Cryptographic operations call for randomness, not only for the generation
of keys, but also for some protocols. In each case, the true goal
is to have a value that the adversary cannot predict. If we can get
a value that no one (even the proper user) can predict, then we have met
that goal. A truly random value is one no one can predict
and would therefore meet our needs in all cases. Unfortunately, getting
true randomness can be extremely difficult.
Many sources offer randomness but in English one tends to use the word
``random'' in a variety of ways. Technically, these have radically
different meanings. For example, one might define five classes of
randomness (being only a little cynical):
There are a variety of hardware devices one can purchase (either separately
or as part of a cryptographic processor) that tap quantum randomness.
Such sources should probably still be conditioned.
Quantum randomness - to the best of our knowledge, this is true
randomness. As far as we know, quantum events are driven by some
truly random process. This could, of course, amount to some lesser
form of randomness (one of the next categories), but at the moment we believe
these events are truly random.
Secret entropy - this is entropy that is not random but that is
hopefully impossible for an enemy to capture and predict. Such entropy
might be elements of the path of a user's mouse when the user is requested
to move it around ``randomly''. It might also include audio samples
taken in a room where the enemy has no chance to plant a microphone or
to turn some existing device into a microphone. The LINUX /dev/random
driver samples various operating system device states that have been determined
(or assumed) difficult for an enemy to sample and uses those states as
Obscure complexity - this is entropy that appears random to a designer,
not because it really is quantum randomness or secret entropy but rather
because the designer doesn't understand the process that generates it.
Such might include operating system states that appear to be changing arbitrarily
only because the designer doesn't know how the operating system works.
To one who does understand the process producing these values, they might
not be obscure at all.
random() function - this represents a source of algorithmically
generated values that are declared random by a battery of statistical tests.
This is usually provided as a library call in some programming language
and is advertized as a source of random numbers. These values are
suitable for things like Monte Carlo simulations but have no cryptographic
value. A random() function can be thought of as a PRBG
of no cryptographic value, usually using a very small seed (16 or 32 bits,
in many cases).
Gee-wow complexity - this is complexity that looks random to a naive
user. The most obvious example in this category is a chaos equation
producing images of astounding complexity. Some have viewed those
images, reacted with the thought that the image is surely random, and then
proposed that the equations generating those images must be a source of
randomness. Chaos equations are examples of particularly insecure
and rapidly searched PRBGs that were not
even designed to be statistically random.
There are many examples of techniques for gathering secret entropy.
To name a few:
Intel RNG - available on the Intel 810 platform (motherboard chipset).
This RNG is a very high performance, true quantum random generator.
Disk drive air turbulence - this is available on any computer with an appropriate
hard drive, but the code that allows the user to harvest those random values
is not readily available.
D. Davis, R. Ihaka, P.R. Fenstermacher,
``Cryptographic Randomness from Air Turbulence in Disk Drives'', in Advances
in Cryptology -- CRYPTO '94.
secure physical random bit generator'', Markus Jakobsson, Elizabeth Shriver,
Bruce K. Hillyer, Ari Juels, presented at CCS5, November 1998.
Quantum leakage through a diode -
Items 3 and above in the list of ``randomness'' types are not worth citing,
except to warn people against.
Mouse tracks - when a user is asked to scribble with the mouse
for a while
Audio - sampled from a room where the enemy is known not to be able
to sneak in a microphone or other audio sampling mechanism
Stereo channels of room audio - a more secure version of the
above, in which the values used are from a pair of microphones. All
values gathered by both microphones are mixed together to fill the
entropy pool, but the rate of entropy accumulation is chosen on the
assumption that the only secret entropy is the position of sound
sources. A static source would offer near 0 entropy. A moving source would
offer a very slow source of entropy.
System parameters believed to be unavailable to an attacker -
as used by /dev/random in LINUX, for example.
Pseudo-randomness is algorithmically produced and is therefore subject
to von Neumann's famous quote (cited by Knuth in his volume 2: Semi-numerical
``Any one who considers arithmetical methods of producing random
digits is, of course, in a state of sin.''
A good PRBG (pseudo-random bit generator) does not create any randomness.
Rather, it generates a stream of bits that a computationally limited adversary
can not distinguish from truly random bits. However, the PRBG needs
to be initialized with some seed value or key and that value needs to be
truly random or at least secret from the adversary. Any adversary
can be assumed to know all PRBG algorithms and to try them with any known
initial values. If the adversary can find a way to know (or search
for) the PRNG seed, then he or she can trivially predict the future output
of the PRNG. Similarly, if a PRBG key is reused, the adversary can
be expected to discover the repetition of ``random'' values and therefore
detect non-randomness and predict future values.
A PRBG is not without value. If one can get a long enough seed
that the adversary cannot search the seed space and that seed is at least
secret entropy, one should be able to use a cryptographically strong PRBG's output as if it were
truly random. The problem here is that even that PRBG hasn't solved the original
problem, which was to find a source of secret entropy. What it can
often do is provide a string of usable bits at a rate higher than the available
source of secret entropy can supply.
Carl M. Ellison; firstname.lastname@example.org