Cryptographic Randomness
[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):

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

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

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

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.

``A practical
secure physical random bit generator'', Markus Jakobsson, Elizabeth Shriver,
Bruce K. Hillyer, Ari Juels, presented at CCS5, November 1998.

Quantum leakage through a diode 
There are many examples of techniques for gathering secret entropy.
To name a few:

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.
Items 3 and above in the list of ``randomness'' types are not worth citing,
except to warn people against.
Pseudorandomness
Pseudorandomness is algorithmically produced and is therefore subject
to von Neumann's famous quote (cited by Knuth in his volume 2: Seminumerical
Algorithms)
``Any one who considers arithmetical methods of producing random
digits is, of course, in a state of sin.''
A good PRBG (pseudorandom 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 nonrandomness 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; cme@acm.org