Tweakable Block Ciphers and the Cost of Sector Independence

A block cipher takes a key and a block. Storage encryption needs something more: the same key must encrypt millions of sectors, and each sector’s ciphertext must be independent of every other’s position and content. Using the cipher directly on each sector with the same key would make identical plaintext blocks at the same offset produce identical ciphertext, which reveals structure and permits splicing attacks in which blocks are moved between sectors.

The standard fix is to make the cipher’s behaviour depend on a second input, the sector index, that is public and need not be secret. Liskov, Rivest, and Wagner formalised this as the tweakable block cipher: a family of permutations $E: \mathcal{K} \times \mathcal{T} \times \mathcal{M} \to \mathcal{M}$ where each key and tweak pair gives an independent permutation. The security notion is that an adversary with access to both directions and the ability to choose tweaks cannot distinguish the family from a collection of independent random permutations.

What a tweak is not

A tweak is not a nonce in the stream-cipher sense, and not a second key. It is public, chosen by the system, and known to the attacker. Its job is domain separation: two blocks at different positions must be encrypted under different effective permutations. Because it is public, it can be stored alongside the ciphertext, derived from the block’s address, or computed from a sector number — no key management is needed for it.

The distinction from a nonce is operational. A nonce must never repeat under one key, and a repeated nonce destroys security. A tweak may repeat as long as the key differs, and the same tweak applied to different keys is fine. The security requirement is per (key, tweak) pair, and the number of distinct pairs is what limits the birthday bound: with a $b$-bit block, collisions become likely after roughly $2^{b/2}$ blocks under one key regardless of how many tweaks are used, because the underlying permutation is the same size.

The construction problem

The naive way to add a tweak is to derive a per-tweak key: hash the key and the tweak, then run the cipher. That is secure if the derivation is secure, but it costs a full key schedule per sector, which is expensive for the small sectors typical of storage.

The cheaper approach is to mix the tweak into the state before the first round and rely on the cipher’s diffusion to spread it. This is what Threefish does: the tweak is added into two words of the state before the first round, and again at the end, with a permutation of the tweak words between the two injections. The argument for security is that the tweak enters before any round, so by the time the state reaches the output it has been through the full round function, and the tweak’s influence is as complete as the key’s.

The argument fails if the tweak is injected late. A construction that XORs the tweak into the output only provides a trivial relation between the ciphertexts of two tweaks: $E_{k,t_1}(x) \oplus E_{k,t_2}(x) = t_1 \oplus t_2$, independent of the key. This is an immediate distinguisher, and it is exactly the failure that a tweakable cipher must avoid.

/* XTS sector encryption: the tweak is the sector number encrypted under
   a second key, then multiplied by alpha in GF(2^128) per block offset.
   The tweak enters before the block cipher's first round. */
static void xts_encrypt_sector(const uint8_t *k1, const uint8_t *k2,
                               uint64_t sector, uint8_t *buf, size_t blocks)
{
    uint8_t tweak[16] = {0};
    store_le64(tweak, sector);
    aes_encrypt_block(k1, tweak);        /* tweak = E_{k1}(sector) */

    for (size_t i = 0; i < blocks; i++) {
        for (int j = 0; j < 16; j++)
            buf[i * 16 + j] ^= tweak[j];  /* pre-whiten */
        aes_encrypt_block(k2, buf + i * 16);
        for (int j = 0; j < 16; j++)
            buf[i * 16 + j] ^= tweak[j];  /* post-whiten */
        xts_mul_alpha(tweak);             /* advance to next block */
    }
}

XTS and its two-key structure

The IEEE 1619 standard defines XTS, the construction used for sector-level disk encryption. It takes two keys. The first encrypts the sector number to produce a 128-bit tweak value; the second is the block cipher key. Each block within the sector is whitened with the current tweak, encrypted, and whitened again, and the tweak is multiplied by the primitive element $\alpha$ in $\mathrm{GF}(2^{128})$ between blocks.

The multiplication by $\alpha$ is a cheap operation: a left shift with a conditional XOR by the reduction polynomial. It ensures that adjacent blocks within a sector use distinct tweaks, so that identical plaintext blocks at different offsets produce different ciphertexts. The sequence of tweaks has period $2^{128} - 1$ before repeating, which is far longer than any sector. The whitening itself is an XOR of the same 16-byte value into every block of the sector, so it costs one vector XOR per block and leaves the state layout of the underlying cipher untouched.

The two keys are used for different purposes, and the standard requires them to be independent — deriving both from one key by a KDF is acceptable, using the same key for both is not. The reason is that the tweak-encryption function’s output is public in the sense that it can be computed by anyone with the first key, and if the two keys were equal, the construction would collapse into a single-key scheme whose security argument no longer holds. The exact reduction is not tight, and the standard’s requirement of independent keys is a conservative choice.

XTS has a specific weakness that is worth understanding because it is often misunderstood. It provides confidentiality only. It does not detect modification: an attacker who can write to the disk can swap two ciphertext blocks within a sector, or swap two whole sectors, and the result decrypts to a valid plaintext with the blocks transposed. XTS has no authentication tag and no redundancy to detect this. The defence is a separate integrity layer, such as a Merkle tree over sector hashes stored elsewhere, or an authenticated mode applied above the sector layer.

The construction also has a ciphertext-stealing variant for sectors whose length is not a multiple of the block size. The final two blocks are handled by a procedure that truncates and swaps bytes so that the total length is preserved without padding. The procedure is fiddly and is a common source of implementation bugs: the swap must be done in the right order, and the tweak for the final block must be advanced correctly.

Threefish and the tweak as part of the state

Threefish takes the opposite approach: rather than whitening around a standard cipher, it builds the tweak into the round function. The state is 256, 512, or 1024 bits, held as four, eight, or sixteen 64-bit words. The tweak is 128 bits, injected as two words into positions determined by the round number, and the subkey injection every four rounds includes the tweak words in a fixed pattern.

The design’s argument is that the tweak is treated exactly like key material in the injection schedule, so its influence propagates through the same diffusion as the key. The cost is that the tweak must be available at every subkey injection, which is fine because it is public and can be held in registers. The benefit is that the construction needs no whitening layer and no multiplication in a finite field.

Threefish’s round function is ARX — additions, rotations, XORs — with rotation constants that differ per round and per position. The design uses 72 rounds for the 256-bit variant and 80 for the larger ones, with the round count chosen to provide margin against the best known attacks rather than derived from a branch-number argument. The tweakable structure is part of the round function, not a wrapper around it, which is a genuinely different architectural choice from XTS.

Why not tweak everything

The cost of a tweakable cipher is not in the tweak but in the loss of flexibility. A standard cipher can be used in any mode; a tweakable cipher’s tweak is part of its interface, and modes built on it must supply a tweak per block. That is natural for storage, where the tweak is the block address, and awkward for protocols where there is no natural per-block index.

There is also a security-margin cost. A tweakable cipher must resist attacks that choose tweaks adversarially, including attacks that hold the tweak fixed and vary the key, or that exploit relations between tweaks. The proof that a construction is a tweakable PRP is generally in the ideal-cipher model, and the reduction’s tightness determines how many blocks can safely be encrypted under one key. For XTS the bound is around $2^{64}$ blocks for a 128-bit block, which for 4 KiB sectors is about $2^{52}$ sectors — a large but not unlimited figure, and one that matters for full-disk encryption over years.

The alternative to a tweakable cipher is a mode that synthesises the tweak from the block index, as counter mode does with its nonce and counter. That works for confidentiality but not for the random-access property storage needs: a sector must decrypt without decrypting everything before it, and counter mode satisfies that only if the counter can be computed from the sector number, which is exactly the tweak. The distinction between a tweakable cipher and a mode is therefore mostly about where the index enters — inside the permutation or in the surrounding construction — and both designs appear in practice.

Within this cluster, the tweak’s injection point connects to the diffusion argument: a tweak that enters before the first round is protected by the same active S-box counting as the key, whereas one that enters after the last round is not protected at all. That is the same principle as key schedule design, applied to a value that is public but position-dependent. The parallel is exact enough to be a useful check when evaluating a new tweakable construction: ask where the tweak enters relative to the nonlinear layer, and the security argument follows from the answer.

A late tweak injection is a differential distinguisher with probability one, which is the strongest form of the weakness that differential cryptanalysis searches for. That framing is more useful than the informal “tweak must be mixed in well”: it identifies the failure as a deterministic characteristic, and deterministic characteristics cannot be fixed by adding rounds.