Cryptography is an indispensable tool for protecting information in computer systems. In this course you will learn the inner workings of cryptographic systems and how to correctly use them in real-world applications. The course begins with a detailed discussion of how two parties who have a shared secret key can communicate securely when a powerful adversary eavesdrops and tampers with traffic. We will examine many deployed protocols and analyze mistakes in existing systems. The second half of the course discusses public-key techniques that let two parties generate a shared secret key. Throughout the course participants will be exposed to many exciting open problems in the field and work on fun (optional) programming projects. In a second course (Crypto II) we will cover more advanced cryptographic tasks such as zero-knowledge, privacy mechanisms, and other forms of encryption.
MAC Padding
Loading...
From the course by Stanford University
Cryptography I
2130 ratings
From the lesson
Message Integrity
Week 3. This week's topic is data integrity. We will discuss a number of classic constructions for MAC systems that are used to ensure data integrity. For now we only discuss how to prevent modification of non-secret data. Next week we will come back to encryption and show how to provide both confidentiality and integrity. This week's programming project shows how to authenticate large video files. Even if you don't do the project, please read the project description --- it teaches an important concept called a hash chain.
Meet the Instructors
Dan BonehProfessor
Computer Science
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.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
