1:48

Okay, so now the nice thing about this design is that now every user only

has to remember one secret key. The question is now, what happens when Alice

wants to talk to Bob? Somehow the two of them have to engage in a certain protocol,

such that at the end of this protocol they will have a shared secret key KAB that the

attacker wouldn't be able to know. And so the question is how do Alice and Bob

generate this shared secret key KAB. So let's look at an example toy protocol for

doing that. So here we have our friends Alice and Bob. As usual Bob has his key

KB, which is shared with a trusted third party. Alice has her secret key KA,

which is also shared with a trusted third party. So here the trusted third party

has both KA and KB. And the question is, how do they generate a shared key that

they both agree on, but the attacker would have no idea what this shared key is? So

here we're only gonna look at a toy protocol. In particular, this protocol is

only gonna to be secure against eavesdropping. It's not gonna be secure

against more tampering or active attacks. As I said, we're gonna come back and

design secure key exchange protocols later on in the course. But for now, just to

introduce this idea of key exchange, let's look at the simplest, simplest mechanism

that's only secure against eavesdropping. So in other words, adversary that listens

to the conversation won't know what the shared key KAB is gonna be. And so the

protocol works as follows. Alice is going to start by sending a message to the

trusted third party saying, hey I want a secret key that's going to be shared with

Bob. What the trusted third party will do is it will actually go ahead and choose a

random secret key, KAB. So the trusted third party is the one who's gonna

generate their shared secret key. And what it will do with this key is the following.

It's gonna send one message back to Alice. But this message consists of, of

two parts. The first part of the message is an encryption using Alice's secret key,

using the key KA, of the message this key is supposed to be used between parties

Alice and Bob, and she includes the secret key KAB inside the message. Okay? So just

to be clear, what's happening here is that the message that gets encrypted is the key

KAB plus the fact that this key is supposed to be a shared key between Alice

and Bob. Okay. And this whole message is encrypted using Alice's secret key. The

other part of the message that the TTP sends to Alice is what's called a ticket.

And this ticket is basically a message that's encrypted for Bob. So in other

words, the ticket is gonna be an encryption under the key KB of, again, the

fact that this key is supposed to be used between Alice and Bob. And she

concatenates to that the, the secret key, KAB. Okay, so again, the message that's

encrypted inside of the ticket is the fact that this key is to be used by Alice and

Bob. And, the secret key, KAB, is included in the ticket as well. Okay, So these two

messages, Here, let me circle them. These two messages are sent from the trusted

third party to Alice. Now I should mention that the encryption system E that is

actually being used here is a CPA secure cipher and we'll see why that's needed in

just a minute. So, this is the end of the conversation between Alice and this

trusted third party. Basically as we said at the end of this conversation,

Alice receives one message that's encrypted for her and another message

called a ticket that's encrypted for Bob. Now at a later time when Alice wants to

communicate securely with Bob what she will do, is of course, she will decrypt

her part of the message. In other words she will decrypt the cipher text that was

encrypted using the key KA and now she has the key KAB. And then to Bob, she's going

to send over this ticket. Bob is going to receive the ticket and he is going to

use his own secret key KB to decrypt it and then he himself will also recover the

secret key KAB. So now they have the shared secret key KAB that they can use

to communicate securely with one another. And the first question to ask is, Why is

this protocol secure? Even if we only consider eavesdropping adversaries. So,

let's think about that for a minute. So, at the moment all we care about is just

security against an eavesdropper, So let's think. What does an eavesdropper see in

this protocol. Well basically he sees these two cipher texts. Right, he sees the

cipher text that's encrypted for Alice. And then he sees the ticket that's

encrypted for Bob. And in fact he might see many instances of these messages, in

particular if Alice and Bob continuously exchange keys in this way he's gonna see

many messages of this type and our goal is to say that he has no information about

the exchanged key KAB. So this follows directly from the CPA security of the

cipher E D because the eavesdropper can't really distinguish between encryptions of

the secret key KAB from encryption of just random junk. That's the definition of CPA

security and as a result, he can't distinguish the key KAB from, you know,

random junk which means that he learns nothing about KAB. This is kind of a very

high level argument for why this is eavesdropping security but it's enough for

our purposes here. So the bottom line is that in this protocol the eavesdropper

would actually have no information about what KAB is. And therefore it's okay to

use KAB as secret key to exchange messages between Alice and Bob. Now let's think

about the TTP for a minute. So first of all, you notice that the TTP is needed for

every single key exchange. So basically Alice and Bob simply cannot do key change

unless the TTP is online and available to help them do that. And the other property

of this protocol is in fact, the TTP knows all the session keys. So if somehow the

TTP is corrupt, or maybe it's broken into, then an attacker can very easily steal all

the secret keys that have been exchanged between every user of this system. This is

why this TTP is called the Trusted Third Party because, essentially, it knows all

the session keys that have been generated in the system. Nevertheless the beauty of

this mechanism is that it only uses symmetric key cryptography, nothing beyond

what we've already seen and as a result it is very fast and efficient. The only issue is

that you have to use this online trusted party and it's not immediately clear if for

example we wanted to use this in the world wide web who would function as this

online trusted third party. However, in a corporate setting this might actually make

sense if you have a single company with a single point of trust it might make sense

to actually designate a machine as a trusted third party. And in fact a

mechanism like this not quite as the way I described it, but a mechanism like this is

the basis of the Kerberos system. So this is our first example of a key

exchange protocol that allowed Alice and Bob to set up shared keys, however I

really want to point out that this is just a toy protocol. Very, very simple and is

only secure against eavesdropping attack. It's actually completely insecure

against an active attacker. And here's a very simple example of how an active

attacker might destroy this protocol, and so let's just look at replay attacks. So

here imagine the attacker records the conversation between Alice and some online

merchant. Let's call him Merchant Bob. So for example, imagine Alice orders a book

from the merchant Bob and the transaction completes and Bob accepts payment for this

book. And actually sends Alice a copy of this book. What an attacker can do now

is, he can complete, completely record the conversation and simply replay the

conversation to merchant Bob at a later time. Bob will think that Alice just

reordered another, another copy of the book and he'll charge her again for it,

and send her this, this copy again. So essentially by replaying a conversation

you can cause quite a bit of harm to Alice, and as a result this is a simple

example of why this protocol is completely insecure against active attacks, and

should never be used in the real world. As I said we're going to come back in a few weeks

and talk about secure versions of this protocol, and you'll see how to make this

work, in the real world. Nevertheless, you see that this, this very simple protocol

already raises a very interesting question. And the question is, can we

basically design key exchange protocols whether they're secure against

eavesdropping or secure against active attackers. The question is, can we design

key exchange protocols that are secure, but work without an online trusted third

party. So we don't wanna rely on any online trusted party that's necessary to

complete the key exchange protocol. And so the amazing answer is that in fact this is

possible. We can do key exchange without a trusted third party. And this is, in fact,

the starting point of public cryptography. So I'm gonna show you three ideas for

making this happen and we're gonna talk about them in much more detail in the, in

the coming modules. So the first idea is actually due to Ralph Merkle back in 1974.

This was, he was, when he was just an undergraduate student. And already he came

up with this really nice idea for key exchange without an online trusted third

party. So that's one example that we're gonna look at. Another example is

due to Diffie and Hellman. Back in 1976 they both actually, working here at

Stanford University, came up with this idea that launched the world of modern key

cryptography. And the third idea is due to Rivest, Shamir and Adleman working at MIT and

we're going to look in detail exactly how each of these ideas work. But I do want to

mention that the work on public key management hasn't stopped in the late

seventies. In fact there have been many ideas over the years and here I'll just

mention two from the last decade. One is call identity based encryption, which is

another way for managing public keys. And another is called functional encryption,

which is a way of giving secret keys that only partially decrypt a given cipher text.

And so we're gonna talk about the core of public key crypto in this and the next week

and we'll talk about these more advanced ideas later on in the course.