Cache-Timing Attack — recovering key bytes from which cache line a table lookup touched

A cache-timing attack recovers a secret (typically an AES key byte) not from *how long* an operation took, but from *which cache line* a secret-indexed table lookup touched — measured via Flush+Reload or Prime+Probe on a co-located/shared-memory victim.

The signal that gives it away

- The victim does table-driven crypto — the flagship case is AES implemented with T-tables, where the first-round lookup is T[pt[i] ^ key[i]]. Any lookup table indexed by plaintext XOR secret is the shape to look for. - The setting is co-located or shared-memory: same host, shared library (libcrypto.so-style T-tables shared across processes), or a sandboxed/simulated equivalent. Without shared memory or a shared cache there is no line to observe. - There's a way to measure or be told about cache-line access, not just wall-clock latency: rdtsc-style timing around a load, a clflush primitive, or — very common in CTF framing — the challenge just hands you an oracle that returns *which* cache lines (or sets) were touched per query, skipping the raw-timing noise entirely. - Textual tells: "shared library", "T-table AES", clflush, rdtsc, "cache line", "Flush+Reload", "Prime+Probe", or a granularity hint like "64-byte lines".

How to exploit it

The mechanism: a 64-byte cache line holds several T-table entries (for a standard 4-byte-per-entry AES T-table, 64/4 = 16 entries share one line), so observing *which line* was accessed reveals the table index only down to that granularity — line = index >> 4 when 16 entries share a line. That's coarser than the full byte, but combined across many plaintext/observation pairs it collapses fast:

1. For each accessed line, the actual index could be any of the (line-size) entries that map to it. In the T-table formulation the S-box is already baked into each table entry's *value* — the lookup is T[pt ^ key_byte] directly, so the table *index* is just pt ^ key_byte (no separate S-box indexing step). Each observed line therefore rules out most key-byte candidates for that position: keep k only if (pt ^ k) >> 4 lands in the observed line set. 2. Repeat across many known-plaintext queries; intersect the candidate set for each key byte across samples. The set shrinks fast — a handful of samples per byte is usually enough to collapse to one candidate, because each observation rules out roughly 15/16 of the remaining space. 3. Do this independently per byte position (16 bytes for AES-128) — they don't interact in the first round, so it parallelizes trivially.

``python cands = [set(range(256)) for _ in range(16)] for pt, lines in samples: # lines: set of touched cache lines (0..15) for this query for b in range(16): ok = {k for k in range(256) if ((pt[b] ^ k) >> 4) in lines} cands[b] &= ok key = [next(iter(c)) for c in cands] ``

4. When only hit/miss timing is exposed (no explicit line set) — e.g. you can only tell "was this address cached" via latency — reduce it to a single-bit oracle per probe: fast response = line was in cache (victim touched it recently), slow = miss. That degrades the attack to a statistical version of Timing Attack — recovering a secret from how long a secret-dependent operation takes: average many trials per candidate line to separate the two latency populations before feeding the result into the same set-intersection logic above. 5. Practical framing that saved time: in most CTF instances the challenge does NOT make you actually run Flush+Reload against real hardware — it *simulates* the primitive (an oracle function that returns accessed-line sets or raw hit/miss bits per query), so the real work is steps 1-3 (the set-intersection cryptanalysis), not micro-architecture plumbing. Confirm which flavor you're given before investing in timing-measurement code you won't need.

What does NOT work

- Treating cache-line leakage as if it revealed the exact index. It only reveals the index down to the entries-per-line granularity (e.g. one of 16 candidates for a 4-byte-entry/64-byte-line table) — a single observation never determines a key byte on its own. Trying to "solve" from one query and getting a wrong-looking-right answer is the classic mistake; always intersect across multiple samples before trusting a candidate. - Ignoring noise and treating a raw hit/miss oracle as deterministic. On real hardware (unlike a clean CTF simulation), a single Flush+Reload probe is noisy — context switches, prefetching, and other co-resident processes cause spurious hits/misses. Averaging or repeating probes per candidate is required; single-shot timing calls are unreliable even when the underlying leak is real. - Assuming this attack needs raw wall-clock timing at all. If the challenge already hands you accessed-line sets, building an elaborate timing/statistics pipeline (borrowed from Timing Attack — recovering a secret from how long a secret-dependent operation takes) is wasted effort — that machinery is only needed when the *only* signal is latency, not when the oracle already resolves to lines. - Confusing this with a general "the algorithm/comparison is slow" timing leak. Cache-timing depends specifically on a *table lookup* whose index is secret-dependent; it does not apply to, say, a non-constant-time string comparison (that's plain Timing Attack — recovering a secret from how long a secret-dependent operation takes) or to power draw (that's Power Analysis (SPA/DPA/CPA) — reading a key off a device's power draw) — misclassifying the leak source sends you down the wrong exploitation script even though the family "measure something, don't know the key" looks similar from a distance.

Related

Timing Attack — recovering a secret from how long a secret-dependent operation takes Power Analysis (SPA/DPA/CPA) — reading a key off a device's power draw Cryptanalysis Methodology — classify the family before you reach for an attack