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.

Â