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.
