Now that we know how two users can protect data using a shared secret key, the next question is how did these two users generate a shared secret key to begin with? This question will take us into the world of public key cryptography. In this module, we will look at a few toy key exchange protocols as a way to introduce the main ideas of public key cryptography. We're gonna come back and talk about key exchange and design secure key exchange protocols after we build a few more public key tools. So imagine for a second that there a N users in the world. And the question is, how do these users manage these secret keys that they're gonna use to communicate with one another? So, for example, let's assume N equals four and there are four users in the world. One option is that basically every pair of users will share a shared secret key. And so, for example, U1 and U3 will share a shared, a shared secret key. I'll call it K13. U1 and U2 will share a, a shared secret key. We'll call it K12 so on and so forth. K24 K34 and so on and so forth. K14 and finally K23. The problem with this approach is that now there are many, many shared keys that users have to manage. And in particular, every user has to store on the order of N keys if he's gonna talk to N other parties in this world. So the question is can we do any better than storing N keys per user? And the answer is yes. And one way to do that is what's called an online trusted third party. I'll use TTP to denote that trusted third party. So the way we are going to use the trusted third party is every user will now share a single key with this trusted third party. So user one will share a secret key, user two will share a secret key. And here are our friends Alice and Bob, let's call their secret keys k sub A and k sub B. 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.
