Loading...

Authenticated Encryption

Course video 29 of 48

Message Authentication Codes

Криптография

Мэрилендский университет в Колледж-Парке

Курс 3 из 5 — Безопасность в киберпространстве Специализация

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

Просмотреть программу курса

Получаемые навыки

Number Theory, Cryptography, Public-Key Cryptography

Преподаватели

Jonathan Katz
Professor, University of Maryland, and Director, Maryland Cybersecurity Center

Текст видео

[SOUND]

Up til now, we've shown different primitives for achieving both secrecy and

integrity in the private key setting.

But what if we want to achieve both?

That is, what if we have a sender and

receiver who want to be able to communicate while ensuring both

the secrecy and the integrity of their communication?

It's very natural to try to achieve this by simply combining any private

key encryption scheme with a message authentication code in what

I'll call the encrypt and authenticate fashion that I'll describe now.

So here we have a sender and receiver who have shared two keys in advance,

one of which will be used for a private key encryption scheme and

the other of which will be used for a secure message authentication code.

To transmit a message m, the sender can first encrypt its message

using the key k1 and the secure encryption scheme to generate a ciphertext c,

and then separately authenticate the message m using the key k2 and

some secure message authentication code.

The sender can then transmit both c and t to the receiver.

At the other end, the receiver can first decrypt the ciphertext component using k1

to obtain the message and then verify the associated tag

t on that message to check whether it was indeed sent by the sender.

Is this combination secure?

That is, is it going to give us both the secrecy and

integrity properties that we want?

In fact, there's a subtle problem here and

that is that the tag t might leak information about the message m.

And if you think about it a little bit, that's simply because nothing in

the definition of security for message authentication code

says anything about whether or not it hides information about m.

And in fact, it's quite easy to construct a message authentication code which is

secure in the sense that it achieves integrity,

like a message authentication code is supposed to.

But which reveals lots of information about the message or

even the entire message itself.

This is not just a theoretical problem.

In fact, if the message authentication code is deterministic, as most

constructions including CBC-MAC and HMAC are, then the message authentication

code will leak whether or not the same message is being encrypted twice.

And that's simply because when the sender transmits a message m,

even though the underlying private key encryption scheme might be randomized,

resulting in a different ciphertext component c, if the MAC is deterministic,

then the tag t will be the same when the sender transmits the same message twice.

This will therefore leak to an attacker whether or

not the sender is sending the same thing twice.

And this is something, as we've discussed before, that can be problematic and

that we'd like to avoid.

So the combinations shown on the previous slide in which we simply encrypt and

authenticate the message independently is not

achieving the secrecy notion that we had intended or that we want.

What we can do instead is to use a different approach that I'll

call encrypt then authenticate.

Here, the parties again share keys k1 and k2 as before.

But now, to send the message m,

what the sender does is first encrypt m as before, resulting in a ciphertext c.

And then authenticate the ciphertext.

Authenticate c rather than authenticating m itself.

And then send c and t as before.

On the receiving end,

the receiver will first verify the tag t on the ciphertext component c.

And only if verification succeeds, will then go ahead and

decrypt the ciphertext component to recover the message m.

What can we say about security here?

Well, it turns out that it's possible to prove that if the underlying encryption

scheme is CPA-secure and the underlying message authentication code is secure,

that is, it ensures integrity, then the combination of the two in this encrypt and

authenticate approach is CPA-secure.

That is, it does give us the secrecy that we desire for the combination of the two

when the sender uses this mechanism to send messages to the receiver.

In addition, the combination is also a secure MAC.

Now here, this is not quite true because the construction on

the previous slide doesn't quite fit into the syntactic definition of

a message authentication code.

Nevertheless, the idea should be clear and

that is that the combination does guarantee the integrity property that we

desire, essentially that the attacker cannot trick

the receiver into outputting any message that was not sent by the sender.

In fact, if you look at the combination a little bit more closely,

you might notice that it achieves something even stronger than what

we've claimed in the previous slide.

And that is that given a bunch of ciphertexts corresponding to

chosen plaintexts m1, m2, et cetera, it's infeasible for

an attacker to generate any new, valid ciphertext.

I'll just note here that I'm viewing the ciphertext as the pair c, t.

So I'm viewing the sender is doing as encrypting its message and

obtaining a ciphertext c, t containing two components.

And the claim is even that after having absorbed encryptions of a sequence of

known messages and obtaining the corresponding ciphertext c1, t1, ct2, t2,

et cetera, it would be infeasible for an attacker to generate any

new ciphertext c, t that the receiver would accept as valid.

Encryption schemes with this property are called authenticated encryption schemes.

And again, this simply means that given a bunch of valid ciphertexts,

it's infeasible for an attacker to generate any new, valid ciphertext.

That is, any ciphertext that the receiver would decrypt as valid and

would not result in the receiver outputting an error message.

Put differently, this means that if the attacker observes a sequence of ciphertext

being sent from sender to receiver, and then the, and then the attacker tries to

inject its own ciphertext, different from any sent previously, the receiver will,

with overwhelming probability, output an error message.

It turns out that the property of authenticated encryption,

in combination with CPA-security,

implies that the encryption scheme achieves chosen ciphertext security.

And what this means, very simply, is that the encrypt and authenticate

combination that we've discussed before is itself a CCA-secure encryption scheme.

To recap, the encrypt-then-authenticate approach, using independent keys for

encryption and authentication, is a sound way to construct authenticated encryption.

What I mean here is that you can plug in any underlying CPA-secure encryption

scheme and any underlying secure message authentication code and

be guaranteed that the combination,

when used as the approach indicates, is an authenticated encryption scheme.

It, interestingly raw, other more efficient constructions have been

proposed and are currently an active area of research and potential standardization.

О Coursera

На онлайн-курсах, специализациях и дипломных программах у вас будут первоклассные преподаватели из лучших университетов и учебных заведений мира.

Join a community of 40 million learners from around the world

Earn a skill-based course certificate to apply your knowledge

Gain confidence in your skills and further your career

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2019 Все права защищены.

Загрузить из App Store

Загрузить в Google Play