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

435 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

[NOISE].

In the last lecture we talked about authenticated encryption.

Which provides a way for

two parties to communicate with both secrecy and integrity.

Now, let's consider two parties who again wish to communicate securely,

that is with secrecy and integrity.

But now they want to do so in the context of a communication session.

Whereby a communication session, I simply mean a period of

time over which the two parties are willing to maintain state.

Now, of course the natural thing here, is to use authenticated encryption.

So, in this picture I've shown two parties sharing a key k in advance, and

using an authenticated encryption scheme to communicate.

So, in this and

the next few slides, by Enc, I mean an authenticated encryption scheme.

In this picture we have Bob sending messages m1 and m2 to Alice.

And then Alice replying with a message m3.

And because the parties are using authenticated encryption.

We know that if the attacker injects any ciphertext different

from the ones it's seen already.

That will be detected as invalid by one of the parties.

And if the attacker modifies any of the cyphertexts being sent by either party,

that too will be detected as being invalid by the other side.

Does this mean that using authenticated encryption in this way

gives us the notion of security that we want during the context of their session?

In fact, I claim that there are several attacks that can still be carried out.

An easy one is a replay attack.

So, imagine that Bob sends the message m1 to Alice,

and then tries to send a message, m2.

But the attacker can somehow prevent that message from reaching Alice.

Dropping it in the network that day.

And instead, the attacker simply replays the first ciphertext to Alice.

Well, Bob intended to send m1 followed by m2.

But Alice will receive m1 followed by m1.

And a priori, Alice doesn't know whether Bob intended to send m1 twice or not.

So, this causes a mismatch between the view of Alice and Bob in their session.

Again, Bob thinks he sent m1 m2, or Bob intended to send m1 m2.

Whereas Alice receives m1 m1,

and doesn't have any idea a priori that anything went wrong.

Other attacks are possible as well.

For example here I've shown what I'll call a re-ordering attack.

So, in this setting Bob sends m1 followed by m2.

But the adversary who might have control over scheduling in

the network delivers m2.

Or the encryption of m2 before delivering the encryption of m1.

So, again this will cause a mismatch in the parties respective views of this

communication session.

Bob has intended to send m1m2, but Alice has received m2m1.

And again, there's no way for Alice to tell here that anything has gone wrong.

Finally I want to point out what may be a more insidious sort of an attack,

which I'll call a reflection attack.

So, here Bob sends m1 to Alice, and then tries to send m2.

Whether or not m2 reaches Alice, we can imagine that the attacker here

simply redirects the encryption of m2 that Bob just sent.

And forwards it to Bob as if it's coming from Alice.

Now from Bob's point of view, he'll decrypt, not get any error and

believe that Alice has intended to send him the message m2.

So this, again, will introduce a mismatch between the views of Alice and Bob.

Bob, intended to send m1m2.

Alice in this picture, didn't send anything, but

Bob thinks he's received a message m2 from Alice.

So, all of these examples, show how even using authenticated encryption alone,

is not enough to get the security.

The integrity guarantees that we might want in a secure session.

It turns out that these attacks and

others can be prevented very simply using what are, what are called counters.

And by incorporating the identities of the parties.

And these, as I said, are rather simple but do need to be incorporated.

If the parties want to achieve the notion of integrity across their

communication session.

Let me show how these are done.

So, what the parties will do is simply incorporate both a counter and

their identity, in any message that they want to transmit.

Before applying the authenticated encryption scheme.

So, here we see how Bob, when sending the message m1.

Includes both a counter value 1, because this is the first message that Bob is

sending to Alice along with his identity, Bob.

And then when he sends the second message, he'll include the counter value

2 along with his identity, at the other end of course.

Alice, upon decrypting,

will check that the sender field corresponds with the intended other party.

In this case that would be Bob, and

also verifies that the sequence number matches what she expects.

So, the first sequence number should be one, and any subsequent point of time,

point in time, upon decrypting some cypher text.

She should observe a counter number that's one more than the last counter value

she received.

In the final message, Alice sends m3, and she will include the counter value 1,

because this is her first message, along with her identity Alice.

And Bob will perform similar chats, checks at his end.

It turns out that a notion of secure sessions can be defined.

We won't do that here, and one can prove that this construction.

That is, using authenticated encryption and incorporating counters and

identities, realizes this notion of secure sessions.

It's clear that it provides secrecy, at least against the passive eavesdropper.

But the argument for integrity is a bit more complicated, and

relies exactly on the fact that the parties are willing and

able to maintain state throughout the course of this session.

This completes our treatment of the private-key settings.

Congratulations on making it this far.

Of course, this doesn't mean you should forget everything we've covered so far.

And in particular, the primitives we've discussed in the context of

private key cryptography will be used even in the public key setting.

Just to recap the things we've discussed so far, we've seen

appropriate primitives for ensuring secrecy in the private key setting.

Namely private-key encryption schemes, as well as the appropriate primitive for

achieving integrity in the private-key setting.

That is, message authentication codes.

We've also talked about authenticated encryption.

And how to appropriately design an authenticated encryption scheme.

That allows parties to achieve both secrecy and integrity for

their communication.

Along the way,

we've often discussed the notion of collision resistant hash functions.

And discussed how they can be used for message authentication.

Next week, we'll start moving on to the public-key setting.

And in particular, we'll begin with a discussion of number theory.

And cryptographic hardness assumptions, that can be based on number theory.

I hope to see you all there.

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