Well, we're almost done with our discussion of symmetric encryption. There are just a couple of odds and ends that I'd like to discuss before we move on to the next topic. So the first thing I'd like to mention is how we derive many keys from one key. And it, actually, this comes up all the time in practice, so I'd like to make sure you know how to do this correctly. So what's the setting that we're looking at? Well, imagine we have a certain source key that's generated by one of, a number of methods. Imagine the source key is generated by a hardware random number generator or perhaps is generated by a key exchange protocol which we're going to discuss later. But anyhow, there are a number of ways in which a source key might be generated between Alice and Bob, such that the attacker doesn't know what the source key is. But now, as we said, in many cases, we actually need many keys to secure a session, not just one single source key. For example, if you remember, in TLS there were unidirectional keys and we needed keys in each direction. And in fact, in each direction, we needed multiple keys. We needed a MAC key, we needed an encryption key. We need an IV, and so on. Similarly nonce based encryption, you remember, there were multiple keys that were being used, and so on. And so, the question is, how do we use the one source key that we just derived, either from a hardware process or by key exchange, and generate a bunch of keys from it that we could then use to secure our session. The way that's done, is using a mechanism called a key derivation function, KDF. And I want to talk a little bit about how KDF's are constructed. So first of all, suppose we have a secure PRF, that happens to have key space K. And now, suppose that it so happens that our source key SK is uniform in the key K. In this case, the source key is, in fact, a uniform random key for the secure PRF F. And we can use it directly to generate keys, all the keys that we need to secure the session. So in this case, the KDF is really simple. The key derivation function would just work as follows. It would take as input the source key. It would take an input, a parameter context, which I'm gonna describe in just a minute. And then it's gonna take a length input as input as well. And then what it will do is it will basically evaluate the PRF on zero. Then it will evaluate the PRF on one. Then it will evaluate the PRF on two, up until L. And I will talk about what this context is in just a second. And then, basically, you would use as many bits of the output as you would need to generate all the keys for the session. So, if you need unidirectional keys you would generate, you know, one key in each direction where each key might include an encryption key and a MAC key. And so, you would basically generate as many bits as you need and then finally cut off the output at the time when you've generated enough keys to secure your session. Okay so this is a fairly straight forward mechanism it's basically using the secure PRF as a pseudo random generator. And the only question is what is its context string. Well, I'll tell you that the context string is basically a unique string that identifies the application. So in fact you might have multiple applications on the same system that's trying to establish multiple secure keys. Maybe you have SSH running as one process, you have a web server running as another process, IPsec as a third process and all three need to have secret keys generated. And this context variable basically tries to separate the three of them. So, let me ask you, more precisely, what do you think the purpose of this context variable is? So I guess I've given it away and this context variable is supposed to basically separate applications, so that even if, for example, the three services that we just talked about, SSH, web server, and IPsec, if they all happen to obtain the same source key from the hardware random number generator then the context since it's different for the three apps will make sure that they still get three independent strings that they can then use to secure the sessions. I just want you to remember that, even though this is actually fairly straightforward, and we discussed this before, the context string is actually important, and it does need to be specific to the application, so that each application gets its own session keys, even if multiple applications happen to sample the same SK. The next question is, what do we do if the source key actually isn't uniform? Well, now we got a problem. If the source key is not a uniform key for the pseudo random function then we can no longer assume that the output of the pseudo random function is indistinguishable from random. In fact, if we just use the KDF that we just described then the output might not look random to the adversary and then he might be able to anticipate some of the session keys that we'll be using and thereby break the session. So then we have a problem. Now why would this source key not be uniform? Well there are many reasons why this happened. For example if you use a key exchange protocol, it so happens typically that key exchange protocols will generate a high entropy key. But the high entropy key is gonna be distributed in some subspace of the key space. So it's not going to be a uniform string. It will be uniform in some subset of a larger set, And we'll see examples of that as soon as we talk about key exchange protocols. And so KDFs have to kind of accommodate for the fact that key exchange protocols actually don't generate uniform bit strings. The other problem is, that, in fact, the hardware random number generator you're using might actually produce biased outputs. We don't wanna rely on the non bias of the hardware random number generator. And so all we want to assume is that it generates a high entropy string, but one that might be biased. In which case, we have to somehow clean this bias. And so this introduces this, this paradigm for building KDFs. This is called the extract-then-expand paradigm, where the first step of the KDF is to extract a pseudo random key from the actual source key. So in a picture you can think about it like this. In some sense these are the different possible values of the source key. This is the horizontal line and the vertical axis is basically the probability of each one of these values, and you can see that this is a kind of a bumpy function which would say that the source key is not uniformly distributed in the key space. What we do in this case is we use what's called an extractor. So an extractor is something that takes a bumpy distribution and makes it into a uniform distribution over the key space. In our case we're actually just gonna be using what are called computational extractors, namely extractors that don't necessarily produce uniform distribution at the end but they generated distribution that's indistinguishable from uniform. Now extractors typically take as input something called a salt, and a salt just like in a salad, it kind of adds flavor to things, what it does is basically kind of jumbles things around, so that no matter what the input distribution is, the output distribution is still going to be indistinguishable from random. So a salt basically, what is it? It's a non-secret string, so it's publicly known. It doesn't matter if the adversary knows what the salt is, and it's fixed forever. The only point is that when you chose it, you chose one at random. And then the hope is that the funny distribution that you're trying to extract from kinda doesn't inherently depends on the salt that you chose and hence as a result using your salt, you will actually get a distribution that looks indistinguishable from random. So essentially the salt, you know, you can just bang it the keyboard a couple of times when you generate it but it just needs to be something that's random initially but then it's fixed forever, and it's fine if the adversary knows what it is and nevertheless the extractor is able to extract the entropy and output a uniformly random string K. In some sense the salt is only there to defend against adversarially bad distributions that might mess up our extractor. Okay, so now that we have extracted a pseudo random key. Now, we might as well just use it in a KDF that we just saw using a secure pseudo random function to expand the key into as many bits as we need to actually secure the session. Okay, so there are these two steps. The first one is we extract a pseudo-random key, and then once we have a pseudo-random key we already know how to extend it into as many keys as we need using a pseudo-random function. So the standardized way of doing this is called HKDF. This is a KDF, a key derivation function that's built from HMAC. And here HMAC is used both as the PRF for expanding and an extractor for extracting the initial pseudo-random key. So let me explain how this works. So in the extract step, we're gonna use our salt which you remember is a public value just happened to be generated at random at the beginning of time. And we use this salt as the HMAC key. And then the source key we're gonna use as the HMAC data. So we're kind of using a public value as a key. And nevertheless, one can argue that HMAC has extraction properties, such that, when we apply HMAC, the resulting key is going to look indistinguishable from random, assuming that the source key actually has enough entropy to it. And now that we have the pseudo random key we're simply going to use HMAC as a PRF to generate a session key of you know as many bits as we need for the session keys. Okay. So that basically concludes our discussion of HKDF. And I just want you to remember that, once you obtain a source key, either from hardware or from a key exchange protocol, the way you convert it into session keys is not by using that sample directly. You would never use a source key directly as a session key in a protocol. What you would do is you will run the source key through a KDF. And the KDF would give you all the keys and output that you need, for, the randomness, for the random keys to be used in your protocol. And a typical KDF to use is HKDF, which is actually getting quite a bit of traction out there. Okay. The last topic I wanna talk about in this segment is, how do you extract keys from passwords. These are called password based KDFs or PBKDFs. The problem here is that passwords have relatively low entropy. In fact, we're gonna talk about passwords later on in the course when we talk about user authentication. And so, I'm not gonna say too much here. I'll just say passwords generally have very little entropy estimated on the order of twenty bits of entropy, say. And as a result, there is simply not enough entropy to generate session keys out of a password. And yet we still need to do it very frequently. We still need to derive encryption keys and MACs and so on out of passwords, so the question is how to do it. The first thing is, you know, for this kind of purpose, don't use HKDF. That's not what it's designed for. What will happen is that the derived keys will actually be vulnerable to something called a dictionary attack, which we're gonna talk about much later in the course when we talk about user authentication. So, the way PBKDFs defend against this low entropy problem that results in a dictionary attack is by two means. First of all, as before they use a salt, a public, random value that's fixed forever. But in addition, they also use what's called a slow hash function. And let me describe kind of the standard approach to deriving keys from passwords. This is called PKCS#5, and in particular, the version I'll describe is what's called PBKDF1. And I should say that this mechanism is implemented in most crypto libraries so you shouldn't have to implement this yourself. All you would do, you know, you would call a function, you know, derived key from password. You would give the password in as input, and you would get a key as output. But you should be aware of course that this key is not going to have high entropy so in fact it will be guessable. What these PBKDFs try to do is make the guessing problem as hard as possible. Okay. So the way they work, first of all, is, as we said, they basically hash, the concatenation of the password and the salt. And then the hash itself is designed to be a very slow hash function. And the way we build a slow hash function is by taking one particular hash function, say, SHA-256, and we iterate it many, many times, C times. So you can imagine 1000 times, perhaps even a million times. And what do I mean by iterating it? So, well, we take the password and the salt. And we put them inside of one input to the hash function. And then we apply the hash function, oops, let me write it like this. And then we apply the hash function and we get an output, and then we apply the hash function again and we get another output. And we do this again and again and again maybe a thousand times or a million times depending on how fast your processors are and then finally we get the final output that we actually output as, as the key output of this key derivation function. Now what is the point here? Iterating a function 10,000 times or even a million times is going to take very little time on a modern CPU, and as a result, it doesn't really affect the user's experience. The user types in his password, it gets hashed a million times and then it gets output. And maybe that could even take, you know a tenth of a second and the user wouldn't even notice it. However the attacker, all he can do is he can try all the passwords in the dictionary, because we know people tend to pick passwords in dictionaries, and so he could just try them one by one, remember the SALT is public, so he knows what the SALT is. And so he can just try this hash one by one. However because the hash function is slow, each attempt is gonna take him a tenth of second. So if he needs to run through a dictionary, you know, with, with a 200 billion passwords in it, because the hash function is slow, this is gonna take quite awhile. And by doing that, we slow down the dictionary attack, and we make it harder for the attacker to get our session keys. Not impossible, just harder. That's all this is trying to do. Okay, so this is basically what I wanted to say about password based KDFs. As I said, this is not something you would build yourself. All crypto libraries have an implementation of a PKCS#5 mechanism. And you would just call the appropriate function to convert a password into a key, and then use the resulting key. Okay, in the next segment, we're gonna see how to use symmetric encryption in a way that allows us to search on the cipher texts.
