0:00

In this segment,

we're gonna look at another form of encryption called tweakable encryption.

I'm gonna modify tweakable encryption using this encryption as an application

and we'll see this encryption is yet another application for

deterministic encryption.

So the disk encryption problem is that we wanna encrypt sectors on disks.

Say each sector is four kilobytes long.

And the problem is that there's no space to expand.

In other words, if the sector size is four kilobytes,

the cipher text size also has to exactly four kilobytes because there's nowhere to

write the extra bits if the cipher text was bigger than the plain text.

And so our goal is basically to build a non-expanded encryption

where the cipher text size is identical, exactly equal to the plain text size.

So what does it mean that encryption can't expand?

Well, technically, we're saying basically the message space is equal to the cipher

text space, so the message space would be four-kilobyte messages and

the cipher text space would be also four-kilobyte messages.

In this case, clearly we have to use deterministic encryption, because if

encryption was randomized, there would be no place to store the randomness.

And similarly, we have no room for

integrity because we can't expand a ciphertext and add any integrity bits.

So the most we can achieve is deterministic CPA security and

that's gonna be our goal.

Now it turns out, there's a really simple lemma to prove that basically says,

that if you give me a deterministically CPA secure cipher,

where the message space is equal to the cipher text base, so no expansion.

Then in fact, the cipher is a PRP.

So really all we're saying here is if we want no expansion at all,

our only option for

encrypting is what we called construction number two in the previous segment.

Namely, we have to encrypt using a PRP.

So let's look at how we might encrypt using a PRP while we take our disk and

we break it into sectors.

Now if we encrypted every sector using a pure P under the same key,

we could have run into our standard problem with a truistic encryption,

namely if sector one and sector three happen to have the same plain text,

then the encrypted sector 1 would be equal to the encrypted sector 3 and

the attacker would learn that the corresponding plain texts are the same.

Now this actually is a real problem.

For example, if some of your sectors are empty, you know they're all set to zero,

then in fact, the crypted sectors would be identical, and as a result, the attacker

would know exactly which sectors on your disk are empty and which sectors are not.

So, this is actually quite problematic and the question is, can we do any better?

And so the answer is yes.

And the first idea that comes to mind is, well, why don't we use a different key for

every sector?

So you can see sector number one gets encrypted with key one,

sector number two gets encrypted with key two and so on and so forth.

So now even if the content of sector number one is equal to sector number three

the cipher texts of sector 1 and

sector 3 will be different because they are encrypted under different keys.

So this actually avoids the leakage that we talked about before, although I do want

to point out there is still a little bit of leakage with this mode, for

example if the user happened to change 1 bit in sector 1.

And then that sector gets encrypted into a different cyphodext so this will be

garbled all completely because this is a pseudorandom permutation.

The sector will be even if one bit of the plaint exchanges,

the sector will just be mapped to a completely new random output.

However if the user then undoes the change and reverts back to the original sector,

then the encrypted sector will revert back to its original state.

And the attacker can tell that a change was made and then reverted, so

there is still a little bit of information leakage but that type of information

leakage is really nothing we can do without really sacrificing performance so

we are just going to ignore that and deem that acceptable.

So the next question is now you realize our discs are actually getting pretty big

and there are lots of sectors so this would mean we are generating lots and

lots of keys here.

But of course we don't have to store all these keys,

we can simply generate these keys using a pseudorandom function.

So the way this would work is we would have a master key which we would call K,

and then the sector number which I'm going to denote by T is going to be

encrypted using the master key, and the result of that encryption would be

the particular sector key which I'll denote by k sub t.

Now the reason this is secure is again because the PRF is indistinguishable from

a random function which means that basically if we apply a random function

to the sector numbers one, two, three, four up to L they basically get mapped to

completely random elements in the key space and

as a result we're encrypting every sector using a new random independent.

4:29

So this is a fine construction, however, again, for

every sector we would have to apply this PRF.

And so the natural question is, can we do even better?

And it turns out we can.

And this introduces this concept of a tweakable block cipher where really,

what we want, is basically, to have one master key.

And we want this one master key to derive many, many, many PRPs.

So, we said one way to do that is simply encrypt the key K, using the PRP number.

But, as we'll see, there's a more efficient way to do that.

Now, this PRP number is actually what's called a tweak, and

that introduces this concept of tweakable block cipher.

So in a tweakable block cipher the encryption and decryption algorithm

basically as usual take the key as inputs, they take a tweak as inputs.

This capital T is what is called the tweak space, and

of course they take the data as input and the output data in the set X.

The property says that for every tweak in the tweak space and a random key,

basically if we fix the key in the tweak we end up with an invertible function,

a one to one function on the site X, and

because the key is random the function is in fact indistinguishable from random.

In other words, for every setting of the tweak,

we basically get an independent PRP from X to X.

And as I said, the application for

this is now we're gonna use the sector number as the tweak.

And as a result, every sector is gonna get its own independent PRP.

So let me very,

very quickly just define more precisely what is a secure tweakable block cipher.

So as we said, there's a tweak space.

There's a key, a tweak space and an intraspace x.

And as usual, we define our two experiments.

Here in experiment one, what's gonna happen is

we're gonna choose a truly random set of permutations, so not just one permutation.

We're gonna choose as many permutations as there are tweaks.

So you'll notice this is why we raised this to the size of of the tweak space.

If the size of the tweak space is five,

this says that we're choosing five random permutations on the set X.

And any other case basically, we're just gonna choose a random key and we're gonna

define our set of permutations as the ones defined by the tweaks in the tweak space.

And at the adversary basically gets to submit a tweak and an x, and

it gets to see the value of the permutation defined by the tweak T1,

evaluated at the point x1.

And he gets to see this again and again.

Again he gets to see the value of the permutation defined by the T2 and

valued it at point x2.

And so on and so forth.

And then his goal is to say whether he interacted with truly random permutations

or pseudorandom permutations.

And if he can't do it we say that this tweakable block cipher is secure.

So the difference from a regular block ciphers is in a regular block cipher,

you only get to interact with one permutation and then it goes to tell

whether you're interacting pseudo random permutation or truly random permutation.

Here you get to interact with T random permutations and again it goes to tell

whether the T random permutations are truly random or pseudo random.

So as usual, if you can't distinguish, if the adversary behaves the same in both

experiments, we say that this PRP is a secure, tweakable PRP.

8:56

We're going to define a tweakable block cipher so

again this tweakable block cipher is going to take two and put the tweak space for

convenience which you're going to see inn just a minute.

We're going to assume this tweak space is made up of two values, T and I.

T is going to be some tweak value which we'll see in a minute and

I is going to be some index.

And then x is gonna be an N bit string,

which we're gonna apply the tweakable block cipher to.

So the way XTS works is as follows.

The first thing we're gonna do is we're gonna encrypt the left half of the tweak,

namely t, using the key k2 and we're gonna call the results N.

So now what we're gonna do is we're gonna X or the message m with some padding

function applied to this value m that we just derived at the index i.

And this padding function is extremely fast.

We can pretty much ignore it in the running time.

The next thing we do is we're gonna encrypt using the key K2.

10:19

And the nice thing about this construction is now if we wanted to encrypt

N plus 1 blocks, all we do is we compute the value N once.

And then for the indices one, two, three,

four, basically we just need to evaluate the PRP E once per block.

So we will need to encrypt end blocks using the tweaks T,1,

T,2, T,3, T,4 and so on.

We would just need n+1 evaluations of the block cipher E.

So it's twice as fast as the trivial construction.

So I want you to stare for just a minute at this XTS construction.

So my question to you is it really necessary to encrypt the tweak

before using it.

That is, is the following construction a secure tweakable PRP?

So you can see in this construction the tweak is used directly as

input to the padding function for the XOR.

And my question to you is if we did that, will that be a secure tweakable PRP.

And let me remind you again that this is the key, this is the tweak, and

this is the data.

11:53

So the fact that this is true means that an attacker can simply query

the challenger at this tweak in this data, this tweak in that data, and then

just compute the of the two responses and compare to the of the appropriate padding

values, and if the quality holds, we're interacting with a pseudo-random function.

Otherwise we're interacting with a truly random function.

So this would allow the attacker to defeat this construction with advantage one.

So just to summarize, the way XTS is used for disk encryption.

What we do is, we look at sector number t and we break it into blocks,

16 byte blocks.

And then block number 1 gets encrypted with a tweak (t,1),

block number 2 gets encrypted with a tweak (t,2), and so on and so forth.

And so every block gets it's own PRP and the whole sector,

as a result, is encrypted, using a collection of PRP's.

Now, you notice, this is a block level PRP, it's not a sector level PRP.

So, in fact, it's not true that each sector gets encrypted with it's own PRP.

It's just each block gets encrypted with it's own PRP.

The distinction would be the sector in a block is somewhat artificial, and

this XTS mode actually provides the terministic CPA encryption

at the block level, at the sixteen byte level, that's the goal.

13:06

And this mode actually is fairly popular in disk encryption products.

I just wrote a couple of examples here that actually support XDS.

So I wanted you to know that this in fact is how this encryption is commonly

done in practice.

So to summarize, tweakable encryption is a useful concept to know

when you need many independent prp's all derived from a single key.

One important thing to remember is in fact the trivial construction is

not the most efficient.

There are constructions like XTS,

are actually more efficient, where he can kind of reuse encryptions from one tweak,

to get many encryptions for many different tweaks.

And so, those are the better ways to use them.

Both the trivial construction and

the XTS construction are, what I call narrow block constructions.

Namely they provide a tweakable block ciphers for a 16 byte block.

But, as we said, we looked at the EME construction in the last segment,

which provided a PIP for much larger blocks.

And in fact, EME is a tweakable mode of operation.

So if you need PIPs for larger blocks or tweakable PIPs for

larger blocks, then you would just use EME.

But you notice there EME, you have to apply the block size for

twice per in per block.

And as a result, it's twice as low as XTS and is not very often used.

So that's what I wanted to say about tweakable encryption and

in the next segment we'll talk about format preserving encryption.