0:00

Now that we know what MACs are, let's go ahead and build our first secure MACs.

Â First I want to remind you that a MAC is a pair of algorithms. The first is a signing

Â algorithm that's given a message and a key will generate a corresponding tag And the

Â second is verification algorithms are given a key message and a tag while

Â outputs zero or one depending on whether the tag is valid or not. And we said that

Â a MAC is secure if it is existentially unforgeable under a chosen message attack.

Â In other words, the attackers allow to mount a chosen message attack where he can

Â submit arbitrary messages of his choice and obtain the corresponding tags for

Â those messages, and then despite the ability to generate arbitrary tags The

Â attacker cannot create a new message-tag pair that was not given to him

Â during the chosen message attack. Okay so we've already seen this definition in the

Â last segment and now the question is how do we build secure MACs? So the first

Â example I want to give you is basically showing that any secure PRF directly gives

Â us a secure MAC as well. So let's see how we do it. So suppose we have a pseudo

Â random function so the pseudo random function takes and inputs X and outputs in

Â Y. And let's define the following MAC. So the way we sign a message 'M' is basically

Â by simply evaluating the function at the point 'M' So the tag for the message M is

Â simply the value of the function at the point M and then the way we verify a

Â message to that pair is by recomputing the value of the function at the message M and

Â checking whether that is equal to the tag given to us. We say yes if so and we

Â reject otherwise. So here you have in pictures basically that when Alice wants

Â to send a message to Bob she computes a tag by the value of PRF and then she

Â appends this tag to the message, Bob receives the corresponding tab pair, he

Â recomputes the value of the function and tests whether the given tag is actually

Â equal to the value of the function at the point M. So let's look at a bad example of

Â this instruction. And so suppose that we have a pseudo-random function that happens

Â to output only ten bits. Okay, so this is a fine pseudo-random function and it just

Â so happens that for any message 'M' it only outputs ten bits value. My question

Â to you is if we use this function 'F' to construct a MAC, is that going to be a

Â secure MAC? So the answer is no, this MAC is insecure. In particular because the

Â tags are too short. So consider the following simple adversary. What the

Â adversary will do is simply choose an arbitrary message M and just guess the

Â value of the MAC for that particular message. Now, because the tag is only ten

Â bits long, the adversary has a chance of one in two to the ten in guessing the MAC

Â correctly. In other words, the advantage of the guessing adversary, one distinctly

Â guesses a random tag for a given message. That adversary is going to have an

Â advantage against the mac that's basically one over two to the ten which is one over

Â a thousand twenty four and that's definitely non negligible. So the adversary

Â basically will successfully forge the mac on a given message with probability one

Â on a thousand which is insecure. However it turns out this is the only example that

Â where things can go wrong, only when the output of the function is small can things

Â go wrong. If the output of the PRF is large Then we get a secure MAC out of this

Â function. And let's state the security theorem here. So suppose we have a

Â function 'F' that takes messages in 'X' and outputs tags in 'Y', then the MAC

Â that's derived from this PRF in fact is a secure MAC. In particular, if you look at

Â the security theorem here, you'll see very clearly the era bounds, in other words

Â since the PRF is secure we know that this quantity here is negligible. And so if we

Â want this quantity to be negligible, this is what we want, we want to say that no

Â adversary can defeat the MAC 'I sub F', that implies that we want this quantity to

Â be negligible, in other words we want the output space to be large. And so for

Â example, taking a PRF that outputs eighty bits is perfectly fine. That will generate

Â an eighty bit MAC and therefore the advantage of any adversary will be at most

Â one over two to the eighty. So now the proof of this theorem is really simple, so lets

Â just go ahead and do it. So in fact lets start by saying that suppose instead of a

Â PRF we have a truly random function from the message space to the tag space so this

Â is just a random function from X to Y that's chosen at random from the set of

Â all such functions. Now lets see if that function can give us a secure mac. So what

Â the adversary says is, 'I want a tag on the message M1'. What he gets back is the

Â tag which just happens to be the function evaluated at the point M1. Notice there is

Â no key here because F is just a truly random function from X to Y. And then the

Â adversary gets to choose a message from M2 and he obtains the tag from M2, he choose

Â M3, M4 up to MQ and he obtains all the corresponding tags. Now his goal is to

Â produce a message tag pair and we say that he wins, remember that this is an

Â existential forgery, in other words first of all T has to be equal to F of M This

Â means that 'T' is a valid tag for the message 'M'. And second of all, the

Â message 'M' has to be new. So the message 'M' had better not be one of M-one to M-Q.

Â But let's just think about this for a minute, what does this mean? So the

Â adversary got to see the value of a truly random function at the points M-one to M-Q

Â and now he?s suppose to predict the value of this function as some new point, M

Â However, for a truly random function, the value of the function at the point M is

Â independent of its value at the points M-1 to M-Q. So the best the adversary can do

Â at predicting the value of the function at the point M is just guess the value,

Â because he has no information about F of M. And as a result his advantage if he

Â guesses the value of the function at the point M he'll guess it right with

Â probability exactly one over Y. And then the tag that he produced will be correct

Â with probability exactly one over Y. Okay, again he had no information about the

Â value of the function of M and so the best he could do is guess. And if he guesses,

Â he'll get it right with probability one over Y. And now of course, because the

Â function capital F is a pseudo random function The adversary is gonna behave the

Â same whether we give him the truly random function or the pseudo random function.

Â The adversary can't tell the difference and as a result even if we use a pseudo

Â random function, the adversary is gonna have advantages at most one over Y in

Â winning the game. Okay, so you can see exactly the security theorem, let's go

Â back there for just a second. Essentially this is basically why we got an error term

Â of one over Y because of the guessing attack and that's the only way that the

Â attacker can win the game. So now that we know that any secure PRF is also a secure

Â MAC, we already know that we have our first example MAC. In particular, we know

Â that AES, or at least we believe that AES is a secure PRF, therefore, AES since it

Â takes sixteen byte inputs, right the message space for AES is 128 bits, which

Â is sixteen bytes. Therefore the AES cipher essentially gives us a MAC that can match

Â messages that are exactly sixteen bytes. Okay, so that's our first example of a

Â MAC. But now the question is if we have a PRF for small inputs like AES that only

Â acts on sixteen bytes, can we build a MAC for big messages that can act on gigabytes

Â of data? Sometimes I call this the McDonald's problem. Basically given a

Â small MAC and we build a big MAC out of it. In other words, given a MAC for small

Â messages and we build a MAC for large messages. So we're gonna look at two

Â constructions for doing so. The first example is called a CBC MAC that again

Â takes PRF for small messages as input and produces a PRF for very large

Â messages. As outputs. The second one we'll see is HMAC which does the same thing

Â again takes a PRF for small inputs and generates a PRF for very large inputs. Now

Â the two are used in very different contexts. Cbc-mac is actually very

Â commonly used in the banking industry. For example, there's a system called the

Â Automatic Clearing House, ACH, which banks use to clear checks with one another and

Â that system, CBC-MAC, is used to ensure integrity of the checks as they're

Â transferred from bank to bank. On the Internet, protocols like SSL and IPsec and

Â SSH, those all use HMAC for integrity. Two different MACs and were gonna discuss them

Â in the next couple of segments. And as I said were also gonna start from a PRF for

Â small messages and produce PRF for messages that are gigabytes long and in

Â particular they can both be substantiated with AES as the underlying cipher. So the

Â last comment I want to make about these PRF based MACs is that in fact their

Â output can be truncated. So suppose we have a PRF that outputs N bit outputs. So

Â again for AES this would be a PRF that outputs 128 bits as outputs. Its an easy

Â lemma to show that in fact if you have an N bit PRF if you truncated, in other words

Â if you only output first key bits The result is also a secure PRF and the

Â intuition here is if the big PRF outputs N bits of randomness for any inputs that you

Â give to the PRF then certainly chopping it off and truncating it to T bits is still

Â gonna look random. The attacker now gets less information so his job of

Â distinguishing the outputs from random just became harder. In other words, if the

Â N bit PRF is secure, then the T less than N bit PRF, the truncated PRF, would also

Â be secure. So this is an easy lemma and since any secure PRF also gives us a

Â secure MAC, what this means is if you give me a MAC that's based on a PRF and what I

Â can do is I can truncate it to W bits, however, because of the error term in the

Â MAC based PRF theorem we know that truncating to W bits will only be secure

Â as long as one over two to the W is negligible. So if you truncate the PRF to

Â only three bits, the resulting MAC is not going to be secure. However, if you

Â truncate it to say 80 bits or maybe even 64 bits, then the resulting MAC is still

Â gonna be a secure MAC. Okay, so the thing to remember here is that even though we

Â use AES to construct larger PRFs and the output of these PRFs is gonna be 128 bits,

Â it doesn't mean that the MAC itself has to produce 128 bit tags We can always

Â truncate the outputs to 90 bits or 80 bits, and as a result, we would get still

Â secure MACs but now the output tag is gonna be more reasonable size and doesn't

Â have to be the full 128 bits. Okay, so in the next segment we're gonna look at how

Â the CBC-MAC works.

Â