The key server that never sees a key

There is a moment that everyone who encrypts servers eventually meets. A kernel update lands, a machine reboots at three in the morning, and instead of coming back up it sits at a prompt in a datacenter where no human has stood for months: Please enter passphrase for disk... The encryption is doing exactly what it promised — refusing to boot without a secret — and that promise is now an outage.

The industry's honest answers to this used to be uniformly bad. Put the passphrase in the initramfs, and you've bolted the key to the door it locks. Leave the volume unencrypted, and a decommissioned drive walks out of a recycling center with your database on it. Wake a human with console access, and your mean time to recovery includes REM sleep.

There is a better answer, and it's a small, sly piece of cryptography: a tiny service called Tang that unlocks disks over the network without ever seeing a key — not the disk's key, not a wrapping key, not even which client is asking. This essay builds the whole picture from the bottom: what LUKS actually does to your disk, sector by sector, with the field arithmetic spelled out; how a passphrase becomes a key without becoming guessable; and then the McCallum-Relyea exchange, a twist on Diffie-Hellman with a kind of algebraic amnesia built in. If you read the Diffie-Hellman essay on this site, you already hold the two-line proof the last act reuses.

A key wrapped in a key

LUKS — the Linux Unified Key Setup — is not itself an encryption engine. The engine is dm-crypt, a kernel device-mapper target that sits between the filesystem and the block device and encrypts every sector on the way down, decrypts on the way up. LUKS is the format: a header at the front of the device that records which cipher, which mode, and — its real job — how the key is managed.

The first design decision is the one everything else hangs on: the passphrase does not encrypt the disk. The disk is encrypted with a volume key: 512 uniformly random bits generated once, at format time, by the kernel's RNG. Your passphrase encrypts the volume key. That one level of indirection buys everything you'd want from key management:

• Changing a passphrase is instant. Re-wrap 64 bytes, not re-encrypt 4 terabytes.
• Multiple ways in. A LUKS2 header has up to 32 keyslots, each one an independent wrapping of the same volume key: one for your passphrase, one for a recovery key in a vault, and (foreshadowing) one for a network server.
• Revocation is real. Destroy a keyslot and that credential is gone, while the others still work.

A keyslot repays a closer look: it's carefully paranoid. The passphrase runs through a key derivation function (next section) to produce a wrapping key, which decrypts the keyslot's stored blob back into the volume key candidate; a stored digest of the true volume key confirms the candidate is right. But the blob on disk holds more than the encrypted volume key: it holds the key expanded four-thousand-fold by an anti-forensic splitter. The key is diffused, via hashing, across 4000 stripes with the property that reconstructing it requires every single bit of all 4000; the stripes XOR-and-hash back down to the key only if intact. Why? Because disks lie about deletion. SSDs remap and wear-level; a "wiped" keyslot might survive in a remapped block. Spread the key across 250 KiB and the odds that all of it survives a wipe collapse toward zero. Clemens Fruhwirth designed this into LUKS from the start; his design paper is still a great read on the threat model of the physical disk itself.

So: random volume key, wrapped per-credential, wipeable on purpose, hard to un-wipe by accident. Now — what does the volume key actually do?

The arithmetic of a sector

Disk encryption lives under a brutal constraint that file encryption never faces: ciphertext must be exactly the size of plaintext. A 512-byte sector encrypts to a 512-byte sector: there is no spare room to store a nonce, an IV, or an authentication tag, because the filesystem above expects sector n to hold 512 bytes and the disk below offers nothing more. Every trick modern encryption relies on — fresh randomness per message, integrity tags — is off the table. What's left is a tweakable block cipher: deterministic encryption where each position on disk gets its own secretly-derived scrambling.

The mode LUKS uses by default is AES in XTS mode (aes-xts-plain64), and its math is a nice afternoon's worth of field theory. The 512-bit volume key is really two 256-bit AES keys, K_1 and K_2, with different jobs. To encrypt sector number n, split it into 16-byte AES blocks P_0, P_1, \ldots, P_{31} (a 512-byte sector holds 32 of them), and compute for block j:

\begin{aligned} T_j &= E_{K_2}(n) \otimes \alpha^{j} \\ C_j &= E_{K_1}(P_j \oplus T_j) \oplus T_j \end{aligned}

The second line is the XEX construction — xor, encrypt, xor — with the same tweak T_j folded in before and after the cipher. The first line is where the field theory lives. E_{K_2}(n) encrypts the sector number itself (as a 64-bit little-endian integer, hence plain64) to get a starting tweak that an attacker can't predict without K_2. Then \otimes is multiplication in the finite field \mathrm{GF}(2^{128}): the 128-bit tweak is read as a polynomial with coefficients in \{0,1\}, and arithmetic is done modulo the fixed irreducible polynomial

x^{128} + x^7 + x^2 + x + 1.

Multiplying by \alpha — the polynomial x — is one shift: slide every bit left one position, and if a bit falls off the top (the x^{128} term appears), reduce it by XORing with \mathtt{0x87}, the bit pattern of x^7 + x^2 + x + 1. So the per-block tweaks E_{K_2}(n), \alpha E_{K_2}(n), \alpha^2 E_{K_2}(n), \ldots cost one shift-and-conditional-XOR each — nearly free — yet are pairwise distinct for thousands of blocks, because \alpha has enormous multiplicative order in the field. One AES call per sector buys 32 distinct whitening masks.

Why all this machinery? Because the naive alternatives fail visibly. Encrypt each block independently with bare AES (ECB mode) and identical plaintext blocks produce identical ciphertext blocks — the famous ECB penguin, where Tux's outline survives encryption because his black pixels all encrypt alike. Early dm-crypt used CBC with the sector number as a predictable IV, and that fell to watermarking: an attacker could craft a file whose presence was detectable through the encryption, because predictable IVs let plaintexts be chosen to collide. The fix at the time (ESSIV) encrypted the IV; XTS is the standardized descendant of a cleaner idea, Rogaway's tweakable-cipher constructions, blessed as IEEE 1619 and NIST SP 800-38E. Under XTS, block j of sector n and block j' of sector n' are scrambled by different masks whenever (n, j) \neq (n', j') — the penguin dissolves into static.

Honesty requires the fine print. XTS is deterministic: write the same plaintext to the same sector twice and you get the same ciphertext, so an attacker who images your disk at two points in time sees which sectors changed. And it authenticates nothing: flip a ciphertext bit and the corresponding 16-byte block decrypts to uniform garbage — often crash-loud, never detected. Full-disk encryption's contract is confidentiality of a disk at rest, against an attacker who gets the hardware once. It is exactly the right contract for a stolen laptop or a decommissioned drive, and it is the contract Tang will extend across the network. But first: the passphrase.

Making a guess cost a gigabyte

The volume key is 512 random bits; brute-forcing it is not a conversation. The keyslot is the real door, and its strength is the passphrase's, which for human-chosen passphrases might be 40 bits of entropy on a good day. The defense is to make each guess expensive, and the interesting part is what currency it's expensive in.

LUKS1 used PBKDF2: iterate a hash hundreds of thousands of times. That multiplies an attacker's work, but a hash iteration needs a few dozen bytes of state, and a GPU has thousands of cores happy to run thousands of tiny independent guesses in parallel. Iteration counts tax the defender's laptop and barely inconvenience the attacker's rig; the asymmetry points the wrong way.

LUKS2 defaults to Argon2id (RFC 9106), which changes the currency from time to memory bandwidth. Argon2 fills a large buffer — cryptsetup benchmarks your machine at format time and typically lands around a gigabyte, several passes, four lanes — with blocks, each computed from a compression of earlier blocks, some chosen data-dependently (the indices depend on the passphrase-derived state itself). The result is a computation whose honest cost is roughly

\text{cost per guess} \;\approx\; m \cdot t \quad \text{(memory} \times \text{passes)},

and — this is the theorem-shaped part — one that resists being computed in less memory: time-memory tradeoff analyses of Argon2 show that shrinking the buffer by a factor k inflates recomputation superlinearly, so the time-area product an attacker pays stays pinned near m \cdot t no matter the hardware. A GPU core doesn't have a gigabyte of fast memory to itself; an ASIC that does is mostly RAM, and RAM costs what RAM costs. Where PBKDF2 let an attacker guess thousands of times in parallel per chip, Argon2id makes each parallel guess rent its own gigabyte. Your login pays two seconds and a gigabyte, once; a dictionary attack pays it forty billion times.

That's the disk at rest: field arithmetic per sector, memory-hard wall in front of the key. Now put this machine in a datacenter and reboot it.

The 3 a.m. problem, stated properly

What we want is a machine that unlocks itself — but only in the right circumstances. Write the requirements down and they're almost contradictory:

1. The server must boot unattended, so the unlocking secret must be reachable without a human.
2. A stolen disk — or the whole stolen machine — must stay locked, so the secret must not be on the machine.
3. Whatever remote party helps must not become a key escrow: it should be unable to decrypt anything by itself, and ideally learn nothing at all from helping.

Requirement 3 is the one that kills the obvious design. A "key server" that stores unlock keys and hands them out is a vault with a bullseye painted on it — compromise it and every disk in the fleet falls, subpoena it and same. The Clevis and Tang projects (Nathaniel McCallum and Robert Relyea, Red Hat) call their alternative network-bound disk encryption: the disk can only be opened in the presence of a particular network, and the server that proves this presence holds no secrets about anyone.

The deployment shape first, because it is small. Tang is a stateless HTTP service — no TLS, no client accounts, no database beyond its own key pair. It answers two requests: GET /adv returns its public keys (a signed JWK set), and POST /rec/<kid> performs one elliptic-curve multiplication on whatever point you send it (P-521, by default) and returns the result. The API ends there. Clevis, on the client, does the rest: clevis luks bind -d /dev/sda2 tang '{"url": "http://tang.internal"}' generates a fresh random passphrase, adds it to a spare LUKS2 keyslot, encrypts it using math we're about to do, and stores the resulting JWE blob in the LUKS2 header's token area. At boot, a hook in the initramfs finds the token, runs the recovery protocol against the Tang server, and feeds the recovered passphrase to the keyslot. No human, no key on disk, no key on the server.

The math it stores and recovers is the good part.

Diffie-Hellman with amnesia

Recall the engine of the Diffie-Hellman essay: exponentials commute, so two parties can each combine their private number with the other's public number and land on the same secret. Here we move from multiplication mod p to an elliptic curve group — points instead of numbers, written additively — but the script is the same. There's a public base point G of prime order; private keys are scalars; public keys are multiples of G. Scalar multiplication distributes over addition,

s(C + E) = sC + sE,

and that one line of linearity is the entire protocol. Recovering the scalar from a point — given C = cG, find c — is the elliptic-curve discrete logarithm problem, believed hard in exactly the way the DH essay's \sqrt{p} wall is hard, with no index-calculus crack known for curves.

Provisioning. Tang holds a long-term key pair: private scalar s, public point S = sG. When Clevis binds a disk, it fetches S, then, entirely offline, generates its own ephemeral pair c and C = cG, and computes a plain Diffie-Hellman shared point:

K = cS = c(sG) = csG.

It derives a symmetric key from K, encrypts the keyslot passphrase under it, and then does the strange thing that makes the whole scheme: it deletes c and K, keeping only the ciphertext, the point C, and S in the LUKS2 token. Nothing was ever sent to the server. Read the state of the world after binding: the disk now holds a ciphertext that nobody can currently decrypt cheaply except by talking to Tang. The client threw away its own decryption capability on purpose. The key K exists nowhere; what remains is the algebraic potential to rebuild it, K = sC, and the only party holding s is the server — which has never heard of C.

Recovery. At boot the client wants K = sC back. It could just send C and ask — Tang would compute sC and return it. That works, but it hands the server (and the network) the very point that unwraps the disk, and it lets the server correlate which disk is asking. McCallum-Relyea adds one blinding step, and it costs almost nothing. The client draws a fresh random scalar e, computes E = eG, and sends the server not C but

X = C + E.

Tang does its one job — multiply by s — and answers Y = sX. Now the client unblinds using e and the server's public key:

Y - eS \;=\; s(C + E) - e(sG) \;=\; sC + seG - seG \;=\; sC \;=\; c(sG) \;=\; cS \;=\; K. \; \checkmark

The middle of that chain is just the distributive law and commutativity of scalars — the same two-line proof that made Diffie-Hellman correct, run through once more with a subtraction. The client derives the symmetric key from K, opens the JWE, feeds the passphrase to LUKS, discards e, and boots.

Now look at the exchange from the server's chair, because this is where the title of the essay lives. Tang received one point, X = C + E. The blinder E is a fresh uniformly random group element, so X is uniformly distributed regardless of C — a one-time pad, played in an elliptic curve group. The server cannot tell which binding is asking, whether it's seen this client before, or anything else: every recovery request it will ever receive is an exact uniform sample from the group. It computes sX — which is K plus the mask sE it cannot remove, since removing it takes e — returns it, and forgets. No state, no log worth stealing, no key material about any client, ever. An eavesdropper on the wire sees S, X, and Y = sX and stands in front of the same computational Diffie-Hellman wall as Eve in the previous essay; even an eavesdropper who also has the disk (and thus knows C, and can compute E = X - C) still needs the discrete log e or s to peel the mask. If you want to feel that wall with your own hands, the Diffie-Hellman playground on this site lets you play the eavesdropper against toy-sized groups — the curve version differs only in costume.

One more elegance: the blinding also protects replay. Each boot uses a fresh e, so recorded recovery exchanges are useless later — yesterday's X and Y unmask only with yesterday's e, which died at boot.

The ledger of who-can-decrypt-what

Every unlocking scheme is really an accounting of which combinations of stolen things suffice. Tang's ledger, entry by entry:

• Disk alone: the thief holds C, S, and a JWE. The key is K = sC; producing it needs s or c, both absent. This is CDH-hard — and, decisively, the stolen machine is now outside the network, so it can't ask the real Tang. The disk demoted itself to a brick that also accepts your fallback passphrase. This is requirement 2, delivered by geography-via-cryptography: the data is bound to network presence.
• Tang server alone: the attacker gets s. And... nothing to point it at. No client points, no ciphertexts, no request logs that distinguish clients — provisioning never contacted the server, and every recovery request was uniform noise. A compromised Tang, by itself, decrypts exactly zero disks.
• Disk + reachability of Tang: unlocks. That is the design working — but notice what it means: Tang answers anyone who can reach it with sX, no authentication. Tang converts "who can decrypt this disk" into "who is standing on this network segment," so the network segment is now a security boundary and deserves to be treated like one: firewall Tang to the machines that should boot, and remember that an attacker who exfiltrates a disk image and keeps network access hasn't been stopped. Tang's threat model is the stolen disk, the RMA'd drive, the machine that leaves — not the live intruder inside the perimeter.
• Disk + Tang's private key s: unlocks offline, forever, for every disk bound to that key. Which is why Tang keys rotate, and why you might not want a single Tang to be the whole story.

For that last worry, Clevis has a pin that closes the loop with one more piece of pretty mathematics: sss, Shamir's secret sharing. The unlocking secret becomes f(0) for a random polynomial f of degree t-1 over a finite field; each of n Tang servers (or a TPM, or a passphrase) protects one share f(x_i); any t shares reconstruct the secret by Lagrange interpolation,

K = f(0) = \sum_{i=1}^{t} f(x_i) \prod_{j \neq i} \frac{x_j}{x_j - x_i},

and any t-1 shares are consistent with every possible secret — not "hard to invert," but information-theoretically silent. Bind a fleet with 2-of-3 across two Tang servers in different racks and a TPM, and no single compromised box — server or client — moves the needle, while any routine reboot still finds two shares without waking anyone.

The whole stack, in one breath

Zoom all the way out and count the kinds of mathematics standing between a thief and your data. Each 512-byte sector is scrambled by AES under masks marching through \mathrm{GF}(2^{128}) by powers of \alpha — one shift and an XOR with \mathtt{0x87} at a time. The key doing that scrambling is wrapped by a function engineered to cost a gigabyte per guess, diffused across 4000 stripes so it can actually be erased. And the unattended copy of the unwrapping secret isn't stored anywhere — it's a point on an elliptic curve, disassembled into a public half on the disk and a scalar on a server that have never been in the same room, reassembled at each boot through a blinded exchange that tells the server nothing and the network less.

The 3 a.m. reboot goes through: initramfs asks, Tang multiplies, the distributive law does the rest, and the machine is serving traffic before your phone would have finished buzzing. The disk that walks out of the datacenter stays noise. And the server that made both things true could publish its entire memory without exposing a single client — because the most useful key server turns out to be the one that never sees a key.