RSA Timing and CRT Faults: What Each Defence Actually Covers

An RSA private key can be perfectly secret in the mathematical sense, impossible to compute from the public key, and still leak through the way it is used. Two families of attack exploit this. The first watches how long private-key operations take, or what other measurable traces they leave, and works backwards to the key. The second does not watch at all; it interferes, causing a private-key computation to go slightly wrong, and then exploits the wrong answer. Paul Kocher described the first family against RSA, Diffie-Hellman and DSS in 1996. Dan Boneh, Richard DeMillo and Richard Lipton described the second in 1997, with a particularly sharp result: when RSA uses the Chinese remainder theorem for speed, a single faulty signature can reveal a factor of the modulus to anyone who holds the correct public key. Engineers usually respond with a short list of defences, constant-time code, blinding and result checking, and treat them as roughly interchangeable. This article argues that they are not. Each defence covers a specific set of attacks, the sets barely overlap, and a deployment that relies on one or two of them has predictable gaps. The goal is a coverage map precise enough to review real implementations against, including the many RSA operations performed today by AI agent platforms.

Two families: observation and interference

RSA decryption and signing raise a value to the private exponent modulo the public modulus. Implementations typically compute this with repeated squaring and multiplication driven by the bits of the exponent, and, for speed, split the computation across the two secret primes using the Chinese remainder theorem (CRT), then recombine the two partial results. Both choices create attack surface. Exponentiation that does different work depending on exponent bits can leak those bits through its timing or other measurable effects. CRT creates two independent half-computations whose consistency an attacker can try to break.

Observation attacks, broadly called side-channel attacks, measure something the computation emits: elapsed time, cache access patterns, power consumption or electromagnetic radiation. Interference attacks, called fault attacks, perturb the computation, for example through voltage glitches, clock manipulation, laser pulses or, in some environments, software-induced memory errors, and then exploit the incorrect output. The two families need different access, different equipment and different defences, and conflating them is the root of most coverage gaps.

Timing attacks: from Kocher's model to remote measurement

Kocher's 1996 insight was that the time a private-key operation takes is a sum of many small operation times, some of which depend on secret data, for example whether a particular exponent bit causes an extra multiplication, or whether a modular reduction step needs a final subtraction. An attacker who can submit chosen inputs and time the responses can build a statistical model, guess the next unknown exponent bit, predict how the timing should behave under each guess, and keep the guess that best matches the measurements. Repeated bit by bit, this recovers the exponent. The attack needs many measurements, but noise can be averaged away.

Later research showed that such measurements need not be local. Brumley and Boneh demonstrated in 2003 that timing differences in a widely used library's RSA implementation could be measured over a local network well enough to extract a server's private key, establishing that remote timing attacks against RSA are practical when implementations are not constant time. Microarchitectural variants, which observe shared processor caches or branch predictors from a co-located process, extend the same idea to finer-grained leaks in shared computing environments.

The structural lesson is that any secret-dependent variation in work, memory access or control flow is a potential leak, and that the attacker's position, local, co-located or remote, mainly changes how many measurements are needed.

Fault attacks on CRT: one bad signature

Boneh, DeMillo and Lipton showed in 1997 how fragile CRT makes RSA signing. In CRT signing, the signature is computed separately modulo each secret prime and then recombined. Suppose a fault corrupts exactly one of the two half-computations, say the one modulo the first prime, while the other completes correctly. The resulting faulty signature is still correct modulo the second prime but wrong modulo the first. An attacker who holds both the faulty signature and, depending on the variant, either the correct signature or simply the message and the public key, can compute a value that is divisible by the second prime but not by the first, and a single greatest-common-divisor computation with the modulus then reveals the second prime, which factors the modulus and yields the private key.

Several properties make this attack severe. It needs only one successful fault, not many. The fault does not need to be precise, only to affect one half of the computation. And because the faulty output is released as if it were valid, any party that receives it, not only the one who caused the fault, may be able to exploit it. Faults can arise from deliberate physical attacks on smart cards and hardware modules, but also from accidental hardware errors, which means the vulnerability exists even without a determined adversary.

The attack does not apply in the same form to non-CRT RSA, but non-CRT RSA is roughly four times slower and has its own, less dramatic fault vulnerabilities. In practice, essentially all production RSA uses CRT, so the defence must be applied rather than avoided.

The three defences, precisely

Constant-time implementation means that the sequence of instructions executed and the memory addresses accessed do not depend on secret values. For RSA exponentiation this typically means processing every exponent bit or window with the same operations, selecting precomputed values with arithmetic masking rather than secret-indexed table lookups, and using modular arithmetic routines whose reduction steps do not branch on secrets. Constant-time code removes the variation that timing and many microarchitectural attacks measure.

Blinding randomises the data the exponentiation operates on, so that even a leaky computation leaks information about values the attacker does not know. Base blinding, described by Kocher and standard in RSA implementations, multiplies the input by a random value raised to the public exponent before the private operation and removes the factor afterwards; the attacker's chosen input is therefore never what is actually exponentiated, which defeats chosen-input statistical modelling. Exponent blinding adds a random multiple of the group order to the private exponent for each operation, so the exponent bits processed differ every time, which frustrates attacks that accumulate information about fixed exponent bits across many traces.

Result checking verifies a computed signature or decryption before releasing it, typically by applying the public exponent and comparing with the input, which is cheap because the public exponent is small. If a fault corrupted the computation, the check fails and the output is withheld. Result checking is the defence that directly addresses the CRT fault attack. Variants check consistency of the CRT components themselves, but the end-to-end public-key check is the simplest and most widely recommended, and RFC 8017 describes the CRT representation whose components must remain consistent.

A coverage matrix

Mapping the defences against the attack classes yields the main contribution of this article. Remote and local timing attacks that depend on chosen inputs are stopped by constant-time code and substantially weakened by base blinding. Microarchitectural attacks that observe secret-dependent memory access or branches are stopped by constant-time code and only partly mitigated by blinding, which changes values but not access patterns if the code itself is not constant time. Power and electromagnetic attacks that average many traces of fixed exponent bits are mitigated mainly by exponent blinding together with hardware countermeasures. Single-fault CRT attacks are stopped only by result checking; neither constant-time code nor blinding affects them at all.

The matrix makes the gaps visible. A deployment with constant-time code and blinding but no result checking is fully exposed to the CRT fault attack. A deployment with result checking but secret-dependent code is exposed to timing and cache attacks. In this article's synthesis, the minimum robust configuration for software RSA is constant-time exponentiation, base blinding and result checking, with exponent blinding and hardware countermeasures added where physical observation is in scope.

The matrix also explains a common review mistake: accepting 'the library uses blinding' as evidence of side-channel resistance in general. Blinding is a strong control in its column and irrelevant in another.

How defences get bypassed

Each defence has characteristic failure modes. Constant-time guarantees can be broken by compilers that turn masked selections back into branches, by modular arithmetic routines with data-dependent early exits, and by library paths, such as key loading or format conversion, that were not written with the same discipline as the core exponentiation. Blinding can be weakened when the blinding factor is reused across operations or generated with poor randomness, which lets an attacker cancel it out. Result checking can be bypassed if the check itself is skipped for performance, if a fault is injected after the check but before output, or if the check compares against a value the fault also corrupted.

The defensive implication is that each control needs its own verification: binary-level analysis or statistical timing tests for constant-time code, review of blinding-factor generation and refresh, and fault-injection testing in hardware evaluations, or at least code review confirming that the check sits immediately before release. A control that is present in source but absent in the compiled or deployed path provides no coverage.

Exposure in AI agent platforms

AI agent platforms perform RSA private-key operations at a scale and in settings that favour both attack families. Agents may sign JSON Web Tokens with RS256 or PS256 for every tool call, unwrap keys with RSA-OAEP, or authenticate with client certificates, often from shared cloud hosts where other tenants' workloads run nearby. Remote timing attacks need many measurements; an agent that performs thousands of signatures a day on behalf of inputs an attacker can partly influence, for instance through injected content that causes repeated tool calls, supplies measurements at no cost. Shared hosts bring microarchitectural observation into scope.

Faults deserve attention for a different reason. Agent platforms frequently run on large fleets of commodity hardware, where accidental memory and computation errors are a statistical certainty at scale. Without result checking, an occasional faulty CRT signature produced by a hardware error, not an attacker, would be released, logged and possibly stored, exposing a prime to anyone who later finds it. This article presents that as a reasoned exposure rather than a documented agent incident, but the mechanism requires no adversary at all.

The defensive response is to keep RSA private-key operations out of agent processes entirely, performing them in a key management service or hardware security module that is evaluated against timing and fault attacks, and to confirm that any software fallback implements all three defences.

Limitations

This article analyses mechanisms and defences conceptually and omits the statistical and algebraic details needed to mount the attacks. It focuses on RSA; analogous issues for elliptic-curve and post-quantum schemes involve different mechanisms and defences. The coverage matrix reflects the primary literature cited and general practice rather than an evaluation of any particular library. The agent-platform analysis is an extrapolation from known mechanisms and fleet characteristics, not a measured incident. Finally, high-assurance environments require formal side-channel and fault evaluation by specialists; the matrix is a review aid for engineers, not a substitute for such evaluation.

Practitioner Toolkit

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

classes = partition_inputs_by_secret_dependent_property(test_key)
for cls in classes:
    times[cls] = [time(private_op(test_key, x)) for x in sample(cls, N)]
assert distributions_indistinguishable(times)   # e.g. fixed-vs-random input test
assert result_check_enabled(test_build)
assert blinding_factor_refreshed_per_operation(test_build)

rsa_private_operations:
  allowed_locations: [evaluated_kms, hsm]
  agent_process_private_keys: forbidden
  software_fallback_requirements:
    constant_time_exponentiation: required
    base_blinding: required
    result_checking: required
  high_volume_signing: prefer_ed25519_where_interoperable

Glossary

Side-channel attack

An attack that learns secrets from measurable effects of a computation, such as time, cache use or power.

Fault attack

An attack that induces errors in a computation and exploits the incorrect output.

Chinese remainder theorem (CRT)

The result used to split RSA private-key operations across the two primes and recombine them for speed.

Constant-time implementation

Code whose instruction sequence and memory accesses do not depend on secret values.

Base blinding

Randomising the input to an RSA private operation so the attacker's chosen value is never exponentiated directly.

Exponent blinding

Adding a random multiple of the group order to the private exponent for each operation.

Result checking

Verifying a private-key result with the public key before releasing it, to catch faulty computations.

Microarchitectural attack

A side-channel attack that observes shared processor state such as caches or branch predictors.

References

1. P. C. Kocher, Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems, CRYPTO 1996
2. D. Boneh, R. A. DeMillo, R. J. Lipton, On the Importance of Checking Cryptographic Protocols for Faults, EUROCRYPT 1997
3. D. Brumley, D. Boneh, Remote Timing Attacks Are Practical, USENIX Security 2003
4. RFC 8017: PKCS #1: RSA Cryptography Specifications Version 2.2 (IETF)
5. R. L. Rivest, A. Shamir, L. Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Communications of the ACM, 1978