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

415 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

[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 provides universal access to the worldâ€™s best education,
partnering with top universities and organizations to offer courses online.