up:: Migration Architecture MOC

PQC Implementation Pitfalls

PQC implementation pitfalls are the class of bugs that break a mathematically correct post-quantum algorithm through the way its code runs on a real machine, rather than through any flaw in the standard itself. ML-KEM and ML-DSA carry security proofs, but a proof covers the algorithm as an abstract sequence of operations, and a running implementation leaks information the abstraction never modeled: how long an operation took, which memory it touched, what the hardware did when its power was glitched.

An attacker who cannot dent the lattice math can still recover a secret key from an implementation that branches on secret data, reuses randomness, answers malformed inputs distinguishably, or handles the algorithm’s internal reject step carelessly. FIPS 203 states the boundary plainly: conforming to the standard “does not guarantee that the result will be secure,” because security lives in the implementation, and the implementation is where breaks actually happen.

Source: NIST, “Module-Lattice-Based Key-Encapsulation Mechanism Standard,” FIPS 203, August 13, 2024, §3.3, csrc.nist.gov/pubs/fips/203/final.

The short version:

• The proof is about the algorithm; the break is about the code. A perfect standard implemented carelessly is exploitable, so implementation security is a separate discipline from choosing the right algorithm.
• The biggest pitfall is non-constant-time code: any branch or memory access that depends on secret data leaks timing that an attacker measures to reconstruct the secret. KyberSlash was exactly this, a secret-dependent division in real ML-KEM libraries.
• Randomness is load-bearing. FIPS 203 requires fresh bytes from an approved generator for every key generation and encapsulation, and reusing a nonce or a seed can collapse the security of the whole operation.
• ML-KEM’s Fujisaki-Okamoto rejection step is a security mechanism, and getting it wrong reopens a decryption-error oracle. FIPS 203 treats the internal accept/reject flag as secret data that must be destroyed, never leaked.
• Fault injection is the physical version: glitching power or timing to skip the verification step or corrupt a computation can turn a correct algorithm into one that signs or decrypts for an attacker. Testing is the control that catches all of it, per Testing as the Control Surface.

Picture a bank vault whose lock mechanism is mathematically flawless, engineered so that no combination of dials can be reasoned out. Now watch the teller who operates it. If the teller mutters the correct digit a beat faster when you guess right, an observer in the lobby learns the combination without ever touching the dial. If the teller reuses yesterday’s one-time slip, two transactions line up and reveal the secret between them. If a sharp bang on the vault door makes the teller skip the identity check, a stranger walks in. None of these are failures of the lock. They are failures of how the lock is operated, and post-quantum implementation pitfalls are precisely the failures of how a proven algorithm is operated in code and hardware.

Why can a proven algorithm still be broken?

Because a security proof covers the algorithm as an idealized mathematical object, and a deployed implementation is a physical process that emits information the idealization never included. The proof for ML-KEM establishes that an attacker who sees only the defined inputs and outputs cannot recover the key. A real execution also emits timing, power draw, electromagnetic radiation, cache-access patterns, and behavior under physical fault, and any of those side effects can carry secret-dependent information that the proof’s model excluded by assumption.

FIPS 203 is unusually direct about this gap. Its implementation-requirements section opens by warning that even a fully conforming implementation is not thereby secure, and it spends the rest of the section imposing obligations the pure algorithm description does not: destroy intermediate values, use an approved generator for randomness, check inputs, keep the reject decision secret. Those are not refinements of the math. They are the acknowledgment that the math was never the whole security story, and that a team who reads “we deployed the NIST standard” as “we are secure” has skipped the half of the work where real attacks land.

Source: NIST, FIPS 203, §3.3 (conformance “does not guarantee that the result will be secure”), csrc.nist.gov/pubs/fips/203/final.

The reframe worth internalizing is that in post-quantum cryptography, as in classical cryptography before it, the algorithm is the part most likely to be right and the implementation is the part most likely to be wrong. Decades of classical breaks came from side channels and coding errors rather than broken ciphers, and the post-quantum standards inherit that reality wholesale.

Pitfall	What leaks or breaks	FIPS 203 obligation	Defense
Non-constant-time code	Secret read from timing or cache pattern	No floating-point arithmetic	Constant-time coding and analysis
Randomness or nonce reuse	Independence the proof assumed	Fresh approved RBG bytes per invocation	A seeded CSPRNG at matched strength
Decryption-error oracle	Key leaked from reject-vs-accept difference	Destroy the implicit-reject flag; check inputs	Indistinguishable reject via the FO transform
Fault injection	Skipped check or corrupted signing	Destroy intermediate values	Verify-before-release, redundancy, sensors

What is non-constant-time code and why does it leak?

Non-constant-time code is any code whose execution time, memory-access pattern, or hardware behavior depends on a secret value, and it leaks because an attacker who can measure that variation reads the secret out of the timing. The requirement it violates is constant-time execution, meaning the operation takes the same time and touches the same memory regardless of the secret data it processes, so an observer learns nothing from watching it run.

The two classic sources are secret-dependent branches and secret-dependent memory access.

1. Secret-dependent branches. An if statement that tests a secret takes one path when the secret bit is set and another when it is clear, and the two paths almost never take identical time, so measuring the duration reveals the bit. Repeat across every bit and the whole secret falls out.
2. Secret-dependent memory access. Indexing a table at a position derived from a secret pulls different cache lines depending on the secret, and cache-timing measurements expose which lines were touched, which recovers the secret index. This is why a lookup table addressed by secret data is a side channel even with no branch in sight.

The worked example that made this concrete for post-quantum code is KyberSlash, a family of timing vulnerabilities in real ML-KEM software. Several widely used Kyber and ML-KEM libraries contained a line that divided a secret value by a public one, and because the CPU’s division instruction takes a number of cycles that varies with its operands, the running time leaked information about the secret, enough in some settings to recover the private key. The lattice math was untouched. A single division written the ordinary way, without the constant-time discipline the algorithm demands, was the whole vulnerability.

Source: Bernstein et al., “KyberSlash: division timing side channels in Kyber/ML-KEM,” kyberslash.cr.yp.to.

FIPS 203 anticipates this by forbidding one of the most dangerous constructs outright: implementations “shall not use floating-point arithmetic,” because floating-point rounding both risks incorrect results and tends to run in variable time. Constant-time coding is not a nicety layered on top of a correct implementation. It is a correctness requirement of a secure one.

Source: NIST, FIPS 203, §3.3 (no floating-point arithmetic), csrc.nist.gov/pubs/fips/203/final.

How do randomness and nonce reuse break PQC?

Randomness is a security-critical input to the post-quantum algorithms, and reusing it or drawing it from a weak source can collapse the guarantee the algorithm was supposed to provide, because the security proofs assume fresh, unpredictable, unique random values at exactly the points the standard specifies. FIPS 203 makes the requirement explicit and quantitative.

1. Fresh randomness every time. Key generation and encapsulation each draw random bytes internally, and the standard states that “a fresh string of random bytes must be generated for every such invocation.” Reusing the bytes across two encapsulations, or across key generations, breaks the independence the security rests on.
2. An approved generator at a matched strength. Those bytes “shall be generated using an approved RBG,” and that generator “shall have a security strength of at least 128 bits for ML-KEM-512, at least 192 bits for ML-KEM-768, and at least 256 bits for ML-KEM-1024.” A weak or low-entropy generator undercuts the whole parameter set regardless of how strong the lattice is.

Source: NIST, FIPS 203, §3.3 (randomness generation requirements), csrc.nist.gov/pubs/fips/203/final.

The signature side is even less forgiving of randomness failure. Randomized signature schemes that reuse a per-signature nonce across two different messages can leak the long-term signing key directly, which is the exact failure that has broken classical ECDSA deployments repeatedly, and the lesson carries into the post-quantum signatures. A weak generator shared across a device fleet also turns a randomness bug into a multi-target break, because one flawed seed compromises every device that shares it. The defense is a properly seeded CSPRNG delivering unique values at every draw the standard requires, which is why the generator is treated as part of the cryptographic module rather than an afterthought.

What is a decryption-error oracle, and how does the FO transform fit?

A decryption-error oracle is any observable difference in how a system responds to a malformed ciphertext versus a well-formed one, and it is dangerous because the lattice cores inside the post-quantum KEMs leak secret-key information through the pattern of which crafted ciphertexts decrypt cleanly and which fail. The Fujisaki-Okamoto transform exists to close that oracle, and an implementation that reintroduces it undoes the transform’s entire purpose.

The mechanism ML-KEM uses is implicit rejection. At decapsulation the implementation re-encrypts the recovered message, compares the result against the ciphertext that arrived, and on a mismatch returns a pseudorandom value derived from a stored secret seed rather than an error, so that from the outside a rejected ciphertext is output-indistinguishable from an accepted one and the attacker gets no accept-or-reject hint to feed the oracle. That indistinguishability is the security property, and it is fragile against implementation shortcuts.

FIPS 203 is emphatic about the one internal value that would betray it. The standard specifies that the “‘implicit reject’ flag computed in step 9 (by comparing c and c′) is a secret piece of intermediate data” and that “this flag shall be destroyed” before decapsulation finishes, so it is never returned in any form. An implementation that returns a distinct error on a bad ciphertext, or that leaks the accept/reject decision through a timing difference, an error message, a log line, or a downstream behavior change, hands the attacker exactly the fact the FO transform was built to hide, and the decryption-error oracle is back. The transform’s protection is only as good as the implementation’s discipline about never leaking that single flag.

Source: NIST, FIPS 203, §3.3 and §6.3 (the implicit-reject flag is secret intermediate data that shall be destroyed), csrc.nist.gov/pubs/fips/203/final.

The related requirement is input checking. FIPS 203 requires that encapsulation and decapsulation “are only executed on inputs that have been checked,” with explicit type and length checks on keys and ciphertexts, because skipping validation is another way a malformed input produces a distinguishable, secret-leaking response.

Source: NIST, FIPS 203, §3.3 and §7 (input checking on Encaps and Decaps), csrc.nist.gov/pubs/fips/203/final.

How does fault injection turn a correct algorithm hostile?

Fault injection is a physical attack that deliberately corrupts a computation, by glitching the power supply, the clock, or the temperature, or by hitting the chip with a laser, so that a step the algorithm depends on produces the wrong result or is skipped entirely, and the corrupted output leaks a secret or bypasses a check. It attacks the hardware executing the algorithm rather than the algorithm, which is why a mathematically sound scheme is exposed to it.

Two shapes matter for post-quantum code specifically.

1. Skipping a verification step. The FO re-encryption check in a KEM, or a signature’s own internal verification, is exactly the kind of conditional a fault can target: a glitch that forces the comparison to pass turns implicit rejection off, so the device happily decapsulates malformed ciphertexts and reopens the decryption-error oracle from the hardware side.
2. Corrupting a signature computation. For lattice signatures, inducing a fault during signing can produce a faulty signature that, combined with a correct one over the same message, leaks information about the secret key, a differential fault attack. The classical precedent is the fault attack on RSA-CRT signatures, and the lattice schemes have their own studied variants.

The defenses are countermeasures baked into the implementation and the hardware: verifying a signature before releasing it (so a faulted signature is caught internally), redundant or checked computation of sensitive steps, and physical sensors that detect glitching. FIPS 203’s requirement to destroy intermediate values and treat the reject flag as secret is a first line, but fault resistance is a hardware-and-implementation property that has to be designed in, especially for devices an attacker can hold like smartcards, HSMs, and embedded modules. The abstract algorithm assumes its steps execute faithfully; fault injection breaks that assumption, and only the implementation can defend it.

Source: NIST, FIPS 203, §3.3 (destruction of intermediate values), csrc.nist.gov/pubs/fips/203/final.

How do you catch these before they ship?

You catch implementation pitfalls with a testing regime aimed at the running code and the hardware, because none of these bugs show up in a functional test: an implementation with a timing leak, a reused nonce, or a fault vulnerability still produces correct outputs on valid inputs, so it passes every “does it work” check while remaining broken. Per Testing as the Control Surface, deploying the algorithm is the claim and validating the deployment is the security.

1. Constant-time verification. Use tooling that checks for secret-dependent branches and memory accesses, and statistical timing tests against the running binary, so a KyberSlash-style division leak is caught before an attacker finds it.
2. Known-answer and cross-implementation tests. Run the standard’s official test vectors and cross-check against an independent implementation, so a subtle arithmetic or FO-rejection error surfaces as a mismatch.
3. Malformed-input and oracle testing. Feed deliberately invalid ciphertexts and observe whether the response, in value, in timing, and in error behavior, is indistinguishable from a valid one, so a leaked reject flag is caught as a distinguishable difference.
4. Randomness validation. Confirm the generator is an approved DRBG at the required strength and that fresh bytes are drawn per invocation, so a reused seed or a weak source is found in review rather than in production.
5. Fault and side-channel evaluation for exposed hardware. For smartcards, HSMs, and embedded targets, run physical side-channel and fault-injection evaluation, because those threat models only appear when an attacker can hold the device.

Source: NIST, FIPS 203, §3.3 (input checking, approved RBG, destruction of intermediate values as conformance requirements), csrc.nist.gov/pubs/fips/203/final.

The organizing idea is that the standard tells you what a secure implementation must do, and testing is how you prove yours actually did it. A migration that swaps in a post-quantum library and runs a functional smoke test has verified that the algorithm computes, and has verified nothing about whether it computes securely, which is the gap every pitfall on this page lives in.

Common misconceptions

• “We deployed the NIST standard, so we are secure.” FIPS 203 says in its own text that conformance does not guarantee security. The standard specifies a correct algorithm, and the security depends on constant-time code, fresh randomness, careful reject handling, and fault resistance that the implementation has to supply.
• “The security proof means the code is safe.” A proof covers the algorithm as an abstract object and excludes timing, power, cache behavior, and physical faults. Real implementations emit exactly those side channels, which is why proven algorithms are still broken through their code.
• “If it passes the test vectors, it is fine.” Known-answer tests confirm the algorithm computes the right output, and a timing leak, a reused nonce, or a fault vulnerability all produce correct outputs on valid inputs, so they sail through functional tests while leaving the implementation exploitable.
• “Nonce and randomness handling is a classical problem, not a post-quantum one.” FIPS 203 requires fresh approved randomness at a specified strength for every key generation and encapsulation, and randomized signatures leak their key on nonce reuse, so randomness discipline is fully load-bearing in the post-quantum standards.
• “The FO re-encryption check is redundant work I can optimize away.” That check is the chosen-ciphertext-security mechanism, and the internal accept/reject flag is secret data the standard requires you to destroy. Leaking or skipping it reopens the decryption-error oracle the transform exists to close.

Questions people ask

Why can a mathematically proven algorithm still be broken in practice? Because the proof models the algorithm as pure input-output behavior, while a running implementation also emits timing, power draw, cache patterns, and behavior under physical fault, and any of those can carry secret information the proof never accounted for. FIPS 203 states outright that conformance does not guarantee security.

What is constant-time code and why does PQC need it? Constant-time code runs in the same time and touches the same memory no matter what secret it processes, so an observer learns nothing from watching it. PQC needs it because a secret-dependent branch or table lookup leaks timing an attacker measures to recover the key, which is exactly the KyberSlash division bug in real ML-KEM libraries.

What happens if an implementation reuses randomness? It can collapse the security the algorithm assumed. FIPS 203 requires fresh bytes from an approved generator for every key generation and encapsulation, and on the signature side reusing a per-signature nonce across messages can leak the signing key directly, the same failure that has broken classical ECDSA.

What is a decryption-error oracle? It is any observable difference in how a system responds to a malformed ciphertext versus a valid one. The lattice cores leak key information through that difference, which is why ML-KEM wraps them in the Fujisaki-Okamoto transform and why FIPS 203 requires the internal reject flag to be kept secret and destroyed rather than leaked.

How is fault injection different from a timing side channel? A timing side channel passively reads secret-dependent variation out of normal execution, while fault injection actively corrupts the execution, glitching power or clock to skip a check or spoil a computation, so the device produces a faulty output that leaks a secret or bypasses verification. It is the main reason smartcards and HSMs need hardware countermeasures.

How do I make sure my post-quantum deployment is implemented securely? Test the running code, not the abstract algorithm: constant-time analysis, official known-answer vectors cross-checked against an independent implementation, malformed-input oracle testing, randomness-source validation, and physical fault and side-channel evaluation for any hardware an attacker can hold. Testing is what proves the implementation did what the standard requires.

---

Everything here is the map, given freely. When your team needs its own post-quantum implementations and hardware assessed for the timing, randomness, oracle, and fault weaknesses that a functional test never catches, that’s what an alignment briefing is for.

Last verified 2026-07-12 · Maintained by Addie LaMarr, LaMarr Labs.