[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:04.05,Default,,0000,0000,0000,,Now that we know what MACs are, let's go\Nahead and build our first secure MACs.
Dialogue: 0,0:00:04.05,0:00:08.47,Default,,0000,0000,0000,,First I want to remind you that a MAC is a\Npair of algorithms. The first is a signing
Dialogue: 0,0:00:08.47,0:00:12.92,Default,,0000,0000,0000,,algorithm that's given a message and a key\Nwill generate a corresponding tag And the
Dialogue: 0,0:00:12.92,0:00:17.10,Default,,0000,0000,0000,,second is verification algorithms are\Ngiven a key message and a tag while
Dialogue: 0,0:00:17.10,0:00:21.74,Default,,0000,0000,0000,,outputs zero or one depending on whether\Nthe tag is valid or not. And we said that
Dialogue: 0,0:00:21.74,0:00:26.31,Default,,0000,0000,0000,,a MAC is secure if it is existentially\Nunforgeable under a chosen message attack.
Dialogue: 0,0:00:26.31,0:00:30.89,Default,,0000,0000,0000,,In other words, the attackers allow to\Nmount a chosen message attack where he can
Dialogue: 0,0:00:30.89,0:00:35.30,Default,,0000,0000,0000,,submit arbitrary messages of his choice\Nand obtain the corresponding tags for
Dialogue: 0,0:00:35.30,0:00:39.52,Default,,0000,0000,0000,,those messages, and then despite the\Nability to generate arbitrary tags The
Dialogue: 0,0:00:39.52,0:00:43.62,Default,,0000,0000,0000,,attacker cannot create a new message-tag pair that was not given to him
Dialogue: 0,0:00:43.62,0:00:47.98,Default,,0000,0000,0000,,during the chosen message attack. Okay so\Nwe've already seen this definition in the
Dialogue: 0,0:00:47.98,0:00:52.18,Default,,0000,0000,0000,,last segment and now the question is how\Ndo we build secure MACs? So the first
Dialogue: 0,0:00:52.18,0:00:57.22,Default,,0000,0000,0000,,example I want to give you is basically\Nshowing that any secure PRF directly gives
Dialogue: 0,0:00:57.22,0:01:01.95,Default,,0000,0000,0000,,us a secure MAC as well. So let's see how\Nwe do it. So suppose we have a pseudo
Dialogue: 0,0:01:01.95,0:01:06.81,Default,,0000,0000,0000,,random function so the pseudo random\Nfunction takes and inputs X and outputs in
Dialogue: 0,0:01:06.81,0:01:12.17,Default,,0000,0000,0000,,Y. And let's define the following MAC. So\Nthe way we sign a message 'M' is basically
Dialogue: 0,0:01:12.17,0:01:17.18,Default,,0000,0000,0000,,by simply evaluating the function at the\Npoint 'M' So the tag for the message M is
Dialogue: 0,0:01:17.18,0:01:21.35,Default,,0000,0000,0000,,simply the value of the function at the\Npoint M and then the way we verify a
Dialogue: 0,0:01:21.35,0:01:26.01,Default,,0000,0000,0000,,message to that pair is by recomputing the\Nvalue of the function at the message M and
Dialogue: 0,0:01:26.01,0:01:30.28,Default,,0000,0000,0000,,checking whether that is equal to the tag\Ngiven to us. We say yes if so and we
Dialogue: 0,0:01:30.28,0:01:34.68,Default,,0000,0000,0000,,reject otherwise. So here you have in\Npictures basically that when Alice wants
Dialogue: 0,0:01:34.68,0:01:39.02,Default,,0000,0000,0000,,to send a message to Bob she computes a\Ntag by the value of PRF and then she
Dialogue: 0,0:01:39.02,0:01:43.25,Default,,0000,0000,0000,,appends this tag to the message, Bob\Nreceives the corresponding tab pair, he
Dialogue: 0,0:01:43.25,0:01:47.82,Default,,0000,0000,0000,,recomputes the value of the function and\Ntests whether the given tag is actually
Dialogue: 0,0:01:47.82,0:01:52.73,Default,,0000,0000,0000,,equal to the value of the function at the\Npoint M. So let's look at a bad example of
Dialogue: 0,0:01:52.73,0:01:57.83,Default,,0000,0000,0000,,this instruction. And so suppose that we\Nhave a pseudo-random function that happens
Dialogue: 0,0:01:57.83,0:02:02.87,Default,,0000,0000,0000,,to output only ten bits. Okay, so this is\Na fine pseudo-random function and it just
Dialogue: 0,0:02:02.87,0:02:07.67,Default,,0000,0000,0000,,so happens that for any message 'M' it\Nonly outputs ten bits value. My question
Dialogue: 0,0:02:07.67,0:02:12.46,Default,,0000,0000,0000,,to you is if we use this function 'F' to\Nconstruct a MAC, is that going to be a
Dialogue: 0,0:02:12.46,0:02:17.18,Default,,0000,0000,0000,,secure MAC? So the answer is no, this MAC\Nis insecure. In particular because the
Dialogue: 0,0:02:17.18,0:02:21.47,Default,,0000,0000,0000,,tags are too short. So consider the\Nfollowing simple adversary. What the
Dialogue: 0,0:02:21.47,0:02:26.12,Default,,0000,0000,0000,,adversary will do is simply choose an\Narbitrary message M and just guess the
Dialogue: 0,0:02:26.12,0:02:30.77,Default,,0000,0000,0000,,value of the MAC for that particular\Nmessage. Now, because the tag is only ten
Dialogue: 0,0:02:30.77,0:02:35.18,Default,,0000,0000,0000,,bits long, the adversary has a chance of\None in two to the ten in guessing the MAC
Dialogue: 0,0:02:35.18,0:02:40.00,Default,,0000,0000,0000,,correctly. In other words, the advantage\Nof the guessing adversary, one distinctly
Dialogue: 0,0:02:40.00,0:02:44.35,Default,,0000,0000,0000,,guesses a random tag for a given message.\NThat adversary is going to have an
Dialogue: 0,0:02:44.35,0:02:48.90,Default,,0000,0000,0000,,advantage against the mac that's basically\None over two to the ten which is one over
Dialogue: 0,0:02:48.90,0:02:52.96,Default,,0000,0000,0000,,a thousand twenty four and that's\Ndefinitely non negligible. So the adversary
Dialogue: 0,0:02:52.96,0:02:57.35,Default,,0000,0000,0000,,basically will successfully forge the mac\Non a given message with probability one
Dialogue: 0,0:02:57.35,0:03:01.84,Default,,0000,0000,0000,,on a thousand which is insecure. However\Nit turns out this is the only example that
Dialogue: 0,0:03:01.84,0:03:06.28,Default,,0000,0000,0000,,where things can go wrong, only when the\Noutput of the function is small can things
Dialogue: 0,0:03:06.28,0:03:10.54,Default,,0000,0000,0000,,go wrong. If the output of the PRF is\Nlarge Then we get a secure MAC out of this
Dialogue: 0,0:03:10.54,0:03:14.34,Default,,0000,0000,0000,,function. And let's state the security\Ntheorem here. So suppose we have a
Dialogue: 0,0:03:14.34,0:03:18.26,Default,,0000,0000,0000,,function 'F' that takes messages in 'X'\Nand outputs tags in 'Y', then the MAC
Dialogue: 0,0:03:18.26,0:03:22.59,Default,,0000,0000,0000,,that's derived from this PRF in fact is a\Nsecure MAC. In particular, if you look at
Dialogue: 0,0:03:22.59,0:03:26.80,Default,,0000,0000,0000,,the security theorem here, you'll see very\Nclearly the era bounds, in other words
Dialogue: 0,0:03:26.80,0:03:31.18,Default,,0000,0000,0000,,since the PRF is secure we know that this\Nquantity here is negligible. And so if we
Dialogue: 0,0:03:31.18,0:03:35.40,Default,,0000,0000,0000,,want this quantity to be negligible, this\Nis what we want, we want to say that no
Dialogue: 0,0:03:35.40,0:03:39.66,Default,,0000,0000,0000,,adversary can defeat the MAC 'I sub F',\Nthat implies that we want this quantity to
Dialogue: 0,0:03:39.66,0:03:43.72,Default,,0000,0000,0000,,be negligible, in other words we want the\Noutput space to be large. And so for
Dialogue: 0,0:03:43.72,0:03:48.10,Default,,0000,0000,0000,,example, taking a PRF that outputs eighty\Nbits is perfectly fine. That will generate
Dialogue: 0,0:03:48.10,0:03:52.10,Default,,0000,0000,0000,,an eighty bit MAC and therefore the\Nadvantage of any adversary will be at most
Dialogue: 0,0:03:52.10,0:03:56.52,Default,,0000,0000,0000,,one over two to the eighty. So now the proof\Nof this theorem is really simple, so lets
Dialogue: 0,0:03:56.52,0:04:00.91,Default,,0000,0000,0000,,just go ahead and do it. So in fact lets\Nstart by saying that suppose instead of a
Dialogue: 0,0:04:00.91,0:04:05.45,Default,,0000,0000,0000,,PRF we have a truly random function from\Nthe message space to the tag space so this
Dialogue: 0,0:04:05.45,0:04:10.09,Default,,0000,0000,0000,,is just a random function from X to Y\Nthat's chosen at random from the set of
Dialogue: 0,0:04:10.09,0:04:14.97,Default,,0000,0000,0000,,all such functions. Now lets see if that\Nfunction can give us a secure mac. So what
Dialogue: 0,0:04:14.97,0:04:19.55,Default,,0000,0000,0000,,the adversary says is, 'I want a tag on\Nthe message M1'. What he gets back is the
Dialogue: 0,0:04:19.55,0:04:24.16,Default,,0000,0000,0000,,tag which just happens to be the function\Nevaluated at the point M1. Notice there is
Dialogue: 0,0:04:24.16,0:04:28.49,Default,,0000,0000,0000,,no key here because F is just a truly\Nrandom function from X to Y. And then the
Dialogue: 0,0:04:28.49,0:04:33.10,Default,,0000,0000,0000,,adversary gets to choose a message from M2\Nand he obtains the tag from M2, he choose
Dialogue: 0,0:04:33.10,0:04:37.26,Default,,0000,0000,0000,,M3, M4 up to MQ and he obtains all the\Ncorresponding tags. Now his goal is to
Dialogue: 0,0:04:37.26,0:04:41.43,Default,,0000,0000,0000,,produce a message tag pair and we say that\Nhe wins, remember that this is an
Dialogue: 0,0:04:41.43,0:04:45.89,Default,,0000,0000,0000,,existential forgery, in other words first\Nof all T has to be equal to F of M This
Dialogue: 0,0:04:45.89,0:04:49.97,Default,,0000,0000,0000,,means that 'T' is a valid tag for the\Nmessage 'M'. And second of all, the
Dialogue: 0,0:04:49.97,0:04:54.68,Default,,0000,0000,0000,,message 'M' has to be new. So the message\N'M' had better not be one of M-one to M-Q.
Dialogue: 0,0:04:54.68,0:04:58.88,Default,,0000,0000,0000,,But let's just think about this for a\Nminute, what does this mean? So the
Dialogue: 0,0:04:58.88,0:05:03.83,Default,,0000,0000,0000,,adversary got to see the value of a truly\Nrandom function at the points M-one to M-Q
Dialogue: 0,0:05:03.83,0:05:08.80,Default,,0000,0000,0000,,and now he?s suppose to predict the value\Nof this function as some new point, M
Dialogue: 0,0:05:08.80,0:05:13.41,Default,,0000,0000,0000,,However, for a truly random function, the\Nvalue of the function at the point M is
Dialogue: 0,0:05:13.41,0:05:18.20,Default,,0000,0000,0000,,independent of its value at the points M-1\Nto M-Q. So the best the adversary can do
Dialogue: 0,0:05:18.20,0:05:22.75,Default,,0000,0000,0000,,at predicting the value of the function at\Nthe point M is just guess the value,
Dialogue: 0,0:05:22.75,0:05:27.30,Default,,0000,0000,0000,,because he has no information about F of\NM. And as a result his advantage if he
Dialogue: 0,0:05:27.30,0:05:31.62,Default,,0000,0000,0000,,guesses the value of the function at the\Npoint M he'll guess it right with
Dialogue: 0,0:05:31.62,0:05:36.29,Default,,0000,0000,0000,,probability exactly one over Y. And then\Nthe tag that he produced will be correct
Dialogue: 0,0:05:36.29,0:05:40.58,Default,,0000,0000,0000,,with probability exactly one over Y. Okay,\Nagain he had no information about the
Dialogue: 0,0:05:40.58,0:05:44.80,Default,,0000,0000,0000,,value of the function of M and so the best\Nhe could do is guess. And if he guesses,
Dialogue: 0,0:05:44.80,0:05:49.35,Default,,0000,0000,0000,,he'll get it right with probability one\Nover Y. And now of course, because the
Dialogue: 0,0:05:49.35,0:05:54.42,Default,,0000,0000,0000,,function capital F is a pseudo random\Nfunction The adversary is gonna behave the
Dialogue: 0,0:05:54.42,0:05:58.56,Default,,0000,0000,0000,,same whether we give him the truly random\Nfunction or the pseudo random function.
Dialogue: 0,0:05:58.56,0:06:02.66,Default,,0000,0000,0000,,The adversary can't tell the difference\Nand as a result even if we use a pseudo
Dialogue: 0,0:06:02.66,0:06:06.60,Default,,0000,0000,0000,,random function, the adversary is gonna\Nhave advantages at most one over Y in
Dialogue: 0,0:06:06.60,0:06:10.77,Default,,0000,0000,0000,,winning the game. Okay, so you can see\Nexactly the security theorem, let's go
Dialogue: 0,0:06:10.77,0:06:15.56,Default,,0000,0000,0000,,back there for just a second. Essentially\Nthis is basically why we got an error term
Dialogue: 0,0:06:15.56,0:06:20.00,Default,,0000,0000,0000,,of one over Y because of the guessing\Nattack and that's the only way that the
Dialogue: 0,0:06:20.00,0:06:24.73,Default,,0000,0000,0000,,attacker can win the game. So now that we\Nknow that any secure PRF is also a secure
Dialogue: 0,0:06:24.73,0:06:29.12,Default,,0000,0000,0000,,MAC, we already know that we have our\Nfirst example MAC. In particular, we know
Dialogue: 0,0:06:29.12,0:06:33.68,Default,,0000,0000,0000,,that AES, or at least we believe that AES\Nis a secure PRF, therefore, AES since it
Dialogue: 0,0:06:33.68,0:06:38.01,Default,,0000,0000,0000,,takes sixteen byte inputs, right the\Nmessage space for AES is 128 bits, which
Dialogue: 0,0:06:38.01,0:06:43.21,Default,,0000,0000,0000,,is sixteen bytes. Therefore the AES cipher\Nessentially gives us a MAC that can match
Dialogue: 0,0:06:43.21,0:06:48.14,Default,,0000,0000,0000,,messages that are exactly sixteen bytes.\NOkay, so that's our first example of a
Dialogue: 0,0:06:48.14,0:06:53.26,Default,,0000,0000,0000,,MAC. But now the question is if we have a\NPRF for small inputs like AES that only
Dialogue: 0,0:06:53.26,0:06:58.56,Default,,0000,0000,0000,,acts on sixteen bytes, can we build a MAC\Nfor big messages that can act on gigabytes
Dialogue: 0,0:06:58.56,0:07:02.07,Default,,0000,0000,0000,,of data? Sometimes I call this the\NMcDonald's problem. Basically given a
Dialogue: 0,0:07:02.07,0:07:05.87,Default,,0000,0000,0000,,small MAC and we build a big MAC out of\Nit. In other words, given a MAC for small
Dialogue: 0,0:07:05.87,0:07:10.23,Default,,0000,0000,0000,,messages and we build a MAC for large\Nmessages. So we're gonna look at two
Dialogue: 0,0:07:10.23,0:07:14.84,Default,,0000,0000,0000,,constructions for doing so. The first\Nexample is called a CBC MAC that again
Dialogue: 0,0:07:14.84,0:07:19.32,Default,,0000,0000,0000,,takes PRF for small messages as input\Nand produces a PRF for very large
Dialogue: 0,0:07:19.32,0:07:23.69,Default,,0000,0000,0000,,messages. As outputs. The second one we'll\Nsee is HMAC which does the same thing
Dialogue: 0,0:07:23.69,0:07:28.28,Default,,0000,0000,0000,,again takes a PRF for small inputs and\Ngenerates a PRF for very large inputs. Now
Dialogue: 0,0:07:28.28,0:07:32.05,Default,,0000,0000,0000,,the two are used in very different\Ncontexts. Cbc-mac is actually very
Dialogue: 0,0:07:32.05,0:07:36.32,Default,,0000,0000,0000,,commonly used in the banking industry. For\Nexample, there's a system called the
Dialogue: 0,0:07:36.32,0:07:40.80,Default,,0000,0000,0000,,Automatic Clearing House, ACH, which banks\Nuse to clear checks with one another and
Dialogue: 0,0:07:40.80,0:07:44.79,Default,,0000,0000,0000,,that system, CBC-MAC, is used to ensure\Nintegrity of the checks as they're
Dialogue: 0,0:07:44.79,0:07:49.11,Default,,0000,0000,0000,,transferred from bank to bank. On the\NInternet, protocols like SSL and IPsec and
Dialogue: 0,0:07:49.11,0:07:53.17,Default,,0000,0000,0000,,SSH, those all use HMAC for integrity. Two\Ndifferent MACs and were gonna discuss them
Dialogue: 0,0:07:53.17,0:07:57.09,Default,,0000,0000,0000,,in the next couple of segments. And as I\Nsaid were also gonna start from a PRF for
Dialogue: 0,0:07:57.09,0:08:01.27,Default,,0000,0000,0000,,small messages and produce PRF for\Nmessages that are gigabytes long and in
Dialogue: 0,0:08:01.27,0:08:06.04,Default,,0000,0000,0000,,particular they can both be substantiated\Nwith AES as the underlying cipher. So the
Dialogue: 0,0:08:06.04,0:08:10.60,Default,,0000,0000,0000,,last comment I want to make about these\NPRF based MACs is that in fact their
Dialogue: 0,0:08:10.60,0:08:15.27,Default,,0000,0000,0000,,output can be truncated. So suppose we\Nhave a PRF that outputs N bit outputs. So
Dialogue: 0,0:08:15.27,0:08:19.94,Default,,0000,0000,0000,,again for AES this would be a PRF that\Noutputs 128 bits as outputs. Its an easy
Dialogue: 0,0:08:19.94,0:08:24.91,Default,,0000,0000,0000,,lemma to show that in fact if you have an\NN bit PRF if you truncated, in other words
Dialogue: 0,0:08:24.91,0:08:31.06,Default,,0000,0000,0000,,if you only output first key bits The\Nresult is also a secure PRF and the
Dialogue: 0,0:08:31.06,0:08:36.53,Default,,0000,0000,0000,,intuition here is if the big PRF outputs N\Nbits of randomness for any inputs that you
Dialogue: 0,0:08:36.53,0:08:42.06,Default,,0000,0000,0000,,give to the PRF then certainly chopping it\Noff and truncating it to T bits is still
Dialogue: 0,0:08:42.06,0:08:46.57,Default,,0000,0000,0000,,gonna look random. The attacker now gets\Nless information so his job of
Dialogue: 0,0:08:46.57,0:08:51.66,Default,,0000,0000,0000,,distinguishing the outputs from random\Njust became harder. In other words, if the
Dialogue: 0,0:08:51.66,0:08:56.74,Default,,0000,0000,0000,,N bit PRF is secure, then the T less than\NN bit PRF, the truncated PRF, would also
Dialogue: 0,0:08:56.74,0:09:01.18,Default,,0000,0000,0000,,be secure. So this is an easy lemma and\Nsince any secure PRF also gives us a
Dialogue: 0,0:09:01.18,0:09:05.99,Default,,0000,0000,0000,,secure MAC, what this means is if you give\Nme a MAC that's based on a PRF and what I
Dialogue: 0,0:09:05.99,0:09:10.69,Default,,0000,0000,0000,,can do is I can truncate it to W bits,\Nhowever, because of the error term in the
Dialogue: 0,0:09:10.86,0:09:15.38,Default,,0000,0000,0000,,MAC based PRF theorem we know that\Ntruncating to W bits will only be secure
Dialogue: 0,0:09:15.38,0:09:19.95,Default,,0000,0000,0000,,as long as one over two to the W is\Nnegligible. So if you truncate the PRF to
Dialogue: 0,0:09:19.95,0:09:24.41,Default,,0000,0000,0000,,only three bits, the resulting MAC is not\Ngoing to be secure. However, if you
Dialogue: 0,0:09:24.41,0:09:29.22,Default,,0000,0000,0000,,truncate it to say 80 bits or maybe even\N64 bits, then the resulting MAC is still
Dialogue: 0,0:09:29.22,0:09:33.97,Default,,0000,0000,0000,,gonna be a secure MAC. Okay, so the thing\Nto remember here is that even though we
Dialogue: 0,0:09:33.97,0:09:39.24,Default,,0000,0000,0000,,use AES to construct larger PRFs and the\Noutput of these PRFs is gonna be 128 bits,
Dialogue: 0,0:09:39.24,0:09:44.12,Default,,0000,0000,0000,,it doesn't mean that the MAC itself has to\Nproduce 128 bit tags We can always
Dialogue: 0,0:09:44.12,0:09:48.55,Default,,0000,0000,0000,,truncate the outputs to 90 bits or 80\Nbits, and as a result, we would get still
Dialogue: 0,0:09:48.55,0:09:53.10,Default,,0000,0000,0000,,secure MACs but now the output tag is\Ngonna be more reasonable size and doesn't
Dialogue: 0,0:09:53.10,0:09:57.70,Default,,0000,0000,0000,,have to be the full 128 bits. Okay, so in\Nthe next segment we're gonna look at how
Dialogue: 0,0:09:57.70,0:09:58.73,Default,,0000,0000,0000,,the CBC-MAC works.