From before the midterm we know how to encrypt data using two approaches, symmetric key encryption and public key encryption. Symmetric key encryption, remember we use the same key at both end points. In public key encryption we have a pair of keys, we encrypt with one and decrypt with the other. For example, encrypt with a public key, decrypt with a private key. This topic is about how do we distribute and manage keys. So let's say every student came here, we had 40 students in this lecture and you want to use symmetric key encryption. The 40 students, you want to use symmetric key encryption, think about if you want to be able to communicate with any other student, how many keys do you need to exchange? Think from your perspective, you want to be able to communicate with every other student and you want to use a different key for each pair of communications because when one student communicates with another using one key, they don't want to use the same key to someone else because then that third person can decrypt the first pair of communications. So think about how many keys do you need to exchange with other people? Anyone know the answer? 40 students, if everyone turned up, 40 keys. Close? 39. From my perspective, if I was a student, I would need to exchange with 39 other people. If they're 40 in the group. So from one person's perspective, if we need to use a key, a shared secret key between every separate pair of users, that student would need to go to the first person and say let's use this key. Go to the next person and say let's use this other key and do that for all 39 other people and they would exchange 39 keys. So that's from the perspective of one student. You need to go to 39 other people to exchange keys. So in terms of the total class, how many keys are there? One student has 39, that is one with the 39 other students. How many keys in total? 40 times 39, not quite. 1,560. Where did you get that from? I don't know the answer. 40 times 40 minus 40. No? I think the logic is that one student needs to exchange with 39 people. The second student needs to exchange with another 38, correct? Because he's already exchanged with that first one and the other 38 he needs to exchange another key with. So 39 plus 38, the third student has exchanged one with the first two and he now needs to exchange with 37 others. So 39 plus 38 plus 37 goes down. So one student needs to exchange with 39 in total, the total number of keys exchanged and there's a formula for that. The general formula is how many pairs are there? If there are n users, what is it? n times n minus 1 on 2. Not so important but we'll see that's used. So for example with 40 users, there are 40 times 39 divided by 2 which is what? 20 times 39, 780 pairs. Meaning if we have a, so 780 pairs of students, meaning if every pair has a key we need in this network of students, 780 keys. This formula n by n minus 1 over 2 just gives us n, this 39 plus 38 plus 37 and so on. How many pairs in some set of n users? So now, if we want to allow communications between all our 40 users we need to exchange 780 different keys. How do you choose a key? So if you want to do AES encryption you need to choose a 128 bit random value. So how are you going to get your key to the 39 other people? Share it. You need to get one random 128 bit key to 39 other people. How are you going to do that? Give me some more practical way. You want to get a one value, a random value, 128 bits to this person and then the next person and a different value to each person. Give me a way that you may do it in practice. Post on Facebook, okay? Post your key on Facebook but remember we're dealing with symmetric secret key encryption. If you post it publicly it's no longer secret. These are secret keys. You need to get a key from one person to another without anyone else knowing that key. Posting on Facebook and your email or whatever is may not be appropriate. So we need some way to do that. Send, encrypt the key with another key and send that encrypted one but then the problem as you see is how do we get that other key between the people? Okay, so it just keeps growing and growing. Well that gives a hint one way to do it is use public key encryption. We'll see one way is public key encryption. Remember one of the keys is public. You can post it on Facebook but as long as you keep your private key private. So that will be one way. This topic is about how do we distribute keys? Public key encryption we'll see is one. Another manually write the 128 bit value on a piece of paper. Go to your friend, give it to them. Don't let anyone see it. Then do it with 38 other people. Or okay instead of on paper maybe via some USB. Okay, share. Now maybe it's possible in this small group of 40 people who see each other every day but what about when you want to do it across the internet? To anyone else on the internet. Stegonography, hide something. Stegonography is good for hiding things until someone knows the pattern and then they can see it. So it becomes a practical problem of when you don't have face-to-face access, when you're communicating across the network, how do you get a key from A to B? And more generally how do you get a key to anyone that you may potentially want to communicate with? So we've got a whole topic which will take this and probably next week to cover the different ways to distribute keys and to keep track of them. Use them in the right way. Key management. So the challenges, we want to use symmetric key encryption. The challenge is how do we share a secret key so that no one else discovers the secret. When we use public key encryption, anyone remember what do we encrypt with when we use public key encryption for a confidentiality? To encrypt a message for confidentiality, to send to someone else, you use their public key so that they can decrypt because they have their private key. But how do I get their public key?  That makes sense. It's a public key, anyone can see it. How do I know it's really their public key and not someone else's? What if you see a public key on a website saying this is Steve's public key? So what you do is you download it, you to send me a message, you use that public key and send me a message. But it was really a student who posted what was their public key, but they said it was Steve's public key and that student intercepts your message and can decrypt what you sent. So we have this problem that yes, public keys can be public, but how are we sure that the one that we have is in fact of that person? You're leading to signatures and some of the cryptographic techniques that we've talked about will take advantage of them. Who signs it? Why me? Well, we'll see you're on the right track. Get someone you trust to sign it. We'll see that's the way to distribute public keys. So we'll spend some time on that as well. The other thing is you choose a secret key between two users and you encrypt your data and you use it today and you use the same key tomorrow and you use it for the whole year and for four years of studying together, you're using the same key. Do you think you should change it? Any benefits of changing the key? Well, in theory, yes, there are because the less times you use a key, the less chance an attacker has to try and find that key. So if I keep changing keys every day, the attacker's problem becomes harder and harder because if they're even trying a brute-force attempt, then they start it today, but tomorrow they have to try it on a different key and then the next day on a different key. So changing keys is recommended. How often? How do we change them? That's what we need to look at in this topic. So we're going to try and address some of these challenges in managing keys. How often do you change passwords, the similar concept, although they're even easier for the attackers to find? The more often you change, the more secure it can be, but that more inconvenient it is. So to continue, we're going to make some assumptions to analyze and look at these challenges. Let's assume that our users are not necessarily inside a class and all know each other and have physical access, but in a network, like the internet. So they may not have physical access. You can't walk to someone and give them a written down key if they're in another country. So let's assume that there are many users and they want to communicate securely across a network, across the internet, for example. And we're going to assume that there's a malicious user or an attacker that can intercept anywhere in that network. So they'll have an opportunity to intercept anything that's sent. Therefore, anything that's sent across the network, if we don't want the attacker to see the contents, we must encrypt it. We want to minimize the number of manual interactions. A manual interaction is like physically going to someone and giving them the key. An automatic interaction is when we use some software or protocol to automatically exchange keys. That's what we'd like to do. Manual interactions are expensive, they're inconvenient and sometimes can be insecure. And the other assumption or principle we'll use is that the more times a key is used, the greater chance for the attacker to discover the key. And that will lead us to this approach, well, let's change keys on a regular basis. Don't use the same one forever. So let's look at some issues involved with key management. First, let's start with this example network. I've just drawn a simple network, our internet, which has, what, 10 computers, 10 hosts, A through to J, some switches, some network switches and some routers. We just connect them together. So we have some issues of, if we want to encrypt data, say, I want to send data from A through to J, where do we perform the encryption? Where do you think we should have performed the encryption and decryption? I want to send from A to J. Encrypt at A and decrypt at J. That's the first approach. Encrypt at the endpoints. A has some data, A, the computer A encrypts the data, sends it through switch one, router one, switch four, router four, switch six, received at J and J decrypts. That's what we say, encrypt at the endpoints. But there's another approach. Encrypt across each link. That is, A has data, encrypt the data, send it to the switch, the switch decrypts. And then encrypts again with a different key to send to router one. The router one receives decrypts. Encrypts again to send it through to switch four, decrypt, encrypt to router four and so on. So encrypt and decrypt across each link is another way to do it. Which way is best? So the question is, how does the router know the key to decrypt? It must have exchanged the key with one of the other entities. Similar, how does A and J, how do they know which key to use? They must have exchanged keys. If they have exchanged keys, then two basic approaches, encrypt across the links in a network or encrypt from end to end at the endpoints only. Let's consider both of those cases and consider, well, how many keys would we need to exchange if we did either of them? If we do the second one, encrypt across the links only, how many keys do we need? In this example, that is, A and the switch must have one shared secret key to encrypt across that link in both directions. They use the same key. The switch one and router one must have a key. How many keys? Oh, sorry, I have a question. Yeah. The question, can the router intercept? No, let's say these are wired links just for simplicity. So that means if B sends to the switch and if it's encrypted, then when B, it's encrypted. The only person who can get the content of that data is that it has the key. Even if they could listen in, let's say we encrypt it. So B, or A coming back to our example, has some data to send to J. It knows it must send to switch one. Therefore, it encrypts with a key shared with switch one and sends to switch one. Then switch one encrypts and sends to router one and so on. How many keys needed in the network? How many? Six. Six. In the type. Now let's assume, I think you're correct, let's assume any computer wants to communicate with any other computer. That is, yes, A wants to talk to J, but maybe B wants to talk to I and J wants to talk to F. How many keys are needed in the network if we do link level encryption? How many? 20. Why 20? All the links. I can't remember how many links. You can count them. 5, 6, 7, 11, 13, 16. Yeah, there are 20 links. So if we use encryption across each link, a key is needed between E and switch two. Anything sent between them uses that key. Anything sent between D and switch two uses a different key and so on. So if you count the lines in here, the links, there are 20. So we would need 20 keys in that case. Just remember, I'll just write down how many keys we needed. With link level encryption, link only, we'd need 20 keys in our example, because there are 20 links. How would we distribute those keys? Well, one option would be the person who builds the network. They set up the switches and the routers and they program in some keys for each link. So the person who plugs in this cable programs in a key for the switch and computer E. When they plug in the cable between switch two and router one, they program a key for that link. So that's one way to manually enter the key. So 20 need to be entered here. Now let's consider another case. End only encryption, endpoint only. The case where A encrypts, JD encrypts, how many keys needed if anyone wants to communicate. If any host, any of these squares, A through to J, there are 10 of them. If any of them want to be able to communicate. So A needs a key shared with J, there's one. A needs a key shared with I, there's a second key. A with H and A with the other nine. How many in total needed? If any user wants to communicate with any other computer. A with E, C with H, 45. How do you get 45? 10 times 9 divided by 2. Correct? Where did that come from? Like our first example, there are 10 entities. User A needs to share nine keys with the nine others. B needs to share with eight others because he's already shared one with A. So there's first nine keys plus eight that B shares with others. So nine plus eight because B and A already have one shared key. So don't count that again. C has a key shared with A. It already has a key shared with B. So it needs to share another seven keys because there are, is it seven? Yeah, there are seven other nodes. So nine plus eight plus seven plus. And the general formula we said was with N entities, the number of pairs are N times N minus one divided by two. This was the one. That's how if N is 10, 10 times nine is 90 divided by two 45 keys. Nice formula to remember. Otherwise you have to manually add it up. N points and I'll make a note between computers. We'll change it in a moment. We need 45 keys. So you see at this point, one of the benefits of using link only encryption, less keys to distribute. The fewer keys to distribute, generally the easier it is. Because someone has to do that distribution. So link link only generally will use less keys, but there are some disadvantages. One more case. Let's say on those computers are applications. So let's say computer E is running five different networked applications. I don't care web browsers or some specific application that wants to communicate with other applications on other computers. So there are let's to keep it simple. There are five applications on every computer, five on a five on j and so on. And we want to allow any application to communicate with any other application securely. And each application will use its own key. So the application one on E to application two on D will use one key. And the other pairs of applications would use a different key. So just a generalized form that let's say there are five applications running on every computer and all of those applications would like to be able to potentially communicate with any other application, including the special case of applications on the same computer. How many keys or how would you calculate? So still on the end points, but let's say five applications. There are five apps per computer. How many entities need to communicate 10 computers? Each computer has five applications. Let's say we allow them all to communicate with anyone else. There are 50 applications in the network. 50 entities. So how many pairs 50 times 49 divided by two, just extending if you have five applications per computer, there'd be what 50 times 49 divided by two, which is what 1225 keys. This is again our n times n minus one divided by two 50 times 49 2450 divided by two 1225 keys. So depending upon who does the encryption, we'll have a difference number of keys to have to distribute through the network. The fewer the keys, the better. Encrypting between applications will require more than if we encrypt between just computers because most computers may run multiple applications. Encrypting across links only will usually be much fewer keys needed than between end points. So in terms of number of keys, link only is better. What's the problem with link only encryption? What's the problem with link only encryption? Let's assume we have a way to distribute those what I mean 20 keys. What's still a problem with link only encryption? A wants to communicate with J. We're using link only encryption encrypt across each link separately. There are 20 different. Okay, if there may be multiple different ciphertexts for the same messages. Yes, true. But if we have a strong enough encryption algorithm, then that would be that is a large enough key and block size and practically no difference. In theory, I think that's true. But what's more practical? You're malicious. What can you do? A sending a message to J. A encrypts sends to switch one, switch one decrypts, then encrypts with a different key sends to router one, router one decrypts. This is the link only encryption. Just encrypt separately across each link, router one decrypts and so on. What's the problem? pretend to be a you need to let's say you cannot. You don't know the keys. Pretending to be a I don't know if that's any different in terms of link only or host only. Let's say you want to implement this in the internet. Note that each of these network devices looks what happens at router one switch one encrypts sends to the router the router inside the software decrypts the message gets the plain text and then encrypts that plain text with another key and sends the ciphertext to switch for while that router is running. There was a small time instead when the plain text was available because the receive ciphertext is decrypted. We get the plain text. It's in the memory on router one and then the router one encrypts that plain text and then sends. So if someone can get access if someone can get access and read the memory on router one then we have a problem. That is link level encryption. We must trust the intermediate devices. But if some malicious user can access those intermediate devices it's not effective. Of course if someone could access the device the other thing they can do is get the key. So link level encryption we must trust that the network devices. When you do your banking or do some financial transactions across the internet do you trust all of the devices between you and the server you're connecting with. Do you trust the switch in SIT. Do you trust your internet service provider. I don't. Okay. I'm not saying that they're say in SIT but it would be quite easy for someone to with a bit of effort. Plug in some special device into the switch in the computer center and capture everything that went through that switch. So everything that goes through the switch and even potentially monitor what's happening in the decryptions and that are happening there. In large networks built by different organizations trusting that network equipment is not a good idea in terms of security. In a small network where one organization manages that internal network it may be applicable. That is everything inside SIT maybe we could trust but should SIT trust our internet service provider and the internet service provider in other countries. No. Okay. So in the internet link level encryption is not really used. It's only used within organizations networks. So even though less keys that's the main problem. We were not considerate much further from now on. We'll assume that the computers want they want to communicate will use some end to end communication and encryption. Which means there are many keys that we must distribute. Which means that we must have some automatic way for distributing those keys. We cannot distribute 1,025 keys by writing them down on a piece of paper going to another person and giving them that key. We must automatically do it. So link versus end to end. With end to end we don't rely on the intermediate devices. With link level encryption we must trust the intermediate devices and that's not appropriate in large networks. We've just went through both that example of how many keys would be needed. So our problem many keys to be distributed. How do we do it automatically? Several options. The manual approach. Write them all down. Give them to someone face to face. Too inconvenient. As the number of keys grows. We cannot do that. So it's an option but only when we have a few keys that have to be distributed. We will go through this second option. All the users exchange one key with some trusted third party. Some other entity. And then that key called a master key is used to automatically distribute other keys to the users. Coming back to our first case. Every student, 40 students want to be able to exchange keys with every other student. We said there was 40 times 39 divided by 2. Which is what? It's alright. 40 times 39 divided by 2 keys which is our 780. 2 times 39, 780 keys. If there are 40 students in the class, there are 780 pairs of students. We'd need 780 keys to distribute. Another way. Everyone trusts me. So what you do is every student comes to me and we exchange one key with a master key with each student. So one student has a master key that I now have. Another student has a separate master key. So there's 40 exchanges. 40 students all to the trusted third party. We do that manually and then we'll use some protocol in the network to exchange keys between students encrypting them using the master key. So use someone else to help the exchange. Manual exchange of master keys. Automatic exchange of what we'll call session keys. So we'll go through a scheme for doing that using it. What's called a key distribution centre, KDC. Option three, use public key cryptography. We will come back to that after we go through the key distribution centre and see how that can be used. So now let's go through some ways that we can exchange secrets. That is, symmetric keys need to be distributed and to distribute them across the network we will encrypt them using symmetric key encryption. So objective. Two entities that say two users want to share a secret and will assume that they want to change them on a frequent basis. Maybe every few minutes if it's some applications in the network. Maybe once a day. But they need to change the keys. They can't just exchange keys once and use them for the next 10 years. So how do we exchange a secret key? Let's go through two approaches. A decentralized approach. Decentralized key distribution. And use a key distribution centre, KDC. So we'll go through both of these and explain the trade-offs between the two. We'll talk about different types of keys. We'll distinguish between a master key and a session key where we'll use, so the key hierarchy, where we'll use the master key to encrypt a session key and securely exchange that session key across the network. And then we'll use the session key to encrypt data. So we'll see some examples of how we use the different types of keys. Let's go straight to a scheme for key distribution. Then we'll come back and talk about the keys. Explain the advantage of using a master. So let's assume this notation. We have two entities want to communicate, A and B, two N systems. We'll give them some ID, IDA, IDB. We'll say that there's a master key to be shared between A and B. Let's call it KM. And there'll be, in some of the schemes, we'll see there's a master key specific to a user, KA for user A, KB for user B, and KC for user C and so on. We'll talk about a session key, KS, between two users. So we'll use this notation in these following schemes to distinguish between a master and a session key. Nonce values, we'll come back and explain after we see them in use. Here's a scheme for distributing keys in a decentralized manner. This assumes before these, so there are three steps, one, two, three. So we send a message from A to B containing this information. B sends back a response and then A sends the third message to confirm. So we'll go through what the message is contained shortly. This approach assumes both A and B have exchanged a master key in advance. So before step one, A and B have exchanged keys. Let's go through and draw and see what information we learn as we go. So I'm going to draw this scheme if I can remember it and we'll look at how it provides the key exchange. So it uses A and B. And what do they know? So what do we assume is known by those users in advance? In this case, we assume that they know the notation is KM. Assume they both know KM, some master key. And B also knows KM, the same value. How do they know KM? Again, some manual exchange. User A chose a random number, KM. Then he went to user B and they exchanged manually that key. So we assume that there was some initial exchange of this master key to get started. And then A wants to communicate with B. So we'll use this concept of instead of using KM, we will securely exchange a session key. A key that we can use just for a short period and therefore we can change it on a regular basis. So as per the diagram, user A wants to communicate with B. User A, we denote as IDA. That's their name or their identity. And user B, IDB. We send a message. So that's the first message in our diagram. And what does it contain? It contains user A's identity. So user B knows who sent it. And combined with that, we'll include a nonce on our diagram that you have in front of is N1, I think. So I'm just drawing this one, message one. Just draw it a little bit different. Identity is something that identifies this user in the system. A name of a user, an address of that computer, something that identifies the the entity. What's a nonce? On the previous slide we said there's a nonce. What's a nonce? N-O-N-C-E. Anyone heard of it before? A nonce is short for a number to be used only once. N for number, use only once. So it's a number. The concept is used for cryptography. It's when we need to have some number and it usually needs to be unique and it's going to be different and hard to guess. So we use that number just once. It's short for a number to be used only once. And we'll see that we use nonces several times to provide some form of preventing replays. Preventing someone sending a message the same as before and also authentication to authenticate messages. So how do we choose a nonce? Just going back. A number used only once. It can be a timestamp for example. The time. If we send a message the time right now in milliseconds. The next time we send a message it will be different. Okay so sometimes we can use timestamps. A counter. The first time we send a message send one. The next time two, three. Assuming the counter goes forever. It will be a number we use only once. Or a random value. Okay choose a random value. That's the nonce. The next time we send a message choose a different random value. We'll often use a function sometimes like if the nonce value was 10 the response will be 10 plus 1 increment for example. It should be different for each message. So the first time we send this n1 to communicate from a to b we use some number. The next time we send from a to b use a different number. And it should be difficult for some other entity to guess what you would use. That's not always required but in some cases we use a nonce. It should be hard to guess what what you'll use. That's where a random value is easy. Just choose a random value. How is something going to guess which random value you choose in advance? So if we need that property random values work. We'll see how it works in a moment or how it helps. Nothing secure at the moment. We've just said I'm a here's my let's say random value n1. b receives. b knows that a wants to communicate. So back to our diagram. I'll draw it in a moment. b generates a response which includes we'll zoom in in a moment a secret session key ks the identity of a to confirm this was going to a the identity of b its own nonce value n2 and some function on n1 like increment by one. Let's draw it and then see how that helps. So what b does is chooses a session key ks say some random key that's what they're going to use shortly to encrypt their data sends back a response and it's that long one on that diagram so we'll see what is it encrypt with km this large set of values which if I remember ks the session key combined with the two identities so this is the same as your slide what else is included the nonce values actually I say a function let's say n1 plus one increment and the last one n2 running out of space but we'll see so this is almost the same as on the slide b sends a response it includes the session key that they're going to use the identity of a to confirm this is a response to what a sent and includes the identity of the identity of b saying this is from b n1 a function of n1 let's say n1 plus one I've used as an example function so a chose n1 as some random number we'll give it an example value let's say n1 was some random number that a chose that was n1 then this n1 plus one is just that random number plus one and n2 is another random value chosen by b only in this case n2 is some other some example values so think of the nonces there was a random number and the function is some modification to that random random number known in advance here I've just used increment by one all of this is encrypted with our master key remember our goal is to get a session key between a and b we've chosen a session key we send it back with all this other information encrypted with a master key what does a do they decrypt a knows the master key so they decrypt and when they decrypt they get the session key so they now know the session key and the last step is to respond final confirmation encrypted with that session key some modification of n2 encrypt not with a master key but the session key that was just chosen by b let's say n2 plus one some function applied to n2 the value in our example would be 86343 what's known at the end a knows still km what secret values are known they knew that at the start but they now know ks and of course b knows km they knew to that at the start but they now know ks what we do now is that the data sent between a and b is encrypted with a ks we use the session key to encrypt the data everything okay yeah it's it's some negotiation before the data transfer okay so the intention was a wants to communicate with b they want to send some data transfer a file to do that they're going to encrypt the data what here they're going to use they're going to use a session key why didn't they use the master key why did if they already know the master key in advance why not just encrypt the data with the master key why go through these three complex steps more secure good but more specific why is it more secure we're using this principle that we assume they both know some master key so one option would have been don't do these steps a just encrypts the data using the master key sends it to to b and they keep transferring their files using km as the key but the principle is that don't keep reusing the same key so what we'll do is use the master key just to encrypt a session key use this session key to encrypt the data let's say for one hour and then in one hour's time repeat these steps choose a new session key and encrypt more data using the second session key so we don't reuse the session key too often and how many times we're using the master key we only use it once every time we choose a new session key we use the master key once so this is this principle of don't reuse the keys that is limit the the number of times you use them note that this is done across a network automatically by software by a protocol the user's not involved whereas the master key distribution that we said was manually done maybe the users went to each other and they typed in the the master keys to share that was inconvenient and time consuming but once that's done all of this is automatic done by software and every every end hours we can repeat this process and get a new session key and achieving this this goal of not reusing keys can can you as a malicious user find the session key how do you find the session key put on your black hats think about what will you do to find the session key or can you and assuming this is done across the network you can intercept everything sent across the network that is you can see the contents of these three messages you can see the id of a and n1 no session key there you can see this cipher text but note it's cipher text even though it includes the session key it is encrypted with km the only person who can see the contents is someone who has km and you as the malicious user do not have km it's only shed between a and b so you cannot see the ks that was sent by b to a here we're not sending ks we're encrypting using ks again you cannot given the cipher text you shouldn't be able to discover what key was used to encrypt so you cannot as the malicious user intercept and cks so we've securely distributed a session key between a and b that was our goal what is all the nonce values for why do we need all these n we often use nonce values to stop for example replay attacks what if someone sends a message so they if there was no nonce value they take a copy of this message and send it again in the future uh so we use the nonce to confirm really did you really mean to send that message so if b receives a message with our nonce 4 3 whatever it was 4 3 4 6 3 2 5 9 8 up the top b sends back some modification of that which is really a question to a saying did you really send that message with that nonce value if a receives this and they see b just sent back 4 6 3 2 5 9 9 but i didn't i didn't send a message with 4 6 2 3 5 9 8 then a will not respond with this third one and it will not successfully complete so it's acting as a confirmation did you really send this and that can prevent malicious users from replaying messages to try and confuse and defeat the users similar to the last nonce and to and a replies here to confirm the receipt of the n 2 that was chosen by b so use for authenticating are these messages valid we'll see them in in the next scheme as well in other schemes you want to use this scheme between the 40 students again not with physical but between your computers how many master keys are needed 40 students you're all on your your laptops and mobile phones you're using some software to use this scheme this scheme requires master keys to be distributed in advance how many master keys how many master keys km was between a and b again no not 39 let's go back we have so in this scheme was just between a and b so what do we have we had the master keys a and b shared a key we called it km let's say there was a third user c then a and c would need to share a key i don't know let's just call it k a c i know it's a different terminal a different notation but and b and c would need to share a key that is we'd need three master keys so if there were three users in our system we would need those three master keys if there are four users how many no four if there are four users there's d i don't think it's seven nope not eight keep guessing we'll get there uh y3 again this is our n minus n minus two n times n minus one divided by two how many pairs with three users three times two divided by two there are three pairs with four users it's four times three divided by two twelve divided by two six let's list them just so people understand that concept if we had d we'd have a b a c a d b and a have already shared so that we b c b d and the sixth one would be who c d they are the pairs amongst four users so again we don't care a and b and b a b and b a are the same so there are six pairs six keys and in general it's again i'll repeat with n entities n by n minus one over two pairs n times n minus one nice equation to remember over two why it's three plus two plus one a okay correct lucky someone's awake here we go who is it b d correct a with b a with c a with d b is already shared with a so b with c b with d and the last one c with d so six in total 40 students is our 40 times 39 divided by two which is our 780 for example so this scheme we still need to share a lot of master keys it doesn't help there if there are a thousand entities it's a thousand times 999 divided by two about 500,000 keys not very convenient because it still needs to be done manually this key distribution but once we have done that master key distribution everything from then on is automatic through the network by encrypting the session key with the master key so it has the disadvantage of many master keys but if we can do that we can then automatically distribute session keys only really useful in smaller networks not so many users there's no one else involved in the distribution there's no trusted third party the next scheme we will see there is and explain what that means so alternative that scheme uses too many master keys okay so we want to cut down on the number of master keys distributed use a key distribution center kdc it's a trusted third party that means it's some other entity that's not involved in the communications that all of the users trust like me in the class let's say you don't trust any of the other students therefore you need to do use encryption to communicate but if you trust me i can help you distribute the key so i would be a trusted third party if you don't trust me then you cannot use me as a key distribution center so let's assume we have someone we trust this approach now is that we have manual exchange of master keys between each user and the kdc and then automatic exchange of a session key between users but it's done via the kdc before we draw go through that scheme let's draw it in general the idea the idea of the kdc let's say we have uh this special user kdc and four users a b c and d four normal users and one special user they all trust the kdc the first step is that they exchange manually master keys with the kdc so a and the kdc exchange some key let's call it k a b no k a the notation here this k a is a key that a has and the kdc has and between b and kdc is as you may guess kb that's the first step these are master keys how many master keys four in this case if there were 40 users like in this class there would be 40 master keys a thousand users a thousand master keys one master key per user in the previous scheme the number of master keys was n by n minus one divided by two in the previous scheme with 40 users there were 780 master keys with this scheme with 40 users there are just 40 master keys so we significant reduction in the number of master keys this key exchange is done manually if i'm the kdc you come to me and say let's use this key and then everyone else does that now two users want to communicate so now a wants to communicate with b for example a wants to send some data to b we'll see that the scheme we'll go through the details is that there's an exchange between a and the kdc and they're going to get a session key to be used between a and b so the idea is that the kdc will choose a session key and the kdc will inform both a and b so if a wants to communicate with b they'll go through some steps where a session key will be distributed to both a and b and then their data is sent encrypted using that session key so the first part is the master key distribution is done manually but the second part will be done automatically using some software across the network where kdc will give a session key to both a and b and then when a and b want to send data to each other they encrypt using ks the session key if b and c want to communicate they'll go through similar steps kdc would give b and c a different session key and then b and c would communicate using that session key so these steps must be automatic done across the network which means they must be secure if we send a session key from kdc to a it must be so that no one else can intercept and find that session key so we must encrypt it and that's what this diagram shows it shows these five steps show the detailed way of doing this process okay i've drawn it differently but the idea is get a session key to a and b the usage of that session key is is actually not shown in the the steps steps one to five so this is how to get a session key to a and b let's just introduce it for today we'll continue on it on thursday but show the steps i'll not try and draw it at the moment five steps one two three four five steps one to three are the key distribution the remaining steps are just some confirmation for authentication make sure there's nothing fake sent or repeat so in fact after steps three both a and b know the session key so it starts a wants to communicate with b to do so they need a session key ks so to get started a sends a message to the kdc saying i want to communicate with b and we see the contents of that message include the identity of a a wants to communicate with b so the identity of b and some nonce say some random value from that random value or that nonce the kdc can check is this a repeat of an old message or if this is a unique unique new message kdc response in the response is a session key chosen by the kdc ks the values of the identities a and b the nonce is repeated so that we can confirm that this is the response to the original request it's not some fake response and that is encrypted with k a it's a little bit hard to see on the diagram but the session key and id a id b and n1 are encrypted with k a as a result only a can decrypt so when a receives this first part there are two parts here when it receives the first part it decrypts and a learns ks the second part of this message when it's received by a is forwarded unmodified onto b and that second part includes ks again the identity of a meaning this comes from a and encrypted with kb meaning only b can decrypt when b decrypts it knows ks and we're finished at least we're finished in our goal of getting ks to both a and b that was our aim a and b know the same session key again a says i want to communicate with b kdc chooses ks and sends it encrypted to a a decrypts and now knows ks the second part of this message from the kdc was encrypted with kb and also includes ks so b would learn ks in that case the last two are just confirmations saying did you really send this message so it's just some double checks or some checks to confirm that everything's authentic the end result what keys does a know at the end user a what keys do they know have a look and see which keys a knows session key ks and k a must know k a okay going back to our diagram we said the first step which is not shown in the previous in the slide but the first step was that they each exchange master keys with the kdc so a knows k a and at the end of that procedure a also knows ks similar with b b at the start does kb and at the end of the procedure b will know ks what will the kdc know what keys does a kdc know k k a kb and ks let's list them at the end of the procedure a knows k a and ks b will know kb and ks and the kdc which chose ks so it knows ks and originally knew k a and kb so that's what's known at the end of that procedure the kdc knows these three keys and that's why we call it a trusted third party because now a and b start sending their data financial information between a website and a web browser for example or two applications encrypted with ks everything that's sent between a and b encrypted with ks the kd in theory can decrypt because the k the kdc knows ks as a result we know the kdc can decrypt our information therefore we must trust them if we don't trust them then this is not an effective scheme to use so that's why we call it a trusted third party because they must because they know the keys therefore they can decrypt everything if the kdc is compromised so let's say the kdc is a server in a network doing this automatically if it's compromised by an attacker then the entire scheme falls down because if someone can get access to the information on the kdc they learn everyone's master key and the session keys so they can then decrypt everything that was sent between a and b and other attacks so the kdc must be a very secure entity in the network so for example if i was your kdc if we have a task where you all get a master key or share a master key with me and then i distribute session keys and i store those keys on a piece of paper in my office and i must make sure my office door is locked all the time so that no one can go in and access those values because if they could compromise the kdc everyone's communications is compromised okay so it's very important to secure the kdc in this case how many master keys if there are 40 students how many master keys 40 students 40 master keys you cannot see at the top diagram we had four users there were four master keys with 40 students 40 master keys but the session keys can be automatically created in exchange using this protocol so every 10 minutes you could automatically create a new session key again this principle of don't use a key for too long so simply the kdc distributes a session key to a and b securely in this specific instance the distribution is done to a via message 2 and message 3 is the distribution of ks to b but in fact it goes via a have a look at the scheme and see if you can break it or what you would need to know to defeat it defeat it includes learning any key that you shouldn't know or trying to send messages which were copies of previously sent messages a replay attack that is if you're a malicious user can you send message 1 again later we'll know it would be detected because the nonce value that is received should not be the same as a previous one so that's the idea of the nonce that if we receive a second message with the same value we would detect that at the receiver shall we have another quiz everyone's ready so we need a few more quizzes this semester expect one every week expect one every lecture not today we're out of time okay so be prepared for quizzes on Thursday we'll go through what an attacker can do on this scheme and then start looking at other schemes for key distribution start comparing the advantages and disadvantages of different schemes there is an online quiz available on firewalls there's an online quiz on firewalls there are eight questions in the quiz they're all the same structure and anyone who did the lab on Saturday or on Monday has seen those questions about firewalls they're slightly different but you'll understand if you didn't do the lab after you see the first question you'll see that every question after that uses the same structure so it'll make sense when you first see those questions try them the firewall questions