[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:03.52,Default,,0000,0000,0000,,Well, we're almost done with our\Ndiscussion of symmetric encryption. There
Dialogue: 0,0:00:03.52,0:00:06.47,Default,,0000,0000,0000,,are just a couple of odds and ends that\NI'd like to discuss before we move on to
Dialogue: 0,0:00:06.47,0:00:10.43,Default,,0000,0000,0000,,the next topic. So the first thing I'd\Nlike to mention is how we derive many keys
Dialogue: 0,0:00:10.43,0:00:14.50,Default,,0000,0000,0000,,from one key. And it, actually, this comes\Nup all the time in practice, so I'd like
Dialogue: 0,0:00:14.50,0:00:18.29,Default,,0000,0000,0000,,to make sure you know how to do this\Ncorrectly. So what's the setting that
Dialogue: 0,0:00:18.29,0:00:22.78,Default,,0000,0000,0000,,we're looking at? Well, imagine we have a\Ncertain source key that's generated by one
Dialogue: 0,0:00:22.78,0:00:26.44,Default,,0000,0000,0000,,of, a number of methods. Imagine the\Nsource key is generated by a hardware
Dialogue: 0,0:00:26.44,0:00:30.09,Default,,0000,0000,0000,,random number generator or perhaps is\Ngenerated by a key exchange protocol
Dialogue: 0,0:00:30.09,0:00:34.04,Default,,0000,0000,0000,,which we're going to discuss later. But\Nanyhow, there are a number of ways in
Dialogue: 0,0:00:34.04,0:00:38.11,Default,,0000,0000,0000,,which a source key might be generated\Nbetween Alice and Bob, such that the
Dialogue: 0,0:00:38.11,0:00:42.57,Default,,0000,0000,0000,,attacker doesn't know what the source key\Nis. But now, as we said, in many cases, we
Dialogue: 0,0:00:42.57,0:00:46.86,Default,,0000,0000,0000,,actually need many keys to secure a\Nsession, not just one single source key.
Dialogue: 0,0:00:46.86,0:00:51.27,Default,,0000,0000,0000,,For example, if you remember, in TLS there\Nwere unidirectional keys and we
Dialogue: 0,0:00:51.27,0:00:55.28,Default,,0000,0000,0000,,needed keys in each direction. And in\Nfact, in each direction, we needed
Dialogue: 0,0:00:55.28,0:00:59.47,Default,,0000,0000,0000,,multiple keys. We needed a MAC key, we\Nneeded an encryption key. We need an IV,
Dialogue: 0,0:00:59.47,0:01:03.09,Default,,0000,0000,0000,,and so on. Similarly nonce based\Nencryption, you remember, there were
Dialogue: 0,0:01:03.09,0:01:07.59,Default,,0000,0000,0000,,multiple keys that were being used, and so\Non. And so, the question is, how do we use
Dialogue: 0,0:01:07.59,0:01:12.03,Default,,0000,0000,0000,,the one source key that we just derived,\Neither from a hardware process or
Dialogue: 0,0:01:12.03,0:01:16.35,Default,,0000,0000,0000,,by key exchange, and generate a bunch of\Nkeys from it that we could then use to
Dialogue: 0,0:01:16.35,0:01:20.53,Default,,0000,0000,0000,,secure our session. The way that's done,\Nis using a mechanism called a key
Dialogue: 0,0:01:20.53,0:01:24.95,Default,,0000,0000,0000,,derivation function, KDF. And I want to\Ntalk a little bit about how KDF's are
Dialogue: 0,0:01:24.95,0:01:29.85,Default,,0000,0000,0000,,constructed. So first of all, suppose we\Nhave a secure PRF, that happens to have
Dialogue: 0,0:01:29.85,0:01:34.99,Default,,0000,0000,0000,,key space K. And now, suppose that it so\Nhappens that our source key SK is uniform
Dialogue: 0,0:01:34.99,0:01:41.21,Default,,0000,0000,0000,,in the key K. In this case, the source key\Nis, in fact, a uniform random key for the
Dialogue: 0,0:01:41.21,0:01:46.45,Default,,0000,0000,0000,,secure PRF F. And we can use it directly to\Ngenerate keys, all the keys that we need
Dialogue: 0,0:01:46.45,0:01:50.44,Default,,0000,0000,0000,,to secure the session. So in this case,\Nthe KDF is really simple. The key
Dialogue: 0,0:01:50.44,0:01:53.77,Default,,0000,0000,0000,,derivation function would just work as\Nfollows. It would take as input the
Dialogue: 0,0:01:53.77,0:01:58.02,Default,,0000,0000,0000,,source key. It would take an input, a\Nparameter context, which I'm gonna
Dialogue: 0,0:01:58.02,0:02:02.77,Default,,0000,0000,0000,,describe in just a minute. And then it's\Ngonna take a length input as input as
Dialogue: 0,0:02:02.77,0:02:07.62,Default,,0000,0000,0000,,well. And then what it will do is it will\Nbasically evaluate the PRF on zero. Then
Dialogue: 0,0:02:07.62,0:02:12.40,Default,,0000,0000,0000,,it will evaluate the PRF on one. Then it\Nwill evaluate the PRF on two, up until L.
Dialogue: 0,0:02:12.40,0:02:16.45,Default,,0000,0000,0000,,And I will talk about what this context is\Nin just a second. And then, basically, you
Dialogue: 0,0:02:16.45,0:02:20.35,Default,,0000,0000,0000,,would use as many bits of the output as\Nyou would need to generate all the keys
Dialogue: 0,0:02:20.35,0:02:24.26,Default,,0000,0000,0000,,for the session. So, if you need unidirectional keys you would generate, you
Dialogue: 0,0:02:24.26,0:02:28.36,Default,,0000,0000,0000,,know, one key in each direction where each key\Nmight include an encryption key and a MAC
Dialogue: 0,0:02:28.36,0:02:32.36,Default,,0000,0000,0000,,key. And so, you would basically generate\Nas many bits as you need and then finally
Dialogue: 0,0:02:32.36,0:02:36.26,Default,,0000,0000,0000,,cut off the output at the time when you've\Ngenerated enough keys to secure your
Dialogue: 0,0:02:36.26,0:02:41.18,Default,,0000,0000,0000,,session. Okay so this is a fairly straight\Nforward mechanism it's basically using the
Dialogue: 0,0:02:41.18,0:02:45.66,Default,,0000,0000,0000,,secure PRF as a pseudo random generator.\NAnd the only question is what is its
Dialogue: 0,0:02:45.66,0:02:49.45,Default,,0000,0000,0000,,context string. Well, I'll tell you that\Nthe context string is basically a unique
Dialogue: 0,0:02:49.45,0:02:53.54,Default,,0000,0000,0000,,string that identifies the application. So\Nin fact you might have multiple
Dialogue: 0,0:02:53.54,0:02:58.30,Default,,0000,0000,0000,,applications on the same system that's\Ntrying to establish multiple secure keys.
Dialogue: 0,0:02:58.30,0:03:03.17,Default,,0000,0000,0000,,Maybe you have SSH running as one process,\Nyou have a web server running as another process,
Dialogue: 0,0:03:03.17,0:03:09.14,Default,,0000,0000,0000,,IPsec as a third process and all three need \Nto have secret keys generated. And this
Dialogue: 0,0:03:09.14,0:03:13.53,Default,,0000,0000,0000,,context variable basically tries to separate \Nthe three of them. So, let me ask you,
Dialogue: 0,0:03:13.53,0:03:16.59,Default,,0000,0000,0000,,more precisely, what do you think \Nthe purpose of this context variable is?
Dialogue: 0,0:03:19.20,0:03:22.31,Default,,0000,0000,0000,,So I guess I've given\Nit away and this context variable is
Dialogue: 0,0:03:22.31,0:03:26.17,Default,,0000,0000,0000,,supposed to basically separate\Napplications, so that even if, for
Dialogue: 0,0:03:26.17,0:03:30.86,Default,,0000,0000,0000,,example, the three services that we just\Ntalked about, SSH, web server, and IPsec,
Dialogue: 0,0:03:30.86,0:03:35.74,Default,,0000,0000,0000,,if they all happen to obtain the same\Nsource key from the hardware random number
Dialogue: 0,0:03:35.74,0:03:40.38,Default,,0000,0000,0000,,generator then the context since it's\Ndifferent for the three apps will make
Dialogue: 0,0:03:40.38,0:03:45.62,Default,,0000,0000,0000,,sure that they still get three independent\Nstrings that they can then use to secure
Dialogue: 0,0:03:45.62,0:03:49.87,Default,,0000,0000,0000,,the sessions. I just want you to remember\Nthat, even though this is actually fairly
Dialogue: 0,0:03:49.87,0:03:53.65,Default,,0000,0000,0000,,straightforward, and we discussed this\Nbefore, the context string is actually
Dialogue: 0,0:03:53.65,0:03:57.37,Default,,0000,0000,0000,,important, and it does need to be specific\Nto the application, so that each
Dialogue: 0,0:03:57.37,0:04:01.30,Default,,0000,0000,0000,,application gets its own session keys,\Neven if multiple applications happen to
Dialogue: 0,0:04:01.30,0:04:05.14,Default,,0000,0000,0000,,sample the same SK. The next\Nquestion is, what do we do if the source
Dialogue: 0,0:04:05.14,0:04:09.71,Default,,0000,0000,0000,,key actually isn't uniform? Well, now we\Ngot a problem. If the source key is not a
Dialogue: 0,0:04:09.71,0:04:14.11,Default,,0000,0000,0000,,uniform key for the pseudo random function\Nthen we can no longer assume that the
Dialogue: 0,0:04:14.11,0:04:18.51,Default,,0000,0000,0000,,output of the pseudo random function is\Nindistinguishable from random. In fact, if
Dialogue: 0,0:04:18.51,0:04:23.84,Default,,0000,0000,0000,,we just use the KDF that we just described\Nthen the output might not look random to
Dialogue: 0,0:04:23.84,0:04:27.42,Default,,0000,0000,0000,,the adversary and then he might be able to\Nanticipate some of the session keys that
Dialogue: 0,0:04:27.42,0:04:31.56,Default,,0000,0000,0000,,we'll be using and thereby break the\Nsession. So then we have a problem. Now
Dialogue: 0,0:04:31.56,0:04:35.51,Default,,0000,0000,0000,,why would this source key not be uniform?\NWell there are many reasons why this
Dialogue: 0,0:04:35.51,0:04:39.56,Default,,0000,0000,0000,,happened. For example if you use a key\Nexchange protocol, it so happens typically
Dialogue: 0,0:04:39.56,0:04:42.83,Default,,0000,0000,0000,,that key exchange protocols will generate a\Nhigh entropy key. But the
Dialogue: 0,0:04:42.83,0:04:46.77,Default,,0000,0000,0000,,high entropy key is gonna be\Ndistributed in some subspace of the key
Dialogue: 0,0:04:46.77,0:04:51.46,Default,,0000,0000,0000,,space. So it's not going to be a uniform\Nstring. It will be uniform in some
Dialogue: 0,0:04:51.46,0:04:55.76,Default,,0000,0000,0000,,subset of a larger set, And we'll see\Nexamples of that as soon as we talk about
Dialogue: 0,0:04:55.93,0:05:00.32,Default,,0000,0000,0000,,key exchange protocols. And so KDFs have\Nto kind of accommodate for the fact that
Dialogue: 0,0:05:00.32,0:05:04.49,Default,,0000,0000,0000,,key exchange protocols actually don't\Ngenerate uniform bit strings. The other
Dialogue: 0,0:05:04.49,0:05:08.83,Default,,0000,0000,0000,,problem is, that, in fact, the hardware\Nrandom number generator you're using might
Dialogue: 0,0:05:08.83,0:05:13.38,Default,,0000,0000,0000,,actually produce biased outputs. We don't\Nwanna rely on the non bias of the hardware
Dialogue: 0,0:05:13.38,0:05:17.25,Default,,0000,0000,0000,,random number generator. And so all we\Nwant to assume is that it generates a high
Dialogue: 0,0:05:17.25,0:05:21.84,Default,,0000,0000,0000,,entropy string, but one that might be\Nbiased. In which case, we have to somehow
Dialogue: 0,0:05:21.84,0:05:26.74,Default,,0000,0000,0000,,clean this bias. And so this introduces \Nthis, this paradigm for building KDFs.
Dialogue: 0,0:05:26.74,0:05:31.96,Default,,0000,0000,0000,,This is called the extract-then-expand \Nparadigm, where the first step
Dialogue: 0,0:05:31.96,0:05:37.25,Default,,0000,0000,0000,,of the KDF is to extract a pseudo random\Nkey from the actual source key. So in a
Dialogue: 0,0:05:37.25,0:05:40.83,Default,,0000,0000,0000,,picture you can think about it like this.\NIn some sense these are the different
Dialogue: 0,0:05:40.83,0:05:45.34,Default,,0000,0000,0000,,possible values of the source key. This is\Nthe horizontal line and the vertical axis
Dialogue: 0,0:05:45.34,0:05:49.54,Default,,0000,0000,0000,,is basically the probability of each one\Nof these values, and you can see that this
Dialogue: 0,0:05:49.54,0:05:53.46,Default,,0000,0000,0000,,is a kind of a bumpy function which would\Nsay that the source key is not uniformly
Dialogue: 0,0:05:53.46,0:05:58.56,Default,,0000,0000,0000,,distributed in the key space. What we do\Nin this case is we use what's called an
Dialogue: 0,0:05:58.56,0:06:02.91,Default,,0000,0000,0000,,extractor. So an extractor is something\Nthat takes a bumpy distribution and makes
Dialogue: 0,0:06:02.91,0:06:07.46,Default,,0000,0000,0000,,it into a uniform distribution over the\Nkey space. In our case we're actually just
Dialogue: 0,0:06:07.46,0:06:10.03,Default,,0000,0000,0000,,gonna be using what are called\Ncomputational extractors, namely
Dialogue: 0,0:06:10.03,0:06:14.89,Default,,0000,0000,0000,,extractors that don't necessarily produce\Nuniform distribution at the end but
Dialogue: 0,0:06:14.89,0:06:20.26,Default,,0000,0000,0000,,they generated distribution that's\Nindistinguishable from uniform.
Dialogue: 0,0:06:22.91,0:06:27.32,Default,,0000,0000,0000,,Now extractors typically take as input\Nsomething called a salt, and a salt just
Dialogue: 0,0:06:27.32,0:06:31.32,Default,,0000,0000,0000,,like in a salad, it kind of adds flavor to\Nthings, what it does is basically kind of
Dialogue: 0,0:06:31.32,0:06:36.02,Default,,0000,0000,0000,,jumbles things around, so that no matter\Nwhat the input distribution is, the output
Dialogue: 0,0:06:36.02,0:06:39.74,Default,,0000,0000,0000,,distribution is still going to be\Nindistinguishable from random. So a salt
Dialogue: 0,0:06:39.74,0:06:43.97,Default,,0000,0000,0000,,basically, what is it? It's a non-secret\Nstring, so it's publicly known. It doesn't
Dialogue: 0,0:06:43.97,0:06:48.56,Default,,0000,0000,0000,,matter if the adversary knows what the\Nsalt is, and it's fixed forever. The only
Dialogue: 0,0:06:48.56,0:06:53.10,Default,,0000,0000,0000,,point is that when you chose it, you chose\None at random. And then the hope is that
Dialogue: 0,0:06:53.10,0:06:57.17,Default,,0000,0000,0000,,the funny distribution that you're trying\Nto extract from kinda doesn't inherently
Dialogue: 0,0:06:57.17,0:07:00.27,Default,,0000,0000,0000,,depends on the salt that you chose and\Nhence as a result using your salt, you
Dialogue: 0,0:07:00.27,0:07:03.73,Default,,0000,0000,0000,,will actually get a distribution that\Nlooks indistinguishable from random. So
Dialogue: 0,0:07:03.73,0:07:07.02,Default,,0000,0000,0000,,essentially the salt, you know, you can\Njust bang it the keyboard a couple of
Dialogue: 0,0:07:07.02,0:07:10.22,Default,,0000,0000,0000,,times when you generate it but it just\Nneeds to be something that's random
Dialogue: 0,0:07:10.22,0:07:14.25,Default,,0000,0000,0000,,initially but then it's fixed forever, and\Nit's fine if the adversary knows what
Dialogue: 0,0:07:14.25,0:07:20.30,Default,,0000,0000,0000,,it is and nevertheless the extractor is\Nable to extract the entropy and output a
Dialogue: 0,0:07:20.30,0:07:24.71,Default,,0000,0000,0000,,uniformly random string K. In some sense the\Nsalt is only there to defend against
Dialogue: 0,0:07:24.71,0:07:29.67,Default,,0000,0000,0000,,adversarially bad distributions that might\Nmess up our extractor. Okay, so now that
Dialogue: 0,0:07:29.67,0:07:34.58,Default,,0000,0000,0000,,we have extracted a pseudo random key.\NNow, we might as well just use it in a KDF
Dialogue: 0,0:07:34.58,0:07:38.91,Default,,0000,0000,0000,,that we just saw using a secure\Npseudo random function to expand the key
Dialogue: 0,0:07:38.91,0:07:43.48,Default,,0000,0000,0000,,into as many bits as we need to actually\Nsecure the session. Okay, so there are
Dialogue: 0,0:07:43.48,0:07:47.43,Default,,0000,0000,0000,,these two steps. The first one is we\Nextract a pseudo-random key, and then once
Dialogue: 0,0:07:47.43,0:07:51.58,Default,,0000,0000,0000,,we have a pseudo-random key we already\Nknow how to extend it into as many keys as
Dialogue: 0,0:07:51.58,0:07:56.03,Default,,0000,0000,0000,,we need using a pseudo-random function. So\Nthe standardized way of doing this is
Dialogue: 0,0:07:56.03,0:08:01.17,Default,,0000,0000,0000,,called HKDF. This is a KDF, a key derivation function that's built from HMAC.
Dialogue: 0,0:08:01.17,0:08:06.56,Default,,0000,0000,0000,,And here HMAC is used both as the PRF for\Nexpanding and an extractor for extracting
Dialogue: 0,0:08:06.56,0:08:11.70,Default,,0000,0000,0000,,the initial pseudo-random key. So let me\Nexplain how this works. So in the extract
Dialogue: 0,0:08:11.70,0:08:16.90,Default,,0000,0000,0000,,step, we're gonna use our salt which you\Nremember is a public value just happened to
Dialogue: 0,0:08:16.90,0:08:21.10,Default,,0000,0000,0000,,be generated at random at the beginning of\Ntime. And we use this salt as the HMAC
Dialogue: 0,0:08:21.10,0:08:27.53,Default,,0000,0000,0000,,key. And then the source key we're gonna\Nuse as the HMAC data. So we're kind of
Dialogue: 0,0:08:27.53,0:08:32.29,Default,,0000,0000,0000,,using a public value as a key. And\Nnevertheless, one can argue that HMAC has
Dialogue: 0,0:08:32.29,0:08:37.62,Default,,0000,0000,0000,,extraction properties, such that, when we\Napply HMAC, the resulting key is going to
Dialogue: 0,0:08:37.62,0:08:42.45,Default,,0000,0000,0000,,look indistinguishable from random,\Nassuming that the source key actually has
Dialogue: 0,0:08:42.45,0:08:47.33,Default,,0000,0000,0000,,enough entropy to it. And now that we have\Nthe pseudo random key we're simply going
Dialogue: 0,0:08:47.33,0:08:52.04,Default,,0000,0000,0000,,to use HMAC as a PRF to generate a\Nsession key of you know as many bits as we
Dialogue: 0,0:08:52.04,0:08:56.39,Default,,0000,0000,0000,,need for the session keys. Okay. So that\Nbasically concludes our discussion of
Dialogue: 0,0:08:56.39,0:09:00.76,Default,,0000,0000,0000,,HKDF. And I just want you to remember\Nthat, once you obtain a source key, either
Dialogue: 0,0:09:00.76,0:09:04.91,Default,,0000,0000,0000,,from hardware or from a key exchange\Nprotocol, the way you convert it into
Dialogue: 0,0:09:04.91,0:09:09.57,Default,,0000,0000,0000,,session keys is not by using that sample\Ndirectly. You would never use a source key
Dialogue: 0,0:09:09.57,0:09:14.11,Default,,0000,0000,0000,,directly as a session key in a protocol.\NWhat you would do is you will run the
Dialogue: 0,0:09:14.11,0:09:18.37,Default,,0000,0000,0000,,source key through a KDF. And the KDF\Nwould give you all the keys and output
Dialogue: 0,0:09:18.37,0:09:22.58,Default,,0000,0000,0000,,that you need, for, the randomness, for\Nthe random keys to be used in your
Dialogue: 0,0:09:22.58,0:09:27.04,Default,,0000,0000,0000,,protocol. And a typical KDF to use is\NHKDF, which is actually getting quite a
Dialogue: 0,0:09:27.04,0:09:31.95,Default,,0000,0000,0000,,bit of traction out there. Okay. The last\Ntopic I wanna talk about in this segment
Dialogue: 0,0:09:31.95,0:09:36.43,Default,,0000,0000,0000,,is, how do you extract keys from\Npasswords. These are called password based
Dialogue: 0,0:09:36.43,0:09:41.92,Default,,0000,0000,0000,,KDFs or PBKDFs. The problem here is\Nthat passwords have relatively low
Dialogue: 0,0:09:41.92,0:09:45.76,Default,,0000,0000,0000,,entropy. In fact, we're gonna talk about\Npasswords later on in the course when we
Dialogue: 0,0:09:45.76,0:09:50.15,Default,,0000,0000,0000,,talk about user authentication. And so,\NI'm not gonna say too much here. I'll just
Dialogue: 0,0:09:50.15,0:09:54.29,Default,,0000,0000,0000,,say passwords generally have very little\Nentropy estimated on the order of twenty
Dialogue: 0,0:09:54.29,0:09:59.01,Default,,0000,0000,0000,,bits of entropy, say. And as a result,\Nthere is simply not enough entropy to
Dialogue: 0,0:09:59.01,0:10:02.88,Default,,0000,0000,0000,,generate session keys out of a password.\NAnd yet we still need to do it very
Dialogue: 0,0:10:02.88,0:10:06.80,Default,,0000,0000,0000,,frequently. We still need to derive\Nencryption keys and MACs and so on out of
Dialogue: 0,0:10:06.80,0:10:10.83,Default,,0000,0000,0000,,passwords, so the question is how to do\Nit. The first thing is, you know, for this
Dialogue: 0,0:10:10.83,0:10:14.74,Default,,0000,0000,0000,,kind of purpose, don't use HKDF. That's\Nnot what it's designed for. What will
Dialogue: 0,0:10:14.74,0:10:18.66,Default,,0000,0000,0000,,happen is that the derived keys will\Nactually be vulnerable to something called
Dialogue: 0,0:10:18.66,0:10:22.10,Default,,0000,0000,0000,,a dictionary attack, which we're gonna\Ntalk about much later in the course when
Dialogue: 0,0:10:22.10,0:10:27.79,Default,,0000,0000,0000,,we talk about user authentication. So, the\Nway PBKDFs defend against this low entropy
Dialogue: 0,0:10:27.79,0:10:33.00,Default,,0000,0000,0000,,problem that results in a dictionary\Nattack is by two means. First of all, as
Dialogue: 0,0:10:33.00,0:10:38.88,Default,,0000,0000,0000,,before they use a salt, a public,\Nrandom value that's fixed forever. But in
Dialogue: 0,0:10:38.88,0:10:43.10,Default,,0000,0000,0000,,addition, they also use what's called a\Nslow hash function. And let me describe
Dialogue: 0,0:10:43.10,0:10:49.36,Default,,0000,0000,0000,,kind of the standard approach to deriving\Nkeys from passwords. This is called PKCS#5,
Dialogue: 0,0:10:49.36,0:10:53.91,Default,,0000,0000,0000,,and in particular, the version I'll describe \Nis what's called PBKDF1. And I
Dialogue: 0,0:10:53.91,0:10:57.40,Default,,0000,0000,0000,,should say that this mechanism is\Nimplemented in most crypto libraries so
Dialogue: 0,0:10:57.40,0:11:00.66,Default,,0000,0000,0000,,you shouldn't have to implement this\Nyourself. All you would do, you know, you
Dialogue: 0,0:11:00.66,0:11:03.79,Default,,0000,0000,0000,,would call a function, you know, derived\Nkey from password. You would give the
Dialogue: 0,0:11:03.79,0:11:08.35,Default,,0000,0000,0000,,password in as input, and you would get a\Nkey as output. But you should be aware of
Dialogue: 0,0:11:08.35,0:11:11.74,Default,,0000,0000,0000,,course that this key is not going to have\Nhigh entropy so in fact it will be
Dialogue: 0,0:11:11.74,0:11:17.16,Default,,0000,0000,0000,,guessable. What these PBKDFs try to do is\Nmake the guessing problem as hard as
Dialogue: 0,0:11:17.16,0:11:20.96,Default,,0000,0000,0000,,possible. Okay. So the way they work,\Nfirst of all, is, as we said, they
Dialogue: 0,0:11:20.96,0:11:25.69,Default,,0000,0000,0000,,basically hash, the concatenation of the\Npassword and the salt. And then the hash
Dialogue: 0,0:11:25.69,0:11:29.17,Default,,0000,0000,0000,,itself is designed to be a very slow hash\Nfunction. And the way we build a slow hash
Dialogue: 0,0:11:29.17,0:11:34.06,Default,,0000,0000,0000,,function is by taking one particular hash\Nfunction, say, SHA-256, and we
Dialogue: 0,0:11:34.06,0:11:39.42,Default,,0000,0000,0000,,iterate it many, many times, C times. So\Nyou can imagine 1000 times, perhaps even a
Dialogue: 0,0:11:39.42,0:11:43.36,Default,,0000,0000,0000,,million times. And what do I mean by\Niterating it? So, well, we take the
Dialogue: 0,0:11:43.36,0:11:48.49,Default,,0000,0000,0000,,password and the salt. And we put them\Ninside of one input to the hash function.
Dialogue: 0,0:11:48.49,0:11:54.02,Default,,0000,0000,0000,,And then we apply the hash function, oops,\Nlet me write it like this. And then we
Dialogue: 0,0:11:54.02,0:11:57.78,Default,,0000,0000,0000,,apply the hash function and we get an\Noutput, and then we apply the hash
Dialogue: 0,0:11:57.78,0:12:00.78,Default,,0000,0000,0000,,function again and we get another output.\NAnd we do this again and again and again
Dialogue: 0,0:12:00.78,0:12:05.83,Default,,0000,0000,0000,,maybe a thousand times or a million times\Ndepending on how fast your processors are
Dialogue: 0,0:12:05.83,0:12:10.71,Default,,0000,0000,0000,,and then finally we get the final output\Nthat we actually output as, as the key
Dialogue: 0,0:12:10.71,0:12:15.06,Default,,0000,0000,0000,,output of this key derivation function.\NNow what is the point here? Iterating a
Dialogue: 0,0:12:15.06,0:12:19.37,Default,,0000,0000,0000,,function 10,000 times or even a million\Ntimes is going to take very little time on
Dialogue: 0,0:12:19.37,0:12:22.92,Default,,0000,0000,0000,,a modern CPU, and as a result, it doesn't\Nreally affect the user's experience. The
Dialogue: 0,0:12:22.92,0:12:27.79,Default,,0000,0000,0000,,user types in his password, it gets hashed\Na million times and then it gets output.
Dialogue: 0,0:12:27.79,0:12:31.65,Default,,0000,0000,0000,,And maybe that could even take, you know a\Ntenth of a second and the user wouldn't
Dialogue: 0,0:12:31.65,0:12:35.49,Default,,0000,0000,0000,,even notice it. However the attacker, all\Nhe can do is he can try all the passwords
Dialogue: 0,0:12:35.49,0:12:39.69,Default,,0000,0000,0000,,in the dictionary, because we know people\Ntend to pick passwords in dictionaries,
Dialogue: 0,0:12:39.69,0:12:43.78,Default,,0000,0000,0000,,and so he could just try them one by one,\Nremember the SALT is public, so he knows
Dialogue: 0,0:12:43.78,0:12:49.23,Default,,0000,0000,0000,,what the SALT is. And so he can just try this\Nhash one by one. However because the hash
Dialogue: 0,0:12:49.23,0:12:53.80,Default,,0000,0000,0000,,function is slow, each attempt is gonna\Ntake him a tenth of second. So if he needs
Dialogue: 0,0:12:53.80,0:12:57.96,Default,,0000,0000,0000,,to run through a dictionary, you know, with,\Nwith a 200 billion passwords in it,
Dialogue: 0,0:12:57.96,0:13:02.42,Default,,0000,0000,0000,,because the hash function is slow, this is\Ngonna take quite awhile. And by doing
Dialogue: 0,0:13:02.42,0:13:06.58,Default,,0000,0000,0000,,that, we slow down the dictionary attack,\Nand we make it harder for the attacker to
Dialogue: 0,0:13:06.58,0:13:11.61,Default,,0000,0000,0000,,get our session keys. Not impossible, just\Nharder. That's all this is trying to do.
Dialogue: 0,0:13:11.61,0:13:15.75,Default,,0000,0000,0000,,Okay, so this is basically what I wanted\Nto say about password based KDFs. As I
Dialogue: 0,0:13:15.75,0:13:19.84,Default,,0000,0000,0000,,said, this is not something you would\Nbuild yourself. All crypto libraries have
Dialogue: 0,0:13:19.84,0:13:23.98,Default,,0000,0000,0000,,an implementation of a PKCS#5\Nmechanism. And you would just call the
Dialogue: 0,0:13:23.98,0:13:28.28,Default,,0000,0000,0000,,appropriate function to convert a password\Ninto a key, and then use the resulting
Dialogue: 0,0:13:28.28,0:13:32.36,Default,,0000,0000,0000,,key. Okay, in the next segment, we're\Ngonna see how to use symmetric encryption
Dialogue: 0,0:13:32.36,0:13:35.23,Default,,0000,0000,0000,,in a way that allows us to search on the\Ncipher texts.