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

496 ratings

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

From the lesson

Week 3

Private-Key Encryption

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

Maryland Cybersecurity Center

[MUSIC]

In all the previous definitions of security that we've talked about for

private key encryption, we've been implicitly or

explicitly assuming only a passive, eavesdropping attacker.

In pictures, what this means is that we have an attacker who can

eavesdrop on the communication channel, between the sender and the receiver.

Looking at the cypher texts that are being sent from one party to the other.

And our definitions of security then require that it be infeasible for

the attacker who's observing those cypher texts.

To figure out any information, about the messages that were being communicated.

We can ask, however, what about if we consider stronger attack models?

For example, an attacker who can be active and

actively sending communication on a communication channel, or

interfering with the communication on the communication channel.

So, if we look at the first case of an adversary interfering with

the communication channel we get a picture something like this.

So here, we again have our two party's who have shared a key cane of events and

who wish to communicate.

And we have the fender taking their message, encrypting it

getting a cypher text and then sending to the receiver across the channel.

Now however,

we do not assume that the cypher text can reach the receiver unchanged.

In fact, there might be an attacker who is able to modify the cypher text as it's

being transmitted from the sender to the receiver.

And what such an attacker can do,

is to take the cypher text transmitted by the sender.

Modify it to give a different ciphertext, c prime, and

forward that modified ciphertext to the receiver.

The receiver of course has no way of knowing whether what they receive is what

was sent by the sender or what was sent by anybody else.

And so they're going to take that ciphertext,

the modified ciphertext, c prime, and decrypt it.

In general, this will give some modified cipherte modified plaintext, m prime,

that the receiver will then decide what to do with next.

What are the concerns in this setting?

Well, one concern is that the encryption scheme might be malleable.

Okay this is a technical term that has a formal definition, but

that I'm only going to define informally here.

An encryption scheme is malleable if, roughly speaking, it's possible for

an attacker to modify a cypher text like on the previous slide, and

importantly thereby cause a predictable change to the plain text.

Of course, for

any encryption scheme an attacker can always modify a ciphertext that's sent.

But in general that might result in just garbage or

some unpredictable effect in the plaintext.

But a scheme is malleable if it's possible to modify a ciphertext in a particular way

and, thereby, cause some predictable modification in the underlying plaintext.

We'll show an example in a minute, but first I just want to highlight that

malleability can be really dangerous, anytime you're concerned about

the possibility of an attacker interfering with your communication.

So, think about the case of encrypted email.

If I encrypt an email to somebody else,

that says, say I'm willing to pay you a $100 for something that you've advertised.

Well if an attacker can modify that and change my $100 agreement to

buy to something saying that I'm willing to pay $1,000,

well that can have very damaging consequences for me.

And similarly, in any kind of setting where you have encrypted transactions,

say with your bank.

If I want to withdraw or transfer $100 from my account to someone else's account,

if would be really bad if an attacker could modify my encrypted

transactions with my bank, but thereby call the bank to receive

a message telling it to transfer $1000 or $10,000 to somebody else's account.

So, these kinds of attacks can be very damaging.

If you think about it a little bit, you'll notice that all the schemes, all

the private key encryption schemes we've discussed so far are, in fact, malleable.

For example, the one-time pad is trivially malleable.

Here we'll have the, the picture from the previous slide, but

now with a specific case of encryption using the one-time pad.

So, say we have our sender now, taking their key, k,

and encrypting their message, which I've now written as a sequence of bytes.

M1 through sorry, bits m1 through mn.

So, that means that the sender will take this message m1 through mn, and

XOR it with their key, which is also going to be n bits long.

And obtain some end bit site for tech c.

C is also represented here in terms of bits and we can imagine as

before an attacker who modifies this site for attacks in some way.

For example, say the attacker just flips the final bit of

the cypher text to give a modified cypher text.

That contains the first n1 bits of that cipher text identical to the original one.

And the final bit slipped.

Well what effect is this going to have on the message that receiver obtains when

they decrypt?

Well when the receiver decrypts,

they're going to take the cipher text they received.

Which is going to be the modified cypher text with the final bit flipped.

They're going to record that with their key carry, and what you'll see is

the first and minus 1 bits of the message that they recover will be the same

as the original message, as those of the original message sent by the sender, but

the final bit of the message they recover is going to be flipped.

As compared to the bit that defender intended.

So, this has the effect of flipping the final bit of a plaintext.

So, in summary this means that by flipping the last bit of a ciphertext,

an attacker is able to predictably flip the final bit of the plaintext.

And this is not limited to the final bit.

The attacker can actually flip any bit in the cipher text, and

flipping the ith bit of the cipher text will flip the ith bit of plain text.

And nothing limits the attacker to flipping only a single bit.

If the attacker flips any number of bits of the cipher text, it

will have the effect of flipping exactly those bits in the underlying plain text.

This means if the attacker,

if he knows anything at all about the original plain text.

Can cause very predictable and

possibly damaging effects on their recovery plane text.

Now, this is very interesting, because it implies that even perfect secrecy,

which was the strongest or, or which at least was a very strong notion of

security that we discussed that does not rely on any computational assumptions.

If not sufficient to imply non-malleability.

That is schemes can be perfectly secret like the one-time pad, but

still be very malleable.

And the attack that we've demonstrated on the previous slide,

is not only limited to the one-time pad.

In fact a very similar sort of an attack, and sometimes even other kinds of attacks,

are applicable on all of the other encryption schemes we've seen so far.

I'll leave that as an exercise for you, but it is indeed the case that

every scheme we've seen so far is vulnerable to a similar attack.

So, coming back to our original discussion, right, we walked about

the fact that we might have an active attacker who can inject or modify messages

being sent across the communication channel shared by the sender and receiver.

Well, let's now consider the second case, that of the attacker who

is impersonating the sender and injecting communication on the channel.

This is actually, you can view as a special case of the previous attack,

where the attacker modified something being sent across the channel.

The real difference here is just that this attack can happen without the attacker,

without the sender sending anything at all.

The attacker can just choose to send messages on its own,

to the receiver claiming that they're from defender.

It doesn't have to wait for the sender to do anything.

So, here the picture might look something like this.

Here we have a sender and

receiver communicating over a channel, and an attacker eavesdropping and

observing some cipher text that the sender has already transmitted to the receiver.

But now, rather than just restricting the attacker to remaining passive,

we're going to allow the attacker to additionally inject cipher texts on

the communication channel, between the sender and receiver.

So, the send, what the attacker might be able to do for

example is to send a cypher text c prime to the receiver and

the way it's drawn here, it looks like it's coming from another direction.

But, this is just the limitation of our picture and in reality,

the receiver has no way of telling whether the cypher text that it

receives is coming from the legitimate sender that it intends to speak with, or

from some other party in the network.

So, any way, the attacker may be able to send a cypher text to the receiver,

cause the receiver, then, to decrypt that using the key that

they've shared with the sender, with the honest sender.

Recover some plain text message end prime, and then, at least in principle,

the attacker might be able to learn either m prime or some information about m prime.

This picture should actually remind you of the picture we had in

the context of chosen plain text attacks.

So, in that setting we had the attacker as if it were interacting with the sender.

Injecting messages or

influencing the sender to encrypt certain messages of the attacker's choice.

And then the attacker was able to reserve the results in cypher texts.

Here we're just looking at the other side of the diagram.

And assuming that the attacker might be able to eject cypher texts,

to the receiver and thereby cause the receiver to decrypt those cypher texts and

give some information back to the attacker.

And this class of attacks, where the attacker sends cypher texts to

the receiver for decryption are called chosen-cipertext attacks.

And in chosen-ciphertext attacks, as I just mentioned,

are meant to model settings in which the attacker can potentially influence

what gets decrypted by the receiver, and then observe the effects.

And just as in the case of chosen plain text attacks.

Where it's not clear how to precisely model what an attacker might be

able to do in some real world situations.

What we'll do is we'll just give the attacker as much power as we

can in our formal definition.

So, that is, we're going to consider a definition that allows the attacker to

submit any cypher text of his choice with one restriction.

To the receiver, and then learn the entire corresponding plaintext.

Now again, this is a very strong definition.

This is going to result in a very strong definition that we'll see in a moment.

And the point is that this definition is going to

capture any kind of more limited chosen-ciphertext attack in practice.

That it, it'll also capture weaker attacks.

Where the attacker is limited in what ciphertext it can give to the receiver and

caused to be decrypted, and it's also going to capture weaker attacks where

the attacker doesn't learn the entire decryption of the ciphertext that it

gives to the receiver, but only learns some partial information

about the decryption of the ciphertext he gives to the receiver.

But again her definition is going to be quite strong and

subsume all of those attacks.

The other think I want to mention is that when we

talk about chosen-ciphertext attacks, we're implicitly continuing to allow

the attacker to carry out chosen plain text attacks.

So, chosen ciphertext attacks are there for

a strictly strong then chosen plain text attacks because we

give the attacker all the power that it had for a chosen plain text attack.

And in addition, give it the ability to carry out chosen-cypher text attacks.

The formal definition is as follows.

So, as usual, we're going to fix some encryption scheme pi, and some attacker a.

And then we can define, based on those,

a randomized experiment that I'm calling here PrivCCA.

As usual, this experiment is parametrized by our security parameter N.

And the experiment goes as follows,

first we run the key generation algorithm to obtain a key K.

Then we allow our attacker to interact both with an encryption oracle

as a CPA security, but additionally to also interact with a decryption oracle.

And this decryption oracle is keyed with the same key that was generated in

the first step and that is being used in the encryption oracle as well.

So, the attacker can interact arbitrarily as many times as it likes with both of

these oracles.

And then at some point, as is usual for these kinds of definitions.

The attacker outputs two messages of zero, and then one of the same length.

A uniform bit b is chosen and we then encrypt the message and

b using our encryption scheme and again the key k generated in the first step.

This gives us our challenge type for text c.

We then allow A to continue to interact, with both the encryption oracle and

the decryption oracle, with one restriction.

And that restriction is that we don't allow the attacker to

request decryption of the challenge ciphertext c from the decryption oracle.

If we did, if we had, had allowed the attacker to do that then there's no

possibility of having any scheme satisfy this notion of security.

Now it may look a little bit weird that we sort of artificially restrict

the attacker from doing that, but in fact this results in a meaningful definition.

But as I said earlier captures any kind of chosen-cypher text attack.

That an attacker can actually carry out in the real world.

So finally, the attacker outputs its guess, b prime, as to what was encrypted.

And we'll say as usual that A succeeds if its guess is correct.

And the experiment will evaluate to one in that case.

And we'll say that pi, the encryption scheme,

is secure against chosen-ciphertext attacks or CCA secure.

And for probabilistic polynomial time attackers A there's some

negligible function epsilon such that the probability with which A succeeds in

the experiment on the previous slide is at most one half plus epsilon n.

This is the exact same format of the definitions we've seen before.

The only difference is that we've modified the experiment.

We've made the experiment stronger by giving the attacker more power.

Now, it turns out that there's a relationship between the definition of

CCA-security and the notion of malleability.

And it may be easiest to see by flipping things around a little bit.

So, I claim that if the scheme is malleable, then it cannot be CCA-secure.

And this is really just intuition.

I haven't formally defined what malleable means, so this is not any kind of a proof.

This is just an intuitive sketch as to why this claim is believable.

So let's say we have a scheme that's malleable.

Well, then that means that we can take a ciphertext, and

we can modify it, causing a predictable effect on the underlying plaintext.

So, now I'll show how we can use that to succeed in the CCA experiment.

What we'll do is we'll be,

we'll get as part of the experiment a challenge ciphertext c.

We'll then modify that to get our modified ciphertext c prime.

This modified ciphertext c prime is modified in such a way that when we,

that when it's decrypted the resulting plaintext has some

predictable relationship with the plaintext.

Underlying the original cypher text, C prime.

So, if we submit this modified cypher text C prime to our decryption oracle and

get back the result, then based on the predictable relationship that it should

satisfy, that should tell us information, or that will tell us information about

the original message M that was encrypted to give the challenge cypher text.

And so, we can then use that to break CCA-security of the scheme.

The contrapositive of this is that if a scheme is CCA-secure,

that it must also rule out all such malleability attacks.

And so, if a scheme is CCA-secure,

then it also does imply that the scheme is non-malleable.

In the next lecture what we're going to explore is a real world

example of chosen-ciphertext attacks called padding Oracle attacks.

These kind of attacks are very clever and what I want to get by to get through to

you is by showing them it is that chosen-ciphertext attacks can come up in

the real-world even very benign situations.

And that's going to help motivate why we care about CCA-security in

the first place.

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