Chapter 26Side-Channel Security
26.1Learning objectives#
Every earlier chapter of this book argued about security on paper: a lattice problem is hard, a forgery reduces to Module-SIS, a distinguisher would break LWE. That kind of security is necessary. It is also not sufficient. A scheme does not run on paper; it runs on a physical device that takes time, draws current, radiates, and can be poked with a laser. If any of those measurable, physical quantities depends on the secret key, an attacker can read the key off the machine without ever touching the mathematics. This chapter’s warning is blunt: the math can be perfect and the deployment still broken. It opens the final part of the book, on practice: correct, side-channel-safe implementation is one requirement among several for getting these schemes into real systems, alongside the protocol integration and migration that the chapters after it take up.
After finishing this chapter, you should be able to:
explain why provable, mathematical security is necessary but not sufficient, and say precisely what a side channel is;
name the main families of implementation attacks – timing, cache, power, electromagnetic, and fault – and state what each one actually observes;
state the rules of constant-time programming and write a constant-time conditional select and a constant-time comparison;
connect these ideas to concrete PQC design choices already met in this book: CBD instead of Gaussian sampling (15), Falcon’s floating-point sampler (18), ML-DSA’s deterministic abort loop (17), and the implicit rejection built into ML-KEM decapsulation (16);
describe the higher-order countermeasures – masking and blinding – and weigh their cost against constant-time coding.
Why this chapter matters.#
Shor’s algorithm, the threat that motivated the whole book, attacks the structure of the problem: it factors, it computes discrete logs. The schemes we built defeat it because no efficient quantum algorithm is known for the lattice and code problems underneath. A side-channel attack does something completely different. It ignores the problem structure and instead measures the execution: how long a decryption took, which cache lines it touched, how much power the chip drew on each clock cycle. These attacks are often far cheaper than the mathematical ones – minutes with an oscilloscope rather than aeons on a quantum computer – which is exactly why they matter. The concern is not hypothetical for PQC: several of the schemes in this book have delicate implementation requirements, and those requirements shaped the standards. It is why ML-KEM samples noise with CBD rather than a Gaussian (15), and why FN-DSA (based on Falcon; FIPS 206 remains in development) is especially delicate to deploy safely (18).
26.2The attack families#
A side channel is any observable output of the computation other than the intended result. Below are the families a PQC implementer must keep in mind. Each is sketched in one paragraph; the common thread is that all of them turn a physical measurement into information about the secret.
Timing attacks.#
The total time a computation takes depends on the data it processed [1]. If that data includes the secret, the running time leaks it. The textbook example is a comparison that returns as soon as it finds the first differing byte: an attacker who can vary an input and time the response learns the secret one byte at a time. Timing leaks are the most dangerous class because they need no special equipment and can often be measured remotely, over a network.
Cache attacks.#
Modern CPUs cache recently used memory. If a program indexes a table at a secret-dependent position – as many Gaussian samplers and cipher S-boxes do – then which table entries land in the cache depends on the secret. An attacker sharing the same machine (a co-resident cloud tenant, say) does not see the values, but can time its own memory accesses to learn which cache lines were touched, using techniques such as Flush+Reload or Prime+Probe. Secret-dependent memory addresses are therefore just as leaky as secret-dependent timing.
Power analysis.#
The instantaneous power a chip consumes correlates with the operations it performs and the bits it moves. Simple power analysis (SPA) reads a single trace to recognize the sequence of operations – for instance, telling a multiply from a square in a modular exponentiation, which spells out exponent bits. Differential power analysis (DPA) [2] is stronger: it collects many traces and correlates them, sample by sample, against a hypothesis about a few key bits, pulling the secret out even when it sits far below the measurement noise.
Electromagnetic analysis.#
A switching transistor radiates. The same information that power analysis reads from the supply line can be read from the electromagnetic emanations near the chip, often with a small probe and no electrical contact. EM analysis can also be spatially localized to a single region of the die, which sometimes defeats countermeasures that only balance the global power draw.
Fault injection.#
The attacks above are passive: they observe. Fault injection is active. By glitching the supply voltage or clock, or firing a laser or EM pulse at the die, an attacker induces a controlled error – a skipped instruction, a flipped bit, a corrupted value – and exploits the faulty output. Signature schemes are especially fragile here: a single faulty signature can, through differential fault analysis, reveal the signing key, and skipping a bounds check can leak the mask in a scheme like ML-DSA.
26.3Constant-time programming#
The central software defense against secret-dependent timing and cache leakage is constant-time programming. It is necessary but not sufficient for physical power or EM attacks. The name is slightly misleading: the goal is not that the code always takes the same wall-clock time, but that its timing, memory-access pattern, and operation sequence do not depend on secret data. Variation that depends only on public data (the length of a message, the public iteration count of a loop) is fine.
The discipline reduces to three rules:
No secret-dependent branches. An
ifwhose condition involves a secret takes one path or another, and the two paths almost never cost the same. Replace the branch with straight-line arithmetic.No secret-dependent memory indices. Never use a secret as an array index or a jump target. A table lookup at a secret address leaks through the cache even if the code has no branches at all.
Avoid variable-time instructions on secret data. Division and modulo, and on some processors even multiplication, take a data-dependent number of cycles. Early-exit library routines such as
memcmpare the same hazard in disguise. Use fixed-cost operations, or reduce with Montgomery/Barrett arithmetic instead of a hardware divide.
Figure 26.1 contrasts the hazard with its fix. On the left, a secret bit chooses between a short path and a long path; the difference in duration is the leak. On the right, the same choice is computed with a mask so that every input runs the identical sequence of operations.
The workhorse that removes a secret branch is the constant-time select. It turns the selector bit into an all-ones or all-zero mask and uses that mask to blend the two candidate values with bitwise arithmetic, so both candidates are always computed and no branch is taken.
The trick is the mask \(-s\): negating the bit \(1\) in two’s complement gives the all-ones word, and negating \(0\) gives the all-zero word. When \(s=1\) the first term passes \(a\) and the second term is zeroed; when \(s=0\) the roles swap. There is no branch and no secret-dependent address. The same masking idea gives a constant-time equality test, ct_eq, which must never return early: it accumulates the differences across all bytes and only then collapses the result to a single bit.
Listing 26.1 shows both patterns in C: the leaky branch, its masked replacement, and a no-early-exit comparison.
#include <stdint.h>
#include <stddef.h>
/* LEAKY: the branch condition is a secret; the two paths differ */
uint32_t leaky_select(int secret_bit, uint32_t a, uint32_t b) {
if (secret_bit) /* timing/cache/power all reveal which way */
return a;
else
return b;
}
/* CONSTANT-TIME: no branch, no secret-dependent memory access */
uint32_t ct_select(uint32_t secret_bit, uint32_t a, uint32_t b) {
uint32_t mask = -secret_bit; /* 0xFFFFFFFF if 1, 0x00000000 if 0 */
return (a & mask) | (b & ~mask);
}
/* CONSTANT-TIME equality: 1 if equal, else 0, never exits early */
uint32_t ct_eq(const uint8_t *x, const uint8_t *y, size_t n) {
uint8_t diff = 0;
for (size_t i = 0; i < n; i++)
diff |= x[i] ^ y[i]; /* fold every byte, no break */
/* top bit of (diff | -diff) is 1 iff diff != 0 */
uint32_t nz = ((uint32_t)diff | (0u - (uint32_t)diff)) >> 31;
return nz ^ 1u; /* invert: equal -> 1 */
}26.4PQC-specific concerns#
Constant-time discipline is general, but post-quantum schemes concentrate the risk in a few specific places. Each of the following ties back to a design choice made in an earlier chapter.
Sampling: the reason CBD exists.#
The noise in a lattice scheme must be sampled every time a key or ciphertext is made. A discrete Gaussian sampler is the natural mathematical choice, but it is a side-channel minefield: it typically needs rejection loops (a secret-dependent number of iterations), table lookups (secret-dependent memory addresses), and floating-point arithmetic (variable-time on most hardware). ML-KEM samples its small noise polynomials from the centered binomial distribution of Chapter 15. ML-DSA uses its own bounded-uniform and rejection-sampling procedures for secrets and masks; it is not an instance of the ML-KEM CBD sampler. Both standards avoid a general-purpose discrete-Gaussian sampler, but their sampling interfaces and side-channel reviews must be considered separately. FN-DSA (18) is the cautionary opposite. Its trapdoor sampler genuinely needs a high-precision Gaussian over the reals, computed with floating-point FFT, and making that constant-time is the hardest implementation problem among all the standards – if the sampler’s timing or rounding leaks, the secret basis can be reconstructed. That difficulty, forward-referenced at the end of Chapter 18, is this chapter: it is the single strongest reason Falcon is the most demanding of the three signature standards to deploy safely.
Rejection sampling in ML-DSA.#
ML-DSA signing (17) also loops: it draws a mask, forms \(\mathbf{z}=\mathbf{y}+c\,\mathbf{s}_1\), and applies rejection conditions involving secret-dependent quantities, including checks related to \(\mathbf{s}_2\) and \(\mathbf{t}_0\). The retry count and signing time therefore must not be declared harmless merely from distributional intuition. Implementations must follow FIPS 204’s sampling and side-channel design, protect intermediate values, and evaluate the resulting machine code on the target platform. FIPS 204 supports hedged signing, with randomness derived from secret \(K\), the message representative \(\mu\), and input \(rnd\); deterministic operation fixes \(rnd\), but does not remove \(K\) or the secret-related rejection conditions.
Decapsulation and the Fujisaki–Okamoto transform.#
The subtlest PQC side channel lives in KEM decapsulation. A raw lattice decryption can fail, and whether it failed depends on the secret key and the (possibly attacker-chosen) ciphertext. If decapsulation ever behaved differently on success versus failure – returned an error, took longer, or drew different power – the attacker would gain a decryption-failure or plaintext-checking oracle, querying malformed ciphertexts and using the yes/no answers to peel the secret apart. The Fujisaki–Okamoto (FO) transform [3], developed in Section 16.13, closes this door with implicit rejection. Decapsulation re-encrypts the recovered message and compares the result to the received ciphertext in constant time. On a match it returns the real shared key; on a mismatch it returns a pseudorandom key derived from a secret seed and the ciphertext – not a distinguishable ciphertext-validity error. This applies after basic input and decapsulation-key checks; an API may still reject malformed types, lengths, or unusable key material. Both cryptographic outcomes produce a key of identical form, and the final choice is a constant-time select, so the caller cannot tell success from failure. Figure 26.2 shows the flow.
The NTT and polynomial arithmetic.#
The number-theoretic transform and the modular polynomial arithmetic that surround it run on secret data on every operation. They must be constant-time too: the modular reductions after each butterfly should use fixed-cost Montgomery or Barrett reduction rather than a hardware division, and there must be no secret-dependent branch anywhere in the transform. This is usually easy to achieve – the NTT is naturally straight-line – but it is easy to spoil with a careless conditional subtraction that runs only “when the coefficient is too large.”
26.5Countermeasures beyond constant-time#
Constant-time coding primarily addresses timing, cache, and secret-dependent control-flow leakage. Differential power and EM analysis are stronger, because they average many traces and can pull out a secret that influences the power draw even when the control flow is perfectly uniform. Defeating those needs a further layer.
Masking.#
The main tool is masking: split every secret value into several random shares whose combination (XOR, for Boolean masking; addition mod \(q\), for arithmetic masking) equals the secret, and compute on the shares so that no single intermediate value in the whole computation ever equals, or correlates with, the secret. A first-order masking uses two shares and forces the attacker to combine measurements from two points at once; an order-\(d\) masking uses \(d+1\) shares. The security grows with \(d\), but so does the cost – the number of shares grows linearly while the number of secure operations and the fresh randomness they consume grow faster, so masking overhead is often several-fold and sometimes an order of magnitude. For lattice schemes the specific difficulty is that they mix Boolean operations (hashing, comparison in the FO check) with arithmetic operations (the NTT), and securely converting between Boolean and arithmetic masking is the expensive, delicate part.
Blinding.#
A lighter-weight relative is blinding: randomize the representation of a computation without changing its result, so that traces do not line up across runs. One can add a random multiple of the modulus to a value before an operation, randomize the projective coordinates in an elliptic-curve step, or shuffle the order in which independent coefficients are processed so the attacker cannot know which sample in a trace corresponds to which secret element. Blinding is cheaper than full masking but weaker; the two are often combined.
Cost and benefit.#
None of this is free, and none of it is always necessary. A server behind a network, where an attacker can only measure timing remotely, needs constant-time code but rarely full masking. One qualification has emerged: dynamic frequency scaling (Turbo Boost and its relatives) makes the clock frequency depend on power draw, which depends on the data being processed – so power leakage can surface in remote timings even when the code itself is constant-time, and network key-extraction attacks over this channel have been demonstrated [4]. Where the threat model includes them, disabling frequency boosting for cryptographic workloads is the direct countermeasure. A smart card or an embedded key store, where the attacker holds the device and can wire up an oscilloscope, needs masking and fault countermeasures as well. The right level is a threat-model decision, not a fixed recipe – but constant-time coding is the floor beneath all of it.
26.6Pitfalls#
Pitfall 1: assuming the compiler preserves your constant-time code.#
An optimizing compiler is free to rewrite \((a \mathbin{\&} mask)\mathbin{|}(b \mathbin{\&}\overline{mask})\) back into a branch or a conditional move, or to short-circuit a masked comparison, if it decides that is faster. Constant-time behavior is a property of the emitted machine code, not of the source. It must be checked – by reading the assembly, using verification tools, or barriers that stop the optimizer – not assumed.
Pitfall 2: confusing constant-time with constant wall-clock time.#
Constant-time does not mean the code always runs for the same number of nanoseconds. It means no secret-dependent variation. Variation that depends only on public data – for example the length of a message – is perfectly acceptable. Chasing literally constant duration is both unnecessary and, on modern out-of-order CPUs, impossible.
Pitfall 3: reporting a decapsulation failure.#
Returning an error, or logging, or taking a fast path when lattice decryption fails, hands the attacker exactly the plaintext-checking oracle the FO transform was built to deny. Decapsulation must always run to completion and always return a key; use implicit rejection, never an error branch.
Pitfall 4: comparing secrets with memcmp.#
The standard library comparison returns as soon as it finds a differing byte, so its timing reveals how many leading bytes matched – fatal for a MAC tag or the FO ciphertext check. Always use a no-early-exit comparison such as ct_eq.
Pitfall 5: masking that leaks anyway.#
Two shares that are correct on paper still leak if the hardware or the compiler recombines them – for example, if consecutive instructions write both shares to the same register or bus, or if masking is applied without fresh, independent randomness each run. Masking is only as good as the independence of its shares in the actual silicon.
26.7Summary#
The post-quantum mathematics of the previous chapters is genuine: it defeats Shor’s algorithm, and no efficient quantum attack on the underlying lattice and code problems is known. But that mathematics protects only the abstract scheme. A careless implementation can hand the very same secret to an attacker with an oscilloscope, a shared cache, or a laser – an attack that costs minutes and dollars rather than a quantum computer.
The defense is a discipline, not a gadget:
write constant-time code – no secret-dependent branches, no secret-dependent memory addresses, no variable-time instructions on secrets;
where the threat model includes physical access, add masking and fault countermeasures on top;
verify the property in the emitted machine code, because the compiler does not promise to preserve it.
And this is where the theory of the previous parts closes the loop with practice. The standards did not treat implementation security as an afterthought; they engineered for it. ML-KEM’s CBD sampler avoids a general discrete Gaussian (15); ML-DSA and FN-DSA require careful treatment of secret-dependent sampling and rejection conditions (17, 18); ML-KEM decapsulation is built on implicit rejection so success and failure are indistinguishable (16); and Falcon’s floating-point sampler stands as the standing reminder that when a scheme is hard to implement safely, that difficulty is itself a security cost (18). Post-quantum security is not only a theorem to be proved. It is a property of the running system – and keeping it there, all the way down to the machine code, is not optional.
Comments