0:56

The answer is the standard extension of that, and if you think back to the Merkle-Damgard construction, you realize

that if I tell you the tag of a particular message, in other words I tell you the

value at this point. It's very easy for the attacker to just add another block and

then compute one more application of the compression function H. And now they'll be

able to get the tag for the original message concatenated the padding block,

concatenated the word W that they added themselves and as a result this is an

existential forgery. Yes, so basically this is exactly what we get here. Where

after concatenating the padding block, the attacker can actually concatenate whatever

he wants and he would get the tag on this combined message. So this is totally

insecure and I cannot tell you how many products have actually made this mistake

where they assumed that this is a secure Mac. This is completely insecure and

should never ever, ever, ever be used. Instead there's a standardized method to

convert a collision resistant hash function to a MAC and that method is

called HMAC. So in particular we could use the SHA-256 hash function to build

this MAC. The output is going to be 256 bits and in fact HMAC is believed to be a

pseudo-random function, so in fact out of SHA-256 we get a pseudo-random

function that outputs 256 bit outputs. So let me show the construction. Here's the

construction in symbols and it works as follows. First we take our key k and we

concatenate what's we call an internal pad to it, an ipad to it. This makes it into

one block of the Merkle-Damguard construction, so for example this would be

512 bits in the case of SHA256. We prepend this to the message M and then we hash.

Now this by itself we just said is completely insecure, however what HMAC

does in addition, it takes the output, which is 256 bits, it prepends to that the

key again XOR with, what's called the outer pad, the opad. This also becomes

512 bits. It's one block. And then it hashes the combination of these two to

finally obtain the resulting tag on the message M. So it's more rather looking

into some symbols. It's more instructive to look at HMAC in pictures. And so you

can see that here are the two keys k XOR inner-pad, which is then fed into the

Merkle-Damgard chain. And then the resulting output of this chain is fed into

another Merkle-Damgard chain and finally the final output is produced. Okay, so

this is how HMAC works in pictures and now I want to argue that we've already

seen something very similar to this. In particular, if you can think of the

compression function H as a PRF where the key is the first, the top inputs, then

what we're actually doing here is we're evaluating this PRF H at a fixed IV and

the result here is a random value which we're gonna call K1. And then we apply the

Merkle-Damgard chain and we can do the same thing on the outer pad. If you think

of little h as a PRF where the key is the upper inputs. Again, we're applying this

PRF using a different key to a fixed value IV and as a result, we're gonna get

another random value K2 So now when we compute HMAC using these keys, K1 and K2,

this would actually look very familiar this is basically NMAC. It's identical to

NMac that we discussed in a previous segment. And notice to argue that this is

an NMac construction we have to assume that the compression function, little h,

is a PRF where the key is actually the lower inputs to the function. Now let me

say that these pads, the ipad and the opad , these are fixed constants that are

specified in the HMAC standard. So these are literally just 512 bit constants that

never change. And so when we go back to look at the complete HMAC construction,

you realize that the main difference between this and NMAC is that these keys

here since they are dependent, you notice they're both just the same key XORed

with different constants. Essentially, the keys K1 and K2 are also somewhat dependent

because they're computed by applying a PRF to the same fixed value, namely IV, but

with dependent keys. And so to argue that K1 and K2 are pseudo random and

independent of one another, one has to argue that the compression function not

only is a PRF where when the inputs, the top input, is the key inputs, but it's

also a PRF when dependent keys are used. But under those assumptions, basically the

exact same analysis NMAC would apply to HMAC and we would get security argument

that HMAC is a secure MAC. So as I said, HMAC can be proven secure under these PRF

assumptions about the compression function H. The security bounds are just as they

are for NMAC, in other words you should not have to change the key as long as the

number of messages you're MAC-ing Is smaller than the size of the output tag to

the one-half, but for HMAC SHA256 the output space is 2 to the 256. The square

root of that would put us at 2 to the 128. Which means that basically you can

use HMAC SHA256 for as many outputs as you want, and you'll always maintain security.

And as a last point about HMAC I'll tell you that TLS Standard actually requires

that one support HMAC SHA-196 which means that HMAC built form the SHA1 function and

truncated to 96 bits. SHA-1 remember outputs 160 bits. And we truncated to the

most significant 96 bits. Now you might be wondering, remember we said before that

SHA-1 is no longer considered a secure hash function, so how come we're using

SHA-1 in HMac? Well, it turns out it's actually fine. Because HMAC the analysis

of HMAC doesn't need SHA-1 to be collision resistant. All it needs is that

the compression function of SHA-1 one be a PRF when either input is allowed

to be the key. And as far as we know that's still correct for the underlying

compression function for SHA-1. Even though it might not be collision

resistant. As far as we know it's still fine to use it inside of HMAC. So this is

the end of our discussion of HMAC and in our next segment we're going to look at

timing attacks on HMAC.