Tip:
Highlight text to annotate it
X
In the last segment we defined authenticated encryption, but I didn't
really show you why authenticated encryption is the right notion of
security. In this segment I want to show you that authenticated encryption in fact
is a very natural notion of security and I'll do it by showing you that it defends
against a very powerful attack called a chosen cipher text attack. So in fact we
already saw a number of examples of a chosen cipher text attack so imagine the
adversary has some cipher text C that it wants to decrypt. And what it can do
is, for example, fool the decryption server into decrypting some cipher text
but not actually the cipher text c. So we already saw some examples of that. If you
remember in the first segment, we looked at an adversary that can submit arbitrary
cipher text, and if the plaintext happened to start with destination equals 25, then
the adversary is actually given the plaintext in the clear. So that's an
example of an adversary that can obtain the decryption of certain cipher texts but
not all cipher texts. Another example we saw is an adversary that can learn
something about the plaintext by submitting cipher texts to the decrypter.
So we have this example where the adversary submits encrypted TCP/IP packets
to the decryption server, and if the decryption server sends back an ACK, the
adversary learns that the decrypted plain text had a valid check sum. And otherwise,
the decrypted plain text didn't have a valid check sum. So this is, again, an
example of a chosen cipher text attack, where the attacker submits cipher text,
and learns something about the decryption of that cipher text. So to address this
type of threats, we're gonna define a very general notion of security, called chosen
cipher text security. So here, we're gonna give the adversary a lot of power, okay?
So he can do both chosen plain text attack, and a chosen cipher text attack.
In other words, he can obtain the encryption of arbitrary messages of his
choice. And he can decrypt any cipher text of his choice, other than some challenge
cipher texts. And as I showed you before, this is actually a fairly conservative
modeling of real life. In real life, often, the attacker can fool the, the
decrypter, into decrypting certain cipher texts for the attacker, but not all cipher
texts. So the model here is that the attacker has a certain cipher text that it
wants to decrypt. It can interact with the decrypter by issuing these chosen
cipher text queries to the decrypter. Namely, to decrypt various cipher text
other than the challenge cipher text. And then the adversary's goal is to break
semantic security of the challenge cipher text. So you notice that we're giving the
adversary a lot of power. And all we're asking you to do is break semantic
security. So it's going to be fairly difficult to design systems that are
secure against such adversaries. Nevertheless, we're going to do it. So
let's define the chosen cipher text security model more precisely. So, as
usual, we have a cipher (E, D). And we're gonna define two experiments, experiment
zero and experiment one. So this should look somewhat familiar by now. The
challenger is gonna start off by choosing a random key. And now the adversary is
gonna submit queries to this challenger. Every query can be one of two types. It
can be a chosen plain text query, or it can be a chosen cipher text query. So a
chosen plain text query, as we already know. Basically, the adversary submits two
messages, M zero and M1. They have to be the same length. And the adversary
receives the encryption of either M zero if we're in experiment zero, or M1, if we're
in experiment one. So he receives the encryption of the left or the right
depending on whether we were in experiment zero or in experiment one. The second type
of query is the more interesting one. This is where the adversary submits an arbitrary
cipher text of his choice and what he gets back is the decryption of that cipher
text. So you notice the adverary's allowed to decrypt arbitrary cipher texts of his
choice. The only restriction is that the cipher text is not one of the cipher texts
that were obtained as a result of a CPA query. And of course this wouldn't be fair
otherwise, because the attacker can simply take one cipher text that was obtained
from a CPA query. That's gonna to be either the encryption of M0 or the
encryption of M1. If he could submit a CCA query for that particular cipher text, he
will in response either obtain M0 or M1, and then he'll know whether he is in experiment
zero or experiment one. So this wouldn't be fair. So we say that the CPA cipher
texts that he received are the challenge cipher texts. And he's allowed to decrypt
any cipher texts of his choice, other than these challenge cipher texts. And as
usual, his goal is to determine whether he's in experiment zero, or in experiment
one. So I'm gonna emphasize again, that this is an extremely powerful adversary.
One that can decrypt any cipher text of his choice, other than the challenge
cipher text. And still, he can't distinguish whether he is in experiment
zero, or in experiment one. So, as usual, we say that the cipher is CCA secure,
chosen cipher text secure, if the adversary behaves the same in experiment
zero as it does in experiment one. Namely, it cannot distinguish the two experiments. So
let's start with a simple example, and show that, in fact, CBC with a random IV,
is not CCA secure, is not secure against chosen cipher text attacks. So let's see
why that's the case. So what the adversary's gonna start by doing, he's
gonna simply submit two distinct messages, M0 and M1. And let's just pretend that
these messages are one block messages. And what he's gonna get back is the CBC
encryption of either M0 or M1. You notice the cipher text only has
one block, because the plain texts were only one block long. Now what is the
attacker gonna do? Well, he's gonna modify this cipher text C that he was given into
C prime simply by changing the IV. Okay? So he just takes the IV and XORs it with
one. That's it. This gives a new cipher text, C prime, which is different from C
and as a result it's perfectly valid for the adversary to submit C prime as its
chosen cipher text query. So he asks the challenger please decrypt this C
prime for me. The challenger, because c prime is not equal to c, must decrypt c
prime. And now let's see, what happens when he decrypts c prime? Well, what's the
decryption of c prime, let me ask you. So you probably remember from the first
segment that if we xor the IV by one, that simply xors the plaintext by one. So now
that adversary received M0 xor one, or M1 xor one, and now he can perfectly tell
whether he's in experiment zero and, or in experiment one. So the advantage of this
adversary is basically one, because he can very easily tell which experiment he's in.
And as a result he can win the chosen cipher text security game. So if you think
about it for a second, you'll see that this attack game exactly captured the first
active attack that we saw, where the adversary slightly changed the cipher text
that he was given. And then he got the decrypter to decrypt it for him. And
therefore, he was able to eavesdrop on messages that were not intended for the
adversary. So I wanna emphasize again that this chosen cipher text game really does
come up in real life, where the adversary can submit cipher texts to the decrypter
and the decrypter can reveal information about the plain text, or it can give the
plain text outright to the adversary for certain cipher texts but not others. So
this is a very natural notion of security, and the question is, how do we design
crypto-systems that are CCA secure? So I claim that this authenticated encryption
notion that we defined before actually implies chosen cipher text security, and
this is why authenticated encryption is such a natural concept. Okay? So the
theorem basically says, well, if you give me a cipher that provides authenticated
encryption, the cipher can withstand chosen cipher text attacks. And more
precisely, the theorem says the following. If we have an adversary that issues Q
queries, in other words, at most, q CPA queries and q chosen cipher text queries,
then there are two efficient adversaries, B1 and B2, that satisfy this inequality
here. So since the scheme has authenticated encryption, we know that
this quantity is negligible because it's CPA secure. And we know that this
quantity is negligible because the encryption scheme has cipher text
integrity. And as a result, since both terms are negligible we know that
adversary's advantage in winning the CCA game is also negligible. So let's prove
this theorem. It's actually a very simple theorem to prove. And so let's just do it
as proof by pictures. Okay, so here we have two copies of the CCA game, so this
would be experiment zero. And the bottom one is experiment one. You can see the
adversary's issuing CPA queries, and he's issuing CCA queries, and at the end he
outputs, you know, a certain guess b, let's call it b prime, and our goal is to
show that this b prime is indistinguishable in both cases. In other
words, probability that b prime is equal to one in the top game is the same as the
probability that b prime is equal to one in the bottom game. Okay, so the way we're
gonna do it is the following. Well, first of all, we're gonna change the challenger
a little bit, so that instead of actually outputting the decryption of CCA queries,
the challenger is just gonna always output bottom. So every time the adversary
submits a CCA query, the challenger says bottom. And I claim that these two
games are, in fact, indistinguishable. In other words, the adversary can't
distinguish these two games, for the simple reason that, because the scheme has
cipher text integrity, the adversary simply cannot create a cipher text that's
not in C1 to CI-1 that decrypts to anything other than bottom. That is the
definition of cipher text integrity. And as a result, again, because of cipher text
integrity, it must be the case that every chosen cipher text query that the
adversary issues results in bottom. If the adversary, in fact, could distinguish
between the left game and the right game, that would mean that at some point he
issued a query that decrypted to something other than bottom. And that we could use
to then break cipher text integrity of the scheme. And since the scheme has
cipher-text integrity, these left and right games are indistinguishable. Okay,
so that's kind of a cute argument that shows that it's very easy to respond to
chosen cipher-text queries when you have cipher-text integrity. And the same thing
exactly applies on the bottom, where we can simply replace the chosen cipher-text
responses by just always saying bottom. Okay, very good. But now, since the chosen
cipher text queries always respond in the same way, they're not giving the adversary
any information. The adversary always knows that we're always gonna just respond
with bottom. So we might as well just remove these queries, 'cause they don't
contribute any information to the adversary. But now, once we remove these
queries, the resulting game should look fairly familiar. The top right game, and
the [bottom right] game are basically the two games that come up in the definition of
CPA security. And as a result, because the scheme is CPA secure, we know that the
adversary can't distinguish the top from the bottom. And so now, by this change of
reasoning, we've proven that all of these games are equivalent. And in particular,
the original two games that we started with are also equivalent, and therefore,
the adversary can't distinguish the top left from the bottom left. And therefore,
the scheme is CCA secure. So this gives you the intuition as to why authenticated
encryption is such a cool concept. Because primarily it implies security against
chosen cipher test attacks. Okay, so as we said authenticated encryption
ensures confidentiality. Even if the adversary can decrypt a subset of the
cipher text, and more generally, even if he can mount a general chosen cipher text attack,
he still is not going to be able to break semantic security of the system. However,
it is important to remember the two limitations. First of all, it does not
prevent replay attacks on its own. We're going to have to do something in addition
to defend against replay attacks. We're going to see several examples where if the
decryption engine reveals more information about why a cipher text is rejected, it
doesn't just output bottom, but it actually outputs more information, say, by
timing attacks. And that explains why the cipher text is rejected. Then in fact that
can completely destroy security of the authenticated encryption system. So we'll
see some cute attacks like this in a later segment. Okay. So, in the next segment
we're gonna turn to constructing authenticated encryption systems.