No Room for a Nonce: Disk and Length-Preserving Encryption, from XTS to FPE

1. Two Failures, One Cause#

A security team did everything the checklist demanded. They encrypted a server's disk with AES-XTS, the mode NIST approved for storage devices ^[1], and confirmed the volume was unreadable without the key. Months later an attacker with write access to that volume rolled the machine back to a vulnerable kernel, flipped a policy byte, and corrupted a specific database page -- never learning a single byte of plaintext, never touching the key, and never tripping an alert. The disk was still, technically, encrypted the entire time.

Two floors down, a different team faced a legacy analytics pipeline that would only accept six-digit codes -- a short, PIN-length field of exactly the kind format-preserving encryption was built to protect. They enciphered each real code into a different but still-valid six-digit code and moved on.

An analyst with query access to the encryptor then rebuilt the entire mapping from fewer query pairs than there are codes -- a few hundred thousand, an afternoon's compute -- and read every value behind it ^[2][3]. That is the same weakness that broke the FF3 standard outright, and Section 8 will put exact numbers on it.

Two very different systems, two very different failures. They share one root cause, and naming it is the whole point of this article.

Both teams were forced into length preservation. A disk sector is a fixed 512 or 4096 bytes with no spare room; a code field is exactly six digits wide.

When you cannot add even one byte, two tools that every modern cipher leans on vanish at once. You lose the nonce, the fresh random input that makes encrypting the same message twice produce different ciphertext. And you lose the tag, the short checksum an authenticated cipher appends so the receiver can reject anything tampered with. Remove both, and encryption collapses back to its oldest form: a single keyed permutation on a fixed set of values.

Length preservation forces two properties at once. The cipher is deterministic -- identical plaintext at the identical position under the identical key always yields identical ciphertext -- so the best security you can even ask for is that it look like a random permutation, never the semantic secrecy of a randomized cipher. And it is unauthenticated -- with no tag there is nothing to reject, so it is malleable by construction.

That is why the first team's disk could be rewritten by someone who could not read it. There was no tag to say "no." And it hints at why the second team's codes fell: a permutation is only as good as the space it hides in is large. Everything that follows lives on exactly two knobs.

flowchart TD
Root["Every length-preserving cipher is one point in width by domain space"]
Root --> Disk["Large domain: a whole disk or volume"]
Root --> Field["Small domain: a fixed-format field"]
Disk --> XTS["Narrow width, AES-XTS, 16-byte diffusion"]
Disk --> Wide["Wide width, Adiantum and HCTR2, whole-unit diffusion"]
Field --> FPE["Format-preserving, FF1 and FF3-1, domain is the ceiling"]

Block width is how far a single changed input bit diffuses through the output. Domain size is how many possible values the permutation is defined over. Narrow width and a large domain give you AES-XTS; wide width and a large domain give you Adiantum and HCTR2; a deliberately tiny domain, at any width, gives you format-preserving encryption.

Format-preserving encryption was designed for exactly the small field the second team reached for -- a PIN, a short code, the six middle digits of a card number a processor still has to parse -- which is why that column fell so cheaply. A full sixteen-digit card number, it turns out, is far more expensive to recover, because the cost scales with the size of the domain, not with the format; Section 8 quantifies both.

This is Part 9 of the series. It assumes you take AES as a pseudorandom permutation for granted, that you met authenticated encryption in Part 7, and that you have the security definitions from Part 1. To see why the whole field reduces to these two knobs, start where both problems were born: in a disk sector and a database column that both refused to grow.

2. Two Problems With the Same Shape#

Rewind to the turn of the millennium. Two engineers, in two industries that never spoke to each other, hit the same wall.

The first was a storage engineer. A disk is an array of fixed sectors, and the encryption layer sits underneath the filesystem, transparent to it. Sector number 8,675,309 must encrypt to exactly 512 bytes and decrypt back in place, with no per-sector header to stash an initialization vector. So where does the IV go?

The naive answer, Electronic Codebook mode, encrypts each 16-byte block independently under one key. It needs no IV at all -- and it leaks catastrophically. Identical plaintext blocks produce identical ciphertext blocks everywhere on the disk, so the structure of files, repeated records, and zeroed regions survives encryption in plain sight. This is the famous "ECB penguin": encrypt a bitmap of the Linux mascot Tux in ECB mode and the penguin is still perfectly visible in the ciphertext, because the cipher preserves every repeated block ^[4].

Cipher Block Chaining with a per-sector IV helps, but if that IV is predictable an attacker can mount watermarking attacks -- planting files whose ciphertext betrays their presence -- and CBC on a disk stays malleable end to end. Clemens Fruhwirth's 2005 survey of hard-disk encryption catalogs exactly these failure modes ^[5].

The second engineer worked in payments. A legacy mainframe validates that a primary account number is sixteen digits and passes a checksum; it will reject anything else. You must encrypt that field so downstream systems still see a well-formed account number. Practitioners called this "datatype-preserving encryption" and traded folklore recipes through the 1990s.

In 2002 John Black and Phillip Rogaway gave the problem a real security model in a paper titled Ciphers with Arbitrary Finite Domains ^[6]. They contributed two reusable techniques that every later scheme inherits: cycle-walking (encipher a value under a larger cipher and re-encrypt until the result lands back in the target set) and a Feistel network over a radix (build a permutation on the integers modulo N from keyed round functions).

Here is the observation that unifies the two stories. When you cannot spend a single byte, you are not choosing between encryption modes; you are choosing a permutation on exactly this space. And the theory for that had already been written.

In 1999 Moni Naor and Omer Reingold, revisiting the classic Luby-Rackoff construction, named the right target -- a strong pseudorandom permutation -- and showed that a wide one, enciphering a whole block at once, could be built cheaply from simpler parts ^[7]. That result sat mostly unused for two decades. Both the disk world and the payments world were, without knowing it, asking Naor and Reingold's question.

timeline
title The two rails of length-preserving encryption, 1999 to 2025
1999 : Naor-Reingold, a wide strong PRP can be built cheaply
2002 : Black-Rogaway formalize FPE : LRW names the tweak
2004 : XEX fixes the tweak for disks
2007 : XTS-AES standardized for storage
2016 : NIST approves FF1 and FF3
2017 : FF3 broken by Durak-Vaudenay
2018 : Adiantum published, wide-block from hash-encrypt-hash
2021 : HCTR2 published : FF3-1 broken by Beyne
2025 : NIST removes FF3 and FF3-1

The nonce that length preservation takes away is the subject of Part 2; here it is simply gone. Both camps reached for the same fix at almost the same moment -- a tweak, a public per-position input that re-keys the permutation cheaply for each sector or each field. It worked. Then it failed, in a way that taught the field its first hard lesson about where key material is allowed to appear.

3. The First Answers, and Why They Broke#

The first generation of real answers shared a blind spot: they confused diffusion with security, and format with strength. Three named near-misses show the confusion, and each taught a lesson the survivors still carry.

ESSIV: a real fix that fixed the wrong thing#

Fruhwirth's ESSIV -- Encrypted Salt-Sector IV -- attacks the predictable-IV problem head on. Instead of deriving the CBC initialization vector from the visible sector number, it computes $\mathrm{IV} = E_{\mathrm{salt}}(\text{sector})$ with $\mathrm{salt} = H(K)$, so the IV is a secret function of the key and an attacker can no longer predict it ^[5]. Watermarking dies.

But ESSIV is a fix to confidentiality leakage, not to tampering: the underlying CBC is still malleable, and its diffusion runs only forward, so a flipped ciphertext bit corrupts one block and predictably flips the corresponding plaintext bit in the next. ESSIV made the disk harder to read. It did nothing to make it harder to rewrite.

The Elephant diffuser: a diffuser is not a MAC#

Microsoft's first BitLocker, shipped in Windows Vista, saw the malleability problem and answered it with engineering muscle. Niels Ferguson's 2006 design bolts an unkeyed, invertible diffuser -- nicknamed Elephant -- onto AES-CBC, explicitly "to improve security against manipulation attacks" ^[8]. The diffuser spreads any single changed bit across the entire sector, so tampering yields sector-wide noise instead of a clean bit-flip. That feels like integrity. It is not.

LRW: a cipher defeated by encrypting its own key#

The line that actually led somewhere abandoned chaining for a tweak. In 2002 Moses Liskov, Ronald Rivest, and David Wagner formalized the idea ^[10].

Their LRW mode computes $C = E_{K_1}(P \oplus \Delta) \oplus \Delta$ with the mask $\Delta = K_2 \otimes i$, where $K_2$ is a second key, $i$ is the block index, and $\otimes$ is multiplication in the finite field $\mathrm{GF}(2^{128})$. Each block gets its own location-bound permutation, fully parallel and random-access. It was the right shape -- and it carried a fatal detail.

The mask is built from raw key material. On a disk that is not hypothetical: a full-disk-encryption key can be paged or hibernated onto the very disk it protects, so a plaintext block can equal the tweak key $K_2$ itself. And because the mask is a linear function of $K_2$, a handful of such known blocks are enough to recover it.

FPE's first generation: format is not strength#

On the payments rail, Black and Rogaway's cycle-walking and Feistel-over-radix were the first rigorous constructions ^[6]. They are elegant and correct -- and they quietly encode the domain problem that will dominate the rest of this article.

The demo below enciphers four-digit values into four-digit values by cycle-walking a toy 16-bit permutation down into the range 0 to 9,999. Notice two things: the output is always a valid four-digit number, and the same input always maps to the same output. Format is preserved, determinism is total -- and the whole security rests on how large that range is.

// Enciphering 4-digit values using a bigger permutation, then walking back into range.
// The toy 16-bit map is a Feistel network, which is a bijection for ANY round function.
function roundF(half, k) {
return ((half * 167) ^ (k * 91) ^ ((half << 3) & 0xFF)) & 0xFF;
}
function feistel16(x, keys) {
let L = (x >> 8) & 0xFF, R = x & 0xFF;
for (let r = 0; r < 4; r++) {
  const nL = R, nR = L ^ roundF(R, keys[r]);
  L = nL; R = nR;
}
return ((L << 8) | R) & 0xFFFF;
}
const KEYS = [23, 57, 131, 200];
const N = 10000; // the 4-digit domain: values 0000..9999

function fpeEncrypt(x) {
let y = feistel16(x, KEYS), walks = 0;
while (y >= N) { y = feistel16(y, KEYS); walks++; }
return { y: y, walks: walks };
}

for (const v of [1, 42, 1234, 9999]) {
const r = fpeEncrypt(v);
console.log(String(v).padStart(4,'0') + ' -> ' + String(r.y).padStart(4,'0') + '   (walks: ' + r.walks + ')');
}
console.log('Deterministic: encrypting 1234 twice gives ' + fpeEncrypt(1234).y + ' both times.');

LRW's lesson was precise: never let key material into the mask; derive the offset from the cipher itself. That one idea, written $\Delta = E_K(i) \cdot \alpha^j$, is the hinge on which the entire disk rail now turns.

4. The Climb, Generation by Generation#

Now the climb begins. Two rails, and every generation is motivated by a concrete, named failure of the one before it.

flowchart TD
subgraph Disk["Disk rail: the block-width climb"]
ECB["ECB, no diffusion"] -->|"leaks patterns"| CBC["CBC with ESSIV"]
CBC -->|"still malleable"| LRW["LRW tweak"]
LRW -->|"key material leaks"| XEX["XEX offsets"]
XEX -->|"two keys and stealing"| XTS["XTS-AES"]
XTS -->|"still too narrow"| WIDE["Adiantum and HCTR2"]
end
subgraph FPErail["Format-preserving rail: the domain-size limit"]
BR["Black-Rogaway model"] -->|"parameterize"| FFX["FFX and BPS"]
FFX -->|"standardize"| FF["FF1 and FF3"]
FF -->|"FF3 broken 2017"| FF31["FF3-1"]
FF31 -->|"broken again 2021"| REMOVED["Removed by NIST 2025"]
end

From XEX to XTS: the offset that carries no key#

Phillip Rogaway's 2004 XEX construction applies LRW's lesson exactly ^[11]. It uses a single key and derives the per-block offset from the cipher: encipher the data-unit number once, then step the offset across block positions by repeatedly multiplying by the field element alpha. No key material ever enters the mask.

flowchart LR
I["Data-unit number i"] --> E2["Encrypt i under key K2"]
E2 --> A["Multiply by alpha, once per block position j"]
A --> D["Offset for block j"]
P["Plaintext block Pj"] --> X1["XOR with the offset"]
D --> X1
X1 --> E1["Encrypt under key K1"]
E1 --> X2["XOR with the offset again"]
D --> X2
X2 --> C["Ciphertext block Cj"]

The multiply-by-alpha step is why XTS is fast and parallel. Multiplying by alpha in this field is just a one-bit left shift of the 128-bit offset followed by a conditional XOR with the reduction constant 0x87 when the top bit overflows. No general multiplier is needed, and every block's offset can be computed independently. The simulator below advances the offset exactly this way and enciphers the same plaintext block at four consecutive positions. The ciphertext differs every time -- position binding -- while re-running the demo reproduces it exactly -- determinism.

// Advance the per-block offset by multiply-by-alpha in GF(2^128),
// then encipher each block as C = E(P XOR offset) XOR offset.
function mulAlpha(t) {                 // t: 16-byte little-endian offset
let carry = 0;
for (let i = 0; i < 16; i++) {
  const b = t[i];
  t[i] = ((b << 1) | carry) & 0xFF;
  carry = b >>> 7;
}
if (carry) t[0] ^= 0x87;            // reduction for the field GF(2^128)
return t;
}
function toyCipher(block, key) {        // a stand-in permutation with diffusion, NOT real AES
const out = Uint8Array.from(block);
for (let r = 0; r < 3; r++) {
  let acc = (key + r * 97 + 1) & 0xFF;
  for (let i = 0; i < 16; i++) {
    acc = (acc + out[i] + key + i * 31) & 0xFF;
    out[i] = (out[i] ^ acc ^ 0x5A) & 0xFF;
  }
  for (let i = 1; i < 16; i++) out[i] = (out[i] + out[i - 1]) & 0xFF;
}
return out;
}
function hex(a) { return Array.from(a, b => b.toString(16).padStart(2, '0')).join(''); }

const seed = new Uint8Array(16); seed[0] = 0x01;   // stands in for Encrypt(i) under K2
let offset = Uint8Array.from(seed);
const plaintext = new Uint8Array(16).fill(0xAA);   // the SAME plaintext at every position

for (let j = 0; j < 4; j++) {
const masked = new Uint8Array(16);
for (let i = 0; i < 16; i++) masked[i] = plaintext[i] ^ offset[i];
const enc = toyCipher(masked, 0x3C);
const ct = new Uint8Array(16);
for (let i = 0; i < 16; i++) ct[i] = enc[i] ^ offset[i];
console.log('position ' + j + '   offset ' + hex(offset).slice(0,12) + '..   ciphertext ' + hex(ct).slice(0,12) + '..');
mulAlpha(offset);                                 // step to the next position
}
console.log('Identical plaintext, different position, different ciphertext.');

XTS-AES, standardized as IEEE 1619-2007 and adopted by NIST as SP 800-38E, turns XEX into a shippable disk mode ^[12][1]. It uses two independent keys -- one to encipher, one to derive the tweak from the data-unit number -- and adds a trick for data units whose length is not a whole number of blocks.

NIST caps a single XTS data unit at $2^{20}$ AES blocks, or 16 MiB ^[1]. And an "AES-256-XTS" key is therefore two 256-bit keys, 512 bits in total -- a fact that trips up more implementers than any other on this list. XTS is excellent at what it does, but three residual limits, all inherent to a narrow block, drive everything after it: it diffuses across only one 16-byte block, it is unauthenticated, and it leaks equality of identical blocks at identical positions.

The wide-block ideal, briefly#

If narrow diffusion is the problem, the obvious cure is to encipher the entire data unit as one wide block, so that flipping any single bit re-randomizes the whole sector. Shai Halevi and Phillip Rogaway built exactly this: CMC in 2003 and the parallelizable EME in 2004 are wide-block strong PRPs over a whole variable-length unit ^[13][14]. They are the ideal that XTS only approximates.

They also cost roughly two block-cipher passes over every byte, with no hardware primitive to accelerate the whole construction the way AES-NI accelerates XTS, and they carried patent clouds. So they never became the disk default, surviving only as a niche (EME2 lives in IEEE Std 1619.2 ^[15]).

The wide ideal was known for fifteen years before it was cheap enough to ship -- and the thing that made it cheap was the 1999 Naor-Reingold result waiting in the wings ^[7]. Hold that thought; it is the next section.

The format-preserving rail: FFX, BPS, and the NIST methods#

On the payments side, the community turned Black-Rogaway's Feistel-over-radix into concrete, submittable modes with public tweaks and fixed round counts. Two proposals mattered. FFX, from Mihir Bellare, Phillip Rogaway, and Terence Spies, uses a larger tweak and about ten rounds -- the conservative choice ^[16]. BPS, from Eric Brier, Thomas Peyrin, and Jacques Stern, uses a compact per-message tweak and fewer rounds for speed ^[17].

A third submission, VAES3, became the draft method FF2 but was withdrawn before finalization over a security concern. The withdrawal is documented in a 2015 analysis, "Analysis of VAES3 (FF2)" ^[18]; when NIST published its standard the next year, only FF1 and FF3 remained. When NIST finalized SP 800-38G in 2016, it approved exactly two methods: FF1, from FFX, with ten Feistel rounds and a large tweak; and FF3, from BPS, with eight rounds and a 64-bit tweak ^[19]. Both are AES-backed unbalanced Feistel networks over the message radix, and the standard required a minimum domain of at least 100 values, recommending at least one million.

flowchart TD
Split["Digit string split into halves A and B"] --> Round["Round function: AES-based PRF over round number, tweak, and half B"]
Round --> Combine["Add the PRF output into half A, modulo radix to the m, the half's range"]
Combine --> Swap["Swap the halves and repeat for every round"]
Swap --> Out["Recombine into a same-length digit string"]

The difference that matters downstream is precisely FF3's smaller tweak and fewer rounds versus FF1's larger tweak and ten rounds ^[19]. FF3 bought speed by spending security margin. Within a year, someone came to collect.

Each rail had reached a plateau. XTS was narrow; FF3 was fast and fragile. What the field lacked was not another cipher but a reframing -- one that would explain both plateaus at once and, in the same move, make the wide permutation cheap enough to deploy.

5. The Right Target Was a Permutation All Along#

Step back from the individual ciphers and ask what you are actually allowed to want. Not the secrecy of a randomized message -- there is no randomness. Not integrity -- there is no tag. What you can ask for is the best keyed permutation over this exact space, one that behaves like a randomly chosen permutation even against an adversary who can query it forward and backward.

That is a tweakable strong pseudorandom permutation, and once you name it, the whole field snaps into focus. XTS is a narrow approximation of it. CMC and EME are wide but expensive versions of it. Every FF method is a version of it on a tiny domain.

Two ideas define the modern state of the art, one for each rail. The first is how to make the wide permutation cheap. Naor and Reingold's 1999 insight was that you do not need two full cipher passes to get a wide strong PRP; you can sandwich a small amount of real cipher work between two passes of fast keyed hashing ^[7]. This is the hash-encrypt-hash shape, and it is the skeleton of both deployed wide-block modes.

flowchart LR
P["Whole data unit, plaintext"] --> H1["Keyed universal hash over the whole unit"]
H1 --> Mid["One narrow primitive call on a short middle block"]
Mid --> H2["The same keyed hash, applied again"]
H2 --> C["Whole data unit, ciphertext"]

Adiantum instantiates it with NH and Poly1305 hashing wrapped around a single AES call and an XChaCha12 stream cipher ^[20]. HCTR2 instantiates it with POLYVAL hashing around an XCTR-over-AES core ^[21]. The payoff is the second surprise of this article: the wide ideal is not intrinsically expensive. Adiantum runs at 10.6 cycles per byte on an ARM Cortex-A7, over five times faster than AES-256-XTS implemented in software on the same chip ^[20]. The mode that gives you whole-sector diffusion is faster than narrow XTS on hardware that lacks an AES instruction.

Why one narrow call is enough, and why it is strong#

It is easy to assert that Adiantum and HCTR2 are strong pseudorandom permutations. It is more useful to see why, because the reason is the entire point of the hash-encrypt-hash shape. Take Adiantum concretely. Split the data unit into a long left part $P_L$ (the bulk of the sector) and a single block-sized right part $P_R$. Four steps encipher it:

$P_M = P_R \boxplus H_k(T, P_L), \qquad C_M = \mathrm{AES}(P_M),$

$C_L = P_L \oplus \mathrm{stream}(C_M), \qquad C_R = C_M \boxminus H_k(T, C_L).$

Here $H_k$ is a fast keyed almost-universal hash (NH plus Poly1305 in Adiantum), $T$ is the tweak, $\boxplus$ and $\boxminus$ are addition and subtraction on one block, and $\mathrm{stream}$ is a stream cipher (XChaCha12) seeded by the single enciphered block. Read it as three beats.

The first hash layer buys unpredictability. Because $H_k$ is keyed and depends on the entire left bulk, the input $P_M$ to the one real cipher call is a secret function of the whole message. An adversary cannot steer that middle input: change any part of $P_L$ and $P_M$ jumps unpredictably, so two distinct queries land on essentially independent middle inputs.

The middle is why one narrow pass suffices. The hash has already done the wide mixing, so the cryptographic core only has to supply pseudorandomness on a single block. That is why one AES call can stand in for a full wide-block cipher pass -- the expensive part was never the enciphering, it was the diffusion, and cheap keyed hashing does the diffusion.

The second hash layer spreads the result back out. Running the stream cipher over the bulk and folding the enciphered block back through the hash makes one changed input bit rewrite the entire unit -- wide-block avalanche, built from one block-cipher call and two linear-time hash passes.

Now the part that makes it a strong PRP, secure even against an adversary who queries decryption. The construction is symmetric and invertible, so the identical "you cannot steer the middle" argument runs backward for inverse queries: a decryption query is just as unable to force a chosen middle block as an encryption query is.

An adversary mixing adaptive forward and inverse queries can win only by making two queries collide on the same middle block $P_M$ -- and because $H_k$ randomizes that block, a collision is a birthday event of probability about $q^2 / 2^b$ for $q$ queries and a $b$-bit block. That two-directional birthday bound is strong-PRP security; it is Adiantum's "provable quadratic advantage bound" ^[20].

This is Naor and Reingold's insight in operational form: two universal-hash layers do the work of the outer rounds of a Feistel network, so a single cryptographic core reaches the strong PRP that Luby-Rackoff needs four Feistel rounds -- and CMC or EME need two full cipher passes -- to reach ^[7].

"HCTR2 is a tweakable super-pseudorandom permutation: any change to the plaintext will result in an unrecognizably different ciphertext." -- the google/hctr2 project README ^[22]

The second idea is the hard one, and it lives on the format-preserving rail. There is no reframing that saves small-domain FPE, because the enemy is not the cipher's construction; it is the size of the set.

So the community's real progress on FPE was an act of acceptance: minimum-domain floors are not conservative style, they are load-bearing defenses, and a field too small to defend should not be format-preserved at all. That verdict is the subject of Section 8. For now, hold both realizations together.

Wide-block enciphering is the disk field finally reaching the ideal permutation that XTS only approximated -- and doing it cheaply. But reaching the ideal permutation changes nothing about integrity: even a perfect tweakable SPRP has no tag, so tampering still produces plaintext the layer above will consume. Wide-block fixes diffusion. It does not, and cannot, add authentication.

So the wide permutation shipped. Which raises the obvious question, and its genuinely surprising answer: if wide-block is provably better and can run faster, why is the disk in front of you -- and the phone in your pocket -- still enciphering its contents with narrow XTS?

6. What Actually Ships in 2026#

Here is the deployed map, and its most honest surprise: the better cipher shipped, but not where you would guess. The wide-block permutation went to phones -- for filenames and for chips without an AES instruction -- while the contents of nearly every encrypted volume on Earth are still enciphered with narrow XTS.

AES-XTS -- the mode, not a fixed key size -- is the universal full-volume default. BitLocker has defaulted to XTS-AES since Windows 10 version 1511 ^[9]. Apple states plainly that "FileVault uses the AES-XTS data encryption algorithm to protect full volumes on internal and removable storage devices" ^[23]. On Linux, LUKS and dm-crypt default to aes-xts-plain64 ^[24]. Three operating systems, three vendors, one narrow-block mode.

What is not universal is the key size, and conflating the two is a frequent error: BitLocker and FileVault default to AES-128-XTS -- Microsoft's own menu lists "XTS-AES 128-bit (default)" ^[25], and FileVault's often-quoted "256-bit key" is the two-key XTS total of two 128-bit keys -- while LUKS and dm-crypt default to AES-256-XTS, a 512-bit volume key, because an XTS key size is twice the underlying AES key ^[26]. The BitLocker architecture post covers the Windows side of this in depth.

File-based encryption is where wide-block actually ships, and its details are the single most mis-stated fact in this area. In Android and Linux fscrypt, on hardware with AES acceleration, file contents use aes-256-xts and filenames use aes-256-hctr2; the AOSP documentation says HCTR2 has been the "preferred mode of filenames encryption for devices with accelerated cryptography instructions" since Android 14, and is planned to become the default ^[27]. On hardware without AES acceleration, Adiantum encrypts both contents and filenames ^[27][28]. The Adiantum announcement is often mis-cited. Its actual title is "Introducing Adiantum: Encryption for the Next Billion Users" ^[29]; the "entry-level processors" phrasing comes from the research paper's subtitle, not the blog post.

On the payments rail, the map collapsed to a single survivor. NIST's second public draft of SP 800-38G Revision 1, dated February 2025, states that "the encryption method FF3 is no longer specified," leaving FF1 as the sole NIST-approved format-preserving method ^[30].

Integrity is a first-class part of the picture, not a footnote#

Because none of these permutations authenticate anything, real systems bolt integrity on at an adjacent layer, and that layer is genuinely part of the state of the art:

• dm-verity builds a Merkle hash tree over a read-only volume and verifies every block on read against a trusted root hash. It is how Android Verified Boot detects any modification of a system image ^[31].
• dm-integrity keeps a per-sector integrity journal for read-write volumes; combined with dm-crypt it detects modification -- alter the device and the read returns an I/O error instead of forged plaintext -- at a storage and write cost ^[32]. It does not stop rollback or replay: the per-sector tag has no freshness anchor, so restoring a sector's own earlier authentic ciphertext-and-tag pair still verifies. Anti-rollback needs an externally-anchored root, whose options Section 9 spells out in full.
• fscrypt's per-file nonce is a random 16-byte value per file, fed through HKDF-SHA512 to derive a per-file key, so identical plaintext in two different files does not produce identical ciphertext ^[33]. It restores the per-unit uniqueness that a bare deterministic cipher throws away.

flowchart TD
Data["Data at rest"] --> Conf["Confidentiality: XTS, Adiantum, or HCTR2, with no tag"]
Conf --> Q{"Is tamper in scope?"}
Q -->|"read-only image"| Verity["dm-verity: read-only Merkle root, resists rollback"]
Q -->|"read-write volume"| Integ["dm-integrity: modification only, no freshness anchor"]
Q -->|"per-file uniqueness"| Nonce["fscrypt 16-byte nonce"]
Q -->|"room to expand"| AEAD["Use an AEAD one layer up"]

The engineering even shows in the key management: an Adiantum key carries more per-key overhead than an AES-256-XTS key, which is why fscrypt offers a DIRECT_KEY option to amortize it. ※ This is the kind of detail that reveals which mode a platform expects to be common: the optimization exists because Adiantum keys are the expensive case ^[33]. The map now shows three disk permutations and one surviving FPE method, each optimizing something different. To choose among them you need the head-to-head -- and one decisive question that sits above all four.

7. Narrow, Wide, or Authenticated#

The question everyone asks is "which length-preserving cipher should I use?" The better question sits one layer up. Start with the disk contenders head to head.

The table has a punchline. On AES hardware, XTS and HCTR2 are close in speed, and HCTR2's only advantage is diffusion -- better tamper behavior and no same-offset leak -- never authentication ^[21][1]. If tampering is in your threat model, none of the three columns on the left answers it. Only the right-hand column does.

"Which length-preserving cipher?" is downstream of a prior question: am I actually forced to be length-preserving, or can I add a tag one layer up? If you can spend even a few bytes, the honest answer is not a better permutation but authenticated encryption -- the subject of Part 7 of this series. Length-preserving modes are what you reach for only when expansion is genuinely impossible.

That framing is exactly why 2026 deployment keeps XTS for contents (fast, accelerated, random-access) and adds wide-block only where it cheaply helps -- HCTR2 for filenames, Adiantum where there is no AES instruction -- while putting authentication in dm-verity, dm-integrity, or a per-file nonce ^[32].

FF1 versus FF3-1, calibrated#

On the format-preserving rail the head-to-head is narrower, and it is easy to read it wrong.

Do not read this as "FF1 secure, FF3-1 broken, done." All small-domain format-preserving encryption leaks; FF1's larger tweak and ten rounds simply give it a wider margin, not immunity. FF1 is the more defensible choice, not a substitute for a genuinely large-domain permutation. The break that removed FF3-1 was structural to the FF3 family, which is why no tweak-size tuning saved it.

Every trade-off in both tables bottoms out in the same two limits: block width and domain size. It is time to show that these are not engineering accidents that a cleverer design will someday fix. They are theorems -- and one of them has a measurable height.

8. What Length Preservation Makes Impossible#

Everything so far could be read as "we just need a better cipher." We do not. Three of these limits are theorems, and the fourth is a wall no cipher climbs -- but it is a wall you can measure. The security definitions behind them come from Part 1.

First theorem: no expansion means no randomness, so the cipher is deterministic. Semantic security against a chosen-plaintext attacker -- the IND-CPA notion -- provably requires that encrypting the same message twice can produce different ciphertexts. A length-preserving cipher has nowhere to put the randomness that would make that happen, so IND-CPA is unreachable by construction. The best achievable target is indistinguishability from a random permutation, an SPRP. This is not a weakness of XTS; it is the ceiling for anything that refuses to expand.

Second theorem: no expansion means no tag, so there is no integrity. With zero expansion there is nothing to carry a MAC, so every ciphertext decrypts to some plaintext and the cipher can never reject a forgery. A length-preserving cipher can only randomize on tamper (wide-block) or permit position-bound edits (narrow-block). It can never say "no." Authentication is provably outside the primitive and must live at another layer.

Third theorem: a per-position tweak leaks equality at its own granularity -- but be precise about which positions. A deterministic tweakable cipher with a public per-position tweak necessarily reveals when two positions hold identical plaintext. XTS leaks equality of identical 16-byte blocks at the same key, data unit, and block index. It does not leak equality of two identical sectors at different offsets: every data-unit index feeds its own tweak, so the same 512 bytes at sector 10 and sector 20 encipher to completely different ciphertext.

The one place byte-identical plaintext does collide is file-relative. In file-based encryption such as fscrypt, where each file's data-unit index restarts at zero, two byte-identical files would run through the same tweak sequence and encipher identically -- which is exactly why fscrypt derives a distinct per-file key from a random 16-byte nonce, so even identical files no longer collide ^[33].

This is not a whole-volume claim: under whole-disk dm-crypt with absolute-sector tweaks, two identical files at different offsets get different data-unit numbers and therefore different tweaks, and do not collide -- the only equality leak there is between data units that share the same key and tweak, such as one logical block rewritten in place. Wide-block modes do not remove this addressing-model leak; they only push its boundary out from a 16-byte block to the whole unit.

The fourth limit: the small-domain wall, measured#

The deepest cut is on the format-preserving rail, and it is not a theorem about any cipher's construction. It is a theorem about the domain. For a permutation over a set of size $N$, message recovery and codebook reconstruction are achievable in work that is polynomial in $N$. Security does not fall off a cliff at some threshold; it degrades smoothly toward zero as the field shrinks.

The attack line is a decade of steadily sharper results: Bellare, Hoang, and Tessaro gave the first message-recovery attacks that exploit the small domain rather than any flaw in the round function ^[37]; Hoang, Tessaro, and Trieu generalized them in a paper aptly titled The Curse of Small Domains ^[34]; and Hoang, Miller, and Trieu pushed the FF3 attack out to large domains ^[3].

Put numbers on it, because the numbers are the payoff. Durak and Vaudenay's 2017 break of FF3 -- the one that broke a deployed NIST standard outright -- runs in time about $\mathrm{radix}^{5n/2}$, which for an $n$-digit field of size $D = \mathrm{radix}^{n}$ is $D^{2.5}$, using about $\mathrm{radix}^{11n/12} = D^{11/12}$ adaptively chosen plaintext-ciphertext pairs under two related tweaks ^[38][2].

Two features make this devastating rather than academic. First, the data cost $D^{11/12}$ is sublinear in the domain: you need fewer query pairs than there are values in the field. Second, the attack recovers the round functions themselves, so it yields "any plaintext under any tweak" -- a key-equivalent break, not the exposure of a single record ^[38]. NIST's own note put the cost at roughly $2^{75}$ steps for a nine-digit field such as a Social Security number ^[38].

Two years later Hoang, Miller, and Trieu improved the running time from $O(N^5)$ to $O(N^{17/6})$ -- on the order of $D^{17/12}$, about $D^{1.42}$ -- and, as their title Attacks Only Get Better promises, extended the break to large domains rather than only tiny ones ^[3].

The table makes the scaling visceral, and settles one honesty debt the cold open owed you.

A note on the last column: the $2^{50}$ entry for the nine-digit SSN is Hoang, Miller, and Trieu's concrete reported cost for that imbalanced domain (an uneven split, with constant factors folded in), which sits above the symmetric leading term $D^{17/12} \approx 2^{42}$ at $D = 10^9$. Recomputing the header formula alone therefore gives the smaller exponent; no figure in the table changes ^[3].

Read the rows in order. A six-digit field -- a PIN, or the six middle digits of a card, exactly the size FF3 was designed for -- has a million points, and recovering its whole codebook takes a few hundred thousand adaptive pairs and on the order of $2^{30}$ operations, an afternoon of compute. That is the cold open's second failure, now with numbers.

But look at the last row: a full sixteen-digit card number lives in a domain near $10^{16}$, and the same polynomial attack costs about $2^{75}$ by the best known method and about $2^{133}$ by Durak-Vaudenay's $D^{2.5}$ -- which actually exceeds a $2^{128}$ key search. The break tracks the field size, not the cipher and not the format. It is the small field that dies, which is exactly why the honest claim is "a six-digit column falls cheaply," never "a whole card column falls to a few thousand queries."

The crudest version of the attack needs no cleverness at all. If the domain is small, you can simply query every point and write down the codebook.

// A permutation is a lock only if its domain is astronomically large.
// Here N = 1,000,000 (a six-digit field). We recover the ENTIRE codebook
// by brute enumeration -- the worst case for the attacker, and it still wins.
function makeSecretPermutation(n, seed) {
const p = new Int32Array(n);
for (let i = 0; i < n; i++) p[i] = i;
let s = seed >>> 0;
for (let i = n - 1; i > 0; i--) {                 // Fisher-Yates shuffle, toy PRNG
  s = (Math.imul(s, 1103515245) + 12345) & 0x7fffffff;
  const j = s % (i + 1);
  const t = p[i]; p[i] = p[j]; p[j] = t;
}
return p;                                          // secret to the attacker
}
const N = 1000000;                                   // the six-digit domain
const secret = makeSecretPermutation(N, 20260709);
function oracle(x) { return secret[x]; }             // attacker gets only oracle access

const recovered = new Int32Array(N);
let queries = 0;
for (let x = 0; x < N; x++) { recovered[x] = oracle(x); queries++; }

let correct = 0;
for (let x = 0; x < N; x++) if (recovered[x] === secret[x]) correct++;
console.log('domain size N            = ' + N.toLocaleString());
console.log('queries used (brute)     = ' + queries.toLocaleString());
console.log('codebook entries learned = ' + correct.toLocaleString() + ' of ' + N.toLocaleString());
console.log('A 128-bit block hides among 2^128 points. This field hides among ' + N.toLocaleString() + '.');

The demo is deliberately a worst case for the attacker: brute enumeration spends the full $N$ queries and learns the codebook one point at a time. The real attacks in the table do strictly better on all three axes at once. They use sublinear data -- about $D^{11/12}$ pairs, fewer than $N$; they recover the round functions rather than individual points, so the whole codebook and every tweak fall together; and they extend to domains far too large to enumerate by hand. Enumeration is only the ceiling. The cryptanalysis lives well beneath it. Either way, the verdict is identical.

A permutation over a million points is not a lock. It is a puzzle -- and the attacker has all the pieces.

Why FF3-1 could not be patched a second time#

NIST had already conceded the problem in public. Its April 2017 note stated that FF3 "is no longer suitable as a general-purpose FPE method" and floated reducing the tweak from eight bytes to six ^[38]. NIST's fix took the same reduce-the-tweak approach but settled on a more modest cut, and it lived only in a draft: the 2019 initial public draft of SP 800-38G Revision 1 defined FF3-1, shrinking the tweak from 64 to 56 bits -- seven bytes, not the six the researchers had floated -- and mandating a million-value minimum domain ^[39]. The only final NIST format-preserving standard remained the 2016 document, with FF1 and FF3.

Then Tim Beyne broke FF3-1 again in 2021 with a linear-cryptanalysis distinguisher that exploits the FF3 tweak schedule -- each tweak half influences only alternating rounds -- an attack that hits FF3 and FF3-1 but not FF1, whose larger tweak and ten rounds do not share the structure ^[35].

The weakness is structural to the FF3 family, so no third round of tweak-size tuning could close it. NIST removed the method entirely rather than shrink the tweak a third time ^[30].

Every entry tagged "width" or "small domain" is one of the two knobs, and the two tagged "key handling" and "integrity" are the lessons that shaped the survivors. FF3-1 sits apart: its 2021 break is structural -- a linear weakness in the tweak schedule, not a knob you can turn. The disk rail carries an upper-bound limit of its own, from the birthday paradox rather than the domain -- and it is widely misdescribed. Two different numbers get conflated here. XTS, Adiantum, and HCTR2 are birthday-bounded: their distinguishing advantage grows like $q^2 / 2^{128}$ for $q$ enciphered blocks under one key, so collisions become a concern only around $2^{64}$ blocks, and that is a per-key threshold. NIST's cap of $2^{20}$ AES blocks on a single XTS data unit is a separate, far more conservative per-data-unit ceiling that SP 800-38E attributes to IEEE 1619 section 5.1, with no birthday rationale attached ^[1]. The cap is not "where XTS breaks," and the birthday bound is not "why the cap is $2^{20}$"; conflating them invites the false idea that XTS fails at 16 MiB. The format-preserving rail, by contrast, ended exactly where the theorems said it would.

"The encryption method FF3 is no longer specified." -- NIST SP 800-38G Revision 1, Second Public Draft, February 2025 ^[30]

If the limits are theorems and the wall has a measured height, then the open questions are not "can we fix these?" They are "given that we cannot, what should we build next, and what does the honest alternative cost?"

9. Where This Still Bites#

The science here is unusually settled, which makes the genuinely open questions sharp and few.

Why is XTS still the disk-contents default? Wide-block SPRPs are provably better at diffusion and ship in production, yet no mainstream operating system defaults contents to a wide-block mode on AES hardware. The reasons are performance and inertia: XTS is single-pass, parallel, random-access, and accelerated by AES-NI on x86 and the ARMv8 Cryptography Extensions, so at line rate it is very hard to beat.

HCTR2's two POLYVAL passes make it modestly heavier than single-pass XTS on the same accelerated chip, and there is no equally standardized wide-block-for-contents mode for general operating-system use. Android shipped wide-block only where it is cheap and clearly helps -- HCTR2 for filenames, Adiantum for chips without AES -- while keeping XTS for contents ^[27]. When, if ever, contents should move to wide-block on accelerated hardware is a real and unresolved deployment question.

Can authenticated storage be cheap enough to default? Integrity is opt-in today, and it helps to size why. For read-write volumes, dm-crypt plus dm-integrity attaches a per-sector integrity tag; the kernel's own example uses a 4-byte crc32c, but tamper detection against an active attacker needs a keyed MAC such as a 32-byte hmac(sha256) ^[32].

And note what even a cryptographic tag does and does not buy: dm-integrity detects modification only. As Section 6 noted, it has no freshness anchor, so an old authentic pair still verifies; rollback resistance is therefore a separate requirement met only by an externally-anchored root: dm-verity's read-only Merkle root, a TPM or Secure-Boot-measured counter, or per-sector version counters. So the open problem is really two: cheap modification detection and a cheap freshness anchor for read-write data.

The tag is not the expensive part. The expensive part is atomicity: a sector and its tag must be updated together or not at all, and dm-integrity's default journaled mode guarantees that by writing everything twice. The documentation says plainly that it "degrades write throughput twice because the data have to be written twice" ^[32] -- roughly a 2x write amplification, and the real reason authenticated read-write storage stays an expert opt-in. A faster bitmap mode skips the double write, but the same documentation warns it "is also less reliable" ^[32].

Contrast dm-verity: it protects read-only data with a Merkle tree computed once at build time and pinned to an externally-held root -- the freshness anchor dm-integrity structurally lacks -- then merely verified, and cached, on read, with no write path, no journal, no atomic tag update, and optional forward-error-correction adding only about 0.8% space ^[31]. That asymmetry is exactly why verified boot and system images enable dm-verity by default while mutable user data sits on bare dm-crypt.

Whether tamper detection can be made cheap enough to default for read-write data -- rather than paying a doubled write for it -- is the open engineering question. Where expansion is allowed at all, the clean answer stays an AEAD.

Is any small-domain FPE safe, or is tokenization the only honest answer? The decade-long attack line points one way: shrink the domain and you enumerate the permutation in polynomial work. For genuinely small fields, the consistent verdict is that a tokenization vault, not a cleverer cipher, is the defensible design.

Side channels in the radix arithmetic. FPE's Feistel rounds do modular arithmetic over the message radix, and getting that arithmetic both correct and constant-time is subtle. NIST went so far as to ban floating-point arithmetic in FF1 implementations after a rounding bug in Bouncy Castle's FF1 code -- reported by Daniel Bleichenbacher and fixed in a commit titled "Fix rounding issue with FF1" -- showed how easily a floating-point shortcut corrupts the cipher ^[41][30].

Constant-time radix conversion remains an under-examined implementation area. This kind of slow, standards-driven hardening -- ban the dangerous construct, wait for implementations to catch up -- is the same pattern that governs cipher agility elsewhere.

Open problems belong to the field. You, though, have a disk to encrypt and a column to tokenize today. So here are the rules.

10. A Field Guide: Which Cipher, Which Parameters, Which Layer#

Every rule below is the thesis made operational: pick the widest permitted permutation for your domain, and name the layer that provides integrity.

flowchart TD
Start["What are you encrypting?"] --> Expand{"Can you spend extra bytes?"}
Expand -->|"yes"| AEAD["Use an AEAD, not a length-preserving mode"]
Expand -->|"no"| Kind{"Volume, files, or a field?"}
Kind -->|"full volume"| XTS["AES-XTS-256, plus an integrity layer if tamper matters"]
Kind -->|"file-based"| FBE["fscrypt: XTS plus HCTR2 on AES hardware, Adiantum without"]
Kind -->|"structured field"| Field{"Domain at least a million?"}
Field -->|"yes"| FF1["FF1 with a per-context tweak"]
Field -->|"no"| Vault["Tokenization vault, not FPE"]

Full volume or block device. Configure AES-256-XTS -- the strongest widely-supported choice. Do not mistake that for the default, which varies by product: BitLocker and FileVault ship AES-128-XTS, while LUKS ships AES-256-XTS (Section 6), so name the mode, not a universal key size. Respect the 16 MiB data-unit cap of $2^{20}$ AES blocks ^[1].

If tampering is in your threat model, add integrity at another layer, and be precise about what each layer buys: dm-integrity detects modification only -- it has no freshness anchor, so it does not resist rollback or replay -- while rollback resistance needs an externally-anchored root (see Section 9). Budget dm-integrity's roughly 2x write amplification for read-write volumes. Key management and evil-maid defenses are a separate topic, covered in the BitLocker architecture post; this cipher-level guidance deliberately defers them.

File-based encryption on Android or Linux fscrypt. On hardware with AES acceleration, use aes-256-xts for contents and aes-256-hctr2 for filenames. On hardware without AES acceleration, use adiantum for both. Never hand-roll it; drive it through the platform's file-based-encryption configuration ^[27].

Can you expand at all? Then stop -- do not use a length-preserving mode. The designers of HCTR2 say so themselves, in the plainest terms.

"Usually, the right mode to use for encryption is a mode like AES-GCM or AES-GCM-SIV ... However there are some applications, such as disk encryption, where the ciphertext must be the same size as the plaintext and there is no room for such information." -- the google/hctr2 README ^[22]

Structured field that must keep its format. Use FF1, not FF3-1. Require a domain of at least one million values. Use a maximal-entropy, per-context tweak. Never use it for small fields such as PINs or short codes, and prefer a tokenization vault whenever you can add a lookup ^[30].

The common-misuse mirror#

Each row below is a misconception mapped to the failure it causes.

The mirror above names the misconceptions. Two practical questions sit outside it -- when to reach for an AEAD instead, and exactly how far XTS malleability reaches -- and the FAQ takes those on.

11. Frequently Asked Questions#

The two knobs, one last time#

Return to the two teams from the opening. The first team's disk was rewritten by someone who could not read it because XTS has no tag and diffuses across only 16 bytes -- too narrow, and unauthenticated by construction. The second team's six-digit codes were recovered because a million-value field is a domain small enough that rebuilding its whole permutation costs about $2^{30}$ operations and fewer adaptive queries than there are codes -- too small, and deterministic by construction. Neither failure was a bug. Both were the direct, predictable consequence of forcing a cipher to preserve length.

That is the whole field in one sentence. When ciphertext must occupy exactly the plaintext's space, encryption becomes a deterministic, unauthenticated keyed permutation, and its quality is set by two knobs: how wide its diffusion is, and how large its domain is. Every real break in this article sorts onto one of them, or onto the handful of hard-won lessons the failure catalog logs beside the knobs -- leaky key handling, missing integrity, and a structural tweak-schedule flaw. And the small-domain break, notably, costs work merely polynomial in the domain, not the exponential figure the format advertises.

Because the primitive has no tag, integrity always lives one layer up: in a Merkle tree, an integrity journal, a per-file nonce, or an AEAD wherever you are finally allowed to spend the bytes. Part 10 turns from confidentiality on stored data to the machinery that negotiates it in motion.

You can now read any storage or tokenization design at a glance. Ask three questions: how wide is its permutation, how large is its domain, and -- because it has no tag -- what layer above is keeping it from being rewritten?