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.

Â