In discussions over widespread NSA surveillance revealed by Edward Snowden, there’s one topic that comes up more than almost any other: Encryption. We demand that tech companies improve their encryption to protect their data (which is really our data) from prying eyes. We recoil upon discovering that the NSA has deliberately weakened encryption standards, or even more nefariously, worked with security companies to install backdoors to circumvent it entirely. And we watch the UK government argue that Alan Rusbridger and the Guardian are guilty of endangering state secrets because of the encryption his organization used for the Snowden files.
Terms are thrown around like algorithm, public key, and “military-grade” (always a favorite of those who want to project a vague sense of strength without revealing anything at all). What do they all mean? How can we as consumers make educated assessments of the tools and services we use to ensure our data is safe? And how much does encryption matter when the NSA and other federal authorities maintain such close relationships with technology companies?
To explain the current state of encryption and the various ways it can be defeated, we’ll look at its history and where it’s headed. We’ll also explore how, as technology has infiltrated every corner of our lives, the role of federal security agencies is no longer to protect us from foreign enemies, but to spy on us.
No time to read the whole article? Here's a quick music video summarizing some of the most common ways data is encrypted on the Internet.
The art of encryption has existed for as long as there has been a need for secret messages. It’s difficult to date precisely. The Greeks and Romans were said to use ciphers. One of the earliest known examples of developing a theory of encryption, however, comes from 9th century Iraqi mathematician al-Kindi who wrote about the art of letter substitution.
Letter substitution is the simplest method of disguising text. While this cryptography technique may seem quaint when compared to the complex computer-driven methods used to encrypt passwords and credit card numbers, the basic principles of enciphering, deciphering, and cracking are theoretically similar to the high-powered algorithmic encryption of today.
A rudimentary example of letter substitution would be to shift each letter in a word one space so that FACEBOOK becomes GBDFCPPL. The recipient of the secret message would know ahead of time the “algorithm,” or set of instructions used to encipher the textso that it can be reversed. To make it harder, you could shift the letters more randomly. FACEBOOK becomes TSRGOMMW. For that you’d need to supply the recipient with the full substitution alphabet (A is S, B is O, C is…). That’s a bit tougher to crack without knowing the substitution technique, but still doable for a practiced cryptographer.
How? The first thing that jumps out is the repetition of “MM.” In the English language, not every letter is likely to be appear consecutively. You very rarely see “AA” in a word, and never see “QQ.” Already you’ve eliminated or severely decreased the likely of several letters “M” could be. “OO” on the other hand is one of the most common repeated letter pairs in the English language. The rest is a bit trickier, but could be cracked using the probabilistic techniques developed by mathematician/early computing pioneer Charles Babbage.
Edgar Allan Poe was so confident in his crypto-cracking abilities that he placed a notice in the Philadelphia Alexander’s Weekly (Express) Messenger asking readers to send in cryptograms, pledging to solve all of them. He did.
A more difficult, though still crackable, form of encryption is “polyalphabetic substitution.” That’s where multiple letters can stand in for the same letter, so FACEBOOK might become TSRGOMAW. The so-called Vigenere cipher, which had gone uncracked for three centuries, is one of the most famous examples of polyalphabetic substitution encryption. It generally requires a longer message, to be solvable, but the principle is the same: In a long message, repetition will inevitably occur, allowing a cryptographer to trace repetition found in the enciphered message to repetition found in the real message. (For a deep, math-y dive into how Babbage cracked the Vigenere cipher, click here).
The biggest step forward for crypto after Vigenere’s Cipher came at the end of World War I. A German engineer named Arthur Scherbius invented a machine that combined the polyalphabetic encryption methods used by humans with an electro-mechanical system of rotors and wires that spat out codes that were immensely difficult to crack. It was called the Enigma machine and it was used by the Nazis during World War II to encipher secret communications between German military and government entities.
When it was finally cracked by a team of Allied mathematicians led by Alan Turing at England’s Bletchey Park, the intelligence gathered from this effort (referred to as “Ultra”) led UK Prime Minister Winston Churchill to declare emphatically, “It was thanks to Ultra that we won the war.” It’s an important story in the history of encryption because it underscores an important shift in the role of federal intelligence authorities. Where the brightest Western cryptographic minds and technology were once set upon protecting its citizens, today they are set upon surveilling them. Ostensibly they do so with the same intent, but in practice there’s little evidence to suggest that the massive dragnets conducted by the NSA do more good than harm.
So what exactly was the Enigma?
The Enigma was basically a keyboard connected to rotors and wires. With each letter of a message typed by a technican, a circuit is completed, leading to a different output letter. The technician types A, maybe R comes out.
How did recipients decrypt the messages?
To ensure that recipients could read the message, both sender and receiver were required to calibrate their Enigma machines in the same way. These detailed initial settings changed each day and were distributed in massive codebooks.
Why was the Enigma so hard to crack?
Letters went in and other letters came out, therefore it’s not so different than one of the polyalphabetic substitution systems Charles Babbage had worked to crack, right?
The key to Enigma’s security is that with each keystroke, one or more of the machine’s rotors would shift so that next time the technician types A, it will not be R. It might be X or G. And it won’t be R again until much much later in the message. Babbage’s ability to decrypt polyalphabetic encryptions relied on spotting repetition, however the letters spat out by Enigma contained such little semblance of a repeated pattern that its messages were nearly impossible to crack. In fact, if not for mistakes made by German operators and the discovery and seizure by the Allied forces of key codebooks and hardware, Enigma may never have been cracked and, if Churchill is to be believed, the Nazis might have won the war.
How did the Allied Army pull it off?
The battle against Enigma began in Poland in the 1930s when a team of cryptographers led by Marian Rejewski managed to reverse-engineer the device based on French intelligence and a ton of math. Although the Enigma device could be purchased commercially, the one used by Nazi Germany included significant modifications. By “cloning” the device, Rejewski made important discoveries about its use. He learned that the same six-letter “message key” was used for all messages for a day. He also correctly inferred that the keyboard was arranged in alphabetical order. There are billions of possible arrangements you can make of 26 letters, and the fact that Germany relied on such a predictable arrangement ended up being a major weakness.
Rejewski continued to make headway on reconstructing daily keys, but as Germany continued to increase the complexity of the device, his methods began to falter. Meanwhile, the political situation in Poland had also deteriorated, with Germany withdrawing from the German-Polish Non-Aggression Pact. This led Poland to share its research with Allies France and Britain where work resumed at the PC Bruno intelligence station outside Paris and at Bletchley Park. At Bletchley, Alan Turing helped construct devices known as “bombes” to decipher Enigma messages, which functioned in many ways as some of the earliest computers. Through a series of mathematical and mechanical techniques, plus the interception of codebooks and instruction manuals, the decryptors were able to capture valuable intelligence from both the German Army and Navy, including from German U-Boats.
So what’s America and the NSA got to do with it?
Even prior to joining the war, the US had worked with Britain on the cryptanalysis of Enigma messages. After joining the war, America created its own “bombes” with some unique advantages over the British ones.
But the Enigma story has significance for the US beyond the fact that Americans helped the Allies gather crucial intelligence to help end the war. These activities underlined the importance of having one coordinated intelligence agency. At that time, cryptanalysis in the US was accomplished by competing departments in the Army and Navy. And the collaboration that took place between different countries and branches of the military (which rarely took place prior to World War II) helped lead to the founding of the NSA. Indeed, it’s an inspiring story that the agency still uses to justify its importance, in PR-laced articles like
“How Mathematics Helped Win WWII.” But with the rise of the consumer Internet, and particularly ecommerce and online banking, encryption soon became something that every citizen needed. And while the transition was gradual, just as a hammer sees everything as a nail the NSA eventually set upon cracking and weakening the encryption used to protect our own secrets.
The research Alan Turing did when building those Enigma-fighting “bombes” helped lead to the first computers, which by the 1970s had spread through governments and corporations. Whereas communications and files were once sent via telegraphs, letters, and paper files, an increasing amount of data was now being kept in electronic form. Meanwhile, computers themselves were getting better at cracking polyalphabetic encryption codes. With the US government and financial institutions in possession of an increasing amount of electronic data spread across dozens of agencies and departments, it needed a system and a standard to protect it.
Introducing the Data Encryption Standard (DES)
Developed by a research team at IBM with input and modifications from the NSA, the Data Encryption Standard (DES) was the first-ever encryption algorithm to become officially standardized in the United States. It was approved in 1976.
What do we mean by “encryption algorithm”?
With the Enigma machine, a technician would input a message, known as “plaintext.” After a series of electrical charges and shifts by mechanical rotors, the secret message, known as “ciphertext,” comes out. With an encryption algorithm, the method is similar except instead of circuits and rotors the mechanism for transforming the plaintext is a series of math equations. And because the algorithm is processed by a computer, it can be incredibly complex. Algorithms like DES are referred to as “block ciphers” because the algorithms work on the text one block at a time. In the case of DES, each block is 64 bits long.
Along with the input, output, and algorithm, we also have what’s known as an “encryption key.” This is analogous to the initial settings on the Enigma machine required to properly encipher and decipher text. Along with the plaintext, the algorithm accepts the key as one of its inputs. In the case of DES, the effective key length is 56 bits.
Both sender and receiver use the same key to encrypt and decrypt the message. For that reason, it’s referred to as “symmetric encryption.” To use a physical metaphor, it’s as simple as the sender putting a letter in a padlocked box and locking it with a key, and the receiver opening the box with an exact copy of the same key.
Why was DES so controversial?
The first-ever standard for encryption was met with a great deal of controversy. Although commissioned by the National Bureau of Standards (NBS) and developed by a research team at IBM, the National Security Agency tinkered with the algorithm before it was approved, shortening the key length from 64 to 56 bits and modifying what are known as “substitution boxes” or S-Boxes, which apply transformations to the inputs and theoretically strengthen the encryption. One of the designers of DES, Alan Konheim, ominously said, “We sent the S-boxes off to Washington. They came back and were all different.”
Knowing what we know now about the NSA’s deliberate attempts to weaken encryption standards over the past few years, it’d be easy to assume the worst about the agency’s intentions. And even in the 70s, there were cryptographers who suspected foul play. Had Washington added a secret backdoor to this algorithm that was about to become the security standard for banks and other corporations across the country?
As it turns out, the NSA was still on our side. Or as former NSA mathematician Charles Seife, now a New York University journalism professor, puts it, “Twenty years ago the NSA tried to protect you from spies, not spy on you.” More from Seife:
“It took more than a decade for outside cryptographers to figure out why the NSA had tweaked those S-boxes. In the late 1980s, Eli Biham and Adi Shamir (the S in RSA) figured out a new way of attacking cryptographic systems by feeding very similar — but not identical — blocks of data into the algorithm and comparing how the outputs differ. This technique became known as differential cryptanalysis. It turns out that the NSA-chosen S-boxes are particularly resistant. By tweaking the S-boxes to defend against an attack that hadn’t yet been discovered by outsiders, the NSA proved that it had been trying to strengthen domestic cryptography rather than weaken it.”
With computing power growing exponentially (see Moore’s Law), DES eventually became susceptible to what are known as “brute force” attacks. These involve a supercomputer trying every possible key until a cipher is cracked. Because DES uses a 56-bit key, there are 2^56 or approximately 72 quadrillion possible keys. In 1998, the Electronic Frontier Foundation built a machine for $250,000 that cracked DES in less than three days. By 2002, DES had been replaced by the Advanced Encryption Standard or AES, which has keys of 128 bits, 192 bits, and 256 bits (It’s worth noting that as the bit size of the key goes up, the number of possible keys increases exponentially, not linearly).
So far no brute force attack has taken down a 128 bit key. But symmetric encryption like DES and AES is not always feasible for things like encrypting millions of customers’ passwords or bank accounts. Something more lightweight but still theoretically secure was needed. Thus the 1990s brought about “public key cryptography,” which we’ll explain in the next chapter.
Unfortunately, the 90s also brought about a shift in the NSA’s culture toward spying domestically and cracking our own encryption.
Until the 90s there was still a balance between developing encryption to protect its citizens’ interests and attacking that same encryption. That all changed, writes the former NSA mathematician Charles Seife, sometime in the 1990s. The idea that “unbreakable” encryption could exist threatens the NSA’s ability to collect data on adversaries. The US government viewed any encryption that it didn’t have a hand in developing as a munition. In 1991, the US launched a criminal investigation into Phil Zimmerman, the creator of the Pretty Good Privacy (PGP) encryption software. The investigation, which sought to determine if Zimmerman had violated the Arms Export Control Act, lasted three years and was eventually dropped with no charges filed. But the shift in attitude was easy to spot.
Seife writes, “It became clear that the spread of fast, cheap, secure encryption algorithms would make NSA’s eavesdropping mission much more difficult. So, how could the agency ensure secure communications at home while denying them to potential adversaries?”
The Clipper Chip
In 1993 under the Clinton administration, the NSA introduced what came to be known as the Clipper chip, installed in phones or other devices by a manufacturer and utilizing a “block cipher” encryption algorithm like DES to keep the data secure. The catch? Each Clipper Chip device included a secret key that could unlock all of the user’s data. All the NSA needed to access this backdoor was to have “established their authority” to access it, which could mean anything.
The backlash against the Clipper Chip was intense, spread across the entire political spectrum. Just as you see today in response to the recent crop of NSA revelations, threats to digital security are something both the ACLU and the NRA can be equally pissed about.
By 1996, roundly rejected by Congressmen and corporations alike, the Clipper Chip was no longer a relevant point of discussion. If the NSA learned anything from the public relations debacle it certainly wasn’t, “Hey, maybe we shouldn’t spy on our citizens by undermining encryption standards.” Instead it decided that if it’s going to install backdoors into encryption, it’d better to do it in secret.
“And they went and did it anyway, without telling anyone,” noted cryptographer Paul Kocher told reporters from ProPublica, the Guardian and the New York Times.
Encryption in the age of the consumer Web
As more and more consumers began to do more and more on the Web, from banking to ecommerce, things like credit card numbers and passwords had to be kept secure. One potential weakness of the symmetric encryption methods described in the previous section is that both sender and recipient must share the private key ahead of time before encryption or decryption can occur. The point at which the key must be exchanged is therefore vulnerable to prying eyes.
Today, the most common form of encryption on the Web today utilizes public key cryptography. This method employs two keys, one private and one public. The public key can be used by anybody to encrypt data or verify a signature, but only the verified owner of a private key can decrypt it. It works on the premise of one-way functions: math equations that are easy to solve but extremely difficult to reverse. In widely-used cryptosystems like
RSA, the encryption equation involves multiplying two incredibly large prime numbers, which is easy. But the decryption equation involves working backwards to find those prime factors, an equation that’s not so easy. In fact, the numbers RSA uses are so big that a brute force attack to find the prime factors is considered computationally infeasible, meaning that it would take even the most powerful supercomputers years to crack.
To use a key-and-padlock metaphor, say I send you an open padlock to which only I have the key. The padlock has my initials on it so you know it’s me. You put the information I need in a box and close it with my padlock. You don’t have the key, but that’s okay. All you need to do is shut it to “encrypt” it. Then you send it back to me and I open it with my key, thus “decrypting” it. You and I never had to meet in person to exchange keys, and even if the box is intercepted en route, it’s locked and only I have the key.
Attacks on public key cryptography
Systems like RSA rely on strong random number generation. Without that, the prime numbers used to generate a public key could be guessed, collapsing the whole system. And yet, the NSA deliberately added a backdoor to one such random number generator approved by the National Institute of Standards and Technology (NIST) in 2006. In a statement, the NIST said it “would not deliberately weaken a cryptographic standard,” though it didn’t deny that the NSA “participates” in the development of encryption standards.
This is just one attempt to undermine modern encryption. According to a document leaked by Edward Snowden, the NSA “actively engages the U.S. and foreign IT industries to covertly influence and/or overtly leverage their commercial products’ designs” as part of a program that costs over $250 million a year.
Internal NSA documents also show that the agency has found a way to defeat the encryption used by most of the world’s cell phones, allowing them to decode calls and texts. Again, here’s where stronger encryption standards may have prevented the NSA from listening in. Most phones still use what’s known as A5/1 encryption which has significant weaknesses, many of which were revealed as far back as 2006.
Where the NSA fails to bypass encryption, whether by cracking it surreptitiously or by entering a backdoor, the agency looks for other weaknesses in companies’ data infrastructure. According to documents provided by Snowden to the Washington Post, the NSA was able to break into the communication links between data centers belonging to Google and Yahoo because they were not encrypted.
This underlines the continued importance of encryption even though the NSA has found so many ways around it. “Our best defense is to make surveillance of us as expensive as possible,” writes security technologist Bruce Schneier. Meanwhile, Google, Yahoo, and Microsoft have pledged to intensify their encryption efforts to ensure, as Microsoft general counsel Brad Smith puts it, “that governments use legal processes rather than brute force to access user data.”
How do we make sure tech companies are doing enough?
There’s really only one way: Transparency.
“We would need to see details,” Bruce Schneier told Pando in an email. “Transparency is important. ‘Trust us’ no longer works.”
Schneier added, “It might seem odd to non-cryptographers, but it's no more work to use strong encryption algorithms than weak algorithms. It is more work to use strong key management, but that's what is expected. These companies need to secure our data against the world's governments -- US, China, etc -- and that requires strong encryption.”
But can we really expect transparency from these huge corporations? Eerke Boiten, Director of the Interdisciplinary Centre for Cyber Security at the University of Kent, hopes so.
“I hope for the tech companies, it's self-regulation. They can go up very quickly on the basis of their reputation, if they're open about what they use.”
Unfortunately self-regulation may be the only way. When the body in charge of encryption standards in the US has such close ties to the NSA, why would they pressure tech companies to better protect their secrets?
Earlier we mentioned Moore’s Law, the principle that computing power increases exponentially over time, thus requiring greater and greater encryption standards. While many believe we are reaching the end of Moore’s Law, some predict there will be an even more dramatic spike in computing power in the near future. And it’s all thanks to quantum computing.
What is quantum computing?
Unlike the computer sitting on your desk or in your pocket, which operates by switching bits of information on or off (or 0 or 1), quantum computers rely on qubits which exist in a quantum state, allowing them to be 0, 1, or any number of infinite superpositions in between. This allows computations to be processed in parallel, and scientists say it’s theoretically possible to build quantum computers that are a million times faster than their classical counterparts. (For more, check out our interactive explainer).
It’s still very early days for quantum computers. Scientists are still trying to figure out what sorts of tasks the machines might even be any good at. But one thing they’re pretty sure quantum computers will be very good at indeed is factoring prime numbers. And it just so happens that factoring prime numbers is the predominant method used in public key cryptography that protects the world’s digital financial data.
To give you an idea of how quantum computing could disrupt security and data encryption, a 193-digit number takes months to factor using classical computers, according to John Preskill a theoretical physicist at Cal-Tech. A 500-digit number would take a classical computer the approximate age of the universe to factor. But a quantum computer, Preskill says, could factor the 193-digit number in just 0.1 seconds. The 500-digit number would naturally take a bit longer: around 2 seconds!
Is it possible that the NSA is close to building a practicable quantum computer. Or that it already has one?
According to quantum computing expert Scott Aaronson, unless the NSA has “some gigantic crash program that was decades ahead of everyone else,” the answer is no. “I’ve talked to people at NSA and that seems very unlikely,” says Aaronson, an MIT professor of electrical engineering and computer science.
“There were a hundred years between (computing pioneer) Charles Babbage and the invention of the transistor (in 1947). And we don’t yet have the quantum computing analog of the transistor.”
So we can’t yet use quantum computers to attack encryption. What about to protect it?
While quantum computers are still probably years or decades away from practicality, using quantum mechanics to encrypt information is already happening. In October, a Swiss-based startup called ID Quantique struck a deal with Battelle, a non-profit R&D lab based in Columbus, Ohio, to build America’s first commercial quantum key distribution (QKD) network. In practice, that’s “quantum encryption.” It will use the system to transmit secure data between its offices in the Central Ohio area.
How does it work?
First, data is encrypted using an algorithm like the ones we discussed above. Then the data is encoded onto a light particle known as a photon. Because photons are smaller than atoms, they behave in very strange ways. Scientists can “entangle” two photons so their properties correlate with one another. Even if the two are on opposites ends of the universe, a change to one photon (which can occur as easily as by someone observing it) will cause a change in its correlated twin.
After entangling the light particle, the sender transmits the first photon through a fiber cable to the receiver. If anyone has measured or even observed the photon in transit, it will have altered one of the properties of photon no. 1, like its spin or its polarization, causing entangled photon no. 2, with its correlated properties, to change as well, alerting the sender and receiver that the message had been observed by a third party between point A and point B.
If this makes no sense, that’s okay. Einstein called it “spooky action at a distance.” Richard Feynman said, “If you think you understand quantum theory, you don’t understand quantum theory.”
Right now, the technology is limited but far from useless. It can protect data sent up to 150 miles, but Battelle and ID Quantique are already working to extend that out. In the meantime, people like Serguei Kouzmine, a scientist turned venture capitalist who is an investor in ID Quantique, says there are many small-scale uses for quantum encryption, like protecting sensitive information at banks or technology companies between servers and backup servers. This is kind of connection the NSA was able to dip into at Google and Yahoo without the companies’ knowledge. Quantum encryption, in theory, would have alerted the companies that someone was watching.
It’s all too easy to look at the NSA’s massive dragnets, its attacks on encryption standards, and its cushy relationships with the tech companies we increasingly rely on and to feel powerless. Or even worse, to roll our eyes in contempt at those who are shocked this is going on.
But as the history of information security shows, the US government’s campaign to spy on its citizens by dismantling or compromising encryption is a relatively new development. Without the people’s consent, the role of the NSA shifted from one of preserving cryptographic integrity to one of attacking it, for fear that the US’s real or perceived enemies might figure out how to hide their communications from the agency’s all-seeing eye.
How can we fight it? Sure, Silicon Valley tech companies have their own questionable data collection motives, but they can still be powerful allies. And as consumers, we can and should demand transparency from these companies about what they use our data for and how they are protecting it. So far the results have been mixed. As recently as 2010, Yahoo, Amazon, Twitter, Facebook, and Microsoft’s mail service did not use secure encryption by default. All but one of these companies have since embraced it, with Yahoo being the lone holdout. Last month, the company finally pledged to bring Secure Sockets Layer encryption with a 2048-bit key to Yahoo Mail by January 8, 2014.
On the lobbying front, Google, LinkedIn, AOL, Facebook, Apple, Microsoft, Twitter, and Yahoo all signed an open letter to Washington, pressuring it to rein in the surveillance state. Is a letter really that strong a gesture? As Pando’s Hamish McKenzie notes, “these minor actions will mean nothing if they’re not followed up with aggressive political pressure.” Elsewhere, Mark Ames recently wrote about eBay’s historically close ties to federal law enforcement, regularly putting user data “on a silver platter” for authorities.
While better encryption and stronger lobbying efforts will help, reining in the surveillance state will ultimately require a political solution: The government must step in to put limits on the NSA. President Obama’s surveillance review board has made over 40 recommendations for modifying the NSA’s spying tactics. These include barring the NSA from asking companies to insert “backdoors” so that the agency can circumvent encryption. Again, these are only recommendations. That we’re expected to rely on history’s all-time least-productive Congress to help accomplish some of these reforms doesn’t exactly inspire confidence.
To be clear, all this isn’t to say we should dismantle the NSA or that the American government shouldn’t use surveillance techniques when lawful and appropriate. But the laws in this country haven’t caught up to the technology at the NSA’s disposal, nor have other agencies and departments been capable of acceptable oversight of the NSA. And that combination of technology and power left to metastasize unchecked is a recipe for disaster.