Understanding encryption: No longer just about sending secret messages

October 21, 2015 6:00 am

Encryption by simone mescolini / Shutterstock.com

tags: cybersecurity, encryption, privacy

As part of our contribution to Cybersecurity Awareness Month, we’re making today Encryption Awareness Day here at TechPolicyDaily.com. Encryption is a key aspect of cybersecurity. Indeed, it is hard to have a meaningful conversation about cybersecurity without an understanding of what encryption is and how it works. Unfortunately, encryption is a complicated concept which many people don’t understand all that well. Indeed, as explained in this post, encryption’s most important function probably isn’t that it lets us keep information secret from prying eyes – in the modern setting, encryption serves the more important role of identity verification.

What is encryption?

Before diving into how modern encryption has uses far beyond keeping secrets, let’s briefly recap the basic mechanics of how encryption works. Encryption is the art of hiding information in plain sight. The classic setup involves two people, Alice and Bob, who wish to send secret messages to one another – but whose efforts are made difficult by their nemesis, eavesdropping Eve.

In order to send messages between each other, Alice and Bob need a way to encode messages that will be difficult for Eve to decode. For instance, Alice and Bob could agree to encode messages by shifting each letters one place to the left in the alphabet (e.g., “A” becomes “B,” “B” becomes “C,” etc.). Assuming that Alice and Bob have some way to agree on how far to shift each letter when encoding a message, they can be reasonably sure Eve won’t be able to decode their messages. We can give names to three parts of this process: the “plaintext” is the message that Alice wants to send to Bob; the “cyphertext” is the encoded message that is actually sent (and which Eve is able to see); and the “cypher” is the way that Alice and Bob have agreed on to transform the plaintext to cyphertext and back again.

The clever reader may see two problems with this method of encryption. First, it assumes that Alice and Bob are able to agree on a cypher without Eve overhearing what the cypher is. We’ll return to that in a moment. The second problem is that if Alice and Bob agree on a simple cypher (e.g., “2,” meaning “shift each letter 2 characters to the right”) it is relatively easy for Eve to reverse-engineer the cypher. This is because some letters appear more frequently than others (for instance, in English, the letter “E” appears most often, followed by “T” and then “A”). Eve need only count how often each letter appears in the cyphertext, and she will have a good chance of being able to decode it.

The solution to this attack, which is called frequency analysis, is surprisingly simple: instead of using the same cypher for each letter, Alice and Bob agree on a cypher made up of a series of random numbers (ideally one that is longer than the plaintext message). Because each letter is independently encoded, frequency analysis is no longer an effective attack.

So, if Alice wants to send Bob the message “TOO MANY SECRETS,” which has 14 letters, they would start by agreeing on a cypher with at least 14 random numbers in it. Alice would then add each number to its corresponding letter (wrapping back around to “A” if she goes past “Z”) to generate the cyphertext. The cyphertext, which would look something like “IWPDBTISLAYTJS,” can then be sent to Bob (and Eve). Bob can decode the cyphertext because he knows the cypher; Eve has only a string of random letters that she will be helpless to decode – because the letters are randomly distributed, she will be unable to decode them.

How private key encryption works

Above, we brushed past the question of how Alice and Bob agree upon a good cypher. That seems like a pretty big problem! If Alice and Bob are able to send a secret cypher between them without Eve overhearing, then surely they could also send any message they want, no?

In the early days of encryption – roughly from the time of Caesar through the Second World War – encryption relied on cyphers known as one-time pads. A one-time pad is little more than a really long random number agreed upon by Alice and Bob in advance. This approach to encryption is useful if Alice and Bob know in advance that they are going to be sending encrypted messages between each other. For instance, General Alice can give Commander Bob a book of one-time pads (called a codebook) with one for each day of a mission. Each day, Alice and Bob will be able to communicate secretly using that day’s codes.

In the years following the Second World War, mathematicians developed a new way of communicating cyphers. The key insight in this field of mathematics is that some functions are very easy to calculate in one direction, but very difficult to reverse. For instance, it is relatively easy to multiply two large prime numbers (let’s call them x and y) to get a third number z; but if I give you z it is relatively hard to figure out x and y. The key word here is “relatively”: computationally it is actually quite easy to find x and y; but it will take a long time – more precisely, it will take a lot longer than it took to multiply x and y to get z. So, if calculating z takes a computer 1 second, it may take 100 seconds to calculate x and y; if it takes 10 seconds to calculate z, finding x and y may take 10,000 seconds.

Using this insight, mathematicians realized that Alice and Bob could pretty easily generate large secret numbers that could be used as cyphers. First, each picks a large prime number, which they keep secret. Then Alice sends Bob another large prime number (which Eve may intercept). Both multiply this public number by their secret numbers, and exchange the results; they then multiply the exchanged results by their secret numbers. At the end of this process, Alice and Bob have both calculated the same number, which they can use as a cypher to encrypt messages. Importantly, Eve has all of the pieces needed to calculate this number, too – but doing so would require her to reverse part of the process that Alice and Bob used, and that would take a very long time.

This process is known as the Diffie-Hellman protocol, after the mathematicians who figured it out. It is a key part of almost all modern encryption. If implemented correctly (0), it will guarantee that Alice and Bob can send secret messages that Eve will, practically speaking, never be able to decode. Again, the key words there are “practically speaking” – Eve has all the information required to decode Alice and Bob’s messages. It will just take her a long time. And, if Alice and Bob are worried, they can make it arbitrarily harder for Eve to decode the message by using larger prime numbers. By using numbers that take only a few seconds longer to multiply together, Alice and Bob can literally add years to the time it will take Eve to reverse the process.

Encryption is about more than secrets

It is unsurprising that people generally think the primary use of encryption is to keep information secret (that is, to encrypt information). But modern encryption technologies have another, arguably more important, use: they allow us to verify the source of information being sent over the Internet. In other words, encryption can be used to verify that information sent to your bank is actually going to your bank, or that a software update to your computer’s operating system is actually being sent by Microsoft or Apple.

To understand this, we need to return to the mathematics of how encryption works. The method of encryption described above used the same cypher to encrypt and decrypt messages sent between Alice and Bob. Alice uses the cypher to encode the plaintext, and Bob reverses the process to decode the cyphertext. This is called symmetric, or private key, encryption: it’s symmetric because the same process is used to decode the encrypted message, only in reverse; and it’s a private key because the cypher (the key) needs to be kept secret in order for it to be effective.

Using some slightly more sophisticated mathematics (which actually date to the 18^th century mathematician Euler) allows for asymmetric, public key, encryption. In public key encryption, we have two separate keys, one for encrypting messages and one for decrypting messages. This means that Alice can encrypt a message that only Bob can read – indeed, once the message is encrypted, not even Alice can decode it! In fact, if Bob shares his encryption key, anyone can encode messages that only he can decrypt.

This may seem like a useless technology. Using Diffie-Hellman, Alice and Bob can already send each other secret messages. Secret is already secret – asymmetric, public key, encryption doesn’t let Alice and Bob’s secret messages be more secret.

Public key encryption, it turns out, solves a different problem. Think back to how Alice and Bob use Diffie-Hellman to establish a private key: they start by exchanging a few large prime numbers. But how does Alice know that she’s sending those numbers to Bob? And how does Bob know that he’s sending his prime numbers to Alice? Unless they have established a pre-determined way of identifying each other, they have no way of verifying that each is who they claim to be – and the need to rely on pre-determined information returns us to the age of one-time pads!

Indeed, this reveals an even more fundamental problem with any form of impersonal communications. Unless Alice and Bob are able to share their one-time pad in a direct, face-to-face exchange, they will never be able to trust that it is not a forgery. This may not have been a problem for General Alice sharing codebooks with a few dozen trusted Commander Bobs during wartime. But the story is entirely different in our modern economy: billions of Internet users almost never have personal interactions with any of the millions of websites with which they are likely to interact in the course of their online lives.

**Modern encryption really isn’t about secrets!**

Public key encryption gives us a solution to this problem, in the form of “chains of trust.” If Alice has Bob’s public key, she can encode messages that she is confident only Bob can decode. For instance, if Alice were a customer of Bank Bob, Alice could use Bob’s public key to send her username and password, at which point both Alice and Bob could be confident that they were each who they claimed to be – at which point they could use ordinary private key encryption to communicate.

But how does Alice get Bob’s public key? This is where the “chain of trust” comes in. Bob’s key is kept by an online repository of public keys known as a “certificate authority” – these are service that sell and maintain encryption keys for whomever may need them. When Alice tells her web browser to go to Bob’s web page, her web browser contacts the certificate authority to get Bob’s public key. In order to do so securely, the web browser comes pre-installed with the public keys for various certificate authorities (otherwise your web browser would face the same problem that Alice and Bob have!). And, to make sure that your web browser hasn’t been tampered with, when you install (or update) it, your operating system may use a public key to verify that the web browser is authentic.

So one public key can be used to verify another public key, which can be used to verify another public key. So long as there is a trusted public key at the start of the chain – such as one embedded in your operating system or web browser, which you purchase or install from trusted sources – Alice can trust that Bob is who he says he is.

This process has nothing to do with the ordinary understanding of “encryption.” When we started, our concern was allowing Alice and Bob to communicate secretly despite eavesdropping Eve listening in on their conversation. But public key encryption isn’t about protecting against Eve – it’s about ensuring that Alice and Bob are who they say they are. Public key encryption can also be used to protect against Eve – but that problem is really much simpler than verifying the identities of the endpoints.

It really cannot be understated how important this technology is for the Internet. Every online interaction is indirect and intermediated. Without public key encryption, there is simply no way to trust that anyone or anything online is who or what it claims to be.

Footnotes

https://weakdh.org/

M	T	W	T	F	S	S
« Jan
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28