Two organisms, one envelope

A lichen is not one thing. It is a fungus and a photosynthetic partner living as a single body, and the pair colonises bare rock that neither could hold alone. Pull them apart in a lab and each survives, poorly, as something less than what they were together. The interesting property is not that there are two of them. It is that the failure of one does not end the organism.

That is the whole argument for a hybrid key encapsulation mechanism, and it is why the object store underneath every Paracoding install is sealed by two of them at once.

The thing that waits

Some lichens survive being dried to a crisp for decades. The body does not die; it suspends. Add water and it resumes as though the intervening years were a pause rather than an ending. Dormancy is not weakness in that lineage — it is the strategy.

Encrypted data has the same property, and it is not a feature. An attacker who copies your ciphertext today does not need to open it today. They need to keep it, dry and patient, until a machine exists that can. The industry calls this harvest now, decrypt later, and it is the only threat model in security where doing nothing for fifteen years is a winning strategy for the other side.

It is also the reason post-quantum migration is not something to schedule for the year the machine arrives. Anything copied out of a bucket this morning is already in the freezer. The only decision still available to you is what it was wrapped in when it left.

What a hybrid KEM actually is

A key encapsulation mechanism does one narrow job: it lets someone with your public key produce a fresh shared secret and a ciphertext that carries it, such that only your private key can recover the secret. It does not encrypt your data. It hands you 32 bytes, and you go and do the real work with a symmetric cipher.

A hybrid KEM runs two of them and mixes the results, so an adversary must break both to recover the secret. The two are chosen to fail differently on purpose. ML-KEM rests on the hardness of a lattice problem, is young, and is the one that survives a quantum computer. X25519 rests on elliptic curve Diffie-Hellman, is twenty years old and extremely well understood, and is the one that falls to a quantum computer. A structural break in the lattice would be a bad month for ML-KEM and a normal Tuesday for X25519. Neither the fungus nor the alga on its own holds the rock.

X-Wing, precisely

X-Wing is a specific hybrid construction by Deirdre Connolly, Peter Schwabe and Bas Westerbaan, published as an IETF CFRG draft and an IACR paper. It combines ML-KEM-768 with X25519, and its whole contribution is the care taken in how the two are combined.

The naive hybrid — concatenate the two shared secrets, hash, done — is not obviously wrong, but it gives up properties you want and it is easy to get subtly wrong. X-Wing hashes more than the two secrets:

Combiner(ss_M, ss_X, ct_X, pk_X) =
    SHA3-256( ss_M || ss_X || ct_X || pk_X || XWingLabel )

XWingLabel = the 6 ASCII bytes  \.//^\   (hex 5c2e2f2f5e5c)

Two details are worth stopping on. The X25519 ciphertext and public key go into the hash alongside the secrets, which is what buys the binding properties — the shared secret is committed to the exact ciphertext and key that produced it, so an attacker cannot take one encapsulation and make it appear to belong to a different key. And the label exists purely for domain separation: it makes an X-Wing hash unmistakably an X-Wing hash, so the same primitive used elsewhere in your system can never collide with it. The label happens to be a tiny ASCII X-wing fighter, which tells you something pleasant about the authors.

The published security claim is that X-Wing is IND-CCA secure, bounded by the IND-CCA security of ML-KEM-768 and the gap-CDH hardness of Curve25519, modelling SHA3 as a random oracle. In the language of the lichen: the composite is at least as robust as its more robust partner.

The trade we made, stated plainly

Before X-Wing our vault used ML-KEM-1024 on its own. ML-KEM-1024 targets NIST security category 5. ML-KEM-768, the leg inside X-Wing, targets category 3. Moving to X-Wing therefore lowered our ML-KEM parameter set and added a classical partner beside it.

If your threat model says otherwise — if you want category 5 and you are content to bet entirely on the lattice — ML-KEM-1024 is still there and the envelope still reads it. That is what the epoch byte is for, and we will come back to it.

What Cloud KMS hands you

We did not implement X-Wing. Google did, and the private half of the key never leaves their hardware. Cloud KMS exposes three post-quantum KEMs, and the sizes are worth putting side by side because they are the numbers you will actually be reasoning about when something does not fit:

The operation that matters is decapsulate: you hand KMS a ciphertext, KMS uses the private key it holds and never exports, and you get 32 bytes back. The permission that governs it is cloudkms.cryptoKeyVersions.useToDecapsulate, and it is worth knowing the string by heart, because the failure it produces is not obviously a permissions failure — a job without it dies 403 on the one line that was supposed to materialise your key, and everything downstream reports corruption instead.

Encapsulation is the mirror and needs no secret at all, which is the point of public key cryptography and also the reason the write path is cheap.

The envelope we wrap around it

The KEM gives us 32 bytes. It does not give us encrypted objects. Everything from here is ours, and it is deliberately boring:

magic(4)="PCV1" | epoch(1) | flags(1) | nonce(12) | ciphertext(N) | tag(16)

key = HKDF-SHA256(master, salt=HKDF_SALT, info="pcv1:"+path+":e"+epoch, 32)
AAD = magic | epoch | flags | path

AES-256-GCM, keys derived per object with HKDF-SHA256, a 12-byte nonce because that is GCM’s native size and introducing a rehash between the nonce and the cipher would be a way to be clever and wrong. Header is 18 bytes, tag is 16, so a sealed object is exactly 34 bytes longer than its plaintext. Keep that number: it is the only integrity check in the system that needs no key at all.

The AAD is the part that matters

The additional authenticated data binds the ciphertext to the full Cloud Storage object key — not the repository-relative path, not the virtual filesystem path, the actual bucket key the bytes live under.

Without that binding, a valid envelope from one repository is a valid envelope everywhere. An attacker with write access to the bucket could move a blob from a repository you do not care about into one you do, and the decrypt would succeed and hand you attacker-chosen content that authenticates perfectly. Two repositories mounted at the same virtual path would produce identical AAD for different objects. Binding the storage key means an envelope opens at exactly one location and nowhere else.

In mycological terms: the body only fruits on the block it grew in. Move it and nothing comes up.

One byte that prevented a flag day

The second field in the header is a single byte naming the key scheme that sealed the object. It costs nothing and it is the reason the migration to X-Wing was a Tuesday rather than an outage.

Because the epoch travels in the envelope, the reader derives its per-object key from the blob’s epoch rather than from whatever the process happens to be writing. An object written last month under the old scheme is still opened correctly by today’s code. There is no flag day, no bulk re-encrypt that has to complete before your history is readable again, and no window where half the store is unreadable by half the fleet.

Getting that right needed one more thing, and it is the part that is easy to skip. A reader holding exactly one master key turns any change of scheme back into a flag day, whatever the header says. So the reader holds a map from epoch to master, populated at boot after the KMS decapsulations, and the resolution order is the whole design:

• the master registered for this blob’s epoch, so an epoch-1 object is opened with the epoch-1 key even though the caller passed the current one;
• if no masters are registered at all, the caller’s explicit key — which keeps the module usable as a pure codec, and is exactly how the cross-language test vectors drive it;
• otherwise throw, naming the epoch. A populated registry that lacks this one epoch is a provisioning gap, not a decode error, and quietly falling back to some other epoch’s key would surface three layers away as an authentication tag failure that tells you nothing.

This is subculturing, and it has the same rule. You do not discard the parent when you make the transfer. You keep both alive until the new generation has proved it fruits.

Four ways we nearly made everything unreadable

None of these are cryptographic failures. All of them would have destroyed data just as thoroughly, which is roughly the lesson.

1. Decoding a git object as text

The read path is dual: a blob whose first four bytes are not PCV1 is returned verbatim, so plaintext and ciphertext can coexist during a migration. The Python implementation this was ported from did that branch as blob.decode("utf-8", errors="replace"). A git object is a zlib stream. A UTF-8 round trip through it silently substitutes replacement characters for anything that is not valid UTF-8, which is most of it. The bytes come back the right length, the object is ruined, and nothing raises. The Node implementation never converts a blob to a string, and says so in a comment, because this is the class of bug that is invisible until it is history-shaped.

2. Making every file look permanently modified

Object storage reports the size it stores, which after sealing is the ciphertext length — 34 bytes too many. isomorphic-git records that size in the index and compares against it to decide whether a file changed. A uniformly wrong size means every indexed file looks modified, forever, and no amount of staring at the crypto explains it. The writer therefore stamps the plaintext length in the object’s custom metadata and the reader hands that back to stat. An absent stamp means plaintext, which is the correct answer for every object written before the change.

3. Sealing something that has to stay legible

Buckets have no real directories, so the store represents them as zero-byte marker objects identified by their size. Seal one and it becomes 34 bytes, stops being recognisable as a marker, survives into the object store as a mystery, and git fsck reports garbage. Encryption that cannot tell what it is encrypting is a way to lose a repository slowly.

4. Pointing at the wrong keyring

If the vault environment variables are absent the code falls back to unprefixed resource names. A redeploy that drops them resolves those names successfully, finds a keyring with no decapsulator, and every master derivation returns 403. The symptom is not “crypto is broken” — it is every write to the lake failing, which takes the git object store down with it. Overwrite the master itself and there is no recovery at all: every object sealed under it is gone.

How we know it works

A hand-rolled envelope format is worth nothing if the implementation quietly disagrees with the specification it claims to follow, and two implementations of the same format that were never compared are two formats.

So the Node implementation is cross-validated against the Python one across 57 vectors, 57 of 57 passing, byte-identical under a fixed nonce, plus 18 runtime checks driving the real storage layer. Fixing the nonce is what makes the comparison mean anything: with a random nonce two correct implementations produce different bytes and you can only check that each round-trips, which hides an entire category of derivation bug. Pin the nonce and you are comparing bytes to bytes.

And in production, the cheapest check remains the one that needs no key: a sealed object is 34 bytes longer than its plaintext and starts with PCV1. Equal size means plaintext. Compare bytes to bytes rather than characters, though — an em dash is three UTF-8 bytes, and counting characters gives you false negatives and a confusing afternoon.

What this does not protect you from

Encryption at rest answers exactly one question: what an attacker gets from the bytes at rest. It is worth being precise about everything it leaves open.

• It does not protect data in use. The control plane holds the master in memory while it serves; anything that can read that process can read the store.
• The master registry is per process, therefore per fleet, not per tenant. That is correct for a single-repository control plane and it is not correct the day a second tenant with a different master is served from the same process. It is written down in the source as a limit rather than discovered later as a breach.
• It says nothing about who was allowed to ask. That is IAM, the signed execution path and the journal — a different set of controls, described on the security page.
• Post-quantum is a bet about the future placed with today’s information. We have said which way we bet and why. Re-read that section rather than treating the label as a guarantee.

The reason to build it this way is not that lattices are fashionable. It is that the cost of being wrong is asymmetric and deferred: a store sealed badly today fails in fifteen years, at which point nobody involved is available to explain the decision. Two organisms in one body is how you hedge a question that will not be settled in time to help you.

Sources

• draft-connolly-cfrg-xwing-kem — X-Wing: general-purpose hybrid post-quantum KEM, IETF CFRG
• X-Wing: The Hybrid KEM You’ve Been Looking For — Barbosa, Connolly, Duarte, Kaiser, Schwabe, Varner, Westerbaan (IACR ePrint 2024/039)
• Key encapsulation mechanisms — Cloud KMS documentation, algorithm and size table
• Encapsulate and decapsulate using KEMs — Cloud KMS documentation
• Announcing quantum-safe Key Encapsulation Mechanisms in Cloud KMS — Google Cloud
• FIPS 203 — Module-Lattice-Based Key-Encapsulation Mechanism Standard, NIST