Timing and the Decapsulation Oracle: When Non-Constant-Time Handling Leaks the Plaintext

The Fujisaki-Okamoto transform earned its place by removing the chosen-ciphertext oracle: after the transform, submitting malformed ciphertexts to a decapsulation routine was supposed to teach an attacker nothing, because implicit rejection returns an unpredictable key indistinguishable from success. That guarantee holds only if the implementation reveals nothing beyond its output. A decapsulation whose running time depends on whether the ciphertext was valid violates exactly that condition, handing the attacker back the oracle the transform removed — this time through the clock rather than the return value. And a plaintext-checking oracle, once available, unravels the secret key in a few thousand queries. This article shows how the leak arises, how it is weaponized, and how to close it.

Where secrets flow in decapsulation

Recall the decapsulation sequence. The routine decrypts the incoming ciphertext with the secret key to recover a candidate message, re-encrypts that candidate deterministically, compares the re-encryption to the received ciphertext, and returns either the real shared secret on a match or a pseudorandom rejection key on a mismatch. Every one of these steps touches secret-derived data: the decryption uses the secret key, the recovered message is secret, the comparison operates on secret-dependent values, and the choice between the real and rejection key is secret-dependent.

Because the transform's security depends on an attacker being unable to distinguish a valid from an invalid ciphertext, the implementation must make all of these steps indistinguishable in every observable dimension — not just in the returned value but in time, memory access, and power. The one that is easiest to get wrong, and most remotely observable, is time. If the routine finishes measurably faster or slower depending on whether the ciphertext was valid or what the recovered message was, that timing is a channel carrying the exact bit the transform tried to hide.

This is the crux: the transform's proof models decapsulation as a function that reveals only its output, and a variable-time implementation is not that function. The proof remains true about the idealized object while the real object leaks, which is why an implementation can be a faithful transcription of a proven-secure scheme and still be trivially broken. The gap between the proven object and the running object is precisely the timing side channel.

A plaintext-checking oracle from timing

The leak gives the attacker a plaintext-checking oracle: the ability to submit a ciphertext and learn, from the timing, whether it decrypts to a particular value the attacker has in mind. Concretely, an attacker crafts a ciphertext designed so that decapsulation behaves one way if the recovered message equals a target and another way otherwise — for instance, so that a valid-looking result triggers the fast path and an invalid one the slow path, or vice versa. Timing the response reveals which case occurred, and hence one bit about the relationship between the ciphertext and the secret.

This is exactly the chosen-ciphertext capability the transform was meant to deny. The attacker is not decrypting arbitrary traffic; it is adaptively submitting ciphertexts of its own construction to a decapsulating party and reading the timing reaction, which is the classic reaction attack in physical form. The plaintext-checking oracle is weaker than a full decryption oracle — it answers only yes-or-no about a guessed plaintext — but as the next section shows, yes-or-no answers are enough.

The attack is feasible remotely when the timing difference survives network jitter, which careful statistical measurement across many repetitions can often achieve, and it is far easier for a co-resident or physically present attacker with lower-noise measurements. The point is that implicit rejection, the mechanism that hides validity in the return value, does nothing to hide validity in the timing unless the code is explicitly written to run in constant time.

From oracle to full key recovery

A plaintext-checking oracle recovers the entire secret key, and the method is systematic. The attacker targets one coefficient of the secret at a time. It constructs ciphertexts whose decapsulation outcome depends on whether that coefficient is above or below a chosen threshold, and queries the oracle; each answer halves the range of possible values for the coefficient, a binary search. Repeating the search pins down the coefficient exactly, and iterating over all coefficients reconstructs the whole secret vector.

The cost is modest. Each coefficient needs a logarithmic number of queries in its value range, and the secret has a few hundred small coefficients, so the total is on the order of a few thousand oracle queries — well within reach of an attacker who can send that many ciphertexts and time the responses. Published attacks of this shape, analyzed in the side-channel survey literature, recover the full key of the standardized mechanism from a non-constant-time implementation with exactly this query budget. There is no large computation; the work is almost entirely in the timed interaction.

This efficiency is what makes the timing leak catastrophic rather than merely concerning. It is not a marginal reduction in security but a total break: the secret key, which the entire scheme exists to protect, is extracted by an attacker who never sees a single plaintext, only the time decapsulation takes. A single exploitable timing difference, multiplied across a few thousand adaptive queries, is the whole key.

Where the timing actually leaks

The leak hides in a few specific places. The most common is the ciphertext comparison in the re-encryption check: a comparison that returns as soon as it finds a differing byte takes a time that depends on how far the two ciphertexts agree, leaking information about the recovered message. The second is the implicit rejection itself: selecting between the real and rejection key with an ordinary conditional branch, rather than a branchless move, makes the two paths take different times and possibly different cache footprints, directly exposing validity.

Subtler sources abound. The message-decoding step that maps recovered coordinates back to bits can use variable-time operations; a secret-dependent division or modulo compiles to variable-latency instructions on many processors; and a table lookup indexed by secret data leaks through the cache. Worst of all, a comparison written to be constant-time in the source language can be silently rewritten by an optimizing compiler into branchy machine code, so that source-level constant-time discipline is undone by the toolchain. Constant-time in intent is not constant-time in the emitted instructions.

The unifying lesson is that every operation on the secret path — comparison, selection, decode, arithmetic, memory access — must be verified to run in secret-independent time and access pattern, at the level of the actual machine code, not the source. A single overlooked spot is sufficient for the full-key recovery of the previous section, so the requirement is not that most of the path be constant-time but that all of it is.

Closing the oracle

The defense is uncompromising constant-time discipline over the whole secret path. The re-encryption comparison must examine every byte regardless of where the ciphertexts first differ. The implicit rejection must select the returned key with a branchless conditional move that computes both candidates and picks one without a data-dependent branch. Message decoding and all secret arithmetic must use secret-independent operations, avoiding variable-latency instructions and secret-indexed memory. And the result must be verified on the compiled machine code, because only the emitted instructions determine the actual timing behavior.

This is why the earlier articles insisted on using a validated, reviewed implementation rather than transcribing the specification's pseudocode. The pseudocode is written for clarity and its natural transcription is full of exactly the early exits and branches that leak; a hardened library has had each of these spots identified, rewritten, and tested for constant-time behavior against the real compiler and hardware. Constant-time correctness is a property of a specific compiled binary on a specific processor, not of an algorithm in the abstract, and it must be established empirically, which the final article of this series addresses.

For autonomous AI systems the exposure is direct and remote. A model-serving endpoint or an agent that decapsulates ciphertexts is a network-reachable decapsulation routine, and if it is not constant-time it is a remotely queryable plaintext-checking oracle — an attacker can send it a few thousand crafted ciphertexts, time the responses, and extract its private key without any physical access. The defense is to ensure the decapsulation library used by every agent and model endpoint is a validated constant-time implementation, verified on the actual deployment target, and to treat any such endpoint as an oracle an adversary will probe. The transform closed this attack in theory; only constant-time implementation keeps it closed in practice.

Practitioner Toolkit

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

decapsulation:
  reencrypt_compare: constant_time_all_bytes
  implicit_rejection: branchless_conditional_move
  message_decode: secret_independent
  arithmetic: no_variable_latency_on_secret
  memory: no_secret_indexed_lookup
verification:
  level: compiled_binary_on_target
endpoint:
  treat_as: plaintext_checking_oracle_if_leaky

Glossary

Plaintext-checking oracle

The ability to learn whether a chosen ciphertext decrypts to a particular value; obtained from a decapsulation timing leak.

Reaction attack

Adaptively submitting crafted ciphertexts and observing the victim's reaction (here, timing) to extract secret information.

Constant-time comparison

A comparison that examines every byte regardless of where inputs first differ, so its duration does not depend on the data.

Branchless conditional move

Selecting between two values without a data-dependent branch, used for implicit rejection so validity is not exposed by timing.

Compiler-induced leak

An optimizing compiler rewriting source-level constant-time code into branchy machine code, undoing the intended timing invariance.

Full-key recovery

Reconstructing the entire secret key by binary-searching each coefficient through a few thousand oracle queries.

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. Ravi et al., Side-Channel and Fault Analysis of Lattice-Based KEMs and Signatures (IACR TCHES survey)
3. Kocher, Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS (CRYPTO, 1996)
4. NIST FIPS 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard (2024)
5. Hofheinz, Hovelmanns & Kiltz, A Modular Analysis of the Fujisaki-Okamoto Transformation (TCC, 2017)