How Scientists Search the Cosmos for Encrypted Alien Signals (And Other Ones Too)

In a recent conversation with National Security Agency whistleblower Edward Snowden, astrophysicist Neil deGrasse Tyson asked about communication with alien civilizations, and how such messages might be encoded.

In any advanced civilization, there is only a “small period in the development of their society when all of their communications will be sent via the most primitive and most unprotected means,” Snowden said. And that if we pick up signals emanating from that civilization’s homeworld, such as television shows, phone calls, or satellite communication, it will most likely be encrypted because “all of their communications [would be] encrypted by default.” Because of how encryption works, those encrypted messages would be “indistinguishable to us from cosmic microwave background radiation.”

Snowden was right about encrypted content looking like noise, but he was wrong about what scientists can tell by looking for alien metadata. Whether or not aliens use encryption, we can tell the difference between signals sent through space using transmitters and natural sources of radio signals — such as the radiation left over from when the universe first cooled down enough for photons to decouple themselves from the rest of matter, shortly after the Big Bang.

The media coverage of this conversation has mostly been abysmal nonsense (“Snowden says aliens could be trying to get in touch right now” on CNET, “Edward Snowden Has A Depressing Theory About Aliens” on Huffington Post, “Snowden Re-Emerges from Russian Isolation With Alien Encryption Theories” on Digital Trends) with some sprinkles of evidence-based coverage from Live Science, also carried by Scientific American.

Today I’m going to dive into the science of searching for extraterrestrial life in our galaxy, communicating across interstellar distances, and the role that encryption and information theory play in all of this.

Are aliens real?

“If you want to think the Earth is the only one that has intelligence, there’s no way to prove that that’s wrong,” says Seth Shostak, senior astronomer at the SETI Institute, a scientific and educational nonprofit devoted to the search for extraterrestrial life. “But that’s a really remarkable statement that suggests that there’s something extraordinarily unusual about this world. And that strikes me as maybe not such a reasonable assumption.”

We have never found any direct evidence of alien intelligence, but personally, I’m betting on the aliens. Our home galaxy, the Milky Way, is a big place, and as far as we know, all it takes for life to evolve is the right environment. Exoplanets that could support life are extremely abundant in our galaxy. “We believe that the number of planets out there that could be habitable, just in the Milky Way, is tens of billions,” says Shostak. “It might be as many as a hundred billion.”

In 1952, Stanley Miller, under the supervision of Harold Urey, conducted a groundbreaking experiment that proved that you can take a primordial soup of the basic molecules that made up Earth’s pre-life environment (water vapor, methane, ammonia, and hydrogen), add some electricity — the same stuff that comes from lightning — and you get the amino acids that are a main component of the stuff of life.

Once life exists on a planet, given enough time, it might evolve the kind of intelligence that will let it communicate with radios, like it did on Earth.

Are aliens trying to communicate with us?

You might think browsing the web with the privacy-enhancing Tor Browser is slow, but the latency of bouncing your signals around Earth a few times is nothing at all compared to interstellar communication — sending signals between the stars. If aliens send us a signal, or if we’re sending a signal out to aliens, the signal will only be moving at the speed of light, the fastest speed that nature allows.

Map of the Milky Way.

If we discover evidence of aliens living in a star system 1,000 light-years away — which is still just in our neighborhood, considering that our galaxy is over 100,000 light-years in diameter — and we send them a message, it will take a millennium before they receive it. If they decide to send a response, we’ll need to wait another millennium after that before we know if they even received it to begin with.

If aliens in that star system right now are monitoring our star for evidence of intelligence, all of the signals they are receiving from humans left Earth in the year 1015. At that time, the Vikings had recently founded small settlements in North America; the Byzantine Empire was conquering the First Bulgarian Empire; and Iraqi scientist Alhazen, regarded as humanity’s first theoretical physicist, wrote the Book of Optics while under house arrest in Egypt.

Communication with alien civilizations should be possible as long as we can receive their signals and they can receive ours, however it will be very slow. Proxima Centauri, our nearest stellar neighbor, is over 4 light-years away from us. If we’re lucky enough to find an alien civilization there that’s alive and detectable at the same time as our civilization is looking for life — and that’s an enormous, unlikely if — then it may be possible to communicate with them. Sending a message and receiving a response will take over eight years, though, so it might take many human lifetimes’ worth of communication before coming up with a common language that we both understand.

So are aliens trying to communicate with us? If they are, we haven’t noticed yet. Discovering the metadata — the fact that aliens exist and are using radios to send messages — is the first barrier that we must tackle before we even attempt to look at the content — what the aliens are saying.

SETI is monitoring for metadata, not content

Can we tell the difference between messages sent from extraterrestrial civilizations and natural sources of radiation? “Galaxies make a lot of radio noise. Quasars make a lot of radio noise. Black holes makes some radio noise, and centers of galaxies,” Shostak told me. “All these things make radio noise. But it’s different than a transmitter. A transmitter tends to be on one spot on the radio dial. It’s a narrow-band emission.”

The Allen Telescope Array

The goal of SETI’s experiments right now is to find alien transmitters, which, assuming they use technology similar to ours, can be detected regardless of encryption. If scientists find a radio signal that can’t occur naturally (as far as we know), and that’s a narrow-band emission — occupying a small slice of the radio spectrum, like when you tune your radio to 93.6 FM — then that signal could be produced by extraterrestrial intelligence, even if the message is encrypted. Any message sent through space by an alien civilization will look different than natural radiation, and those differences are what SETI is searching for.

In fact, in the process of looking for evidence of alien metadata, the content itself, whether it’s encrypted or not, gets destroyed. Shostak says that SETI’s radio experiments “average the incoming signals, if there are any, for at least seconds, and usually for minutes,” which will lose any information in the message. We would need much bigger instruments than we’re currently using if we want to record the content of signals from interstellar space.

“It’s like the ‘on the air’ sign you might see in a radio studio doesn’t tell you what the content is,” Shostak explains. “The content might be Top 40, it might be talk radio, who knows what it is? But you at least know they’re on the air.”

Indistinguishable from random

Scientists aren’t going to confuse an encrypted signal from aliens with cosmic microwave background radiation, or other natural sources of radio noise that we understand, because they’re searching for how the signal was transmitted, not what the signals says. But once we start looking at the content of signals from space, Snowden was entirely right when he said, “You can’t distinguish a properly encrypted communication […] from random noise.”

This property of cryptosystems, that encrypted messages are indistinguishable from random data, is known as ciphertext indistinguishability and is necessary to prevent things like the known-plaintext attack from working. The Nazi Enigma machines were vulnerable to known-plaintext attacks, which is how Alan Turing and his team at Bletchly Park defeated their encryption during World War II.

Ciphertext indistinguishability only refers to the scrambled message. In practice, you can often easily tell if a piece of information is encrypted because of its protocol. For example, if you see a block of random-looking characters that begins with “—–BEGIN PGP MESSAGE—–” there’s a good chance that’s an encrypted message. But without having the right key, you can’t actually confirm that the scrambled message part of it isn’t just random noise.

Most everyday encryption loudly proclaims not only that it’s encrypted, but exactly how it’s encrypted. Otherwise, legitimate recipients who hold the decryption keys won’t understand how they’re supposed to decrypt it. This isn’t true of deniable encryption, and it also wouldn’t be true if we recorded a piece of an encrypted message from aliens mid-stream, failing to record any protocol information associated with the message.

Check out this short video from Khan Academy‘s free online cryptography class explaining one-time pads, which Snowden describes to Tyson. One-time pads are the only type of encryption that have been proven to be perfect and uncrackable so long as they’re used correctly and the attacker cannot steal the key.

When we do receive an alien signal, how do we know what it says?

Picture this: You’re at the headquarters of the SETI Institute in Mountain View, California, USA, Earth, Solar System, the Milky Way. It’s the hopefully-not-too-distant future, and for the first time SETI has just recorded the content of a message from an extraterrestrial civilization. We are not alone.

Now that you have an alien message, how are you going to know what it says? Is it encrypted, or is it perhaps an alien Golden Record, full of information about their history, culture, and technology? We don’t speak their language, and we have never communicated before. All we have is a stream of data to work from, but we know that it came from extraterrestrial intelligence.

In order to learn how much information is in the message, you can do “a statistical analysis on the signal and see if it has what’s called low entropy,” Shostak tells me. “If it has patterns in it, if it has repetitions in it at all, even though you don’t understand a single word of what they’re saying, you can determine that there’s information in it.”

This measurement of entropy is similar to how you might measure the strength of a password. Entropy is random noise. Entropy is essential for encryption — for example, if you’re encrypting something with a one-time pad, you want your key to be made of pure entropy, to have zero patterns, to be entirely random and uncertain. Information resolves uncertainly. A message that contains information will be at least somewhat predictable.

If you have 10 minutes to spare, watch this intriguing video from Khan Academy‘s free online information theory class. It describes SETI’s early work in measuring the entropy of signals by recording baby humans in their “babbling phase,” when they’re just learning to speak, and comparing that to the entropy present in adult human speech — and also comparing this to baby and adult dolphin communications. Based on how much entropy is in dolphin communication — that is, how much of it is entirely random versus how much of it is predictable — it appears that dolphins, like humans, communicate in a structured language. Without knowing anything about the aliens who sent us this signal, you can tell if their message, too, is structured.

Of course, if this message is properly encrypted — if it’s an alien television show or phone call from a civilization where everything is encrypted by default — the content will be indistinguishable from random, which means it will appear to be full of entropy. Although we might be confident that the signal was produced by aliens, we wouldn’t be able to glean any information from the content of the message.

“I don’t doubt that they use encryption technology, at least for their internal communications,” Shostak told me. But if aliens were trying to communicate with us, there’s no way that they would encrypt that message. Instead, they would use “anti-encryption,” encoding their message so that it’s as easy as possible for us to understand. “They would try and make it simple,” Shostak says. “They would send you pictures.”

Encryption is only useful if the recipient can decrypt the messages. Earth scientists listening to the stars can’t make sense of a random signal from space any more than they can break the encryption of a one-time pad — they simply can’t, because it’s not possible.

Caption: Radio telescopes of the Allen Telescope Array are seen Tuesday, Oct. 9, 2007, in Hat Creek, Calif.

Update: Changed wording of Live Science / Scientific American article links to point out that they’re the same article.