Understanding AES-XTS – part 1
The IEEE P1619 Security in Storage Working Group has developed the XTS (XEX-based tweaked codebook mode with ciphertext stealing) mode of AES. AES-XTS is designed for use in encrypting data stored on hard disks, and it works within the constraints imposed by disk hardware while keeping the security provided by the AES algorithm. The operation of AES-XTS is defined in the 1619-2007 IEEE Standard for Cryptographic Protection of Data on Block-Oriented Storage Devices, and is currently under consideration by NIST as an approved mode of operation of AES. I have heard rumors that NIST is going to allow AES-XTS as approved mode, but I haven't seen anything yet that confirms this.
Hard disks are partitioned into circular paths called tracks. These are physical divisions of data on the drive that are determined by the location of the data on the surface of the drive. Tracks are in turn partitioned into fixed-sized logical sectors which can be individually read from or written to a hard disk. Sectors are the smallest accessible subdivision of a track, and typically, but not always, comprise 512 bytes. A sector may further be subdivided into logical blocks which are the same size as the block of data encrypted by a block cipher. A sector may or may not contain a number of bytes that is an integer multiple of the block size.
Because all of the bytes of a sector are dedicated to storage, there is no additional space available so store other information. This means that inputs to a encryption algorithm that is useful for encrypting data on a hard disk should only include a cryptographic key, the data itself, the sector number where the data is stored, and the block number within a sector, and AES-XTS does exactly this.
The AES-XTS is based on Rogaway's XEX construction, which is in turn based on the idea of a tweaked block cipher as described by Liskov, Rivest and Wagner. To allow for sectors that do not contain a number of bytes equal to an integer multiple of the AES block size, ciphertext stealing is also used.
Posts over the next few days will explain exactly what each of these things mean and how they're used to create the AES-XTS mode of operation.