Understanding AES-XTS – part 3
To understand the more generalized ways to securely tweak a block cipher with more than one tweak, we need to understand how to multiply bit vectors. Defining a way to add vectors of bits is easy. Adding the vectors component by component works the way that we'd like the operation to work. Defining a way to multiply bit vectors is slightly more complicated.
To do this, we can identify a vector (b0,b1,…bk) with the polynomial b0 + b1 x + … + bk xk. To multiply two bit vectors we then mutiply the polynomials that they correspond to and then reduce this product modulo a polynomial of degree k. If we pick the polynomial that we used for this reduction in the right way, then this definition of multiplication works the way we'd like it to work. In particular, we need this polynomial to act much like a prime number: it should have no factors aside from itself and 1. In the following, any multiplication of bit vectors is done in this way.
Now suppose that E is a block cipher, N and a1 through ak are bit strings and that i1 through ik are integers.
Phil Rogaway showed that if E is a secure block cipher then the construction EK(N, i1, …,ik, M) = EK(M Å D) Å D , where D = a^(i1)…a^(ik) EK(N), is also a secure block cipher that uses the k + 1 tweaks N and i1 through ik.This construction is often called "Rogaway's XEX construction," after the fact that it performs an XOR operation, then an encryption operation, and then another XOR operation. This diagram shows this construction.
The SISWG modified Rogaway's XEX construction slightly to form the basis of the XTS mode of operation. They did this by limiting the number of tweaks to two and by increasing the number of keys used from one to two.
The two tweaks correspond to the sector and block number where data is stored. The use of two keys instead of one should not be interpreted as a criticism of Rogaway's XEX construction. Instead, a more appropriate interpretation is that is the use of two keys is a result of the influence of the commercial users of the technology that perceive the use of two keys being better that the use of a single key. The SISWG is already planning on modifying the P1619 standard to include a way to do one-key XTS, so it looks like they're accepting the fact that they didn't really need to use to keys in the first place.
With the definition of how to multiply bit vectors that we have above,SISWG defines the constant a to be the one that corresponds to the polynomial x. We can also think of a as corresponding to the value 2 if we think of the bit vector as being the binary representation of an integer.
The XTS construction then calculates a ciphertext as EK1,K2(i, j, M) = EK1(M Å D) Å D, where D = ai EK2(j). The value of j is set to the sector number being encrypted, and the value of i is set to the block number within this sector that is being encrypted. This diagram shows this construction.
What we have so far works if the size of a sector is an integer multiple of the block size. If that's not the case, then ciphertext stealing can be used to handle the odd-sized block. We'll describe how that works on the next post.