Tweakable Encryption with XTS and the Limits of Length-Preserving Disk Encryption

Disk encryption has a constraint that protocol encryption does not: the ciphertext must occupy exactly the same bytes as the plaintext, in the same place. A filesystem reserves sector 4096 for a given block and expects to read it back from sector 4096. If encryption added a tag, the record layout would change; if it added padding, the device would need slack. Neither is available, because the storage layer above the encryption expects a fixed-geometry block device.

The requirement sounds like it forces ECB, with all of ECB’s equality leaks. XTS avoids that by introducing a value that changes per position but is not stored alongside the data — a tweak, derived from the sector number. The mode has been the standard for full-disk encryption for well over a decade and is specified in IEEE 1619 and in NIST SP 800-38E. What it does not provide is any integrity, and the consequences of that are the most useful thing to understand about it.

Tweakable block ciphers

A tweakable block cipher is a family of permutations indexed by two values, a key and a tweak. The tweak is not secret; it is a selector like the key, except that it is assumed to be public. Security is defined with respect to a random tweakable permutation: an adversary that can choose tweaks and query the cipher cannot distinguish it from a random permutation chosen independently for each tweak.

If a mode had such a primitive, disk encryption would be easy: encrypt sector $s$ block $i$ with key $K$ and tweak $(s, i)$, and no two positions ever share a permutation, so equality of plaintext blocks at different positions produces unrelated ciphertext. Nothing leaks, and the ciphertext is the same size.

No standard cipher is tweakable. XTS builds one from AES by deriving a per-position tweak value and XORing it into the data before and after the block cipher call:

$$C = E_K(P \oplus T) \oplus T$$

with $T$ computed from the sector number and the key. Because $T$ differs per position, the map is a permutation for each $T$, and different positions use different maps. This is the XEX construction — XOR, encrypt, XOR — and it is the same idea that underlies the mask generation in one-pass tweakable modes.

Deriving the tweak from the sector number

The tweak is a 128-bit value computed by encrypting the sector index with a second key, then multiplying repeatedly by the field element $x$ in the same binary field used by GHASH. For AES-XTS the first key is used to encrypt the data and the second, separate key to encrypt the tweak input; the two keys must be independent, which is why an XTS key for AES-128 is 256 bits and for AES-256 is 512 bits.

Concretely, with sector number $j$ written into a 128-bit block, the tweak for block $i$ within the sector is

$$T_i = \alpha^i \cdot E_{K_2}(j)$$

where $\alpha$ is the primitive element of the field and the multiplication is the carry-less reduction used throughout this cluster’s modes. The multiplication by $x$ is a shift with a conditional reduction, so computing successive tweaks costs a few instructions per block — cheaper than a second cipher call and, importantly, the same cost on every architecture.

Two consequences follow from the tweak being a function of the sector number only. The first is that writing a sector back to a different sector changes its tweak, so the ciphertext will not decrypt correctly: the mode binds ciphertext to address. The second is that two sectors with identical plaintext produce different ciphertext, because their tweaks differ, so the equality pattern of the plaintext is hidden — unless the same sector is written at two different times with the same plaintext, which produces the same ciphertext and is unavoidable.

/* Tweak update: multiply the 128-bit value by x in GF(2^128). The
   reduction polynomial is applied when the top bit shifts out. */
static void xts_mul_x(uint8_t t[16])
{
    uint8_t carry = (uint8_t)(t[15] >> 7);
    for (int i = 15; i > 0; i--)
        t[i] = (uint8_t)((t[i] << 1) | (t[i - 1] >> 7));
    t[0] = (uint8_t)(t[0] << 1);
    if (carry)
        t[0] ^= 0x87;     /* x^128 = x^7 + x^2 + x + 1 */
}

The shift direction here follows the little-endian byte convention used by IEEE 1619 and by most implementations; the constant and the direction are fixed by the field representation, and a mismatch between two implementations produces ciphertexts that do not interoperate.

Ciphertext stealing and the tail block

A sector is not always a multiple of the block size. Disk sectors are typically 512 or 4096 bytes, both multiples of 16, but the mode is specified for arbitrary lengths and the specification must define how the final partial block is handled without expanding the output.

XTS uses ciphertext stealing. Suppose the message has $m$ full blocks and a final partial block of $r$ bytes, with $0 < r < 16$. The mode encrypts the first $m-1$ blocks normally. For the last full block $P_m$ and the partial block $P_{m+1}$, it computes the XEX encryption of $P_m$, takes the first $r$ bytes of that result as the ciphertext tail, and uses the remaining $16 - r$ bytes as the tail of the input to a second encryption together with $P_{m+1}$; the full 16-byte result becomes the ciphertext of block $m$. The receiver reverses the operation, recovering $P_m$ from the full ciphertext block after re-deriving the tail.

The cost is that the last two blocks are coupled, so they cannot be processed in parallel with each other, and the operation is more delicate than the rest of the mode. Implementations that get the tail handling wrong produce data that decrypts correctly under themselves and incorrectly under anything else, which is why the standard includes explicit test vectors for lengths that force stealing. The NIST specification identifies XTS as suited to storage and not to general-purpose use, and the ciphertext-stealing rules are part of why.

The integrity that is not there

XTS is a confidentiality mode. It has no tag, and the specification says so plainly: the mode does not detect modification. An adversary with write access to the device can alter any ciphertext block, and the corresponding plaintext block becomes a pseudorandom block with no indication of tampering. This is not a partial failure; it is a complete absence of the property.

The attacks that follow are practical and have been demonstrated against real disk encryption systems, though the mechanism is worth understanding without the incident detail.

Block moving is the most direct. Because the tweak is a function of the sector number, an attacker cannot move a sector to a different address and expect it to decrypt. But within a sector, and across the whole device where the address is part of the tweak, a relocation attack is still possible in the narrower sense of replaying old ciphertext for the same sector: the attacker records a sector, waits for it to be rewritten, and restores the old ciphertext. The sector decrypts to its old plaintext, and nothing detects this. A filesystem that trusts its own metadata to be current now reads stale data.

Targeted modification of a known plaintext is the second. If the attacker knows the plaintext of a sector — a boot sector’s structure, a known file header, a database page with a predictable format — it can flip bits at chosen offsets and know exactly what the plaintext becomes, because XTS is XOR-malleable at the block level given a known plaintext and tweak. The result decrypts to the modified value with a valid structure, which is enough to corrupt a specific field, change a UID, or alter a configuration value.

The third is a dictionary attack on the tweak derivation when the second key is derived from the first or from a password rather than stored independently. The specification requires the two keys to be independent; an implementation that derives both from one passphrase without proper separation weakens the position binding.

Where XTS sits relative to AEAD

The contrast with the AEAD modes in this cluster is complete, and it is a contrast of requirements rather than of quality. GCM, CCM, and the synthetic-IV constructions all expand the message by at least the tag length and all authenticate the ciphertext, and the tag is checked before any plaintext is used, as discussed in releasing unverified plaintext. XTS cannot expand, so it cannot carry a tag, so it cannot authenticate. The absence is forced by the storage geometry.

The practical resolution in deployed systems is layering. XTS protects data at rest against an attacker who has the physical medium but not the key. Integrity against an attacker who can write is provided above the encryption layer — by filesystem checksums, by a Merkle tree over the device, by a hash tree whose root is stored outside the attacker’s reach — or accepted as absent. The latter is common and is a deliberate scoping decision: the threat model is theft of a powered-off device, not an adversary with write access to a live one.

The key-commitment property described in the key commitment article is also absent from XTS in the same way it is absent from GCM: a ciphertext is bound to a sector number and a key, but nothing prevents an attacker from constructing a ciphertext consistent with two keys. For disk encryption, where the key set is small and rotation is a full re-encryption, this has not been an operational concern.

What XTS does well is what it was designed to do. It is fast — one block cipher call per block plus a few instructions for the tweak — it parallelises across sectors, it requires no padding, and it makes sector-level equality invisible. The mode’s limits are properties of a length-preserving cipher, and any construction with the same constraint inherits them.