[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.
