Keys You Did Not Generate: Malicious Binding, the FIPS 203 Checks and the Seed-Versus-Expanded Decision

Security proofs for key-encapsulation mechanisms quietly start with the same sentence: generate a key pair honestly. In a laboratory that sentence is free. In production it describes a hardware module that exports a key to an application, a control plane that injects a key into a container, a partner that sends its public key over email, a backup that restores last year's private key, and an AI agent platform that lets each tenant bring its own. In every one of those paths the party that will rely on the key did not watch it being born. ML-KEM, standardized as FIPS 203, has specific answers for this situation, and specific gaps. Both are worth knowing exactly, because they determine which of its guarantees still hold.

The assumption inside honest key generation

An ML-KEM key pair comes from a deterministic expansion of two independent 32-byte random values, which FIPS 203 calls d and z. The value d is expanded into the lattice secret and the public key; z is kept aside as the implicit-rejection secret, the value used to produce a pseudorandom key whenever a ciphertext fails its re-encryption check. The expanded decapsulation key that most libraries store concatenates four pieces: the decryption key, a copy of the public encapsulation key, a hash of that public key, and z. That layout is what makes decapsulation fast, and it is also the root of everything that follows, because three of those four pieces are things the decapsulator simply believes.

Each trusted piece has a job during decapsulation. The decryption key recovers the encapsulated message. The stored public-key copy is used to re-encrypt that message, which is how the re-encryption check decides whether the ciphertext was honestly formed. The stored hash of the public key is mixed with the message to derive both the shared secret and the encryption coins. The rejection secret z determines the key returned when the check fails. None of the last three is recomputed by a typical decapsulation routine; each is read from the stored key, which is fast, and which means whoever wrote the stored key also decided how decapsulation behaves.

FIPS 203 is candid about the boundary. It says that secure key establishment depends on key pairs that have been properly generated, and that an owner who received a key pair from someone else may optionally run a key-pair check: regenerate from the seed if one is available, check both keys, and run a pair-wise consistency test that encapsulates to the public key and decapsulates the result. It then adds that this checking process does not guarantee that the key pair is a properly produced output of key generation. The checks detect corruption and malformation. They do not detect intent.

A useful picture is a bank that stores, alongside your safe-deposit box, a photocopy of your signature card and a fingerprint of that photocopy, so that clerks need not fetch the original. If the clerk checks only that the fingerprint matches the photocopy, a forger who can replace both at once passes. If the clerk instead re-derives everything from the original card each time, the forgery fails. Which of those clerks a system employs is decided by its key format and its import code, not by the KEM.

What the FIPS 203 checks verify, and what they cannot

FIPS 203 requires input checking before encapsulation and decapsulation. For an encapsulation key the type check confirms the length, 384 bytes per module rank plus 32, and the modulus check decodes every twelve-bit coefficient and re-encodes it, failing if any value was outside the range zero to q minus one. That check rejects non-canonical encodings, which matter because two byte strings that decode to the same polynomial would otherwise be two names for one key. For decapsulation the ciphertext type check confirms its length, the decapsulation-key type check confirms the key length, and the hash check recomputes the hash of the embedded public-key copy and compares it with the stored hash.

NIST SP 800-227, the 2025 recommendation on using KEMs, explains when a module may skip them. A key the module generated itself and stored so that it cannot be modified needs no recheck; an input checked once and stored unmodifiably needs no second check; and an input imported from a trusted third party that provides assurance, and then stored unmodifiably, may also be used directly. Ciphertext checking is different: FIPS 203 requires it on every decapsulation. The exemptions are conditional on protection against modification, which is precisely the property a key copied through files, environment variables or configuration systems tends to lose.

The table below summarizes the coverage. The pattern is consistent: each check confirms that a value is internally coherent and correctly encoded, none of them can tell a value that came from honest key generation from one constructed to look like it, and the standard says so in each case.

Two malicious keys, one caught and one not

Schmieg's 2024 note made the abstract binding question concrete. Binding asks whether equal shared secrets force equal public keys or ciphertexts; the malicious strength lets the attacker construct the key material. The first construction targets ciphertext binding. The attacker builds a decapsulation key that is honest in every part except the stored public-key hash, which it replaces with the hash of a different, victim's public key. Because ML-KEM derives the accepted shared secret from the decrypted message and the stored hash, the attacker can craft a ciphertext under its own key that decapsulates, without triggering rejection, to the very secret an honest sender produced for the victim. Two ciphertexts, two keys, one secret.

This construction is internally inconsistent: the stored hash does not match the public key stored beside it. The FIPS 203 decapsulation-key hash check, required before decapsulation in the final standard, detects exactly that inconsistency, and private-key validation of this kind is one of the mitigations Schmieg proposes. A conforming implementation that runs the hash check whenever it loads an untrusted key therefore stops the first attack.

The second construction targets public-key binding and is not detectable. The attacker generates two entirely honest-looking key pairs and gives them the same rejection secret z. It then submits one random ciphertext to both. Both reject it, and both return the pseudorandom rejection key computed from z and the ciphertext alone, which is identical. Two different public keys have produced the same shared secret. Schmieg observes that each key on its own looks well formed, since z is random bytes, and no auditor can distinguish a deliberately shared z from an independently drawn one. Every FIPS 203 check passes.

Who would want either outcome? The CFRG security-considerations draft answers that misbinding is not a threat to ordinary key exchange or public-key encryption, and becomes relevant when the shared key is used for authentication and an adversary may control a private key. Examples are protocols in which a party must later reveal its private key, protocols that accept private keys from a third party, and designs in which a server holding many clients' keys could make two clients' sessions collide. In those settings the draft advises authenticating the public key and ciphertext in the protocol as well, rather than relying on the KEM alone.

What the seed buys, and what it does not

FIPS 203 permits storing the 64-byte pair of seeds, d followed by z, instead of the expanded key, and regenerating the expanded key whenever it is needed. The final standard also added a domain-separation byte to key expansion, so a seed accidentally expanded under a different parameter set produces an unrelated key rather than a weaker relative. When private keys travel as seeds, the importer recomputes the public key, its hash and the decryption key from d, so the stored-hash forgery cannot even be expressed. Schmieg proves that ML-KEM without cached public-key hashes is MAL-BIND-K-CT, and RFC 9935, the March 2026 profile for ML-KEM in X.509, records the consequence: the seed format provides malicious-strength ciphertext binding.

The same RFC states the limit in the same paragraph: the seed format still does not provide MAL-BIND-K-PK. The reason is structural. In FIPS 203, z is the second half of the seed, drawn independently of d. An attacker who chooses seeds can choose two different values of d with the same z, and the shared-rejection-secret attack goes through unchanged. Cremers, Dax and Medinger reached the same conclusion: with an independent rejection seed, any combination of key pair and rejection value is well formed, so no sanity check can rule the attack out.

Closing the gap requires deriving z from the same single seed as everything else, so that two keys sharing z would have to share their entire seed. Schmieg sketches this design and proves it MAL-BIND-K-PK. The X-Wing hybrid KEM, specified in a CFRG draft, takes this approach: its decapsulation key is one 32-byte seed expanded with SHAKE256 into d, z and an X25519 private key, and the draft forbids transmitting the expanded key between implementations because the binding analysis does not hold for it. The progression is instructive. The expanded key gives leakage-strength binding, the 64-byte seed adds malicious ciphertext binding, and a single derived seed is needed for malicious public-key binding.

The cost of the seed is small. ML-KEM key generation is fast, so regenerating an expanded key when a stored seed is loaded adds little work, and Schmieg notes that for the most performance-critical case, an ephemeral key pair generated, used once and discarded, the private key is never serialized at all, so the question does not arise. The real cost is interoperability: a deployment that standardizes on seeds needs every system that stores, exports or backs up its keys to preserve the seed, because an expanded key cannot be turned back into one.

Formats on the wire: reading RFC 9935 as an import policy

RFC 9935 encodes an ML-KEM private key inside the standard asymmetric key package as one of three choices: a seed, tagged and always 64 bytes; an expanded key of 1,632, 2,400 or 3,168 bytes depending on the parameter set; or both together. Seed-only is recommended as the most compact. The public key and expanded key may be included alongside a seed specifically to enable key-pair consistency checks during import. The RFC also instructs parsers to distinguish the three choices by their encoding tag, not by any heuristic such as the length of the enclosing string, a small rule that prevents a class of confusion bugs in code that must accept all three.

Read as policy, those rules suggest a ranking. A seed-only key is the strongest import, because every derived value is recomputed locally. A key carrying both forms should be imported by regenerating from the seed and comparing the result with the supplied expanded key, the seed-consistency check of FIPS 203; a mismatch means the file was edited or mis-assembled, and the import should fail. An expanded-only key can be used after the type and hash checks and a pair-wise test, but the importer should record that the key's binding strength is leakage-strength at best and its provenance unverifiable.

SP 800-227 notes that storage, import and export formats are implementation choices outside what algorithm validation tests, and some modules may only export expanded keys. That is a reason to make the policy explicit, not to abandon it. A deployment that accepts expanded keys from third parties should say so, and should not then rely on any malicious-strength binding property in the protocols those keys serve.

Poisoned keys: the limit no check crosses

A further class of bad key passes every check because it is functionally correct. The CFRG ML-KEM security-considerations draft describes it: a lattice public key hides a secret under a small error term, and if additional error is introduced during key generation, the resulting key still decapsulates honestly generated ciphertexts correctly but fails more often on ciphertexts an adversary chooses. Each such decapsulation failure leaks information about the secret, so a patient adversary can eventually recover the private key. The draft calls such a key poisoned.

The pair-wise consistency test that FIPS validation requires approved implementations to run on every freshly generated key pair catches keys that do not work at all, whether from a bug, a hardware fault or deliberate fault injection. The draft is explicit that it cannot rule out a poisoned key, because one honest encapsulation succeeds. The same draft notes a second route to the same outcome: an attacker able to replace the stored copy of the public key on both sides, the copy bound into the decapsulation key and the copy the encapsulator uses, can substitute a key with a marginally higher failure rate. Hence its instruction that the public key and its hash inside the private key be protected from modification.

No validity check can certify honest generation, so the only defence is provenance: generating keys inside a boundary one trusts, with an approved random bit generator of at least the parameter set's security strength, and protecting the stored key against modification from then on. For a key generated elsewhere, the relevant question is not whether it passed the checks but who generated it and who could have changed it since.

Agent runtimes: where keys are born and where they travel

AI agent platforms multiply the paths by which keys arrive. When an agent generates its own ML-KEM key inside its runtime and never exports it, the honest-generation assumption holds as well as the runtime's randomness does; one consequence that follows from FIPS 203's randomness requirements, offered here as analysis rather than a reported incident, is that cloning a running agent's memory or restoring a snapshot can duplicate a seed into two agents, which then share a key and every secret encapsulated to it. When a control plane generates keys and injects them into agent containers, the platform is acting as the trusted third party of SP 800-227, and the exemption from input checks holds only if the injected key is stored so it cannot be modified, which a key copied into secret files or environment variables does not by itself guarantee.

When tenants or partner agents bring their own key material, the platform is in the malicious setting by definition. The defensible configuration accepts private keys only as seeds, runs the hash and consistency checks on everything else, and does not let any protocol that serves those tenants depend on public-key binding from ML-KEM alone, since even seeds do not provide it. Key escrow and recovery deserve the same care: the 64-byte seed is the entire secret, FIPS 203 requires it to be protected exactly like the decapsulation key, and a recovered seed reconstitutes every past and future secret encapsulated to that key.

The evidence limits are worth stating. The malicious-key constructions are proofs of concept for binding games, not reports of exploitation; the poisoned-key mechanism is described in an Internet-Draft from the security-considerations work, not measured in deployed systems; and the cloning concern is reasoning from the standard's requirements. What they establish together is a design rule: for every place an agent platform accepts an ML-KEM key, record who generated it, in what format it travels, which checks run on import, and which binding strength the protocols built on it may therefore claim.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

SCOPE: every ML-KEM private key not generated inside this module.
1. Parse the RFC 9935 CHOICE by its encoding tag; reject unknown tags and never infer the form from length.
2. seed: regenerate the full key pair; store the seed; record binding = MAL-BIND-K-CT.
3. both: regenerate from the seed; reject unless the regenerated expanded key equals the supplied one.
4. expandedKey: run the type and hash checks and a pair-wise test; record binding = LEAK only; flag provenance as unverified.
5. If a public key is supplied, reject unless it equals the regenerated or embedded public key.
6. Store the accepted key so it cannot be modified; log who supplied it and when.
7. Never rely on public-key binding from ML-KEM alone for keys from this path; bind public keys in the protocol.

Glossary

Encapsulation key

ML-KEM's public key, used by a sender to produce a ciphertext and shared secret.

Decapsulation key

ML-KEM's private key; in expanded form it holds the decryption key, a public-key copy, that copy's hash and the rejection secret.

Seed (d, z)

The two 32-byte random values from which ML-KEM regenerates a key pair; d drives the lattice keys and z the rejection secret.

Rejection secret (z)

The value combined with an invalid ciphertext to produce ML-KEM's pseudorandom implicit-rejection key.

Modulus check

The FIPS 203 check that every encoded public-key coefficient is canonical and below the modulus q.

Hash check

The FIPS 203 check that the hash stored in a decapsulation key matches the public key stored beside it.

Pair-wise consistency test

Encapsulating to a new public key and decapsulating the result to confirm the pair works together.

MAL-BIND-K-CT / MAL-BIND-K-PK

Binding of the shared secret to the ciphertext, or to the public key, against an attacker who constructs the key material.

Poisoned key

A key generated with extra error that works on honest ciphertexts but leaks its secret through failures on chosen ones.

Provenance

The record of who generated a key, with what randomness, and who could have modified it since.

Trusted third party (TTP)

In SP 800-227, an external source of keys whose assurance lets a module skip input checks if storage prevents modification.

References

1. NIST FIPS 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard (2024)
2. NIST SP 800-227, Recommendations for Key-Encapsulation Mechanisms (2025)
3. Schmieg, Unbindable Kemmy Schmidt: ML-KEM is neither MAL-BIND-K-CT nor MAL-BIND-K-PK (IACR ePrint 2024/523)
4. Cremers, Dax and Medinger, Keeping Up with the KEMs (ACM CCS 2024, IACR ePrint 2023/1933)
5. RFC 9935, Algorithm Identifiers for the Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM) in X.509 (2026)
6. Fluhrer et al., ML-KEM Security Considerations (draft-sfluhrer-cfrg-ml-kem-security-considerations-05)
7. Connolly, Schwabe and Westerbaan, X-Wing: general-purpose hybrid post-quantum KEM (draft-connolly-cfrg-xwing-kem-11)
8. RFC 5958, Asymmetric Key Packages