Understanding AES-XTS – part 2
Suppose that we have a block cipher E that operates on a message M and a key K to produce a ciphertext C, and we write the operation of this cipher as C = EK(M). A tweakable block cipher is one that uses E to operate on a message M, a key K and an additional input T called a "tweak" to produce a ciphertext C, and we write the operation of this cipher as C = EK(T, M). The tweak operates much like an initialization vector or nonce but has different security properties. An initialization vector needs to be random, while a tweak does not. A nonce needs to be used only once, while a tweak can be freely reused.
The function of the tweak is to provide variability of the ciphertext while the function of the key is to provide security against an adversary recovering the plaintext. It is not necessary to keep a tweak secret, and an tweakable block cipher needs to remain secure even if an adversary can control the tweak input into an encryption operation.
Moses Liskov, Ron Rivest and David Wagner (LRW) showed that if E is a secure block cipher then the constuction EK(T,M) = EK(M Å H(T)) Å H(T) is also a secure block cipher when H is a hash function that meets certain technical conditions (it needs to be an e-AXU2 hash function). This diagram shows this construction.
The LRW constuction provides chosen-ciphertext security, but only allows for the use of a single tweak. A more general construction due to Phil Rogaway provides the same level of security while allowing more general tweaks. If we're encrypting the contents of a hard disk, we'd like to use both the sector number and block number as tweaks, so we need a more general way to implement tweaking. How to do that will be the subject of tomorrow's post.