blocks swapping attack. So the function P actually, is a very easy to compute

function. Essentially given the key and the message block, all it is, is just a

multiplication in some finite fields. So it's a very, very simple function to

compute. It adds very little to the running time of PMAC. And yet, it's

enough in ensure that the PMAC is actually secure. As we've said, the key

for PMAC is this pair of keys. One key for the PRF, and one key for this masking

function P. And finally, I'll tell you that if the message length is not a

multiple of the block length. That is, imagine the last block is shorter than

full block length, then PMAC actually uses a padding that's similar to CMAC, so that

there is no need for an additional dummy block, ever. So that's the PMAC

construction and as usual, we can state its security theorem. So the security

theorem, by now, you should be used to it. Essentially, it says that if you give me

an adversary attacking PMAC, I can construct an adversary attacking the

underlying PRF. Plus an additional error term. And so, since again, the PRF is

secure, we know that this term is negligible. And so if we want this term to

be negligible, we know that, we need this error term to also be negligible. Here, as

usual, q is the number of messages that are MAC-ed using a particular key. And L

is the maximum length of all those messages. And PMAC is secure, as long as

its product is less than the square root of the block size. So for A, yes, this would be

two to the 128, and the square root, therefore, would be two to the 64th. So the

MAC would be secure, as long as Q times L is less than two to the 64th. And every time,

as it gets closer to that value, of course, you would have to change the key

in order to continue MAC-ing more messages. So the main thing to remember is

that PMAC also gives us a PRF, and when it processes the message blocks independently

of one another. Turns out that PMAC also has a very interesting property. Namely,

that PMAC math is incremental. So let me explain to you what that means. So suppose

the function F that's used to construct PMAC is not just a PRF, but, in fact, a

permutation, PRP. So we can actually invert it when we need to. Now suppose

we've already computed the MAC for a particularly long message m. And now,

suppose just one message block of this long message changes. So here, m[1] has

changed into m'[1]. But the remaining message blocks all remain the

same. For other MAC-s, like CBC-MAC, even though only one message block changed, you

would have to recompute the tag on the entire message. Recomputing the tag

basically will take time that's proportional to the length of the message.

It turns out, with PMAC, if we only change one block, or a small number of

blocks, actually, we can recompute the value of the tag for the new message very,

very quickly. And let me ask you a puzzle to see if you can figure out how to do

that yourself. And remember, the function F is a PRP, and therefore is invertible.

So let's see if you can figure out how to compute the MAC in the new message by

yourself. So it turns out this can be done. And you can quickly recompute the

tag on the new message using this third line here. Just to make sure we all see

the solution let's quickly go back to the original diagram for PMAC and I can show

you what I mean. So imagine this one message block changed into some other

block, say, it changed into M'[1]. Then what we could do is we can take the tag on

the original message before the change was made. So we can invert the function F, and

determine the value before the function F was applied. Now, well, since we now have

an XOR of a bunch of blocks, what we can do is we can cancel out the XOR

that came from the original message block, basically by XOR-ing this value that came

from the original message block into this XOR-ed accumulator. And then XOR-ing again

the value that would come from the new message block back into the XOR

accumulator. And then apply the function F again. And that will give us the tag for

the new message, where just one block was changed. So in symbols, basically, I wrote

the formula over here. You can see, basically, we decrypt the tag, and then we

XOR with the block that comes from the original message block. We XOR again with

the block that comes from the new message block. And then we re-encrypt the final

XOR accumulator to get the new tag for the message with a one block changed. So

that's kind of a neat property. It kind of shows that if you have very large

messages, you can very quickly update the tag. Of course you would need the secret

key to do the update, but you can quickly update the tag if just a small number of

message blocks changed. Okay, so that concludes our discussion of PMAC. And now

I wanna switch topics a little bit, and talk about the concept of a one time MAC,

which is basically the analog of the one time pad, but in the world of integrity.

So let me explain what I mean by that. So imagine we wanna build a MAC that is only

used for integrity of a single message. In other words, every time we compute the

integrity of a particular message, we also change the key. So that any particular key

is used only for integrity of one message. Then we can define the security game as

basically saying, the attacker's gonna see one message. Therefore, we only allow him

to do one chosen message attack. So he gets to submit one message query, and he

is given the tag corresponding to that one message query. And now his goal is to

forge a message tag pair. Okay, so you can see his goal was to produce one

message tag pair that verifies correctly and is different from the pair that he was

actually given. As we'll see, just like the one time pad and stream ciphers were

quite useful, it turns out one time MAC-s are also quite useful for the same

applications when we only wanna use a key to encrypt or to provide integrity for

just a single message. So as usual we would say that a one time act is secure,

because basically no adversary can win this game. Now the interesting thing is

that one time MAC-s, just like the one time pad can be secure against infinitely

powerful adversaries. And not only that, because they're only designed to be secure

for one time use, they can actually be faster than MAC-s that are based on PRFs.

And so I just wanted to give you a quick example of one one time MAC, this is a

classic construction for a one time MAC, let me show you how it works. The first

step is to pick a prime that's slightly larger than our block size. In this case

we're going to use 128-bit blocks, so let's pick the first prime that's bigger

than two to the 128th. This happens to be two to the 128th plus 51. And now the key

is going to be a pair of random numbers in the range 1 to our prime, so 1 to q. So we

choose two random integers in the range 1 to q. Now we're given a message so we're

going to take our message and break it into blocks where each block is 128 bits,

and we're going to regard each number as an integer in the range 0 to 2 to the

128th minus 1. Now the MAC is defined as follows. The first thing we do is we take

our message blocks and we kind of construct the polynomial out of them. So

if there are L blocks in our message, we're going to construct the polynomial of

degree L and you notice that the constant term of the polynomial is set to zero. And

then we define the MAC very simply. Basically what we do is we take the

polynomial that corresponds to the message, we evaluate it at the point K

that's one half of our secret key, and then we add the value A which is the

second half of our secret key. And that's it. That's the whole MAC. So just

basically construct the polynomial that corresponds to our message, evaluate that

polynomial at half of the secret key, and add the other half of the secret key to

the result, and of course reduce final result modulo q. Okay so that's it, so

the whole MAC, it's a one time secure MAC and we will argue that this MAC is one

time secure, essentially by arguing that if I tell you the value of MAC for one

particular message, that tells you nothing at all about the value of the MAC at

another message. And as a result, even though you've seen the value of the MAC on

a particular message, you have no way of forging this MAC on some other message.

Now I should emphasize that this is a one time MAC, but it's not two time secure. In

other words, if you get to see the value of the MAC on two different messages, that

actually completely compromises the secret key. And you can actually predict a MAC

for a third or fourth message of your choice. So then the MAC becomes forgeable.

But for one time use, it is a perfectly secure MAC, and I'll tell you that in fact

it's a very fast MAC to evaluate. So now that we've constructed one time MAC-s,

turns out there's actually a general technique that will convert one time MAC-s

into many time MAC-s. And I just wanted to briefly show you how that works. So

suppose we have our one time MAC, let's call it S and V for signing and

verification algorithms, and let's just assume that the tags themselves are n bit

strings. In addition, let's also look at a PRF, a secure PRF, that also happens to

output n bit strings but also takes as inputs n bit strings. So let's now define

a general construction for a MAC. These MAC-s are called Carter-Wegman MAC-s that

works as follows. Basically what we would do is we would apply the one time MAC to

the message M and then we're going to encrypt the results using the PRF. So how do

we encrypt the result? Well, we choose a random r and then we compute kind of a

one time path from this r by applying the PRF to it. And then we XOR the result

with the actual one time MAC. So the neat thing about this construction is that the

fast one time MAC is applied to the long message, which could be gigabytes long.

And the slower PRF is only applied to this nonce r, which is then used to

encrypt the final results of the MAC. And you can argue that if the MAC that was

given to us as a building block is a one time secure MAC, and the PRF is secure,

then, in fact, we get a many time secure MAC that happens to output 2n bit tags.

So we're gonna see Carter-Wegman MAC-s later on when we talk about authenticated

encryption. And, in fact, one of the NIST standard methods for doing encryption with

integrity, uses a Carter-Wegman MAC for providing integrity. I want to mention

that this Carter-Wegman MAC is a good example of a randomized MAC where this nonce

r is chosen afresh every time the tag is computed. And so for example if you try to

compute a tag for the same message twice each time you'll choose a different r and

as a result you'll get different tags both times. And so this is a nice example of a

MAC that's actually not a pseudo random function, not a PRF, because a single

message could actually be mapped to many different tags all of which are valid for

that one message. To conclude our discussion on the Carter-Wegman MAC, let me

ask you the following question. Here we have the equation for the Carter-Wegman

MAC. As usual, you see the nonce r as part of the MAC. And the second part of

the MAC I'm gonna denote by t. This is basically the one time MAC applied to the

message M, and then encrypted using the pseudo-random function applied to the

nonce r. So we'll denote the result of this XOR by t. So my question to

you is, given the Carter-Wegman MAC pair r,t for particular message m, how

would you verify that this MAC is valid? And recall that its algorithm V here, is

the verification algorithm for the underlying one time MAC. So this is the

right answer, and to see why, just observe that this XOR here decrypts the quantity t

to its plain text value, which is basically the original underlying one time

MAC. And so we can directly feed that into the verification algorithm for the one

time MAC. The last type of MAC I wanted to tell you about is one that is very

popular in internet protocols. It's called the HMAC. But before we talk about the HMAC we

have to talk about hash functions and in particular, collision resistant hash

functions and we are going to do that in the next module. So this is the end of our

first module on MAC-s and I wanted to point out that there's beautiful theory that

went into constructing all the MAC-s that we saw. I gave you the highlights showed

you the main constructions, but there's really quite a bit of theory that

goes into constructing these MAC-s, and if you'd like to learn more about that, I

listed a couple of key papers you might want to look at. Let me quickly tell you what they

are. The first one is, what's called the three key construction, which is the basis

of CMAC. A very elegant paper that give a very efficient construction out of CBC-MAC.

The second paper is a more technical paper, but basically shows how to prove

that bounds of CBC-MAC as a PRF. The third paper talks about PMAC and its

construction. Again, a very acute paper. The fourth paper talks about security of

NMAC and HMAC as well. HMAC we're going to cover in, the next module. The last paper

I listed asks an intriguing question. Recall that all of our constructions, we

always assume that AES is a pseudo-random function for sixteen byte messages and we

then built a pseudo-random function and therefore a MAC for much longer messages.

This paper says well, what do we do if AES is not a pseudo-random function, but still

satisfies some weaker security property called an unpredictable function. And then

they ask if AES is only an unpredictable function, but not a pseudo-random

function, can we still build MAC-s for long messages? And so they succeed in actually

giving constructions just based on the weaker assumption that AES is an

unpredictable function. But their constructions are far less sufficient than

CBC-MAC or NMAC, or PMAC that we discussed in these segments. And so if you're

interested in a different perspective on how to build MAC-s from block ciphers like

AES, please take a look at this paper. And there are actually some nice open

questions to work on in this area. So this concludes our first segment on integrity.

And in the next segment, we're gonna talk about collision resistance.