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.