The Internet Chronicles – Part 8 of 12: Encryption for the People
Andrei Mihai
We take it for granted nowadays, but the internet is one of the most impactful inventions of modern times – possibly even of all time. But how did it all start? The story of the internet is a fascinating journey through the minds of visionary thinkers and relentless innovators, many of them coming from mathematics and computer science. In this 12-part series, we will dive into some of the stories and contributions of the trailblazers who laid the foundations for the interconnected world we live in today.
Previously, we looked at how the World Wide Web knitted the world together and how the structure of the internet was developed. But we have not touched on a core aspect of the internet: security. In this installment, we will look at the work of two “veterans” of the Heidelberg Laureate Forum: Whitfield Diffie and Martin Hellman. Their work, along with those of their peers, developed a framework for a secure internet and paved the way for the field of cryptography to bloom.
The Stanford Rebels
In the year 1974, if you wanted to communicate a very delicate secret with someone, you had a massive, physical problem. In some cases, this involved the now-classic lead-lined briefcase carried by a courier whose wrist was literally handcuffed to the handle. People working in every industry from banking to the military wanted a secure, remote way of sending messages. But the solution would come from an unlikely place.
Whitfield Diffie was a creative researcher with hair down to his shoulders and a deep-seated distrust of centralized power. Diffie had joined the Stanford Artificial Intelligence Laboratory in 1969 and left it in 1973 to pursue his independent research on cryptography. He would later credit his “anti-authoritarian views” as a motivation for developing encryption.
He teamed up with Martin Hellman, who, after brief stints at IBM and MIT, joined Stanford as an assistant professor in the department of electrical engineering. At Stanford, Hellman was warned by his colleagues that the government would likely crush him if he kept poking at cryptography. This was, after all, a time when the Cold War was in full swing. At that time, the National Security Agency (NSA) maintained a total monopoly on encryption, viewing it as a “born classified” technology. To the intelligence community, a civilian developing a powerful, unbreakable code was seen as a potential threat.
Hellman sought the advice of the university’s general counsel who told him: “If you’re prosecuted we will defend you. If you’re convicted, we will appeal. But I have to warn you… if all appeals are exhausted, we can’t go to jail for you.”
But Hellman and Diffie were not dissuaded. Together, the two (along with collaborator Ralph Merkle) began hunting for a “one-way function” that could be used for encryption.
In mathematics, most things are reversible. You can add two and two to get four, and you can subtract two from four to get back to two. But a “one-way function” (specifically, a trapdoor function) is easy to compute in one direction, and nearly impossible to compute the other way, unless you have a specific, secret “trapdoor” piece of information.
Merkle, who was an undergraduate at UC Berkeley in 1974, was a pioneer of this approach in cryptography. He devised a concept that involved generating thousands of “puzzles” that were, in essence, encrypted keys of moderate difficulty. The recipient could solve the keys to reach a shared secret. Merkle’s puzzles, as this approach came to be known, allows two parties to agree on a shared secret even if they have no secrets in common beforehand.
Merkle’s work was initially rejected by his advisor and academic editors and was only brought back after Hellman and Diffie published their seminal work.
New Directions in Cryptography
In 1976, Diffie and Hellman published their seminal paper, “New Directions in Cryptography.” The paper famously starts off by saying “We stand today on the brink of a revolution in cryptography,” before declaring, almost brazenly, that the paper “aims to solve open problems.”
The radical idea was distributing cryptographic keys openly. The two researchers proposed a mathematical method for two parties to jointly establish a shared secret key over an insecure channel without ever having met. This method, now known as the Diffie-Hellman-Merkle key exchange, utilized the difficulty of the discrete logarithm problem as its security basis. In the classic “Alice and Bob” example:
- Alice and Bob publicly agree on a large prime modulus p and a generator g
- Alice chooses a secret integer a and sends Bob A = ga (mod p)
- Bob chooses a secret integer b and sends Alice B = gb (mod p).
- Alice computes the shared secret s = Ba (mod p).
- Bob computes the shared secret s = Ab (mod p). The resulting secrets are identical.
The logic is elegant. Think of it like mixing paint. If Alice and Bob first agree on a common color. They each add their own “secret” color (a and b), and then swap the mixtures. They then each add their secret color to the other person’s mixture. Because of the commutative property, they both end up with the exact same shade of “secret” paint.
Technically, Diffie-Hellman is not a trapdoor function in the strictest sense, though it practically performs as one. A trapdoor would allow them to “undo” the function. If Alice encrypts a message with a public key, she needs a trapdoor (private key) to reverse the process and get the original message back. Rather, this is a Key Exchange. Instead of “undoing” each other’s math, Alice and Bob are both performing a second one-way function that leads them to the same mathematical result.
This approach changed everything. Suddenly, two people who had never met could establish a secure connection in milliseconds. The logic is still the reason you can type your credit card number into a browser today without a hacker buying a new phone using your card. It is, in essence, the foundation of internet security.
Yet this was not the end of the story.
While Diffie and Hellman had solved the key exchange problem, they had not yet created a fully functional public-key encryption system that could be used for general-purpose messaging or digital signatures. This was achieved in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT, who developed the RSA algorithm. This RSA algorithm is the fundamental, widely used encryption algorithm that secures the internet. But we will look at that in the next installment.
The Crypto Wars, Part I: Rebels and Friends
Thankfully, Diffie and Hellman did not go to jail for their work, although this seemed like a real option when they started it. Rather, they were both awarded the 2015 ACM A.M. Turing Award, “for fundamental contributions to modern cryptography.”
But this does not mean everyone was thrilled about their work.
In the 1970s, the pushback was immediate. The NSA attempted to implement “pre-publication review,” essentially demanding that any cryptographic research be cleared by the government before being shared. They feared that if the “Stanford Rebels” succeeded, the U.S. would lose its ability to intercept foreign signals.
Tensions between Hellman and the NSA simmered until they erupted in 1977, when a mysterious letter arrived just as the team was preparing to present their findings at an IEEE international symposium. The letter, sent by an employee of the NSA named Joseph Meyer (writing as a private citizen), warned that the public presentation of cryptographic research could be a violation of the International Traffic in Arms Regulations (ITAR). This was because, in 1976 the U.S. government had in fact classified encryption software as a “munition.” In the eyes of the law, a floppy disk containing encryption code was legally treated as a box of guns or grenades.
Much of this was happening under the watchful eye of Admiral Bobby Ray Inman, who became the Director of the NSA shortly after the 1977 letter incident. Inman opposed Diffie and Hellman sharing their work so much that the NSA warned publishers that the authors had violated US laws restricting export of military weapons. Yet despite these threats, the researchers persisted.
Admiral Inman eventually admitted that the NSA could not stop the math. He realized that if the U.S. didn’t lead in public cryptography, other countries would, leaving American businesses and citizens vulnerable. In a curious and very human turn of events, Hellman and Inman started having semi-regular discussions and actually found out they have a lot in common. Both cared about security and both were concerned about nuclear threats. By the early 1980s, the two started meeting privately and developed an unlikely friendship based on mutual respect.
Their relationship became a model for “Responsible Disclosure.” Inman and Hellman began appearing together at conferences to discuss how the government and academia could work together rather than as enemies. But the broader encryption problems persisted.
The Crypto Wars, Part II: Code Munition
In the early 1990s, the “World Wide Web” was shaping up, and with it, encryption became an even bigger headache for intelligence agencies.
If every citizen had access to military-grade encryption, the FBI and NSA could not wiretap terrorists or drug lords. If the math was too strong to break, national security would also be bound by the constraints of encryption. However, as the internet grew, the aforementioned handling of encryption software as munitions under ITAR became somewhat absurd, leading to such things as the “Netscape split.”
Netscape Communications Corporation was an American independent computer services company whose browser was dominant before Internet Explorer came along. Since the export of encryption would be classified as “arms-dealing,” the longest key size allowed for export without individual license proceedings was 40 bits, so Netscape developed two versions of its web browser. The “US edition” had the full 128-bit strength. The “International Edition” had its effective key length reduced to 40 bits.
Because every single bit added to a key doubles the number of possible combinations an attacker must try, the 128-bit version was trillions of trillions of times stronger. The 40-bit version could be broken in a matter of days using a personal computer at the time; a 128-bit version was unbreakable. But because acquiring the “US version” was problematic even in the US, most people ended up with the crackable, 40-bit version anyway.
This (coupled with other pressures) led Netscape to open-source its browser code and create the Mozilla Organization. The rebellion was led by people like Phil Zimmermann. In 1991, Zimmermann wrote a program called PGP (Pretty Good Privacy) so that ordinary people could encrypt their emails. Two years later, he became the formal target of a criminal investigation by the US Government for “munitions export without a license.”
But Zimmerman fought back with the unlikeliest of choices: He printed the source code of PGP in a physical book and exported the book.
This protected him because books are protected by the First Amendment in the US. The matter never went to court and Zimmermann was never charged, but it goes to show how far behind the laws were when it came to the internet: it was illegal to export a digital version of the code, but not a physical version of it.
Encryption for the People
Despite this, the US government did not give up on trying to control encryption. In 1993, the government proposed the “Clipper Chip” as a hardware-based solution to the encryption problem. The chip would provide secure communications for landline phones, but it included a “backdoor” through a process called “key escrow.” The government would hold the keys in two halves, allowing law enforcement to decrypt communications if authorized by a court order.
The Clipper Chip faced massive public opposition from civil liberties organizations, but the chip was only abandoned in 1996 after researcher Matt Blaze discovered a fundamental flaw in the chip’s design that allowed users to bypass the escrow mechanism while still using the encryption. Both Hellman and Diffie spoke out against the idea of having government backdoors in encryption.
However, the moment when encryption truly became “fair game” only came after a judicial decision. In a landmark case, Bernstein v. US Department of Justice, the courts ruled that software source code is speech. This was a massive win for the internet. It meant that security belongs to the people, not just the state.
This legal victory paved the way for the “Padlock” we see in our browser bars. Netscape created SSL (Secure Sockets Layer), which later became TLS (Transport Layer Security). This is the “secret handshake” you use daily, even to read this article. When you go to a website, your computer and the server perform a high-speed version of the Diffie-Hellman exchange, agreeing on a secret key for that session only.
It also paved the way for online shopping. The first object sold securely on the internet was a Sting CD, sold online in 1994 for $12.48. Slowly but surely, the world never looked back, and online shopping is now a trillion-dollar industry.
But there is a big, striking caveat to this entire story. Despite their achievements, the Stanford trio was actually not the first group to develop public-key cryptography. Deep in the British intelligence agency GCHQ, researchers like James Ellis and Clifford Cocks had actually figured this out a few years earlier. But because they worked for the British government, their work was classified. They had to be silent about their work and could not share it. Eventually, the Stanford version came into use before theirs.
It’s one of the great “what-ifs” of modern history: If the British had gone public in 1973, what would the internet have looked like?
We’ve covered how Radia Perlman (The “Mother of the Internet”) organized the web into a “Spanning Tree” to keep it from collapsing under its own weight. We’ve seen how Tim Berners-Lee gave us the links. But public-key cryptography is the vault that keeps the whole thing from being a playground for thieves.
Yet cryptography does not end with the Diffie-Hellman-Merkle key exchange. Not even close. In the next installment, we will look at one of the most important algorithms in the world: RSA.
The post The Internet Chronicles – Part 8 of 12: Encryption for the People originally appeared on the HLFF SciLogs blog.