-
In the last segment we talked about the
CBC-MAC and the NMAC, but throughout
-
the segment we always assumed that the
message length was a multiple of the block
-
size. In this segment, we're going to see
what to do when the message length is not
-
a multiple of the block size. So recall
that the encrypted CBC mac or ECBC-MAC for
-
short uses pseudorandom permutation F to
actually compute the CBC function as we
-
discussed in the last segment. But in the
last segment, we always assumed that the
-
message itself could be broken into an
integer number of blocks for the block
-
cipher. And the question is what to do
when the message length is not a multiple
-
of the block size. So here we have a
message where the last block actually is
-
shorter than the full block and the
question is how to compute the ECBC-MAC in
-
that case. So the solution of course is to
pad the message and the first pad that
-
comes to mind is to simply pad the message
with all zeros. In other words we take the
-
last block and just add zeros to it until
the last block becomes as long as one full
-
block size. And so my question to you is
whether the resulting MAC is secure. So
-
the answer is no, the MAC is not secure.
And let me explain why, basically the
-
problem is that it's possible now to come
up with messages so that message m and the
-
message m concatenated zero happen to have
exactly the same Pad. And as a result once
-
we plug in both m and m||0 into ECBC we'll
get the same tag out, which means that
-
both m and m||0 have the
same tag and therefore the attacker can
-
mount an existential forgery. He would ask
for the tag on the message m. And then he
-
would output as its forgery the tag and the
message m||0. And it's
-
easy to say why that's the case. Basically, to be absolutely clear here, we have our
-
message m. Which after padding becomes m000. So we had to add three
-
0's to it. And here we have the message m
zero, an m that ends with zero. And after
-
padding, we basically now have to add two
0's to it. And lo and behold, they become
-
the same pad, so that they're gonna have
exactly the same tag which allows the
-
adversary to mount the existential forgery
attack. So this is not a good idea. In
-
fact appending all 0s is a terrible idea.
And if you think about concrete case where
-
this comes up imagine the automatic
clearing house system used for clearing
-
checks. I might have a check for a $100
and the tag on that check. Well, now, the
-
attacker basically could append a zero to
my check and make it a check for $1000,
-
and that wouldn't actually change the tag.
So this ability to extend the message
-
without changing the tag actually could
have pretty disastrous consequences. So I
-
hope this example convinces you that the
padding function itself must be a one to
-
one function. In other words, it should be
the case that two distinct messages always
-
map to two distinct padded messages. We
shouldn't actually have a collision on the
-
padding function. Another way of saying it
is that the padding function must be
-
invertible. That guarantees that the
padding function is one to one. So a
-
standard way to do this was proposed by
the International Standards Organization
-
ISO. What they suggested is basically,
let's append the string 100000 to the end
-
of the message to make the message be a
multiple of the block length. Now to see
-
that this padding is invertible, all we do
is describe the inversion algorithm
-
which simply is gonna scan the message
from right to left, until it hits the
-
first one and then it's gonna remove all
the bits to the right of this one,
-
including the one. And you see that once
we've removed the pattern this way, we
-
obtain the original message. So here's an
example, so here we have a message where
-
the last block happens to be shorter than
the block length, and then we
-
append the 1,0,0 string to it.
It's very easy to see what the pad is,
-
simply look for the first one from the
right, we can remove this pad and recover
-
the original message back. Now there's one
corner case that's actually quite
-
important, and that is what do we do if
the original message length is already the
-
multiple of a block size? In that case
it's really very, very important that we
-
add an extra dummy block. That contains
the pad 1000. And again, I can't tell you
-
how many products and standards have
actually made this mistake where they
-
didn't add a dummy block and as a result,
the MAC is insecure because there's an
-
easy existential forgery attack. And let
me show you why. So suppose in case the
-
message is a multiple of a block length,
suppose we didn't add a dummy block and we
-
literally MAC-ed this message here. Well,
the result now is that if you look at
-
the message which is a multiple of the
block size and a message which is not a
-
multiple of the block size but is padded
to the block size, and imagine it so
-
happens that this message m prime one
happens to end with 1-0-0. At this point,
-
you realize that here, the original
message. Here, let me draw it this way.
-
You realize that the original message
after padding. Would become identical to
-
the second message that was not padded at
all. And as a result, if I ask for the tag
-
on this message over here, I would obtain
also the tag on the second message that
-
happened to end in 1-0-0. Okay, so if we
didn't add the dummy block, basically,
-
again, the pad would be not invertible,
because two different messages, two
-
distinct messages, happen to map to the
same padded result. Again, as a result,
-
the MAC becomes insecure. So to summarize,
this ISO standard is a perfectly fine way
-
to pad, except you have to remember also
to add a dummy block in case message is a
-
multiple of the block length to begin
with. Now some of you might be wondering
-
if there is a padding scheme that never
needs to add a dummy block, and the answer
-
is that if you look at a deterministic
padding function, then it's pretty easy to
-
argue that there will always be cases
where we need to pad, and the reason is
-
just literally the number of messages that
are multiples of the block length is much
-
smaller than the total number of messages
that need not be a multiple of the block
-
length. And as a result we can't have a
one to one function from this bigger
-
set of all messages to the smaller set of
messages which are a multiple of
-
the block length. There will always be cases
where we have to extend the original
-
message and in this case that would
correspond to adding this dummy padding
-
block. However, there is a very clever
idea called CMAC which shows that using a
-
randomized padding function we can avoid
having to ever add a dummy block. And so
-
let me explain how CMAC works. So CMAC
actually uses three keys. And, in fact,
-
sometimes this is called a three key
construction. So this first key, K, is
-
used in the CBC, the standard CBC MAC
algorithm. And then the keys, K1 and K2,
-
are used just for the padding scheme at
the very, very last block. And in fact in
-
the CMAC standard, the keys K1, K2 are
derived from the key K by some sort of a
-
pseudo random generator. So the way CMAC
works is as follows. Well, if the message
-
happens to not be a multiple of a block
length, then we append the ISO padding to
-
it. But then we also XOR this last
block with a secret key, K1, that the
-
adversary doesn't know. However, if the
message is a multiple of the block length,
-
then of course, we don't append anything
to it. But we XOR it with a different
-
key, K2, that, again, the adversary
doesn't actually know. So it turns out,
-
just by doing that, it's now impossible to
apply the extension attacks that we could
-
do on the cascade function, and on
raw CBC. Because the poor
-
adversary actually doesn't know what is
the last block that went into the
-
function. He doesn't know K1, and therefore,
he doesn't know the value at this
-
particular point and as a result, he can't do
an extension attack. In fact, this is a
-
provable statement. And so that this
construction here is simply by XOR-ing
-
K1 or XOR-ing K2 is really a PRF.
Despite not having to do a final
-
encryption step after the raw CBC
function is computed. So, that's one
-
benefit, that there's no final encryption
step. And the second benefit is that we resolve
-
this ambiguity between whether padding did
happen or padding didn't happen by using
-
two different keys to distinguish the case
that the message is a multiple of the block
-
length versus the case where it's not but
we have a pad appended to the message. So
-
the two distinct keys resolve this
ambiguity between the two cases, and as a
-
result, this padding actually is
sufficiently secure. And as I said,
-
there's actually a nice security theorem
that goes with CMAC that shows that the
-
CMAC construction really is a pseudo-random
function, with the same security
-
properties as CBC-MAC. So I wanted to
mention that CMAC is a federal standard
-
standardized by NIST and if you now, these
days, wanted to use a CBC-MAC for
-
anything, you would actually be using CMAC
as the standard way to do it. But
-
particularly in CMAC, the underlying block
cypher is AES and that gives us a secure
-
CBC-MAC derived from AES. So that's the end
on the segment and in the next segment
-
we'll talk about a parallel MAC.
