The Story of Bob, Alice, and Eve: A Love Triangle Gone Bad (or, How I Came to Love PKI)

Introduction

Public Key Infrastructure, or PKI, is a term that you may have come across in the past. If you do online banking or shopping (or any internet activity that requires you to connect to an "https" site), you are making use of the benefits of a PKI. To those who don't deal with computer plumbing on a regular basis (and for many of those who do) it seems like just another mundane acronym (except that its letters don't make up some really cool term like Python or OASIS).

However, despite its apparent obscurity, Public Key Cryptography - on which PKI is based - had a very intriguing childhood worthy of fable, song, and book. It is a story of several Davids versus one Goliath, of challenging a thousand years of security dogma, and of the coming of age of personal computing.

This adventure is well documented in “Crypto: How the Code Rebels Beat the Government Saving Privacy in the Digital Age” by Steven Levy and "The Codebreakers" by Simon Singh. I highly encourage giving both a read. They are both histories rather than math books so they are easily accessible. If you thought there could be nothing more boring than the evolution of cryptography, I think you might be surprised. I've drawn much of the historical background for this introduction from these sources.

What Public Key Infrastructure (PKI) Gives Us

If we looked under the hood in a place where PKI is in operation (for example, when you use your bank card), we may find following “security services” being offered:

  • Integrity: A PKI provides the ability for someone to verify that an electronic document or other electronic object has not been modified by someone else while in transit or during storage;
  • Confidentiality: A PKI allows a person to encrypt personal documents for him/herself thereby keeping them in confidence;
  • Authentication: With a PKI, it is possible to strongly demonstrate that "you are who you say you are" and thereby authenticate yourself to someone else. Obviously, this is important for such things as on-line banking (it is always nice to know that the site you have connected to is, in fact, your bank);
  • Non-repudiation: Since it is possible authenticate someone, it is also possible to prove that certain actions were performed by them - that is, they can't "repudiate" responsibility.

How it Works: The Executve Summary

In order to explain PKI, we need to take a slight detour and explain a few very significant challenges that have existed with traditional cryptography since time immemorial.

Traditional Cryptography and the Key Distribution Problem

In traditional cryptography, we aim to make a message unreadable to everyone but certain individuals as illustrated in Figure 1. Here, we want to send the text in FILE from a Source to a Destination. Along the way, anyone who handles the FILE could read it (i.e. the SPY). To prevent this, we use an Encryption device along with a Key to digitally scramble the text at the SOURCE. Of course, we want the people at the DESTINATION to be able to read it so they use a Decryption device along with the same key to make the text readable again.

Figure 1: Traditional Cryptography

As I just noted, the key that is used at both the SOURCE and DESTINATION must be the same. Think of the locks for your house - if you lock the door, anyone else living there also needs a copy of the same key to unlock it.

We call this kind of encryption scheme symmetric key cryptography. It is “symmetric” because the key is the same on both sides (like looking in a mirror).

But how does the SOURCE and DESTINATION get the same key? Clearly, we can't send a copy of the key with the message if the DESTINATION doesn't have one. It looks like the people at the SOURCE and DESTINATION must physically meet prior to communicating so a key can be provided. Another alternative is to have a courier or runner deliver the key.

The situation above is known as the "key distribution" problem - we need to make sure that everyone that needs to read the message has the same key and that they keep it safe. There's no problem if everyone is within driving distance and there are at most 100 people. But what if there are 10,000 people and some are on different continents?

That's a problem.

It's even more of a problem when there are 10,000 people with keys out there and one of them loses his or her key. This has two important side effects.

  • First, all of the keys need to be replaced. Secure messages can't be sent until that is complete. I hope the delivery person has a frequent-flyer card....
  • Second, every text that was *ever* sent using the lost key can now be read by the person who has it. We often assume that messages are sent and then disappear forever. But people can collect and archive encrypted messages in the hopes that one day someone loses a key.
As a final note, this key distribution scheme creates a challenge for cases in which two people want to chat privately but both want to remain anonymous to each other. This is clearly hard to do if they have to meet (either directly or through a third party) in order to exchange keys.

So, traditional symmetric key encryption may be strong but it does not scale very well.

Enter the "Pulic" Key

In "public key" cryptography, we give away our encryption keys to the public.

Wait, what?!?...

You are probably wondering how that could possibly work. Cryptography is based on the paradigm that keys are to be kept secret. In fact, if you suggested the idea of having public encryption keys 40 years ago, you would have been severely brow-beaten or ridiculed. And, in fact, this is what happened to the guys who figured out how to do it. Nowadays it would be like putting up your hand and yelling “I want to study cold fusion!”

Let’s quickly go through what this "public key" encryption is all about.

Let us say that Alice wants to send a note to Bob without allowing Eve to read it. This scenario is shown in Figure 2 (which is very similar to Figure 1). In fact, the only difference between the two figures is that the keys on either end are no longer the same. They are said to be asymmetric.

But they are used in exactly the same way as the keys in Figure 1. Alice puts her text into the ENCRYPT box and feeds in the "public key". The encrypted text goes to Bob who DECRYPTs it using a "private key". Eve can't make any sense out of the text if she happens to intercept it.

Figure 2: Public Key Cryptography

To summarize, "public key" cryptography has the following property: “There is no single key but rather a key-pair”.

So what? Doesn't that just add complexity to the problem of key distribution?

This is where the magic happens. There is still a need for key distribution. But in this case, we intend to distribute the key to everyone and anyone. Better yet, we can put the key in a public place and whenever somebody wants to encrypt something for us, they can go get it.

Of course, that sounds like nonsense. But let's be a bit more precise. The trick here is to realize that each person is going to have a key-pair. One part (the public key) is available to be given away and the other part (the private key) is intended to be kept secret.

Said another way for emphasis, the "public" key is not a secret; we'd prefer it to be distributed as far and wide as possible. We'd like to give it away in restaurant bathrooms and on busses. The "private" key is a secret. Each person keeps that part to themselves.

Thus: To encrypt something for another person, you need to get a hold of their public key and use it as the ecryption key. Then, despite the fact that the public key can be seen by anyone, the only person that can decrypt your message is the person with the private key.

Can you see how key distribution now seems a little bit easier? Each person just has to leave their public key lying around in a place that everyone can get access to it. Or two people can meet and exchange public keys. Or, you can ask a friend to pass your public key to a friend. Or whatever....

It doesn't matter if you lose your public key in some dark corner of the Internet. That's kinda the point.

You may be thinking: "if it was just that easy, why didn't they do that in the first place?"

Why Didn't They Do That In The First Place?

As it turns out, what appears obvious now was certainly not the case forty years ago. When Witfield Diffie and Martin Hellman first proposed the concept of a "public" key system in 1976, it went very much against the paradigm which simply held that a key is a secret that should never be made public.  

Just to be clear: Diffie and Hellman were up against over several hundred years of entrenched cryptography. Thinking outside of this box was not considered good science.  It could get you marginalized quite quickly.

Neither Diffie nor Hellman were sure that it was even feasible to do what they were proposing which is, in some ways, an even more precarious situation before trying to publish.  

In fact, the paper Diffie and Hellman published in 1976 (entitled “New Directions In Cryptography”) proposed only a general idea. There was no implementation.

The Big Idea

So what was this idea-without-implementation that Diffie and Hellman had?   Essentially, what they proposed was a fundamental shift in the way data was encrypted.  

Traditionally, encryption was performed by repeated rounds of transposition and substitution. For example, the word "computer" might be transposed by reversing the positions of all the letters ("retupmoc").   Substitution on this word might involve replacing every letter with the letter to the right of it in the alphabet ("sfuvqnpd").

So, the key in the traditional approach is the sequence of operations that undoes the transposition and substitution.  

The strength of this method of encryption relies on how random the data looks after you're done transposing and substituting. If its not random enough, smart people can tickle out clues that eventually lead to compromise.   

Diffie and Hellman decided to take a different approach. They used mathematical functions to encrypt the data - specifically "one-way trap door" functions.  A one-way function takes some input and turns it into some other output.   It is then impossible to take that output and turn it back into the original input using the original function.  

It's like a live-mouse trap.   The mouse can go through the door in one direction but never back.

However, a one-way trap door function must be able to allow someone to convert the encrypted text back to something readable. Hence the "trap door" part of the function. If they had access to some secret data it would allow them to open a "trap door" in the function and reverse the encryption.  

It's like a live-mouse trap with a small trap door on the side that only a human can open (or a sufficiently curious/hungry raccoon).

So, the key in the Diffie Hellman approach is the trap door.

The strength of this method of encryption relies on how difficult it is to find the trap door without some special knowledge or hint.

Voila! It Works!

The key (excuse the pun) to moving the Big Idea forward was to find a mathematical function with a back door.  

This had to wait until 1977 when Ron Rivest, Adi Shamir and Len Adleman published another celebrated paper entitled “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”.   In this work, they proposed a way of building public and private keys that was based on a mathematical function that had at trap door and was also very difficult to break.

It is important to note that the proposal they put forward could be broken (in the parlance of mathematicians, it was not "provably secure"). However, the time needed to break the system using brute force (i.e. trying every combination until the correct key is discovered) is related to certain numeric parameters that are chosen when building the keys and the speed of computers (oh, and the length of the resulting key too). In the 70's and early 80's, it was estimated that the time needed for a computer to brute force a reasonably sized key was in the thousands of years.  

The algorithm developed by Rivest, Shamir, and Adleman is known as RSA (an acronym made from the letters of the names of each individual). It remains one of the cornerstone technologies in PKI even today.

We won't get into the mathematical details of the RSA algorithm itself. You can find plenty of math nerds who would be tickled pink if you asked them to explain it to you. Here, we focus on the ways that the algorithm is used because this is what you will see when you interact with devices using a PKI.

Communicating Using Public Key Cryptography:

Alice, Eve, Bob, and the Jaded Love Triangle

We would like to demonstrate how the private and public keys could be used in a typical communication.  

In this example, we introduce Alice, Bob, and Eve. These names were first coined by the RSA team in their 1977 paper to represent the "entities" trying to communicate securely. These designations were refreshing substitutes to the antiseptic alternatives normally used in academic journals. They have become the de-facto standard when referring to people trying to communicate securely.

However, whereas other descriptions focus on normal business communication, we will zero-in on talk of a more private nature...

Bob and Eve work at the same company. Bob and Eve are beautiful people (that is, they have all the physical characteristics of Ken and Barbie and, in every subject except fashion sense, they have the same level of general intelligence as the dolls).

As expected, Bob and Eve were romantically involved (to the extent that both could think of someone else other than themselves for any length of time). They were also physically involved (to the extent that staff routinely washed flat surfaces such as the photcopier or staff lounge couch before using them).

One day, Alice arrived. Alice is hot. Just as hot as Eve. This, of course, upset the natural balance of things at the company in terms of beautiful people.

Bob is a guy. Driven by hormones and a lack of forward vision, he dropped Eve at the first opportunity (she commented about Bob's poor choice of car noting that its colour limited her choice of wardrobe and Bob took this as the opening required to "split-up"). Now Bob is "seeing" Alice (when he's not looking in the mirror). 

Eve openly vowed to Alice that she will rip her world apart and get Bob back. Not because she particularly wants Bob but because Alice took him.

Let the Games Begin!

Eve found an email that Bob sent to Alice. She printed and posted it in the coffee room. It was particularly full of gushing sweet nothings and, if it was possible, Bob and Alice would have been embarrassed. Eve didn't have to work hard to get the email either. Bob had given her his password so she could cover for him at work when he had sessions at the tanning studio.  After this initial attempt at embarrassment, Bob changed his password (from 12345 to 54321 if you were wondering).

To ensure that Eve stays out of the picture in their future communications, Alice and Bob visit the techies down in computing services who give them some “public key” software. Using this sofware, each makes a key-pair. Then, the techie makes them exchange the public part of each key-pair on a USB stick (that is, Alice now has a copy of Bob's public key and vice-versa).

The techie also advises both of them to choose a stronger password while looking sternly at Bob.

Things Start Cooking!

Alice decides that she would like to meet Bob on top of the photocopier after dinner. Alice composes a note to Bob with this request (and other gossip about Eve) and clicks Send. A window pops up and asks if she would like to encrypt this message.   "Oh, right" thinks Alice. The techie was down under her desk installing some sort of "email client". She's not sure why he had to be down there for so long to install software but, hey, what does she know about this stuff?.

She uses the public key Bob gave to her and puts the note through the encryption app thingy. This is shown in Figure 3.

Now, the only person who can decrypt the message is the person with the other half of the key pair (that is, Bob).

                                                                                                                             

Figure 3: Alice’s First Love Letter

In the meantime, Eve has used some charm and a little exposure to subvert a techie down in the computing services department. She has managed to obtain a password to the mail server.

Using this password and some tutoring by the techie-who-thinks-he's-her-boyfriend, Eve begins intercepting all messages between Alice and Bob.

But she is very distressed to find out that she can't read any of it. So, she starts hammering out Plan B (in between facials and manicures).

Panic!

One morning, Alice calls Bob to say she accidentally posted his public key to her blog. Bob panics (to the extent that beautiful people can panic over techno-nerd stuff) and makes a call to his brother who understands these things.

Bob's brother calms him down and assures him that the public key is supposed to be given away so there is no need to worry. The public key is public.   It was meant to be handed out.   The worst someone could with this key is to maliciously encrypt something for Bob.

Digital “Signatures”, Marriage, and Body Piercing

Data confidentiality in cryptography is provided by encryption. The other security services – integrity and non-repudiation – are provided through the mechanism of a digital signature.

To keep her love letters confidential, Alice encrypts them for Bob with Bob’s public key.   The only way to decrypt the love letters is for Bob to use the corresponding private key from his key-pair.

Let's re-emphasize that point:   The only person who can decrypt a message encrypted with a public key is the person who has the corresponding private key.

This alone does not protect the communications between Alice and Bob. Eve, finding that she cannot read anything she intercepts, decides to interfere none-the-less. She goes through Bob’s mail account and finds the email he sent to Eve that had his public key as an attachment. She takes a copy of this ...

The next morning, Alice comes in and sends a quick note to Bob describing the resort hotel she has reserved for them on the weekend. Being mindful of Eve, she encrypts the email.

Eve (who still has access to the mail server) sees the message in Bob's basket.

Perfect.

She can’t see the body of the email (it’s encrypted for Bob only) but she can guess from the subject line what’s going on.   Eve dumps the email into the digital trash bin and drafts a new one with the same subject field:

Eve encrypts this new email for Bob using Bob’s public key and then makes a few cosmetic changes to make it look like the email came directly from Alice.

As anticipated, Bob is gravely concerned when he decrypts the message. Actually, panicked is more descriptive. Marriage? Body piercing? What next, a shared mirror?

Nearing hysteria, Bob calls Alice and says he can’t make it that weekend. Alice is upset but perfectly happy to reschedule. On the way out to the travel agent, she passes Eve and immediately senses that something is amiss. Why was she smiling? She even said “hello!”

Alice goes to Bob and presses him for details. After an hour of confusion, both realize that the weekend wasn’t about body piercing, marriage plans, and ten kids after all.

Eve has struck!

Bob and Alice Learn Something

Bob and Alice go to computing services and query the techies on how to deal with their “problem.”  

At first, the techie suggests switching to a symmetric key since there are only two of them (they won’t have a key distribution problem). However, since they already have PGP installed, the technie suggest that Alice and Bob just “sign” their emails in addition to encrypting them.

Bob and Alice were lost at "symmetric" so the techie restarts the explanation at digital signatures. She draws a picture on the board:

“The public and private keys are just keys. We call them public and private but there is really no difference between them. They are just a series of bits and bytes.   To a crypto device, there is no apparent difference between the keys. It just encrypts or decrypts using the keys that are given to it. "

"Normally, we use the public key to encrypt something for someone and they use their private key to decrypt it. The public key is public and can be obtained anywhere.   The private key is private and only one person has it."

"You with me so far?" asks the techie.

Alice nods. Bob admires his biceps in the reflection from a toaster in the kitchenette.

"But what if we encrypted something with the private key instead of using it to decrypt things.   For example, what if Alice   encrypts a message using her private key and sends it to you Bob?"

Bob replies   “That’s stupid.   Then anyone with her public key can read my message!”

“Yes,” the techie replies "you are absolutely correct. But, Bob, if YOU decrypt the message using Alice's public key and its a good message - in other words, it is not jumbled and unreadable - then what have you learned about the message?

Bob takes a few minutes and replies:   "Uhm... I've learned that everyone else can read it too?"

Alice, who has been straining hard to follow the conversation, suddently blurts out: "He knows its from me and not someone else!!!".

Bob: "Whaaaaaaaaaat?" (in the style of Bojack Horseman)

The techie explains:

"Bob, you used her public key to decrypt the message and it worked. The only person who could have encrypted the message so that it would work with Alice's public key is Alice herself. If anyone else encrypted the message using a different private key, then it would have come out jumbled and unreadable when you used Alice's public key to decrypt it."   The techie makes a picture on the board.

"Bob, you have a pile of public keys - one for each friend. By using Alice's public key to decrypt the message, you can be GUARANTEED that the only person who could have written the message was, in fact, Alice since there is only one private key that matches the public key that you have.   This is what we call a digital signature."

"That's nice," Alice says.   “But I don't still don't want Eve to read our stuff. How does this help that problem?”

"Digital signatures don't fix that problem" the techie responds. He erases the board and puts up a new picture.

"Alice, after you sign the message (i.e. encrypt it with your private key), you can encrypt it again using Bob’s public key. When Bob gets it, he will decrypt it using his private key (for confidentiality) and then he uses your public key to decrypt it again to be sure it came from you (i.e. non-repudiation). Now he knows the message came from you and that nobody else saw it. The message is signed and encrypted.”

The techie indicates that her example, although functionally complete, glosses over a number of implementation details. She quickly shows Bob and Alice how to sign an email using PGP software but then starts nerding-out with all of the cool features.

Bob has this eventuality covered with a pre-arranged cell phone call and both Bob and Alice make their getaway from computing services without having to exercise their brains any further that day.

Dude, Where's Your Public Key?

We just described the essential processes involved in “digitally signing” a document.

Now, what if Bob decided to put the note on his website that openly declares to the world his eternal love for Alice (and plans to get married, pierced, and have 30 kids)?  

Could Bill (his close friend and double-latte buddy) verify whether Bob has lost his marbles?  

If Bob digitally signed his note, then the answer is Yes. He could take the note and its digital signature and verify it in the same way as Alice would verify a love note.

There is only one problem...   Bob never gave his public key to Bill.

One way to solve this is to include all keys in a central, searchable directory. This is what happens in a business or corporation that uses PKI for authentication purposes (there are other reasons for keeping this information in a centrally managed directory).

But what if there is no "central" repository of public keys?  In most cases, whenever a message is digitally signed, the public key of the author (in addition to the encrypted hash) is also attached to the note.   This makes it easy for anyone to veryify the authenticity of the message because they have everything they need right in the message.

But this process has a weakness that Eve will almost surely exploit....

Eve Strikes Again

Eve tries to foil Bob and Alice's weekend plans several more times but realizes that something must have changed since they do not appear perturbed.   She queuries her techie pawn and finds out about the use of digital signatures.  Foiled!

But Eve is persistent. She proceeds to get herself a copy of PGP to work with. After some experimenting, she makes a very important discovery. It appears that the software only reports an error to the user whenever the digital signature verification process or decryption *fails*.

Like a cougar, she immediately sees an opening and goes in for the kill....

Alice sends a note to Bob with the subject "Our problem". Eve sees it land in Bob's in-box and immediately deletes it.   She doesn't know what it says but she bets that Alice is referring to her.

"Well then," Eve thinks, "you want a problem? How about this?"

Eve composes a new note using Alice's email account:

Nice.

Eve signs the message with a carefully crafted private key and then encrypts it with Bob's public key. She then attaches it to an email from Alice, presses send and goes for lunch and a victory manicure.

Bob, The Office LineBacker

Eve walks back into the office after lunch just in time to see Bob sail horizontally through the air and crash into Bill. Both continue flying through Janet's cube and into the photocopy room.   Bob is eventually subdued by others in the office while making photopies of Bill's face (which he has firmly planted between the copier glass and the copier lid.

"Hmmmmm..... that's not quite what I was planning," Eve thinks, "but I can work with this..."

What did Eve do? (To be continued)