Side channels: when how long it took is the answer

A side channel is information that leaks from *how* a computation was performed rather than from what it returned. The program answers "no" both times, but it takes longer to say no in one case than the other, and that difference is the bug.

The idea generalises much further than cryptography. A padding oracle is a side channel; blind SQL injection is a side channel; a race condition exploits one. What unites them is a single structure worth naming: you have a function that leaks one bit about a secret, and you turn it into the whole secret by asking repeatedly.

The shape

Every attack in this post is the same three steps.

1. Find an observable that varies with the secret: time, an error message, a response size, a status code, a cache state.
2. Establish that the variation is real - that it exceeds the noise floor.
3. Design a query whose answer bisects the search space, and iterate.

Step two is the one people skip and the one that decides whether the attack works.

Timing: string comparison

memcmp, == on strings, and almost every naive comparison return as soon as they find a difference. So comparing a wrong answer that shares the first three characters takes measurably longer than one that differs at the first.

import time, statistics, requests

ALPHABET = "abcdef0123456789"

def timed(token, trials=25):
    ts = []
    for _ in range(trials):
        t0 = time.perf_counter()
        requests.post(URL, data={"token": token})
        ts.append(time.perf_counter() - t0)
    # The median is far more robust than the mean here: one scheduling hiccup
    # ruins a mean and does nothing to a median.
    return statistics.median(ts)

known = ""
while len(known) < 32:
    scores = {c: timed(known + c + "0" * (31 - len(known))) for c in ALPHABET}
    best = max(scores, key=scores.get)
    known += best
    print(known)

Over a network this is hard but not impossible. The signal from one comparison is nanoseconds and the jitter is milliseconds, so you need many samples and a statistic that ignores outliers - the minimum observed time is often better than the median, because the minimum is the run where nothing else interfered. Locally, or against a service on the same host, the signal is enormous by comparison.

Timing: cryptographic operations

• Square-and-multiply modular exponentiation does extra work for every set bit of the exponent. A naive RSA or Diffie-Hellman implementation therefore leaks the private exponent's Hamming weight, and with per-operation timing, its bits. This is why constant-time exponentiation exists.
• Modular reduction is conditional: subtract if the result exceeded the modulus. That branch is the basis of the classic remote timing attack on OpenSSL's RSA.
• Table lookups in AES are cache-dependent - which entry you access decides whether it is a hit or a miss. Cache-timing attacks on software AES recover the key from this alone.
• Signature verification that compares byte by byte leaks in exactly the way string comparison does, and it is more common than it should be.
• Any `if secret:` at all. A branch on secret data is a timing side channel by construction. Recognising this makes reading source for side channels a mechanical exercise rather than an intuitive one.

In a CTF the giveaway is usually structural: the challenge gives you unlimited queries against a fixed secret and returns almost no information. That combination is the definition of an oracle problem.

The channels that are not time

Compression deserves a note because it is counterintuitive. If a response contains both a secret and something you control, and it is compressed, then the compressed *length* tells you whether your input matched part of the secret - because the compressor replaces the repetition with a back-reference. Guess a character at a time and watch the byte count.

Making a measurement you can trust

The failure mode of every timing attack is convincing yourself of a signal that is not there. Some discipline:

• Establish a noise floor first. Measure the same input a hundred times and look at the distribution. If your expected signal is smaller than that spread, you need more samples or a different channel.
• Include a control. Measure a known-wrong input alongside your candidates every round. If the control ever wins, your signal is noise.
• Use a robust statistic. The minimum or a low percentile beats the mean, because interference only ever makes things slower.
• Verify at the end. After recovering a full secret, check it. A timing attack that goes wrong at character 7 produces a plausible-looking wrong answer, not an error.
• Get closer. If the service is reachable over a local socket, or you can run the binary yourself, do that instead of measuring over the internet. Three orders of magnitude of noise disappear.
• Consider amplification. If you can make the operation happen many times per request - a batch endpoint, a long input, a repeated field - the signal scales and the network jitter does not.

Physical side channels

Hardware categories of CTF include power analysis, which is worth understanding even if you never do it. A CPU's power draw depends on what it computes, so a trace of an encryption operation contains structure that correlates with the key.

• Simple power analysis reads the operation sequence directly off a trace - a square-and-multiply exponentiation shows its bits as visibly different-shaped pulses.
• Differential and correlation power analysis use many traces and a statistical model: guess one key byte, predict the power consumption of an intermediate value, and correlate against the measurements. The correct guess correlates and the other 255 do not. It recovers AES keys byte by byte, which makes the search 16 x 256 rather than 2^128.
• Fault injection is the aggressive sibling: glitch the clock or the voltage during a comparison and the branch takes the wrong path. Against RSA-CRT, a single fault during signing leaks the factorisation of the modulus outright.
• In a CTF these arrive as data. You are given a set of traces and a set of plaintexts, and the work is entirely offline - numpy and a correlation, not an oscilloscope. See hardware and signal challenges for the rest of that category.

Recognising the challenge

• Unlimited queries, a fixed secret, and a one-bit answer.
• A comparison you can see in the source that is not hmac.compare_digest or an equivalent constant-time function.
• A challenge that hands you a large set of measurements with no other structure.
• An endpoint that is conspicuously slow, or one whose response time varies with an input that should not affect it.
• A hint mentioning "be patient", "the server is slow", or a rate limit that is generous rather than tight - which is the author telling you to make many requests.

And the counter-signal: if the code uses a constant-time comparison, if the response time is dominated by a deliberate fixed sleep, or if the number of queries is capped at a small number, the challenge is not this. Constant-time code is easy to spot and its presence is a strong statement about the intended path.