If it hadn’t been for a shortfall in the supply of random numbers, one of history’s most infamous spy rings might never have been exposed. The shortage occurred in late 1941, two years after the start of World War II. With Hitler’s invading armies poised to overrun Moscow, Soviet leader (and erstwhile bank robber) Joseph Stalin ordered key personnel to evacuate the capital. In the chaos that followed, the NKVD — Stalin’s intelligence agency and forerunner of the KGB — made a mistake that would doom all the Soviet agents who would infiltrate the Manhattan Project, the top-secret American effort to build an atomic bomb.
The error involved the NKVD’s codebooks, known as one-time pads, which used random numbers to scramble letters, words and phrases. The random-number key to any particular one-time pad was known only to the sender and recipient. Without it, the encoded message couldn’t be deciphered. As the name suggests, one-time pads were meant to be used once and then destroyed. Used properly, they were completely unbreakable. But making them required the laborious printing of volumes of random numbers. No one knows exactly how the Soviets produced random numbers — computers were still in their infancy. According to some accounts, the NKVD employed a roomful of women who would blurt out numbers haphazardly, or they may have used something like a lottery machine, with numbered balls. This much is known: Their schemes failed to meet demand.
“The Soviet Union couldn’t make random numbers fast enough and distribute them to all the places that needed them,” says Jane Nordholt, a retired physicist from Los Alamos National Laboratory in New Mexico, where the Manhattan Project was based. Faced with the need to encode tens of thousands of messages, NKVD officials cut corners: They printed more than 35,000 pages of duplicate random number keys and distributed them to agents in the field. That fateful decision allowed American cryptographers to crack the Soviet codes by finding repeated patterns in coded messages that would otherwise have remained impregnable.
Two years later, in 1943, the U.S. Army’s Signal Intelligence Service — the precursor of the National Security Agency — started a secret program called Venona to monitor Soviet diplomatic telegrams. The program paid off in December 1946, when Meredith Gardner, a gifted young linguist and cryptographer, deciphered a message that mentioned the names of American scientists involved in the Manhattan Project. His work eventually unmasked all the spies who had revealed American bomb-building plans to the Soviets, including husband and wife team Julius and Ethel Rosenberg, who were executed for treason in 1953. Venona’s crucial role in the Cold War remained hidden from the public until 1995, when the project was finally declassified.
“They were decrypting stuff with Venona until 1980,” says Nordholt, who tells me the Venona story on a warm July afternoon in Santa Fe, New Mexico. We’re sitting on a bench in the city’s old colonial plaza with Nordholt’s husband, Richard Hughes, also a retired physicist from Los Alamos. Just one block east stands the single-story 17th-century adobe building that housed the administrative offices for the Manhattan Project; a shop selling Southwestern tchotchkes occupies the space now. During World War II, the very existence of the town of Los Alamos was a secret, and researchers working on the project used a post office box number in Santa Fe for all their correspondence.
Nordholt walked me through the Venona events because she’s thought about random numbers for quite a while, and she and Hughes are starting to get worried. Here’s a little-known fact: The internet — and much of the world’s economy — could not function without random numbers. They’re the foundation of online security, protecting everything from the national electric grid to the sale of airline tickets. Like the one-time pads used by the Soviet spies, networked computers send each other random digits to serve as keys to unlock mathematical codes. Except these codes aren’t shielding the identities of spies — they’re encrypting online passwords, credit card data and much more.
“Every time you buy something on Amazon or input your credit card information, your computer — somewhere down in its guts — generates a random number, which is necessary to distinguish your interaction and identity from any other interaction and identity,” says Raymond Newell, a physicist at Los Alamos National Laboratory and a colleague of Hughes and Nordholt.
Although there’s no danger of an imminent random-number-induced economic collapse, the technologies that generate random numbers are straining to match the unceasing growth in internet traffic. The computers for giant online retailers like Amazon might have thousands of transactions occurring simultaneously, each requiring the exchange of a unique random-number key. Six years ago, a study found that a small but significant number of keys in use on the internet were not random at all. Almost 27,000 of them — about 4 for every 1,000 public keys — offered no security from hackers. The way random numbers are generated now, says Newell, “is unsustainable. It’s not as secure as people pretend it is.”
There is, it turns out, a way to create random numbers that are invulnerable to hackers — a task that’s actually harder than it sounds.
Defining Random
What exactly is a random number, anyway? And how do computers make them? I put those questions to Hughes and Nordholt as we sip chili-infused hot chocolates in a cafe near Santa Fe’s plaza. At the counter, customers casually pay with plastic cards, heedless of the random numbers working on their behalf.
Randomness is not always easy to recognize. Consider the following string of numbers: 1.41421356237309504880168872420. It certainly looks random — there’s no discernible pattern to it. And it meets one of the criteria that Hughes tells me any string of random numbers must possess: Each number in the string is independent of the one before it (unlike, say, this string: 1248, in which each number is a multiple of its predecessor). But that long string fails a crucial standard for the level of randomness needed in cryptography. Despite appearances, the entire string is predictable: It’s the square root of 2. So it couldn’t be used as a secret key to encode data: Anyone with a mathematical background would recognize the number. For high-level security, complexity alone is not enough. Says Hughes, “You need to have unpredictability and irreproducibility.”
Most of us have a terrible grasp of the true nature of randomness. One classic illustration of how our intuition fails in the realm of the random is known as the gambler’s fallacy, the belief that past outcomes affect future ones. If the first 10 tosses of a coin come up heads, for example, it’s tempting to think that the 11th will probably be tails. But the probability of a tail landing face up remains fixed at 50 percent. People’s unwitting embrace of the gambler’s fallacy has, predictably, enriched many casinos. A particularly dramatic case occurred on Aug. 18, 1913, at the Monte Carlo casino, in Monaco, when a roulette wheel stopped on black 26 times in a row. Midway through that fluky streak, players started betting heavily on red, doubling and tripling their stakes, only to see their losses mount on several more spins of the wheel. The casino made millions of francs that day on the gamblers’ belief that randomness could not be repetitious.
“There’s a Dilbert cartoon where Dilbert comes to the basement of the company and meets the company’s random number generator, and it’s a little monster,” says Hughes. “And he’s just sitting there saying, ‘Nine, nine, nine. …’ Sometimes a random number generator will do that. That doesn’t sound random, but you can get quite long runs of repeating digits, longer than intuition would suggest.”
Even computers have trouble with randomness. Unlike us, they’re built to be predictable; they’re programmed. So how can disorder be coaxed from a deterministic machine? Computers today rely on so-called pseudorandom number generators, software programs that tap natural background jitters in a computer’s electronic circuits and convert that static into strings of numbers. They’re called pseudorandom number generators because they only mimic the caprice of true randomness. The digits they churn out may look as disordered as coins spilled from a piggy bank, but since they’re created by an algorithm — a set of rules — they’re not really unpredictable. “They’re complicated as opposed to random,” says Newell.
With pseudorandom numbers, there’s always the possibility that a skilled adversary, armed with enough output from the program, could figure out the rules it used to generate numbers. In 2010, for example, hackers took advantage of a poorly designed pseudorandom number generator to crack the security of Sony’s PlayStation 3, a flaw that would make it possible for anyone with enough expertise to run pirated games on the device. And in 2016, a former security director for a lottery vendor in Iowa was convicted of rigging the game’s pseudorandom number generator to produce results over a six-year span that netted him $14.3 million. (That criminal mastermind apparently failed to anticipate the suspicions he might arouse by winning millions in the lottery he worked on.)
Such exploits reveal a fundamental problem with existing random number generators. “There’s a chain of trust behind the scenes,” says Hughes, “and part of that chain is, do you trust the randomness that’s being used? Underlying everything is trust.” Ideally, trust would be removed from the enterprise altogether.
Nordholt herself has invented a unique random-number generator, a small box that fits onto a computer circuit board. It’s already being marketed to web-hosting companies, banks and data centers. The Entropy Engine, as it’s called, harnesses a true source of randomness — the chaotic jostling of photons, particles of light — to produce its numbers. If widely used, it would greatly improve security on the internet. Since the device is proprietary, though, Nordholt can’t say too much about how it works, so there remains some need for a modicum of trust, even with her device. When it comes to randomness, there’s only one way to completely eliminate the element of trust: a test devised half a century ago by a man who proved Albert Einstein wrong.
Get Real, Einstein
Affixed to the laboratory door in front of me is a yellow and black warning sticker: “Caution! Local Realism Violation in Progress.” There’s nothing dangerous behind the door, but the experiment housed here does pose a threat of sorts — to our understanding of how reality is put together.
“This whole experiment is like a giant coin flip,” says Krister Shalm, who has been guiding me through a series of long corridors at the National Institute of Standards and Technology in Boulder, Colorado. Since 2012, Shalm, an NIST physicist and dedicated swing dancer (he has used the Lindy Hop to illustrate the principles of quantum theory), and his colleagues here have been building an extraordinary sort of random number generator. Their device is one that would have confounded Einstein, because it confirms the existence of a phenomenon he derisively called spukhafte Fernwirkung — spooky action at a distance.
Einstein never fully accepted quantum mechanics, the theory that describes the properties of atoms, photons and all the other particles of which the universe is made. He was tormented by the central role that chance plays in the theory. The development of quantum mechanics early in the 20th century completely upended the orderly, predictable cosmos bequeathed to us by Isaac Newton. According to quantum mechanics, particles don’t possess any definite speeds, energies or positions until they are actually measured. Before a measurement, their properties can be described only in terms of probabilities; unlike the deterministic rules of Newtonian physics, quantum theory deals with how frequently things will occur.
It’s not just that we ourselves don’t know, say, a particle’s position. Quantum theory suggests something far more radical: The particle actually doesn’t have a fixed position until we try to look at it. Before that, it occupies many positions at once. In quantum theory, reality is like a roulette wheel, except the little white ball is “spread out” over every number on the wheel and “collapses,” as physicists would say, on a single number only when the wheel stops spinning and we look. Einstein refused to believe that the universe was fundamentally random. “God does not play dice,” he famously said. (Nor, he might have added, does God play roulette.)
Still more unsettling to him was the phenomenon of entanglement, whereby one particle can instantaneously influence another, as though invisible wires connected them, even if the two particles are on opposite sides of the universe. The spooky action of entanglement defied one of the central tenets of Einstein’s special theory of relativity, that nothing can travel faster than the speed of light. This convinced Einstein that quantum mechanics was lacking something, and it pointed to the need for a more comprehensive theory. He argued that entanglement could be explained by what have come to be called hidden variables — as-yet-undiscovered rules that govern particle interactions. Some future theory, he felt, would eventually describe those hidden variables and vindicate him.
Most importantly for Einstein, his proposed hidden variables only had local effects — they couldn’t violate the limitations imposed by the speed of light. And if particles did have hidden variables, it meant they must possess at least some definite properties even before they were measured. Physicists now refer to Einstein’s viewpoint as local realism — “local” because there is no faster-than-light spookiness involved, and “realism” because the particles’ properties are permanent, whether observed or not.
A Random Reality
“These recent experiments have put the final nail in the coffin of a theory that was already dead,” says Scott Glancy, one of Shalm’s collaborators on the Bell experiment. “They have confirmed in a final and definitive way what the physics community has known for decades — that is, quantum mechanics is true, and classical theories that obey this principle of local realism are false.”
What does it mean to say that local realism is false? The Bell test proves that our conventional view of reality needs revising. The properties of particles like photons are not just unknown to us before measurement, they’re unknown even to nature: The quantum roulette ball really is smeared out over every possible number. “Physicists stepped into this problem that sounds like what philosophers have been debating for thousands of years,” says Alan Migdall, a physicist at NIST’s Gaithersburg, Maryland, campus. “What’s the nature of reality? Do things have properties before you measure them?” The Bell tests show that they don’t.
Besides the philosophical import, the results are important for cryptography. “The fact that a quantity didn’t exist before you made the measurement — that would be a terrific characteristic to have in a random number generator,” says Migdall. “Because that means it was impossible for somebody to have stolen it before a certain time, because it wasn’t even there to steal!”
Over the next few years, Shalm and his colleagues plan to harness the output from their experiment as an official NIST-sanctioned random-number beacon. They hope eventually to generate 512-digit-long random number strings every minute. Those numbers could be used in a wide variety of applications that require foolproof random numbers, Shalm says, like determining whose child goes to what school or what voting machines you choose to certify. “There are lots of applications like that where this beacon would be very useful.”
Ironically, there’s no formal mathematical proof that guarantees the randomness of any given string of numbers, says Hughes, as we linger over our hot cocoa in Santa Fe. Even mathematics has its limits. In the end, it seems the chain of trust ends with our faith in one final link: quantum mechanics.
Soon, Nordholt and Hughes will be traveling to a security conference in San Francisco, where they’ll talk about their Entropy Engine. Although it hasn’t passed a Bell test, it draws randomness from the same fathomless quantum well (though in a different manner) as the NIST experiment. And it has the advantage of not occupying three rooms.
Hughes, it turns out, was mentored by John Bell at CERN. “When I was at Caltech, I had an office across the corridor from Richard Feynman. [Fellow Nobel laureate] Murray Gell-Mann was next door to him. Bell was in that league. Even though he was a theoretical physicist, he had this very practical perspective on things. It kept him very grounded. He didn’t get way off into the philosophical realm. I think that led him to ask what turned out to be very deep questions. Is there an experimental test I can do that would say if the world had hidden variables, or if it works according to quantum mechanics? He was the guy who proved Einstein wrong.”
God, for better or worse, really does play dice.
