MADS Haahr is in no doubt. 鈥淕enerating randomness is not a task that should be left to humans,鈥� he says.
You might expect him to say that. A computer scientist at Trinity College Dublin, he is the creator of a popular online random number generator, hosted at . But he has a point.
Human brains are wired to spot and generate patterns. That is useful when it鈥檚 all about seeing predators on the savannah before they see you, but it handicaps us when we need to think in random and unpredictable ways. That鈥檚 a problem, because true randomness is a useful thing to have. Random numbers are used in cryptography, computing, design and many other applications. Our inability to 鈥渄o鈥� random means that we usually have to outsource it to machines.
Advertisement
But relying on outside sources of randomness has its own problems. The first dice for divination and gaming were six-sided bones from the heels of sheep, with numbers carved into the faces. The shape made some numbers more likely to appear than others, giving a decisive advantage to those who understood its properties.
Suspicion about the reliability of randomness generators remains with modern equivalents like casino dice, roulette wheels or lottery balls. But it is online where it really matters. Generating random strings of numbers is essential not just for gambling games or shuffling songs on your iPod, but also to produce unguessable keys used to encrypt sensitive digital information. 鈥淚 don鈥檛 think people are very conscious of how important randomness is for the security of their data,鈥� says Haahr.
And it takes more than programming. You can鈥檛 just give computers rules to create random numbers; that wouldn鈥檛 be random. Instead you might use an algorithm to 鈥渟eed鈥� a random-looking output from a smaller, unpredictable input: use the date and time to determine which random digits to extract from a random number string such as pi, say, and work from there. The problem is that such 鈥減seudorandom鈥� numbers are limited by the input, and tend to repeat non-randomly after a certain time in a way that is guessable if you see enough of them.
An alternative is to hook up your computer to some source of physical, 鈥渢rue鈥� randomness. In the 1950s, the UK Post Office wanted a way to generate industrial quantities of random numbers to pick the winners of its Premium Bonds lottery. The job fell to the designers of the pioneering Colossus computer, developed to crack Nazi Germany鈥檚 wartime codes. They created ERNIE, the , which harnessed the chaotic trajectories of electrons passing through neon tubes to produce a randomly timed series of electronic pulses that seeded a random number.
鈥淧robability of Paul the Octopus correctly predicting the results of 8 World Cup games: 1 in 256鈥�
ERNIE is now in his fourth iteration and is a simpler soul, relying on thermal noise from transistors to generate randomness. Many modern computing applications use a similar source, collected using on-chip generating units such as Intel鈥檚 RdRand and Via鈥檚 Padlock. Haahr鈥檚 generator takes its seed from intrinsically noisy atmospheric processes.
Two problems remain. First, with enough computing power anyone can, in theory, reconstruct the processes of classical physics that created the random numbers. Second, and more practically, random number generators based solely on physical processes often can鈥檛 produce random bits fast enough.
Many systems, such as the Unix-based platforms used by Apple, get round the first problem by combining the output from on-chip randomness generators with the contents of an 鈥渆ntropy pool鈥�, filled with other random contributions. This could be anything from thermal noise in devices connected to the computer to the random timings of the user鈥檚 keyboard strokes. The components are then combined using a 鈥渉ash function鈥� to generate a single random number. Hash functions are the mathematical equivalent of stirring ink into water: there鈥檚 no known way to work out what the set of inputs was, given the number the function spits out.
That doesn鈥檛 mean there couldn鈥檛 be in the future 鈥� and there鈥檚 still the speed problem. The workaround is generally to use a physical random number generator only as a seed for a program that generates a more abundant flow.
There we are back with the algorithm problem. The precise nature of the methods these programs use is proprietary, but in 2013 security analysts raised concerns that the US National Security Agency knew the internal workings of one such generator, called Dual_EC_DRBG, . If you鈥檙e just playing online games, that鈥檚 not a big problem. But when making multibillion-dollar financial transactions, or encrypting sensitive documents, a suspicion that you are being watched is a bigger deal.
Gaming the system
Such difficulties lead some researchers to suggest we鈥檒l never have an uncrackable source of randomness as long as we rely on the classical world, where randomness is not intrinsic, but down to who has what information (see 鈥�Random reality鈥�). For safer encryption, we must turn to quantum physics, where things truly do seem random. Instead of a coin toss, you might ask whether a photon hitting a half-silvered mirror passed through it or was reflected. Instead of rolling a die, you might present an electron with a choice of six circuits to pass through. 鈥淎s a mathematician, I like my randomness to come with proof, and quantum random numbers give us that,鈥� says of the University of Michigan in Ann Arbor. 鈥淚t鈥檚 unique in that respect.鈥�
Cryptographic systems that exploit the vagaries of quantum theory for more secure communication do exist. But they are not the last word in security. Extracting quantum randomness always involves someone making non-random choices about equipment, measurements and such like. The less-than-perfect efficiency of photon detectors used in some methods could also provide a back door through which non-randomness can slip in.
One way out that is still under investigation might be to amplify quantum randomness so you always have more of it than anyone can hack. Ways exist in theory , and also to to remove any correlation with the device that first made them.
Such device-independent quantum random number generation is just the latest development in our search for true randomness. Chances are, this too will soon become reality 鈥� only then for someone to find a way to game it. With humans forever in the mix, it could be that we鈥檒l always be searching for randomness we can rely on.
This article appeared in print under the headline 鈥淭hink of a number鈥�
