Random Numbers

Here's a fact that surprises many people – even many computer professionals: one of the most difficult challenges for a computer system is coming up with a truly random number. In fact, without special “non-deterministic” hardware, it is provably impossible for a computer to generate a truly random number.

The reason for random numbers being a challenge for computers is that computers are, by their very nature, “deterministic”. Everything they do is completely predictable, if you know the software that's running on them. Over the years, many talented computer scientists have invested large efforts in developing so-called “pseudo-random” algorithms. These algorithms generate numbers that appear to be random (in that a human can't predict what the next pseudo-random number will be), but actually are completely predictable and even repeatable. More recently there has been a determined effort (especially with Linux) to build systems that collect some truly random information available to a computer (such as the interval between keystrokes, or the delay between sending a packet and receiving a response, or the time it takes to read data from a hard disk) – but these efforts suffer from the low rate of truly random information and unexpected (non-random) patterns that show up. Truly random numbers – meaning numbers that are provably unpredictable no matter what information you have – are still only possible with special hardware attached to your computer. Such hardware exploits some known-to-be-truly-random (e.g., non-deterministic) natural phenomenon, such as the timing of radioactive decay.

This fact has some important consequences. Probably the two biggest consequences: it means that many cryptographic systems have an inherent weakness, and it means that many computer models (in particular, a common kind of model called the “Monte Carlo model”) exhibit some very undesirable biases.

The weakened cryptographic systems are those that depend on a randomly-selected key. A good example of such a system is the very widely used SSL system – this is what you use every time you go to a secure web site. There's no need to panic about this – it's still true that the effort required to break SSL is far more costly than any benefit an attacker might get – and it's also true (so far) that breaking SSL on the basis of the random key selection is theoretical.

Bias in Monte Carlo models is a problem with more immediate consequences. Such models are the basis of pricing many financial instruments (options, many bonds, and especially complex derivatives); errors of any kind in these models could have millions or even billions of dollars in jeopardy. Another common use of these models is in weather forecasting, where errors could cost millions in unnecessary watering or other agricultural activities. Monte Carlo models are used to test designs for new buildings, bridges, airplanes, etc. – where human safety is at issue. For all of these uses, and the many more uses of Monte Carlo models, truly random numbers are, well, truly needed.

Lists of random numbers have been available on the Internet for quite a while. These are useful, but for large scale and oft-repeated modeling they are not enough. What's been missing – until now – is an Internet-based service for retrieving truly random numbers. Such a service is now available, at the Quantum Random Bit Generator Service. Anyone involved with Monte Carlo models will find this very interesting indeed – and I would expect to see some cryptographic systems make use of this service once the secure version of it becomes available…