Cryptographic Randomness

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

1. 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.
2. 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.
3. 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.
4. 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).
5. 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.

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

• 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

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.