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.