Wired 11.08: Totally Random

[an error occurred while processing this directive][an error occurred while processing this directive][an error occurred while processing this directive]

Issue 11.08 - August 2003

Totally Random

How two math geeks with a lava lamp and a webcam are about to unleash chaos on the Internet.

By Tom McNichol

Here's a random thought: "Everything we do to achieve privacy and security in the computer age depends on random numbers."

So says Simon Cooper, an encryption expert and author of Building Internet Firewalls. Random number sequences have been around for 4,000 years, but never have they been in such demand. That's because they're the building blocks of cryptography. Every time you establish an SSL connection to, say, E*Trade, there's a string of digits working hard behind the scenes. As many as 368 bits of random data go into creating the connection - 128 bits to make encryption keys, the rest for authentication codes and the prevention of replay attacks - that's necessary whenever you send your credit card information over an ecommerce site's "secure server" or exchange medical records with your insurance company online. Even the secrecy of the messages whizzing between military commanders in the Middle East depends on random numbers.

A sequence is considered random if no patterns can be recognized in it - the longer the string, the stronger the encryption. Producing these combinations is a painstaking process. Just ask Landon Noll. The 42-year-old mathematician and cryptographer for computer security firm SystemExperts has been tinkering with random number generators, or RNGs, for nearly a decade - an exercise in bringing order to chaos. "There's a lot of beauty in chaos," Noll says. "The Grand Canyon wouldn't be so popular if it was just a uniform trench. The trick is controlling and managing chaos and turning it into something useful."

In 1996, Noll and two colleagues at Silicon Graphics came up with Lavarand, a patented system that used Lava Lites to help generate random numbers. (Patent 5,732,138: "Method for seeding a pseudo-random number generator with a cryptographic hash of a digitization of a chaotic system.") The Web site attracted millions of visitors. Some came for the shagadelic views of lava lamps in full gurgle; others for a peek at the physics and math being used to generate random seeds.

Now Noll is working with Cooper on an improved RNG called LavaRnd (which debuted in May at www.lavarnd.org). The new process replaces the lava lamps with a more Zen-like source of entropy: a webcam with its lens cap on. The chaotic thermal "noise" emitted by the webcam is digitized and put through a hash algorithm that churns the number set, stripping unwanted sections of predictability. The result is a cryptographically strong sequence of numbers, ready for use in the real world. And because the new service is open source, patent-free, and license-free, anyone will be able to cheaply build and operate a LavaRnd server and receive the precious commodity free of charge - a random act of kindness.

Noll has always been fascinated with numbers. He's made several prime- and perfect-number discoveries, and at one time held or coheld nine prime number-related world records. He codiscovered the 25th and 26th Mersenne primes, which, if you're keeping score at home, are 2^21701-1 and 2^23209-1, respectively. With LavaRnd, Noll is letting others get in on the mathematical fun. "We're trying to give people the ability to generate random numbers themselves," he says. "The webcam is a low-cost, readily available stimulus that's not predictable. Producing good random numbers is hard. Anyone who says it's easy is usually doing it wrong."

In popular discourse, people often use the word random to describe things that aren't random at all. The Random button on a CD player, for example, falls woefully short of its name. When you press it, you never hear the same song twice or three times or even ten times in a row, which would have to be possible in a truly random set. (Some CD players more accurately label the function Shuffle.) Random access memory in a computer isn't random, and that's a good thing. RAM is organized and controlled in a way that lets data be stored and retrieved efficiently to and from specific locations. A better name might be nonsequential memory.

True randomness is a stern taskmaster. Random number strings must have no built-in trends or biases. A value generated at a given time shouldn't be correlated in any way with previous values. A hacker trying to determine the next digit in a true random-number sequence will find it computationally infeasible.

The first RNGs were dice. They date back to ancient Sumeria and Egypt, and were used as the key element in games of chance. As RNGs go, dice are pretty efficient. As long as they aren't loaded, or the environment isn't otherwise altered to favor certain outcomes, throwing dice produces a reliable stream of random numbers. The problem is low output. You can generate the numbers only as fast as you can throw - making, say, a craps game an impractical means for generating large strings.

In the 20th century, the demand for random numbers exploded. Pollsters use the sequences to help select representative samples of the public; scientists to model chaotic molecular behavior; physicists to conduct simulations of nuclear detonations. Random numbers also play a crucial role in lotteries and gambling.

As recently as 100 years ago, people who needed random numbers for scientific work still tossed coins, rolled dice, dealt cards, picked numbers out of hats, or browsed census records for lists of digits. In 1927, statistician L.H.C. Tippett published a table of 41,600 random numbers obtained by taking the middle digits from area measurements of English churches. In 1955, the Rand Corporation published A Million Random Numbers With 100,000 Normal Deviates, a massive tome filled with tables of random numbers. To remove slight biases discovered in the course of testing, the million digits were further randomized by adding all pairs and retaining only the last digit. The Rand book became a standard reference, still used today in low-level applications such as picking precincts to poll.

But when large ecommerce sites gobble millions of random digits every day to encrypt information, leafing through a book of tables doesn't cut it. What's needed is a high-output generator that can plumb mere disorder and extract true randomness - a task, incidentally, beyond the reach of any computer on earth.

Computers make lousy RNGs. A digital device can be programmed to scramble the bits of a number in such a way that the result appears to be unrelated to previously generated numbers. But computers are, by design, deterministic; they merely follow set procedures. Start a new process from the same place, and a pattern emerges. Such systems are often referred to as pseudo-random number generators.

RNGs attempt to get around this shortcoming by generating seeds from a number of seemingly unpredictable sources. However, the fact that these seed sources usually aren't random means the system is still more vulnerable to attack than a random source. In the late 1990s, security experts discovered that Netscape's RNG seed was derived from just three quantities: the time of day, the process ID, and the parent process ID. An adversary could predict those values and apply a common algorithm to compute the exact seed generated. A better approach is to include a wholly unpredictable source of entropy as part of the hardware, the way Intel has done with its 800-series chips. A built-in RNG samples thermal noise given off by resistors. Radio-active elements also make great sources of entropy, since - by the laws of quantum mechanics - the rate at which radioactive sources decay is completely unpredictable.

One random-number service, called HotBits (www.fourmilab.ch/hotbits), run by Autodesk founder John Walker, employs a Geiger counter trained on a capsule of krypton-85. Visitors to the site can even order numbers online. Another service, Random.org, uses as its entropy source atmospheric noise from two secondhand radios tuned to different frequencies. Mads Haahr, a lecturer in computer science at Trinity College in Dublin, designed the system, which generates about 111 million random bits a day. Steady customers include Danish TV2, which uses the numbers for its online backgammon service; Technician, an American rock band, which employs them to generate unique covers for its CDs; and an undisclosed US military lab, for an undisclosed purpose.

Random numbers are also available on CD. In 1996, Florida State University computer scientist George Marsaglia produced a disc containing about 5 billion random bits divided into sixty 10-Mbyte files. Marsaglia generated the bits by combining three sources of electronic white noise with the output from a RNG.

Landon Noll's new LavaRnd process ranks among the best RNGs. It can produce 165,000 bits of random data per second, more than twice the output of Intel's RNG, plenty fast enough to meet most demands. Coded in C and Perl, a LavaRnd server also comes cheap. Call it randomness for the masses - and you don't even have to buy lava lamps. "It's too bad we don't use the Lava Lites anymore. They're so cool to look at," says Noll. "But replacing the bulbs got to be a real problem."

For old times' sake, Noll and Simon include shots of the lamps in glorious disorder on the site. They serve as a useful reminder of the thick, gooey randomness most of us unknowingly rely on to drive the modern world.

Contributing editor Tom McNichol (mcnichol@wiredmag.com) wrote about the race back to the moon in Wired 11.05.