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.

Â