Side-Channel Attacks

A side channel is an unintended information leak from the physical implementation of a system, as opposed to a leak through its designed input/output interface. Formally, if a system computes $y = f(x, k)$ where $k$ is secret, a side channel is an additional observable $L = g(x, k, \text{implementation details})$ that an adversary can measure and that is statistically dependent on $k$ even when $y$ alone reveals nothing about $k$. Side channels are classified by the physical quantity observed. Timing channels exploit variation in execution time caused by data-dependent branches, variable-latency instructions (integer division, some multiplications), or cache/TLB behavior. Cache and microarchitectural channels exploit shared hardware resources — L1/L2/L3 caches, translation lookaside buffers, branch predictors, execution ports — whose state after a victim's execution reveals which addresses or code paths the victim touched. Power and electromagnetic (EM) channels exploit the fact that CMOS circuits draw current proportional to the Hamming weight or Hamming distance of the bits being processed, so an oscilloscope trace of supply current (or a nearby EM probe) statistically correlates with intermediate values of a computation. The common mathematical structure across all these channels is a leakage function $L(t) = h(v(k, x)) + \text{noise}$, where $v(k,x)$ is some intermediate value computed during execution (e.g., an S-box output byte, or "cache line $\ell$ was accessed"), and $h$ is a deterministic model of how that value manifests physically (Hamming weight model, Hamming distance model, or a binary hit/miss indicator). An attacker who can guess candidate sub-keys, predict $v$ for each candidate, and correlate the predicted leakage against the measured leakage across many traces can distinguish the correct sub-key hypothesis from wrong ones — this is the essence of Differential Power Analysis and its refinements, and an analogous hypothesis-testing logic underlies cache-timing key recovery.

We present the mechanism in three layers: the general attack pipeline, a concrete timing attack (RSA/modular exponentiation), and a concrete cache attack (Flush+Reload on AES T-tables). All three instantiate the same generic template.

Generic side-channel attack pipeline ``` ALGORITHM GenericSideChannelAttack Input: victim runs f(x, k) for unknown secret k, attacker can trigger many runs leakage_model(hypothesis_bits, x) -- predicts an observable given a guess measure() -- returns a real physical/timing trace 1. traces <- [] 2. predictions <- [] 3. for i = 1 to N: # collect N traces 4. x_i <- choose or observe input (known plaintext / triggerable input) 5. trigger victim to compute f(x_i, k) 6. trace_i <- measure() # timing, power waveform, cache state 7. traces.append(trace_i) 8. for each candidate sub-key guess g in key-space slice: 9. for i = 1 to N: 10. predictions[i] <- leakage_model(g, x_i) 11. score[g] <- correlation(predictions, traces) # e.g. Pearson r, or

# simple mean-difference test 12. best_guess <- argmax_g score[g] 13. output best_guess ```

Why this works, mechanically: if $g$ equals the true sub-key, the predicted leakage $\text{predictions}$ is a genuine (noisy) function of the same intermediate value that physically drives $\text{trace}$, so the correlation is large in magnitude. If $g$ is wrong, the prediction is uncorrelated with the true intermediate value, so the correlation concentrates near zero as $N$ grows (by the law of large numbers). The attacker never needs to see the plaintext-key relationship directly — only that some function of the guess correlates with some physical measurement.

Case 1 — Timing attack on modular exponentiation. The textbook square-and-multiply algorithm for RSA/DH computes $c = m^k \bmod n$ bit-by-bit: ``` ALGORITHM SquareAndMultiply_UNSAFE(m, k, n) # k = k_{t-1} ... k_1 k_0 in binary 1. r <- 1 2. for i = t-1 downto 0: 3. r <- (r r) mod n 4. if k_i == 1: 5. r <- (r m) mod n # extra multiply, extra TIME, only when bit=1 6. return r ``` Line 5 executes conditionally on the secret bit $k_i$. If the modular multiplication's latency is even slightly data-dependent (true of schoolbook long multiplication and of early-exit "optimized" modmul routines), an attacker who can measure total exponentiation time for many known messages $m$ can, bit by bit from the most significant bit down, guess $k_i$, predict the timing contribution of the corresponding multiply, and correlate that prediction against the observed total time — recovering the exponent one bit at a time (Kocher's original 1996 attack).

Case 2 — Flush+Reload cache attack on table-based AES. Software AES implementations historically used precomputed T-tables so that each round reduces to XORs and table lookups: `state[i] = Ttable[state[i] XOR roundkey[i]]`. The table is shared in memory (and in cache) between attacker and victim on the same machine via shared libraries or page deduplication. ``` ALGORITHM FlushReload_AES(shared_Ttable_pages) 1. for each round of victim invocation: 2. for each address a in shared_Ttable_pages: 3. clflush(a) # evict a from ALL cache levels 4. wait(victim_executes_one_AES_round) # trigger/synchronize 5. for each address a in shared_Ttable_pages: 6. t0 <- rdtsc() 7. read(a) 8. t1 <- rdtsc() 9. if (t1 - t0) < THRESHOLD: 10. mark a as "accessed by victim" # cache HIT -> victim touched this line 11. infer which T-table index (hence which key byte XOR plaintext byte) was used 12. combine with known plaintext bytes to solve for key byte ``` Because a cache hit (data already resident) takes on the order of a few nanoseconds while a cache miss (fetch from DRAM) takes on the order of 100+ nanoseconds, the timing threshold cleanly separates "victim accessed this line" from "victim did not," giving the attacker a near-noiseless oracle for which 16-byte-aligned chunk of the T-table (and hence which value of `plaintext_byte XOR key_byte`) was used — enough, across many encryptions, to recover the AES key byte by byte.

Timing attack complexity. For an $n$-bit RSA exponent recovered bit-by-bit, each bit requires collecting timing samples over $O(1/\varepsilon^2)$ traces, where $\varepsilon$ is the timing difference (in units of the measurement's standard deviation) caused by the conditional multiply — this follows directly from the standard sample-size bound for detecting a mean shift $\varepsilon$ with fixed confidence via a $t$-test or correlation test (variance of the sample mean shrinks as $1/N$, so $N = \Theta(\sigma^2/\varepsilon^2)$ traces suffice to separate the two hypotheses). Total work is $O(n / \varepsilon^2)$ traces plus $O(n)$ sequential bit-recovery steps, since each bit's correct value is needed to correctly predict the timing contribution of subsequent bits (errors propagate, so most practical attacks include an error-correction/backtracking step).

Cache attack complexity. Flush+Reload against T-table AES needs, in the noiseless case, only $O(1)$ encryption observed per key byte in principle (16 possible table-region hits directly reveal $p \oplus k$ for a known plaintext byte $p$), but in practice noise — OS scheduling jitter, prefetching, other cache traffic — forces averaging over tens to a few hundred encryptions per byte, giving overall complexity $O(256 \cdot c)$ trace-probes for a full AES-128 key ($16$ bytes $\times 16$ candidate nibble/byte values, times a small constant $c$ of repeated trials for noise averaging) — this is why practical implementations report full-key recovery in seconds to minutes of monitored encryptions, not brute-force $2^{128}$.

Power analysis (DPA/CPA) complexity. Differential Power Analysis partitions $N$ traces into two sets by a predicted single bit of an intermediate value and computes the difference of means; Correlation Power Analysis computes Pearson correlation between a full Hamming-weight prediction and the traces. Both require $N = \Theta(1/\rho^2)$ traces to reliably detect a true correlation of magnitude $\rho$ against Gaussian noise, by the same variance-of-the-sample-correlation argument — smaller $\rho$ (well-shielded, low-leakage hardware) directly forces a quadratically larger number of traces, which is precisely why hiding/masking countermeasures work: they drive $\rho \to 0$.

Correctness argument (why the statistical distinguisher actually recovers the key). The key theoretical fact is a hypothesis-testing separation: under the correct key hypothesis, the predicted leakage $Y = h(v(k^*, x))$ and the measured trace $T = h(v(k^*,x)) + \eta$ share the deterministic component $h(v(k^*,x))$, so $\text{Cov}(Y, T) = \text{Var}(h(v(k^*,x))) > 0$. Under any wrong hypothesis $g \ne k^*$, if the leakage function $h \circ v$ behaves close to a pseudorandom function of the guess (true for AES S-boxes, false for linear operations — a caveat attackers must handle), $v(g,x)$ is statistically independent of the true intermediate value, so $\text{Cov}(Y_g, T) \to 0$ as $N \to \infty$ by the law of large numbers. The correct guess is therefore, with high probability for large enough $N$, the arg-max of the empirical correlation — this is exactly a multiple-hypothesis mean-comparison test, and its sample complexity is governed by the signal-to-noise ratio (SNR) of the channel, matching the $\Theta(1/\rho^2)$ bound above.

Honest tradeoffs. These attacks are not cryptanalysis of AES or RSA — the algorithms remain unbroken as functions. The attack is entirely against the implementation's physical realization, and its cost is dominated by (a) how large the leakage signal $\rho$ is relative to noise, and (b) how many traces/queries the attacker can obtain, which is itself bounded by rate limits, physical access, or co-location constraints in real deployments. Constant-time defenses eliminate $\rho$ at the cost of always executing the "slow path" (e.g., always doing the multiply in square-and-multiply, or using bitsliced/AES-NI hardware instructions instead of table lookups), typically costing a modest constant-factor slowdown, not an asymptotic one.

We trace a simplified Flush+Reload recovery of one byte of an AES-128 key using a 4-entry toy T-table (real AES has 256-entry tables per T-table; we shrink it for legibility) — the recovered relation generalizes identically. Suppose the first-round operation is `idx = plaintext_byte XOR key_byte`, and the implementation looks up `Ttable[idx]`. The attacker knows `plaintext_byte = 0x35` for a given encryption and wants `key_byte`.

Repeating this procedure independently for each of the 16 key bytes of AES-128 recovers the entire key with total work linear in the key length (16 bytes), each requiring only a handful of flush–trigger–reload trials to beat measurement noise — a dramatically smaller search than the $2^{128}$ brute force the cipher nominally requires, precisely because the cache leaked the table index directly instead of leaving the attacker to guess it.

Constant-time cryptographic libraries (BoringSSL, libsodium, HACL*, the Go crypto standard library) are engineered specifically to defeat timing and cache side channels, using techniques such as branch-free conditional selection and bitsliced or hardware-accelerated (AES-NI) implementations that avoid secret-indexed table lookups entirely. Smart cards and hardware security modules undergo formal side-channel evaluation (Common Criteria, FIPS 140-3 physical security testing) using power/EM trace analysis before certification for payment and identity applications. Cloud hypervisors and browser JavaScript engines add mitigations — cache partitioning, reduced timer resolution, site isolation — directly in response to cache-timing and speculative-execution side channels demonstrated against shared multi-tenant infrastructure. The same statistical logic of correlating an observable with a hypothesis reappears in traffic-analysis attacks on encrypted network flows and anonymity networks, linking this material forward to Privacy and Anonymity, and it also depends conceptually on the memory layout assumptions covered in Memory-Safety Vulnerabilities, since many cache attacks require precise control over shared memory pages.

Ask the tutor: How would you design and test a constant-time verification routine to eliminate a MAC-comparison timing side channel?