Timing Attacks on Comparisons
Applied Crypto & Common Pitfalls · Networking & Cryptography track
7 min read
In this module
When Time Tells Secrets
A timing attack extracts secret information by stopwatch alone. The insight: many computations take different amounts of time depending on the values they're chewing on. If those values are secret — a cryptographic key, a password hash — the execution time itself becomes a side channel that leaks bits.
The Simplest Example: String Comparison
Consider a function that verifies an authentication token:
function verify_token(user_token, correct_token) { if length(user_token) != length(correct_token) { return false } for i = 0 to length(user_token) - 1 { if user_token[i] != correct_token[i] { return false // returns early on first mismatch! } } return true}This function bails the moment it finds a mismatched byte. If the first byte is wrong, it returns almost instantly. If the first 10 bytes happen to match, it takes a measurable sliver longer to return false. An attacker can lever that:
- Try all 256 possible values for the first byte. The one that takes a hair longer to reject is correct.
- Move on to the second byte (keeping the first byte fixed). The slowest rejection again reveals the right byte.
- Walk byte-by-byte until the whole token spills out.
Early-return comparisons leak information through timing differences. An attacker who can measure response time with sufficient precision can determine a secret value one byte at a time. This applies to authentication tokens, HMAC verification, password comparison, and any operation that short-circuits on secret data.
How Precise Must Measurements Be?
You'd think nanosecond differences are too small to measure. They aren't. Timing attacks are uncomfortably practical:
Local attacks: On the same machine, timing differences of a few nanoseconds are measurable with rdtsc and friends.
Network attacks: Over a network, any single measurement is noisy. Average thousands of measurements and timing differences as small as a few microseconds rise out of the jitter. Statistics does the rest.
Cross-VM attacks: Even in cloud environments, timing attacks have crossed between virtual machines sharing the same physical hardware. Your noisy neighbour can be your enemy.
Cache Timing Attacks on AES
AES software implementations frequently lean on lookup tables (T-tables) for the SubBytes and MixColumns operations. The CPU cache loads table entries on demand. The first access to an entry is slow (cache miss); subsequent accesses are fast (cache hit). That timing gap is the leak.
An attacker running on the same machine can:
- Evict the AES lookup tables from the cache by hammering their own memory
- Trigger an AES encryption
- Measure which cache lines were loaded by timing their own accesses to the same cache sets
- Infer which table entries the encryption touched, which leaks information about the key
Here's a stripped-down version you can step through. The cache below has 16 lines of 64 bytes, exactly enough to hold one 1 KB T-table (256 entries of 4 bytes) starting at address 0, so table entry i lives at address 4 × i and each line holds 16 entries. The first-round lookup index is plaintext_byte XOR key_byte. Say the attacker chose plaintext byte 0x00 and the secret key byte is 0x3A: the victim reads entry 0x3A, address 232. The sequence starts from an empty cache, plays that one victim access, then has the attacker load the start of every line in turn.
Cache Contents(Direct-Mapped, 16 lines, 64B/line)
| Index | V | Tag | Data |
|---|---|---|---|
| 0 | 0 | - | - |
| 1 | 0 | - | - |
| 2 | 0 | - | - |
| 3 | 0 | - | - |
| 4 | 0 | - | - |
| 5 | 0 | - | - |
| 6 | 0 | - | - |
| 7 | 0 | - | - |
| 8 | 0 | - | - |
| 9 | 0 | - | - |
| 10 | 0 | - | - |
| 11 | 0 | - | - |
| 12 | 0 | - | - |
| 13 | 0 | - | - |
| 14 | 0 | - | - |
| 15 | 0 | - | - |
Every probe misses except address 192, which shares line 3 with the victim's read. Line 3 covers entries 0x30 to 0x3F, so 0x00 XOR key_byte starts with hex digit 3, and the attacker has learned the top four bits of the key byte from one lookup. A real attack is noisier, since each AES round makes 16 table lookups, but repeating it over many chosen plaintexts and later rounds fills in the rest.
This attack has recovered full AES keys from shipping systems. Defences include:
- Hardware AES-NI: Performs AES operations without table lookups, killing the cache side channel
- Bitsliced implementations: Implement AES using only bitwise operations, with no data-dependent memory accesses
- Constant-time software implementations: Touch every table entry on every operation regardless of the input
Timing Attacks on RSA
Private key operations in RSA (modular exponentiation) can leak key bits through timing if the implementation takes different code paths for 0-bits and 1-bits of the exponent. Square-and-multiply algorithms that skip the multiplication for 0-bits execute faster, betraying the bit pattern of the private key one operation at a time.
Real libraries combine two separate defences. Constant-time exponentiation does the same work for every exponent bit: a Montgomery ladder, for example, always performs one multiply and one square per bit, so the sequence of operations no longer depends on the key. (Montgomery multiplication is a different thing, a fast way to do modular reduction, and it has its own data-dependent final subtraction that careful code has to hide.) Blinding randomises the data: multiply the input by a random value raised to e before the private-key operation, then strip it off afterwards. The intermediate values change on every call without changing the result, so an attacker can't line up timings against inputs they chose.
Defending Against Timing Attacks
The fundamental defence is constant-time programming: ensure that the execution time of security-critical operations does not depend on secret data.
Rules for constant-time code:
- No secret-dependent branches: Do not use if/else based on secret values
- No secret-dependent memory access: Do not index into arrays using secret values
- No early returns on secrets: Always process all data, regardless of intermediate results
- Use constant-time comparison: XOR all bytes, OR the results together, check if zero
// Constant-time comparisonfunction secure_compare(a, b) { if length(a) != length(b) { return false } result = 0 for i = 0 to length(a) - 1 { result = result | (a[i] ^ b[i]) } return result == 0}Writing constant-time code is hard and counterintuitive. The compiler may helpfully "optimise" your careful constant-time code straight back into branching code. And verifying that it's actually constant-time — not just that it looks like it should be — requires specialised tools that analyse execution traces. One more reason to lean on well-reviewed cryptographic libraries rather than rolling your own.
The Broader Lesson
Timing attacks epitomise why cryptographic implementation is so devilish. The algorithm can be mathematically perfect, the key unguessable, every input producing the correct output — and a few nanoseconds of timing variation still leaks the whole secret. Side channels exist because computation is a physical process with observable properties, not a clean mathematical abstraction. Power draw, electromagnetic radiation, cache behaviour, even acoustic emissions all betray information, and the Spectre and Meltdown family showed that the CPU's own speculative execution can leak secrets through the cache too. Defending against these channels means reasoning about what the hardware reveals, not just what the software computes. That gap between "appears to work" and "is actually secure" is where most cryptographic implementations quietly bleed out.