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..."