Cryptography is an indispensable tool for protecting information in computer systems. In this course you will learn the inner workings of cryptographic systems and how to correctly use them in real-world applications. The course begins with a detailed discussion of how two parties who have a shared secret key can communicate securely when a powerful adversary eavesdrops and tampers with traffic. We will examine many deployed protocols and analyze mistakes in existing systems. The second half of the course discusses public-key techniques that let two parties generate a shared secret key. Throughout the course participants will be exposed to many exciting open problems in the field and work on fun (optional) programming projects. In a second course (Crypto II) we will cover more advanced cryptographic tasks such as zero-knowledge, privacy mechanisms, and other forms of encryption.
Security for Many-Time Key (CPA security)
Loading...
From the course by Stanford University
Cryptography I
2036 оценки
From the lesson
Block Ciphers
Week 2. We introduce a new primitive called a block cipher that will let us build more powerful forms of encryption. We will look at a few classic block-cipher constructions (AES and 3DES) and see how to use them for encryption. Block ciphers are the work horse of cryptography and have many applications. Next week we will see how to use block ciphers to provide data integrity. The optional programming assignment this week asks students to build an encryption/decryption system using AES.
Meet the Instructors
Dan BonehProfessor
Computer Science
In this segment we will look at how to use block ciphers to encrypt multiple messages
using the same key. This comes up in practice for example in file systems where
the same key's used to encrypt multiple files. It comes up in networking protocols
where the same key is used to encrypt multiple packets. So let's see how to do
it. The first thing we need to do is to define what is mean for a cipher to be
secure when the same key is used to encrypt multiple messages. When we use the
key more than once the result of that is that the adversary gets to see many cyber
text encrypted using the same key. As a result, when we define security, we're
gonna allow the adversary to mount what's called a chosen plain text attack. In
other words, the adversary can obtain the encryption of arbitrary messages of his
choice. So, for example, if the adversary's interacting with Alice. The
adversary can ask Alice to encrypt arbitrary messages of the adversary's
choosing. And Alice will go ahead and encrypt those messages and give the
adversary the resulting cipher texts. You might wonder why would Alice ever do this.
How could this possibly happen in real life? But it turns out this is actually
very common in real life. And in fact, this modeling is quite a conservative
modeling of real life. For example, the adversary might send Alice an email. When
Alice receives the email, the writes it to her encrypted disk, thereby encrypting the
adversary's email using her secret key. If later the adversary steals this disc, then
he obtains the encryption of an email that he sent Alice under Alice's secret key. So
that's an example of a chosen plain text attack, where the adversary provided Alice
with a message and she encrypted that message using her own key. And then later
the attacker was able to obtain the resulting cipher text. So that's the
adversary's power. And then the adversary's goal is basically to break
semantic security. So let's define this more precisely. As usual, we're gonna
define semantic security under a chosen plain text attack using two experiments,
experiment zero and experiment one, that are modeled as a game between a challenger
and an adversary. When the game begins, the challenger is gonna choose a random
key K. And now the adversary basically gets to query the challenger. So the
adversary now begins by submitting a semantic security query, namely, he
submits two messages, M zero and M one. I added another index, but let me ignore
that extra index for a while. So the adversary submits two messages, M zero and
M one, that happen to be of the same length. And then the adversary receives
the encryption of one of those messages, either of M zero or of M one. In
experiment zero, he receives the encryption of M zero. In experiment one,
he receives the encryption of M one. So, so far this would look familiar this looks
exactly like a standard semantic security [inaudible]. However, plain text attack
the adversary can now repeat this query again. So now you can issue a query with
two other plain texts, again of the same length, and again you would receive the
encryption of one of them. In experiment zero you would receive the encryption of M
zero. In experiment one you would receive the encryption of M one. And the attacker
can continue issuing queries like this. In fact we'll say that he can issue up to Q
queries of this type. And then, remember, every time he issues a pair of messages.
That happen to be of the same length and every time he either gets the encryption
of the left side or the right side again in experiment zero he will always get the
encryption of the left message in experiment one he will always get the
encryption of the left message. And, then adversary's goal is, basically, to figure
out whether he's in experimental zero or in experiment one. In other words, whether
he was constantly receiving the encryption of the left message or the encryption of
the right message. So, in some sense, this is a standard semantic security game just
iterated over many queries that the attacker can issue to adaptively one after
the other. Now the chosen plain text attack is captured by the fact that if the
attacker wants the encryption of a particular message m. What he could do is,
for example, use query J for sum J, where in this query J he'll set both the zero
message and the one message to be the exactly same message M. In other words,
both the left message and the right message are the same, and both are set to
the message M. In this case, what he will receive, since both messages are the same,
he knows that he's gonna receive the encryption of this message M that he was
interested in. So this is exactly what we meant by a chosen [inaudible] attack.
Where the advisory can submit a message m and receive the encryption of that
particular message m of his choice. So some of his queries might be of this chose
plain text flavor where the message on the left is equal to the message on the right,
but some of the queries might be standard semantic security queries where the two
messages are distinct and that actually gives him information on whether he's in
experiment zero or in experiment one. Now by now you should be used to this
definition where we say that the system is semantically secure under a chosen plain
text attack. If, for all efficient adversaries, they cannot distinguish
experiment zero from experiment one. In other words, the probability that, at the
end, the output, B Prime, which we're gonna denote by the output of experiment
B. This output will be the same whether [inaudible] experiment zero or experiment
one. So the attacker couldn't distinguish between always receiving encryptions of
the left messages, versus always receiving encryptions of the right messages. So in
your mind, I'd like you to be thinking of an adversary that is able to mount a
chosen plaintext attack, namely, be given the encryption of arbitrary messages of
his choice, and his goal is to break semantic security for some other challenge
cipher texts. And as I said in this [inaudible] model of the real world the
attacker is able to fool Alice into encrypting for him messages of his choice
and then the attacker's goal is to somehow break some challenge cypher text. So I
claim that all the ciphers that we've seen up until now, namely deterministic counter
mode or the one time pad, are insecure under a chosen plain text attack. More
generally, suppose we have an encryption scheme that always outputs the same cipher
text for a particular message M. In other words, if I ask the encryption scheme to
encrypt the message M once. And then I ask the encryption scheme to encrypt the
message m again. If in both cases the encryption scheme outputs the same cypher
text, then that system cannot possibly be secure under a chosen plain text attack.
And both deterministic counter mode and the one time pad were of that flavor. They
always output the same cipher text, given the same message. And so let's see why
that cannot be chosen plain text secure. And the attack is fairly simple, what the
attacker is gonna do, is he's gonna output the same message twice. This just says.
That he really wants the encryption of M0. So here the attacker is given C0 which is
the encryption of M0. So this was his chosen plain text query where he actually
received the encryption of the message M0 of his choice. And now he's going to break
semantic security. So what he does is he outputs two messages, M0 and M1 of the
same length, and he's going to be given the encryption of MB. But low and behold,
we said that the encryption system. Always outputs the same cipher text when its
encrypting the message, M0. Therefore, if B is=to zero, we know that C, this
challenged cipher text, is simply=to CO, because it's the encryption of M0.
However, if B is=to one. Then we know that this challenge cypher text is the
encryption of M1 which is something other than C zero so all the attacker does is he
just checks his C is = to C0 the output's zero in other words he outputs one. So, in
this case, the attacker is able to perfectly guess this bit B, so he knows
exactly [inaudible] given the encryption of M0, or the encryption of M1. And as a
result, his advantage in winning this game is one. Meaning that the system cannot
possibly be CPA secure. One is not a negligible number. So this shows that the
deterministic encryption schemes cannot possibly be CPA-secure, but you might
wonder well, what does this mean in practice? Well in practice this means
again that every message is always encrypted to the same cipher text. What
this means is if you're encrypting files on disk, and you happen to be encrypting
two files that happen to be the same, they will result in the same cipher text and
then the attacker by looking at the encrypted disk, will learn that these two
files actually contain the same content. The attacker might not learn what the
content is, but he will learn that these two encrypted files are an encryption of
the same content and he shouldn't be able to learn that. Similarly, if you send two
encrypted packets on the network that happen to be the same, the attacker will
not learn the content of those packets, but he will learn that those two packets
actually contain the same information. Think for example of an encrypted voice
conversation. Every time there's quiet on the line, the system will be sending
encryptions of zero. But since encryption of zero are always mapped to the same
cypher text. An attacker looking at the network will be able to identify exactly
the points in the conversation where there's quiet because he will always see
those exact same cypher text every time. So these are examples where deterministic
encryption cannot possibly be secure. And as I say formerly we say that the
terministic encryption can not be semantically secure under a chosen plain
text attack. So what do we do, well the lesson here is if the secret keys gonna be
used to encrypt multiple messages, it had better be the case that given the same
plain text to encrypt twice. The encryption algorithm must produce
different cipher texts. And so there are two ways to do that. The first method is
what's called randomized encryption. Here, the encryption algorithm itself is going
to choose some random string during the encryption process and it is going to
encrypt the message M using that random string. So what this means is that a
particular message, M0 for example, isn't just going to be mapped to one cipher text
but it's going to be mapped to a whole ball of cipher texts. Whereon every
encryption, basically, we output one point in this ball. So every time we encrypt, the
encryption algorithm chooses a random string, and that random string leads to
one point in this ball. Of course, the decryption algorithm, when it takes any
point in this ball, will always map the result to M zero. Similarly cipher text M
one will be mapped to a ball, and every time we encrypt M one, we basically output
one point in this ball. And these balls have to be disjoint, so that the
encryption algorithm, when it obtains a point in the ball corresponding to M one,
will always output the message M one. In this way, since the encryption algorithm
uses randomness, if we encrypt the same message twice, with high probability we'll
get different cipher texts. Unfortunately this means that the cipher text
necessarily has to be longer than the plain text because somehow the randomness
that was used to generate the cipher text is now encoded somehow in the cipher text.
So the cipher text takes more space. And roughly speaking, the cipher text size is
going to be larger than the plain text. By basically the number of random bits that
were used during encryption. So if the plain texts are very big, if the plain
texts are gigabytes long, the number of random bits is going to be on the order of
128. So maybe this extra space doesn't really matter. But if the plain texts are
very short, maybe they themselves are 128 bits, then adding an extra 128 bits to
every cipher text is going to double the total cipher text size. And that could be
quite expensive. So as I say randomized encryption is a fine solution but in some
cases it actually introduces quite a bit of costs. So let's look at a simple example.
So imagine we have a pseudorandom function that takes inputs in a certain
space r which is gonna be called a nonce space. And outputs, outputs in the message
space. And, now, let's define the following randomize encryption scheme
where we want to encrypt the message m with the encryption of whatever it's gonna
do is first it's gonna generate a random r in this nonce space R. And then it's going
to open a cypher text that consist of two components, the first component is going
to be this value R and the second component is going to be an evaluation of
the pseudo-random function at the point R XOR with the message M. And my question to
you is, is this encryption system semantically secure under a chosen plain
text attack. So the correct answer is yes. But only if the nonce space R is large
enough so that little R never repeats with very, very high probability. And let's
quickly argue why that's true. So first of all, because F is a secure pseudo-random
function, we might as well replace it with a truly random function. In other words,
this is indistinguishable from the case where we encrypt the message M, using the
truly random function little F, evaluated to point R, and then XOR with M.
But since this little r never repeats every cypher text uses a different little r what
this means is that the values of F(r) are random uniform independent strings
every time. So every time we encrypt a message, we encrypt it essentially using a
new uniform random one time pad. And since XORing a uniform string with any string
simply generates a new uniform string, the resulting cipher text is distributed as
simply two random uniform strings. I'll call them r and r prime. And so both in
experiment zero and in experiment one, all the attacker gets to see are truly uniform
random strings r, r', and since in both experiments the attacker is seeing the same
distribution, he cannot distinguish the two distributions. And so since security
holds completely when we're using a truly random function it's also gonna hold when
we're using a pseudorandom function. Okay, so this is a nice example of how we use
the fact that the pseudo random function behaves like a random function to argue
security of this particular encryption scheme. Okay, so now we have a nice
example of randomized encryption. The other approach to building chosen plain
text secure encryption schemes is what's called a nonce based encryption. Now, in
a non-spaced encryption system, the encryption algorithm actually takes three
inputs rather than two. As usual it takes the key and the message. But it also takes
an additional input called a nonce. And similarly, the decryption algorithm also
takes the nonce as input, and then produces the resulting decrypted plain text. And
what is this nonce value n. This nonce is a public value. It does not need to be
hidden from the adversary but the only requirement is that the pair (k,n)
is only used to encrypt a single message. In other words, this pair (k,n)
must change from message to message. And there are two ways to change it. One way
to change it is by choosing a new random key for every message. And the other way
is to keep using the same key all the time but then we must choose a new nonce for
every message. And, and as I said, I wanna emphasize again, this nonce need not
be secret, and it need not be random. The only requirement is the nonce is unique.
And in fact, we're gonna use this term throughout the course. A nonce
for us, means a unique value that doesn't repeat. It does not have to be random. So
let's look at some examples of choosing an nonce, well the simplest option is
simply to make the nonce of the accounter so for example the networking
protocol you can imagine the nonce being a packet counter that's incremented
every time a packet is sent by a sender or received by the receiver this means that
the encrypter has to keep state from message to message mainly that he has to
keep this counter around and increment it after every message is transmitted.
Interestingly, if the decrypter actually has the same state then there is no need
to include the nuance in the cipher text since the nuance is implicit. Let's look
at an example. The https protocol is run over a reliable transport mechanism which
means that packets sent by the sender are assumed to be received in order at a
recipient. So if the sender sends packet #5 and then packet #6, the recipient
will receive packet #5 and then packet #6 in that order. This
means that if the sender maintains a packet counter, the recipient can also
maintain a packet counter and two counters basically increment in sync. In this case
there is no reason to include the nonce in the packets because the
nonce is implicit between the two sides. However, in other protocols, for
example, in IPsec, IPsec has a protocol designed to encrypt the IP layer. The IP
layer does not guarantee in order delivery. And so the sender might send
packet #5 and then packet #6, but those will be received in reverse order at
the recipient. In this case it's still fine to use a packet counter as a nonce
but now the nonce has to be included in the packet so that the recipient knows
which nonce to use to decrypt the received packet. So as I say, nonce based
encryption is a very efficient way to achieve CPA security. In particular if the
nonce is implicit, it doesn't even increase the cipher text length. Of course
another method to generate a unique nonce is simply to pick the nonce at random
assuming the nonce space is sufficiently large so that with high probability the
nonce will never repeat for the life of the key. Now in this case, nonce
based encryption simply reduces to randomized encryption. However, the
benefit here is that the sender does not need to maintain any state from message to
message. So this is very useful for example if encryption happens to take
place on multiple devices. For example, I might have both a laptop and a smart
phone. They might both use the same key. But in this case if I require state full
encryption, then my laptop and the smartphone would have to coordinate to
make sure that they never reuse the same nonces. Whereas if both of them simply take
nonces at random, they don't need to coordinate because it was very high
probability they'll simply never choose the same nonce. Again assuming the nonce
space is big enough. So there are some cases where stateless encryption is quite
important, in particular where the same key is used by multiple machines. So I
wanted to find, more precisely, what security means for nonce based
encryption. And in particular, I want to emphasize that the system must remain
secure when the nonce are chosen by the adversary. The reason it's important
to allow the adversary to choose the nonces is because the adversary can
choose which cipher text it wants to attack. So imagine the nonce happens to
be a counter and it so happens that when the couter hits the value fifteen, maybe
at that point it's easy for the adversary to break semantic security. So the
adversary will wait until the fifteenth packet is sent and only then he will ask
to break semantic security. So when we talk about nonce based encryption, we
generally allow the adversary to choose the nonce and the system should remain
secure even under those settings. So let's define the CPA game in this case and it's
actually very similar to the game before. Basically the attacker gets to submit
pairs of messages MI, MI0, and MI1. Obviously they both have to be of the same
length. And he gets to supply the nonce. And in response, the adversary is given
the encryption of either MI0, or MI1. But using the nonce that the adversary
chose. And of course, as usual, the adversary's goal is to tell whether he was
given the encryption of the left plain text or the right plain text. And as
before the adversary gets to iterate these queries and he can issue as, as many
queries as he wants, we usually let q denote the number of queries that the
adversary issues. Now the only restriction of course, which is crucial, is that
although the adversary gets to choose the nonces, he's restricted to choosing
distinct nonces. The reason we force him to choose distinct nonces is because
that's the requirement in practice. Even if the adversary fools Alice into
encrypting multiple messages for him, Alice will never use the same nonce
again. As a result, the adversary will never see messages encrypted using the
same nonce and therefore, even in the game, we require that all nonce be
distinct. And then as usual we say that the system is a nonce based encryption
system that's, semantically secure under a chosen plain text attack if the adversary
cannot distinguish experiment zero where he's given encryptions of the left
messages from experiment one where he's given encryptions of the right messages.
So let's look at an example of a nonce based encryption system. As before, we
have a secure PRF that takes inputs in the nonce space R and outputs strings in the
message space M. Now when a new key is chosen, we're going to reset our counter R
to be zero. And now we encrypt the particular message M, what we will do is
we will increment our counter R, and then encrypt the message M using the
pseudorandom function applied to this value R. And as before, the cipher text is
going to contain two components, our current value of the counter and then the
one time pad encryption of the message M. And so my question to you is whether this
is a secure, non-spaced encryption system. So the answer as before is yes, but only
if the nuance space is large enough. So as we increment the counter R, it will never
cycle back to zero so that the nuances will always, always be unique. We argue
security the same way as before. Because the PRF is secure, we know that this
encryption system is indistinguishable from using a truly random function. In
other words, if we apply a truly random function to the counter and XOR the
results with, the plain text M. But now since the nuance R never repeats, every
time we compute this F of R, we get a truly random uniform and independent
string so that we're actually encrypting every message using the one time pad. And
as a result, all the adversary gets to see in both experiments are basically just a
pair of random strings. So both the experiment zero and experiment one the
adversary get's to see exactly the same distribution, namely, the responses to all
this chosen plain text queries are just pairs of strings that are just uniformly
distributed and this is basically the same in experiment zero and experiment one and,
therefore, the attacker cannot distinguish the two experiments. And since he cannot
win the semantic security game with a truly random function he, also, cannot win
the semantics security game with the secure PRF, and, therefore, the scheme is
secure. So now we understand what it means for a symmetric system to be secure when
the keys used to encrypt multiple messages the requirement is that it be secure under
a chosen plan of attack. And we said that basically, the only way to be secure under
a chosen plain text attack is either to use randomized encryption, or to use, use
nonce spaced encryption where the nonce never repeats. And then in the
next two segments, we're gonna build two classic encryption systems that are secure
when the key is used multiple times.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
