Deterministic Encryption: SIV and Wide PRP

Loading...

Do curso por Stanford University

Cryptography I

2354 classificações

Stanford University

Cryptography I

2354 classificações

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.

Na lição

Authenticated Encryption

Week 4. This week's topic is authenticated encryption: encryption methods that ensure both confidentiality and integrity. We will also discuss a few odds and ends such as how to search on encrypted data. This is our last week studying symmetric encryption. Next week we start with key management and public-key cryptography. As usual there is also an extra credit programming project. This week's project involves a bit of networking to experiment with a chosen ciphertext attack on a toy web site.

Deterministic Encryption14:33

Deterministic Encryption: SIV and Wide PRP20:28

Conheça os instrutores

Dan Boneh
Professor
Computer Science

Now that we understand what is deterministic encryption, let's see some

constructions that provide security against deterministic chosen plaintext

attacks. So, first let me remind you that the deterministic encryption is needed,

for example, when encrypting a data base index and later we wanna look up records

using the encrypted index. Because the encryption is deterministic we're

guaranteed that when we do the lookup the encrypted index is gonna be identical to the

encrypted index that was sent to the database when the record was written to

the database. And so, this deterministic encryption allows us a very simple or fast

way to do lookups based on encrypted indices. The problem was that we said the

deterministic encryption can't possibility be secure against a general chosen

plaintext attack because if the attacker sees two cipher texts that are equal

it learns that the underlying encrypted messages are the same. So, then we defined

this concept of deterministic chosen plain text security which means that we have

security as long as the encryptor never encrypts the same message more than once

using a given key. In particular, this key, message pair is only used once, for

every encryption, either the key changes, or the message changes. And then as I

said, formally we define this CPA, deterministic CPA security game, and our

goal in this segment is to actually give constructions that are deterministic CPA

secure. So the first construction we're gonna look at is what's called SIV,

synthetic IV's. And the way this construction works is as follows. Imagine

we have a general CPA secure encryption system. So here's the key and here's the

message and we are gonna denote by R the randomness that's used by the encryption

algorithm. Remember that a CPA secure system that doesn't use nonsense has to be

randomized and so we're explicitly gonna write down this variable R to denote the

random string that's used by the encryption algorithm as it's doing the

encryption. For example if we're using randomized counter mode, r would be the

random IV that's used by randomized counter mode. And of course C is the resulting

ciphertext. Now, in addition, we're also going to need a pseudo random function, f,

that what it does, is it takes our arbitrary messages in the message space

and outputs a strings, R, that can be used as randomness for the CPA secure

encryption scheme. So, the little, r, over here is actually a member of the big R set. Okay.

And we're going to assume this is a, f is a pseudo random function that maps messages

to random strings. Now the way SIV works is as follows. It's going to use two keys

K1 and K2 to encrypt the message M. And what it does, is the first thing is going

to apply the pseudo random function f to the message M to derive randomness for the

CPA secure encryption scheme E. And then it's going to encrypt the message M using

the randomness that it just derived. This is going to give us a cipher text C and

then it's going to output this cipher text C Okay. So that's how this SIV mode works.

Basically it first derives the randomness from the message being encrypted, and then

it uses this derived randomness to actually encrypt the message to obtain the

cipher text. Now I'd like to point out for example, if the encryption scheme E

happened to be randomized counter mode. Then the randomness R would just be the

random IV which would actually be output along with the cipher text. So this means

that the cipher text is a little bit longer than the plain text. But the point

here isn't to generate a short cipher text. Rather the point here is to make

sure that the encryption scheme is deterministic, so if we encrypt the same

message multiple times, every time we should obtain the same cipher text. And

indeed every time, we'll obtain the same randomness, R, and as a result, every time

we'll obtain the same cipher text C. So it's fairly easy to show that this

encryption scheme really is semantically secure under the deterministic chosen

plaintext attack. The reason that's so is because we apply the pseudo random

function F to distinct messages. Well if we apply F to distinct messages then the

random string that F generates is going to look like just truly random strings. A

different random string for every message. And as a result the CPA secure encryption

scheme E is always applied using truly random strings. And that's exactly the

situation where it is CPA secure. So because these R's are just random

indistinguishable from brand new strings, the resulting system is in fact gonna be

CPA secure. So this is just the intuition for why this works and it's actually

fairly straightforward to actually formalize this into a complete proof. Now,

I should emphasize that this is actually well suited for messages that are more

than one AES block. In fact, for short messages, we're gonna see a slightly

different encryption scheme that's actually better suited for these short

messages. Okay, now the really cool thing about SIV is that, actually, we get cipher

text integrity for free. In fact we don't have to use a special Mac if we want to

add integrity. In a sense SIV already has a built in integrity mechanism. And let me

explain what I mean by that. First of all, our goal was to build what's called

deterministic authenticated encryption. Dae. Deterministic Authenticated

Encryption. Which basically means that deterministic CPA security and cipher text

integrity. Remember cipher text integrity means that the attacker gets to ask for

the encryptions of messages of his choice and then he shouldn't be able to produce

another cipher text that decrypts to a valid message. Okay, so I want to claim

that in fact SIV automatically gives a cipher text integrity without the need for

an embedded MAC or anything else. So let's see why. In particular, let's look at a

special case of SIV when the underlying encryption scheme is randomized counter

mode. Okay, so we'll call this SIV-CTR again to denote SIV where we're using

randomized counter mode. Alright. So let me remind you again how SIV works in this

case. Well, so we take our message, here, we take our message, and then we apply a

PRF to it. And that derives an IV. And then that IV is going to be used to

encrypt the message using randomized counter mode. Okay. So in particular,

we're gonna use this PRF FTCRr for F counter, for randomized counter mode and

essentially evaluate this FCTR at Iv, IV plus one up to IV plus L. And, then, we

had sorta that with the message. And that gives us the final ciphertext. Okay. So,

this is SIV with a randomized counter mode. Now, let's see how decryption is

gonna work. And during decryption we're gonna add one more check, and that's

going to provide ciphertext integrity. So let's see how decryption is going to work. So here

we have our input cipher text that contains the IV and the cipher text. Well,

the first thing we're going to do is we're going to decrypt the cipher text using the

given IV, and that will give us candidate plain text. Now we're gonna reapply the

PRF F from the definition of SIV to this message. Now if a message is valid, we

should be getting the same IV that the [adversary??] supplied as part of the cipher

text. If we get a different IV, then we know that this message is not a valid

message and we simply reject the cipher text. So this is really cute. It's a very

simple kinda built in check to make sure that the cipher text is valid, right. We

simply check that after decryption if we re-derive the IV we would actually get

the correct IV. And if not we reject the message. And I claim that this simple check

during decryption is enough to [actually??] provide ciphertext integrity. And therefore,

deterministic authenticated encryption. So I'll state this in a simple theorem.

Basically to say, that if F is a secure PRF, and in counter mode that's derived

from FCTR is CPA secure, then the result is in fact a deterministic authenticated

encryption system. Now the proof for this is not too difficult. In two sentences,

let me just show you the rough intuition for why this is true. So, all we have to

argue is just cipher text integrity. So we already argued before that the system has

deterministic CPA security, all we have to argue is just cipher text integrity. So to

argue that the system has cipher text integrity, let's think again how the

cipher text integrity game works. Adversary asks for the encryption of a

bunch of messages of his choice. And he gets the resulting cipher text. Then, his

goal is to produce a new valid cipher text. Well, if that valid cipher text upon

decryption, decrypts to some completely new message. Then when we plug this new

message into the PRF F, we're just going to get some random IV and it's very unlikely

to hit the IV that the adversary supplied in the cipher text that he output. So

therefore that says that when the advisory outputs his forged cipher text, the

message in that forged cipher text basically should be equal to one of the

messages in his chosen message queries. Otherwise, again the IV that you get is

simply not gonna be equal to the IV in the forged safe index with very high

probability. But if the message is equal to one of the messages that the adversary

queried us on, well then, the cipher text that we're gonna get is also gonna be

equal to one of the cipher texts that we supplied to the adversary. But then his

forgery is simply one of the cipher texts that we gave to him. And therefore, this

is not a valid forgery. He has to give us a new cipher text to win the cipher text

integrity game. But he gave us one of our old cipher texts. So, this is the rough

intuition. I hope, I kinda went through it quickly. I hope it kinda makes sense. If

it doesn't then it's not the end of the world. I'm gonna reference the paper that

describes SIV at the end of the module. And if you wanna see this in more detail

you can read and take a look inside of that paper. But, regardless, this is a

very cute idea that I wanted to show you where kinda the fact that we derive the

randomness for deterministic counter mode using a PRF. Also, gives us an integrity

check when we actually do the decryption. Okay. So this SIV is a good mode for doing

deterministic encryption when you need to, particularly if the messages are long. If

the messages are very short, say they're less than sixteen bytes, in fact there's a

better way to do it, and that's the method that I wanna show you now. So the second

construction is actually trivial. All we're gonna do is we're gonna use a PRP

directly. So here's what we do. So suppose (E, D) is a secure PRP. So E will encrypt, and

D will decrypt. And I claim that if we use E directly, that already gives us

deterministic CPA security. So let me show you very quickly why. So suppose F is a truly random invertible function from X

to X. Okay. So remember a PRP is indistinguishable from a truly random

invertible function, so let's pretend that we actually do have a truly random

invertible function. Now in experiment zero what the attacker is gonna see while

he submits a bunch of messages, you know the messages on the left. And what he's

gonna see is basically the evaluation of f on the messages on the left that he

supplied. Well, in the deterministic CPA game, all these messages are distinct, and

so all he's gonna get back are just q distinct random values in X. That's all he

sees. Yes, there's Q distinct random values in X. Now let's think about

experiment one. In experiment one, he gets to see the encryptions of messages on the

right, okay, the M11 to MQ1. Well, again, all these messages are all distinct so all

he gets to see are just Q random distinct values in X. Well these two distributions,

in experiment zero and experiment one, therefore are identical. Basically, in

both cases what he gets to see are just Q distinct random values in X. And as a

result, he can't distinguish experiment zero from experiment one. And since he

can't do this for a truly random function, he also can't do this for the PRP. Ok,

so that explains why directly encrypting with a PRP already gives us a CPA secure

system very, very, very simple to use. That says that if all we wanna do is

encrypt short messages, say, less than sixteen bytes, then all we need to do is

to directly encrypt them using AES and the result will, in fact, be deterministic CPA

secure. So, if your indices are less than sixteen bytes directly using AES is a fine

thing to do. Notice however, that's not gonna provide any integrity. And we're

gonna see how to add integrity in just a minute. But the question for you is, what

do we do if we have longer than sixteen byte messages? Well, one option is to use

SIV. But what if we actually wanted to use this construction too. It's actually an

interesting question. Can we construct PRP's that have message spaces that are

bigger than just sixteen bytes? If you remember in the past we constructed PRFs

on that had large message spaces from PRFs that had small message spaces. Here,

we're going to construct PRPs with large message spaces from PRFs that have small

message spaces. So, here's how we do it. So suppose E D is a secure PRP that

operates on N bit blocks. There's a standard mode called EME that actually

will construct a PRP that operates on capital N bit blocks, where capital N is

much, much bigger than little n. So this would allow us to do deterministic

encryption on much larger messages than just sixteen bytes. In fact it could be as

long as we want. So let's see how EME works. It's a bit daunting at first but

it's not a difficult construction. So, let's see how it works. So, EME uses two

keys, K and L, and in fact in the real EME L is derived from K. But for our purposes,

let's just pretend that K and L are two distinct keys. The first thing we do, is

we take our message X and we break it up into blocks. And then we XOR each block

with a certain padding function, okay? So we use the secret key L to derive a pad

using this, you know function P that I'm not gonna explain here. We derive a

different pad for each one of the blocks and we XOR that pad. Into the block. The

next thing we do is we apply the PRP E using the Key K, to each of these blocks,

and we're gonna call these outputs PP0, PP1, and PP2. The next thing we do is we

XOR all these ppp's together and we call the result MP. Actually this XOR

doesn't need to be there. We call the result of the XOR MP. The next thing we

do we XOR all these ppp's together and we call the result MP. We encrypt this MP

using E and the key K. We call the outputs of this encryption MC. Okay. So then we use

the XOR MP and MC and this gives us another PM, which we use to derive one

more pad, and then we XOR this output of this pad with all the PPP's to get

these CCC's, [laugh], and then we XOR all these C C C's together that gives us

a value of C C C zero, which we then encrypt one more time with all these E's,

we do one more padding with all these P's and that actually finally gives us the

output of EME. Okay, so like I said, this may look a little daunting, but in

fact there's a theorem that shows that if the underlying block cipher E is a secure

PRP, then in fact. This construction, EME, is a secure PRP on this larger block, you

know, zero, one to the capital N. The nice thing about this construction is you

notice that it's very parallel and actually that's why it's a little

complicated. Counted every block. It's encrypted in parallel, so if you have a

multi-core processor, you can use all your cores to encrypt all the blocks at the

same time and then there would be one kind of sequential step to compute this, check

sum of, all the outputs and then one more parallel around to encrypt one more time

and then finally you get the outputs. These function Ps, by the way, that

generate the pads, are very, very simple functions. They take constant time so

we're just going to ignore them in terms of performance. So the bottom line is

performance here. You notice it requires two applications of E per input block. And

it turns out this can actually be slower than SIV, if SIV is implemented properly

with a very fast PRF to derive the randomness. Then in fact SIV can be twice

as fast, as this particular mode of operation. For this reason I say that the

PRP construction is very good for short messages, whereas SIV is good if you h, if

you want to encrypt longer messages in a deterministic fashion. But now what if we

wanted to add integrity to this PRP-based mechanism? So, can we achieve

deterministic authenticated encryption using the PRP mechanism where we directly

encrypt the message using a PRP? And it turns out the answer is yes and it's

actually again, a very simple encryption scheme that you should know

about. Basically what we're going to do is we're going to take our message and we're

going to append a bunch of zeros to this message and then we're going to apply the

PRP and that's it. And that's going to give us the cipher text. Now, very, very

simple. Just append zeros and encrypt using a PRP. When we decrypt, we're going

to look at these least significant bits of the resulting plain text and if they're

not equal to zero, we're just going to reject the cipher text. And if they are

equal to zero, we're going to output the message as valid. Okay, so that's it,

that's the whole system, very, very simple. Simply append zeroes during

encryption, and then check that the zeroes are there when you decrypt. And I claim

that this very simple mechanism actually provides deterministic authenticated

encryption, assuming, of course, that you've appended enough zeroes. And in

particular, if you append N zeroes, you need one over two to the N to be

negligible. And if so, then, in fact, this direct PRP based encryption, in fact,

provides deterministic authenticated encryption. So let me see why. Well, we

already argued that the system is CPA secure, so all we have to argue is that it

provides cipher text integrity. And again, that's easy to see. Let's look at the

cipher text game. So the adversary is gonna choose let's say a truly random

permutation. So a truly random, invertible function, on the input space. In this case

the input space is the message space and the N zero bits. Now what does the

adversary get to do? Well he gets to submit q messages, and then he receives

the encryption of those Q messages. Mainly he receives the PRP at his chosen points

concatenated with N zeros. Okay, that's what it basically it means to query the

CPA challenger. So in case of a random permutation, he simply gets to see, the

value of this permutation at Q points of his choice, but only concatenated with N

zeroes. And now, what's his goal in the cipher text integrity game? Well, his goal

is to produce some new cipher text that's different from the cipher text that he was

given, that's gonna decrypt properly. Well, what does it mean that it decrypts

properly? It means that if, when we apply, Pi inverse To the cipher text C, it had

better be the case that the N least significant bytes of C are all zeros. And

the question is how likely is that to happen? Well, so let's think about this.

So basically we have a truly random permutation and the adversary got to see

the value of this permutation as Q points. How likely is he to produce a new point

that, when inverted, happens to have N zeroes as the least significant bits? What we're

doing here is basically we're evaluating the permutation Pi inverse at the point c.

And since Pi inverse is a random permutation, how likely is it to have its

n least significant bits be equal to zero? So it isn't hard to see that the answer

is, is, at most, the probability's at most, one over two to the N. Because,

again, basically, the permutation is gonna output a random element inside of, X times

0 1 to the N. And that element is gonna end with N zeroes, but basically

with the probability one over two to the N. And as a result, the adversary wins the

game with negligible probability, Because, this value is negligible. So that's the

end of this segment. I wanted you to see these two very cute deterministic

authenticated encryption schemes. The first one we called SIV, where I said you

would use randomized counter mode and you just arrived at randomness for randomized

counter mode from a PRF applied to the message. And the very cute idea here is

that during decryption you can simply recompute the IV from the, from the decrypted

message and verify that that IV is what's given to you in the cipher text. And that

simple check is actually enough to guarantee authenticated encryption or

rather deterministic authenticated encryption. So this mode is, is the way

you would encrypt an index in a database if the index was large. If the index

happens to be short, maybe say, its eight bytes if it's an 8-byte user ID, then you

can directly use a PRP and the way you would do is, is you would append zeros to

those eight bytes. And then those zeros will be used as an integrity check when

you decrypt and again if you append, are able to append enough zeros, then in fact

this also provides deterministic authenticated encryption. As an aside, I

showed you that there's a way to build the wide block PRP from a narrow PRP and that

particular mode of operation is called EME. So we're gonna refer EME

actually in the next segment.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2019 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play