Decapsulation Failures and Their Consequences: Failure-Boosting Attacks

It is tempting to dismiss a decapsulation failure as a rounding curiosity — an event so rare that in normal operation it will never be seen. That view is wrong in a way that shaped the standard's parameters. Because the underlying scheme hides its message in noise with a finite decoding margin, there is a nonzero probability that noise exceeds the margin and decapsulation fails, and an attacker who can search for ciphertexts more likely to fail, and observe when they do, learns something about the secret key with each one. The failure probability is therefore a security parameter, driven astronomically low on purpose, and this article explains the attack it defends against and the layered defenses that make it safe.

A failure is a nonzero, exploitable event

Recall the mechanism of a failure. Decapsulation recovers the message by subtracting the secret-derived mask and rounding each coordinate to the nearer of two encoded values; this is correct only while the leftover noise stays below a quarter of the modulus. The noise is a random combination of the small errors from key generation and encryption, and although its typical magnitude is comfortably within the margin, its distribution has a tail: with small probability some coordinate's noise exceeds the margin and that coordinate decodes to the wrong bit, making the whole decapsulation produce a different key than the sender intended.

This probability is tiny but strictly positive, and the two parties then disagree about the shared secret. In an honest run that is merely a rare protocol hiccup. In an adversarial setting it is a signal, because whether a given ciphertext causes a failure depends on the secret key — a ciphertext fails precisely when the noise it induces, which is shaped by the secret, crosses the threshold. Each failure is thus correlated with the secret, and correlation is what an attacker mines.

The reason this rises to a genuine threat rather than a curiosity is that an attacker need not wait for random failures. It can deliberately hunt for ciphertexts that are unusually likely to fail, concentrating its queries where the signal is strongest. That hunt is the heart of the failure-boosting attack.

Failure-boosting: hunting weak ciphertexts

Failure-boosting, analyzed by D'Anvers and collaborators, is a precomputation strategy. The attacker does not submit random ciphertexts; it first searches offline for weak ones — ciphertexts whose structure makes the induced noise unusually large and therefore more likely to cross the decoding threshold. By generating many candidate encapsulations and estimating each one's failure probability from its noise magnitude, the attacker keeps only the rare candidates that are much likelier than average to fail, effectively boosting the failure rate it will experience online above the honest baseline.

The attack has two phases with distinct costs. The offline phase is the search for weak ciphertexts, whose cost grows as the target failure probability shrinks, because weak ciphertexts become rarer. The online phase submits these boosted ciphertexts to the decapsulating party and watches for the failures that reveal information. The total effort is a product of how hard it is to find weak ciphertexts and how many observed failures are needed, and the standard's job is to make that product infeasible.

A refinement, multitarget failure-boosting, amortizes the expensive offline search across many victims, so that a single precomputation helps attack many keys. This raises the stakes, because it means the offline cost cannot simply be charged once per target. The parameters must be chosen so that even amortized, boosted, multitarget search cannot surface enough failures to matter.

What one failure leaks

A single observed failure is a geometric fact about the secret. A failure means the noise on some coordinate exceeded the threshold, and that noise is an inner product between quantities the attacker knows — derived from the ciphertext it chose — and the unknown secret and error. So a failure tells the attacker that this known vector has an unusually large inner product with the secret: an inequality that carves away part of the space of possible secrets, revealing a little about the secret's direction. It is a noisy, partial linear constraint, not a full disclosure.

One such constraint is nearly useless, but they accumulate. Each additional failure, from a ciphertext with a different known vector, adds another inequality, and together they pin down the secret's geometry ever more tightly. With enough failures an attacker can statistically reconstruct the secret key, the same way many partial measurements of a hidden vector eventually determine it. The attack's power scales with the number of failures it can collect against a single fixed secret.

This is the crux of why the failure probability is a security parameter and why the key's lifetime matters. The danger is not a single failure but the accumulation of many against the same key, and both levers of the attack — how easily failures are found and how many can be gathered per key — are exactly what the defenses target.

Three layers of defense

The first and most important defense is to make the failure probability astronomically small. The standardized parameters drive it far below any feasible query budget — orders of magnitude beyond one in a nonillion, below two to the negative one-hundred-thirty-eighth for the base parameter set and smaller for the higher ones. At that level, even an attacker who boosts the rate and searches across many targets cannot find enough failures within any computation it could actually perform. Correctness is engineered so deeply that the failure tail is simply out of reach.

The second defense is the implicit rejection from the Fujisaki-Okamoto transform. Because a failed decapsulation returns a pseudorandom key rather than a visible error, an attacker probing a single decapsulation cannot directly tell that a failure occurred — the observable signal is suppressed at the mechanism level. This does not by itself stop failures that manifest as a downstream protocol disagreement, but it removes the easy oracle and forces the attacker to rely on higher-level, noisier signals.

The third defense is ephemeral keys. Since the attack needs many failures against one fixed secret, using a fresh key pair for each exchange — as post-quantum key exchange does in a handshake — denies the attacker the chance to accumulate failures against a single key. Even if a failure could be found and observed, it would concern a key that is never used again. Static, long-lived keys are the riskier configuration precisely because they let failures pile up, so ephemeral use is the recommended default wherever the protocol allows it.

Correctness is security

The overarching lesson is that for a noise-based key-encapsulation mechanism, correctness and security are not separate concerns. The same decoding margin that determines whether honest decapsulation succeeds also determines how much a failure would leak and how hard failures are to provoke. Choosing parameters is therefore a joint optimization: enough noise for security against the lattice attacks of the earlier track, small enough failure probability that the failure-boosting attack is infeasible, and compact enough ciphertexts to be practical. The standardized sets sit at a carefully balanced point in that space.

This also reframes the earlier articles. The nonzero failure probability that appeared as a footnote in the encryption scheme, and as a term in the Fujisaki-Okamoto security bound, is revealed here as a live attack surface that those parameters and that transform were designed to close. The pieces fit together: the transform hides individual failures, the parameters make them unfindable, and correct key hygiene prevents them from accumulating.

For autonomous AI systems the practical guidance is concrete and mostly about configuration. Use the standardized mechanism with its parameters unchanged — never widen the noise or shrink it to tune performance, since either can move the failure probability into dangerous territory — and prefer ephemeral key exchange, which the hybrid handshakes protecting model and agent traffic already do, so that no single key ever sees enough traffic for failures to accumulate. Where a static key must be used, its exposure to attacker-chosen ciphertexts should be minimized and monitored. The failure tail is fully defended in the standard, but only if its parameters and ephemeral-key assumptions are respected in deployment.

Practitioner Toolkit

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

kem_failure_defense:
  parameters: standardized_unchanged
  failure_probability: below_2^-138
  implicit_rejection: preserved
  key_mode: ephemeral_preferred
  static_key: minimize_and_monitor
principle:
  correctness_is_security: true
  retune_noise: forbidden

Glossary

Decapsulation failure

The event that decapsulation recovers a different key than intended because noise exceeded the decoding margin; nonzero and secret-correlated.

Failure-boosting

Precomputing to find weak ciphertexts with unusually large noise, raising the effective failure rate an attacker observes above the honest value.

Multitarget failure-boosting

Amortizing the expensive offline search for weak ciphertexts across many victim keys.

Leaked inequality

The geometric constraint on the secret revealed by an observed failure: a known vector has an unusually large inner product with the secret.

Ephemeral key

A key pair used for a single exchange, denying the attacker the chance to accumulate many failures against one secret.

Correctness-is-security

The principle that in a noise-based KEM the decoding margin governs both honest correctness and resistance to failure attacks, so they are optimized jointly.

References

1. D'Anvers et al., On the Impact of Decryption Failures on the Security of LWE/LWR-Based Schemes (IACR ePrint 2018/1089)
2. NIST FIPS 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard (2024)
3. Bos et al., CRYSTALS-Kyber: A CCA-Secure Module-Lattice-Based KEM (IEEE EuroS&P, 2018)
4. Hofheinz, Hovelmanns & Kiltz, A Modular Analysis of the Fujisaki-Okamoto Transformation (TCC, 2017)
5. Regev, On Lattices, Learning with Errors, Random Linear Codes, and Cryptography (JACM, 2009)