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. 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. Okay. Very good. So let's look at some examples. So we already looked at the trivial example. In the trivial example, what we do, we're gonna assume that the key space is equal to the input space. So this PRP really acts on x times x to x. So think of AES, for example, where the key space is 128 bits, the data space is 128 bits, and of course, the output is 128 bits. And then the way that we define the tweakable blocks. There's a key, a tweak, and data as input. Is basically we encrypt the tweak using our master key and then we encrypt the data using the resulting random key. Now you realize that if we wanted to encrypt n blocks with this tweak of block cypher, this would require two n evaluations of the block cypher. N evaluations to encrypt the given tweaks and then, and more evaluations to encrypt the actual given data. So I want to show you a nice example that shows that we can actually do better. This is called the XTS construction, it's actually originally based on XEX and it works as follows. Suppose you give me a regular block cipher that operates on N bed blocks. So not a tweakable block cipher, just a regular block cipher. 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. And then we're gonna x or again, using the same path. So we're gonna x or again using the path of, and apply to i. And the result, is gonna be the cypher text which we will denote by c. Okay, so again as I said, the function p is some very, very simple function, it's just some multiplication in a finite field, which I'm not gonna explain here Very, very fast. So the running time is really dominated by the running time of the block cipher for E. And that's it, that's XTS. 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. I hope everybody said that this is the correct answer. Basically if we set the data to be PT comma one, then we exorate with the corresponding tweak which is also PT comma one. We're gonna get here, zero, and so what's gonna get encrypted is actually zero, so whatever that comes out to be, let's say that's some value c zero. And then the actual output is gonna be c zero x or p t one. Now when we do the same thing with p t two, we're gonna get c zero x or p t two. And when we x or these two things together, we just get p t one x or p t two. 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. 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.
