How to thwart an eavesdropper — with paint
Eve is a snoop. Ever since she was born in 1985, she’s been listening to our messages. That’s because Eve is part of an extended (fairly dysfunctional) family invented by cryptographers and her sole purpose is to “eavesdrop” on information exchanged between Alice and Bob. Originally better known as “User A” and “User B”, Alice and Bob are fictional characters. They were first used to help explain techniques to secretly transfer information, but have since entered into science and engineering folklore.
As they have been used to explain so many communication scenarios, a potted history of Alice and Bob’s relationship is certainly intriguing. They are recently divorced, but sometimes play poker over the phone; Bob is a stockbroker trying to defraud insurance companies, Alice is trying to hide her financial dealings from her husband; because of some mysterious past wrong, Alice doesn’t trust Bob — but as they are wanted by both the Tax Authority and the Secret Police, presumably she doesn’t trust anyone. These scenarios have all been used to help cryptographers develop systems to protect information. As data-security expert John Gordon said in his Alice and Bob After Dinner Speech in 1984, “A coding theorist is someone who doesn’t think Alice is crazy”.
The lives of Alice and Bob (or any two parties looking to exchange information) are always complicated by the presence of Eve, the eavesdropper. In order to develop a secure communications system, we have to imagine that Eve is always there, attempting to listen in to our messages. We need to find ways to thwart this “eavesdropper”.
In our scenario, I have a message I want to send you, but I don’t know who you are as we’ve never met. One thing we could do is agree on a way of encoding my message, so that it looks like scrambled jargon to everyone else, but to us (as we know how to untangle the message) it will be readable. A Caesar cipher is a simple example, so called as Julius Caesar apparently used this technique in his military communications. With a Caesar cipher, I substitute one letter for another of a fixed position down the alphabet. For example, with a shift of three, “D” becomes “A”, “E” becomes “B” and so on until the alphabet wraps round at “A”, which becomes “X” in our new message:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
XYZABCDEFGHIJKLMNOPQRSTUVW
With this in mind, a message sent to you as “JBBW JB XQ KLLK” could be translated as “MEET ME AT NOON”. However, in order for you to understand my message, we have to have previously agreed on the cipher (the steps for encoding and decoding the message) otherwise you wouldn’t know how to unscramble the text. This means our attempt at concealment is worthless. Since we’re assuming that Eve is always listening in, all she had to do was listen to our initial discussions and use that cipher we’ve agreed on to decode any messages we send. In reality, a Caesar cipher offers no security in communication as it is so easily broken (think of this as step one in the “how to break a code” manual for dummies), but because we can’t make our initial conversation secure we’ve even saved Eve the bother of having to work out the code. If we were to expand our analogy to the internet, it’s a bit like you and I exchanging an email agreeing to refer to “George’s Bank” as “KFC” in future to try to hide our secret plans to steal gold bullion — that doesn’t offer us any secrecy if Eve is already receiving our emails.
We could try harder to secure all our communications, but that could be very expensive. We could use computer algorithms to generate very complex codes that are very tricky to solve if someone didn’t know the secret to unlocking them (known as the “key”). You can experiment using this website, which takes your text and scrambles it using an algorithm based on the key — in this case a password. Find my colourful password on this page and you can decrypt this message from me:
PVGi2ri5L8lhZXCnib3IOjtNE67kdAdrqTyaNCEzNCEEXMHUTQFVpMPGt9TpApFwITEzIX41lq79JOeQeFhAZPsj9j23pImXlssP3rb4zBUhOSGj7R6pjPZ/9XTeKXlXF13d9lH5dOnRITEyIXLqGDfKdyQhMzkhzxM3e4CceXbmyMcc0BO8hVm8lVBHFQ==
Using these algorithms might protect us from a “brute force attack” (this would be Eve literally trying every single combination of possible password). If we pick our password sensibly, she would probably never find it. Regardless, these exercises in encryption may all be in vain as there still exists a point of vulnerability: the point where our two computers (or more, if other parties are involved) agree on the key used to make and break our codes. So how did we get to today, when we send millions of packets of encrypted information over the internet every day?
There has always been a certain fascination with cryptography (the art of making and breaking codes). Edgar Allan Poe was well-known amateur enthusiast of “secret writing”, famously quoting “human ingenuity cannot concoct a cipher which human ingenuity cannot resolve”. However, before the 1970s, progress in cryptography was generally hidden away as the domain of governments and their militaries. Codemaking and codebreaking had been instrumental in winning WWII for the Allied forces, where computer-like mechanical instruments had been used for the first time to crack “unbreakable” codes like those created by the German Enigma machine. US and British activities had produced a gold mine of intelligence on both the German and Japanese forces, and so during the Cold War they continued to develop their surveillance and intelligence capabilities through organisations like the NSA (National Security Agency) and GCHQ (Government Communications Headquarters). Cryptographic tools and systems were closely guarded secrets: their export from the US, for example, was severely restricted.
In the public domain, interest in cryptography was limited to an academic pursuit. The primary use of cryptography in modern computing is to protect the exchange of sensitive information across a network. Prior to the rise of networked computing in the 1970s, there was little commercial demand for such products. However, as the number of computers and communication networks grew, and transactions became increasingly handled by computers, banks and others in financial services sought ways to protect their databases. At the same time, the US government had decided to set a standard for encrypting sensitive information, to ensure the computers it purchased for its own use were secure enough.
A team from IBM were tasked with designing an algorithm that would do the job, though the NSA “unquestionably exercised an influential role” in its development. For this reason, when the Data Encryption Standard was released in 1977, the academic community were highly skeptical. Scientists accused the NSA of influencing the standard to suit their own needs and some suggested that the system was insecure. These allegations led to an investigation by the Senate. Though they concluded that the NSA had had no improper involvement, the concerns regardless led to a profound distrust in the cryptographic community of any government intervention. We can understand this skepticism better when we remember this was only a few years after Watergate and the discoveries of multiple abuses of power by government organisations like the CIA and FBI. Additionally, this cryptographic community were genuinely under pressure. Government organisations were trying to navigate the issues of academic freedom vs national security, and not often winning hearts and minds as they tried to figure it out. As an example, organisers of a cryptography conference held in 1977 received a letter from a member of staff at the NSA, highlighting that government approval may be required for the publication of conference papers since cryptographic systems were covered by ITAR (International Traffic in Arms Regulation). An account of the incident was published in Science magazine, which accused the NSA of harassing scientists and restricting research into public cryptography.
Martin Hellman was part of the faculty of Electrical Engineering at Stanford University during this first “crypto war”. He was concerned about what he saw as a government monopoly on cryptography and strongly advocated both the rights of a cryptographic researcher to openly publish their work and the individual’s right to encryption that could withstand decryption attempts. Though trained as an electrical engineer, a previous stint at IBM convinced him that cryptography could have commercial importance. Colleagues reportedly tried to dissuade him from pursuing it as a research topic, suggesting that real advancements were being made in secret and so his discoveries would not be new. Hellman, believing strongly that who invented it did not matter, just who published and released it into the commercial world, continued nonetheless with his research. Working with a doctoral student, Whitfield Diffie (Hellman is also keen to credit the influence of computer scientist Ralph Merkle), Hellman turned his attention to solving the key distribution problem — the point of vulnerability mentioned earlier. Their publication in 1976 laid the foundation for the systems we use across the internet today.
Diffie and Hellman outlined how two people could create a secret key without ever revealing it to each other. Let’s explain with paints.
Imagine that Alice and Bob want to have a common secret — in this case an agreed colour of paint. Alice and Bob both state publicly that yellow will be a central colour. Eve, always listening, also understands that “yellow” will be used. But Alice and Bob both have a private colour that they’re using. In this case, Alice is using red. She adds the colour red to the yellow paint and sends the resulting orange colour to Bob.
Bob doesn’t know that her private colour was red; his was blue, and he has sent the yellow-blue combination paint (which is now green) to Alice. Eve is listening in to the exchange so receives both Alice’s orange paint and Bob’s green paint.
But what can Eve do with this? It’s very difficult to work backwards from mixed paint to identify Alice and Bob’s secret colours, even if you know one of the combinations (in this case, yellow). What Alice and Bob can do is both add their secret colour to the paint they have received. They both end up with the same colour, brown. Why? Because they’ve both mixed the same three colours together: Alice has mixed red+green (which is yellow+blue), while Bob has mixed blue+orange (yellow+red). Without having discussed it, or revealed their own private colours, they have agreed on their secret colour.
Eve, having only received yellow, orange and green paint, doesn’t know what this colour is. She’d need to know Alice’s or Bob’s private colour to identify the secret colour.
Diffie and Hellman understood that security would come from a procedure that is easy for two people to carry out (like mixing paints together), but is hard for anyone else, knowing the output (e.g. brown paint), to reverse and find the original keys. Maths can enable this. For instance, which is easier — finding the prime factors of 233,503 or multiplying 977 and 239? These algorithms, easy one way and hard the other, protect and secure information. Let’s try it now (if you’re more rocker than mod — mathematically speaking — trying following along with a calculator. Trust me, it works):
- I come up with two prime numbers and share them with you: 3 and 17
- You then pick a secret number (4) but don’t tell me. Instead you use that secret number in a mathematical equation (3⁴ mod 17) and send me back the answer (13)
- I do the same thing, but my secret number is 11. I perform the same equation with my secret number (3¹¹ mod 17) and send you my answer (7)
- You run the same operation but using the answer I gave you in the equation this time (7⁴ mod 17). You get 4 as the answer.
- Here’s the magic: I do the same thing but swapping in your answer in the same way (13¹¹ mod 17). What do I get? You got it, 4. We can then both use the number 4 in an algorithm as the key to encrypt our messages.
(Adapted from this very helpful post on stack exchange)
In real terms, the numbers computers are working with are much, much larger to offer greater protection. But, as in our paints example, Eve would have overheard us agreeing on the prime numbers to start with (3 and 17). She would also have heard us agreeing on the equation to use, and the answers we swapped initially. It’s easy for us to calculate our key as we’re both just following a process. But without all the information, it’s very difficult for Eve to figure out either our key or the secret numbers we used to make it.
That’s how we thwart the eavesdropper.
Today, the Diffie-Hellman key exchange, as its known, is one of the most commonly used systems in networking. It’s working in the background when you’re on the internet so you’re probably not aware its happening. On its own, it can’t confirm the recipients (how could you know that you (Bob) had actually been exchanging with Alice? What if Alice’s communications were cut or intercepted, and Mallory, our malicious attacker in the cryptographic family, composed a secret key with you in her place?) and so it is usually partnered with some authorisation system. However, the description, evolution and implementation of Diffie-Hellman key exchange finally eliminated the need for keys to be established using carrier pigeons, secure phone lines, registered mail or briefcases handcuffed to trusted couriers.
But that’s not the end of the story. At the same time as describing this new technique for public-key distribution, Diffie and Hellman outlined a whole new approach to secure communications called a “public-key cryptosystem”. They proved that it was possible to create a way for messages to be encrypted using a key that is public and widely known. You could shout this key from the rooftops — much like our colour “yellow” in the earlier example — as the message could only be decrypted by a related private key. You never need to reveal this private key and it’s (nearly) impossible to figure out (of course, if you’ve got lots of time and infinite computing power lying around, you could give it a shot). As a bonus, they also outlined principles for a digital signature that could authorise that only the person you believe sent the message could have sent the message.
Though computer scientists are now advocating for stronger key exchange systems, it can’t be underestimated how revolutionary Diffie and Hellman’s paper was when it was published. It finally made encryption technologies publicly available. The Turing Prize, the Nobel Prize of Computing named after Alan Turing, credited Diffie and Hellman in 2016 for “laying the foundation for today’s online security industry and establishing cryptography as a leading discipline within computer science”. Not bad going for someone who didn’t finish their doctorate (Diffie: “I didn’t get around to it”). As New York Times Magazine described it in 1994:
“From the moment Diffie and Hellman published their findings in 1976, the National Security Agency’s crypto monopoly was effectively terminated. … Every company, every citizen now had routine access to the sorts of cryptographic technology that not many years ago ranked alongside the atom bomb as a source of power.”
To prove this point, a public-key cryptosystem had actually been conceived in 1969 at GCHQ but this was only revealed in 1997 when the materials were declassified. After that, James Ellis, Clifford Cocks and Malcolm Williamson could shout their involvement from the rooftops.
(Much like… cough, ahem, cough)
