This course will introduce you to the foundations of modern cryptography, with an eye toward practical applications.

Loading...

From the course by University of Maryland, College Park

Cryptography

371 ratings

This course will introduce you to the foundations of modern cryptography, with an eye toward practical applications.

From the lesson

Week 4

Message Authentication Codes

- Jonathan KatzProfessor, University of Maryland, and Director, Maryland Cybersecurity Center

Maryland Cybersecurity Center

Returning to the sending of message authentication codes.

Remember from a few lectures back that we showed how to

construct a secure message authentication code for short fixed length messages.

Based on any sort of random function, aka block cypher.

And what we wanted to do was to extend this to give us

secure message authentication code for arbitrary length messages.

We've already seen one such construction, cbc MAC.

Here we'll explore another construction based on hash-functions.

The intuition is actually rather simple.

Let's assume we have two parties who have between them

a secure channel that can handle short messages.

And I've depicted that here via a cylinder which is very narrow.

To indicate that the parties have between them a way to reliably send messages, but

that can only handle very short messages.

Let's assume the center now has a larger message that it

wants to communicate reliably to the other party.

How can they do this?

Well in fact, the idea is rather simple.

What the sender can do is to take its message M and

hash it down to a shorter fixed length digest here called h.

The sender can then transmit the short digest h

to the receiver using the secure channel between them.

And then, transmit the longer message M over an insecure channel.

At the other end, the receiver will simply check.

Whether the hash of the longer message end that it

received is equal to the digest h that it received over the secure channel.

And this will give reliable transmission of the longer message M,

bootstrapping from the security of the secure channel.

That allows the parties to communicate the shorter message h.

And the reason this is secure is very simple.

By assumption the, the channel for h is reliable, it's secure.

So the adversary can't tamper with that.

So that means that the receiver will indeed receive digest h

that the sender sends.

Well, the adversary can then try to tamper with the longer message, M.

But the attacker will not be able to convince the verifier,

the receiver to accept a different message, M prime.

Unless the attacker can find another message M prime that also hashes to

the same value h.

But if the hash function the parties are using is collision resistant,

then an attacker will not be able to do this.

We can use this idea to bootstrap a method authentication code for short messages.

Into a message authentication code for arbitrary length messages.

Well, what the parties will do is simply instantiate this secured channel for

short messages.

Using some message authentication code that can handle short messages.

So now we're in

a setting where the parties don't have any secure channel between them.

But instead they share some key k in advance.

And once again the sender has some longer message M

that it wants to transmit reliably to the receiver.

Well, what the sender can do here,

is again, hash the message to obtain a digest h.

And then compute a message authentication code on the digest h

using the shared key k.

And again this is going to be done using some message authentication code that can

handle short fixed-length messages.

Like the one we've shown already a couple of lectures back.

The sender can then transmit h along with its tag t.

And then in addition, send the message m itself.

And the point is again that we can view this transmission of h

along with it's tag, t.

As a way of sending h over what's effectively a reliable secure channel.

So, at the other end, just to go through the steps,

the receiver will compute h of M and recover the digest h.

And then verify whether the tag t on the receive message h

indeed verifies under this short, fixed length message authentication code.

And if so, the receiver will accept the longer message M

as being the intended message of the other party.

Now in fact, you can notice pretty quickly, that there's no need for

the sender to actually transmit h, itself.

And it's suffices for

the sender to simply transmit the longer message M along with the tag t.

Where, again, the tag t is being computed, still over the shorter digest h.

What we can prove about this construction is that if

the underlying message authentication code is secure for fixed-length messages.

I.e, messages whose length is equal to the output length of the hash function.

And if the hash function h is itself collision-resistant,

then the previous construction, the combination of the two.

Gives a secure method authentication code for arbitrary length messages.

The intuition is very similar to what we've already said.

However, I wanted to go through a very simple proof sketch just to

give a high level idea of how a formal proof would go.

So let's assume that the sender authenticates messages in one and two etc.

Where, as usual in the experiment defining security for

message authentication codes, the attacker is free to choose these messages.

And can even choose them adaptively, based on previous tags that it's received.

And let's define by way of notation h of i as the hash of the ith message.

Now at some point in time let's assume the attacker outputs a forgery M,t.

For this to be a forgery, of course,

it has to be the case that M is not equal to Mi for any value i.

That is, M cannot be equal to any previously authenticated method.

Well there are two cases.

The first case is when the hash of M, the hash of the message on which the attacker

outputs its for, forgery, is equal to the hash of Mi for some i.

That is, the hash of M is equal to the hash of some previously

authenticated message.

Well in that case, the attacker certainly can output a forgery by simply

replaying the tag ti that was computed on Mi.

But the point is that this would mean the attacker has found a collision in H.

And that's simply because we know that M is not equal to Mi.

So if H of M is equal to H of Mi that exactly give a collision.

And if H is collision resistant then this is something that the attacker should not

be able to do.

This is infeasible for any efficient attacker.

On the other hand,

the second case is where H of M is not equal to h i for all i.

That is, the hash of M is distinct from the hashes of

all previously authenticated messages.

Well in this case, that means that the,

that the attacker, if its forgery is valid.

Then the attacker must have been able to find a valid tag

t on a previously unauthenticated message h.

With respect to the underlying fixed length message authentication code.

So under the assumption that the underlying message authentication code

is secure for authenticating short messages.

This too is in-feasible, and so this rules out any sort of way that

the adversary might try for concocting a forgery.

If we look at the hash and mac scheme that we presented a few slides back,

how may we instantiate that in practice?

Well, we've already shown a simple construction of

a message authentication code for fixed length messages based on any block cipher.

And if you remember, in that construction.

The message length that we were able to handle was exactly equal to

the block length of the underlying block cipher being used.

Or I suppose, technically, we could handle messages of at most that length by

suitably padding the messages before applying the block cipher.

So we could then try to take that block cipher baked based MAC for

fixed length messages and couple that with some cryptographic hash function.

If you try to do that you'll notice that there's a block length mismatch.

So for example, if we try instantiating the block cipher based MAC using AES.

Then that means that we can authenticate messages whose length is,

at most, 128 bits.

Because 128 bits is the block length of AES.

However, cryptographic hash functions like SHA-1 have

output lengths of 160 bits or more.

So we have a mismatch between the two, and we can't directly couple them

together to give an instantiation of the hash and MAC instruction.

One could imagine designing hash functions and

blog ciphers that would pair well together.

But even if we did that.

There will still be a drawback of instantiating the hash and

MAC approach in that way.

And that would be that

we need to implement two different cryptographic primitives.

We would have to implement both a hash function as well as a block cipher.

In general, this is not really a significant problem but

in certain applications for example if you're implementing crypto on hardware.

You might prefer not to have to implement two different cryptographic primitives

just to obtain a message authentication code.

To address these issues researchers have designed what's called HMAC.

Which can be viewed as a particular instantiation of the hash and

MAC approach.

That can be constructed entirely from a certain type of hash function.

Importantly MD5, SHA-1, and SHA-2 are all different sorts of hash functions.

That satisfy the requirements of HMAC.

And so HMAC can be defined based on any of these hash functions.

We've already talked about how MD5 is no longer collision resistant and

should not be used.

nevertheless, as far as we know it remains secure when used to construct HMAC.

Still it's prudent to avoid using MD5 even in such a construction and

to migrate to HMAC SHA-1 or HMAC SHA-2 instead.

Unfortunately SHA-3 is not of the same type.

And cannot be directly plugged in to HMAC,

to give an instantiation of the hash-and-MAC approach.

And, for that reason different mechanisms for

achieving message authentication based on SHA-3 are currently being worked out.

The HMAC approach can be viewed,

as I said, as following the hash-and-MAC paradigm.

By using a part of the hash function, a certain component of the hash function.

We haven't had a reason to introduce up til now.

Being used essentially as a block cipher.

I didn't want to present any of the details because it presents a bit of

digression to show how exactly that's the case.

But at an intuitive level that's exactly what's going on.

In the next lecture, we'll talk about combining both secrecy and

integrity to the get the best of both.

And to get what we call authenticated encryption.

That is, an encryption scheme that achieves the joint goals of

secrecy and integrity

Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.