Fixed window, sliding window, token bucket — behavior under attack

Rate limits are the most common mitigation in OTP threat models and the least examined. A row that says “rate limited” usually hides an algorithm nobody chose deliberately, keyed on a value nobody questioned, with a threshold copied from a blog post. This series examines each of those choices against a real adversary. We start with the algorithm, because different algorithms admit very different traffic for the same nominal limit.

Throughout the series we follow Quillon Pay, a fictional peer-to-peer payments app, and its abuse engineer Odalys Fenwick. Quillon’s OTP verify endpoint has a nominal policy of five attempts per thirty seconds per account. Let us see what that sentence actually means under three algorithms.

Fixed window

A fixed-window counter divides time into aligned buckets — 00:00:00 to 00:00:30, 00:00:30 to 00:01:00 — and counts requests per key in the current bucket. It is trivial to implement with a single integer per key and an expiry, which is why it is the default in many gateways. Its weakness is the boundary. An attacker who sends five requests at 00:00:29 and five more at 00:00:30 gets ten attempts in about one second while never violating the counter.

Sliding window

A sliding window evaluates the last N seconds from the current moment rather than from an aligned boundary. The exact form, a sliding log, stores a timestamp per request and counts those within the window. It is precise but costs memory proportional to the limit: five timestamps per account is nothing, five thousand per IP is significant. The approximate form, a sliding window counter, keeps the current and previous fixed-window counts and weights the previous one by how much of it still overlaps the sliding window. It uses two integers and is accurate to within a few percent, which is enough for most purposes.

// Sliding window counter: two fixed buckets, weighted
function allowed(now: number, win: number, limit: number, cur: number, prev: number) {
  const elapsed = (now % win) / win;           // 0..1 through current bucket
  const estimate = prev * (1 - elapsed) + cur;  // weighted overlap
  return estimate < limit;
}

Token bucket

A token bucket holds up to B tokens and refills at R tokens per second. Each request consumes one; if the bucket is empty, the request is rejected. The capacity B sets how large a burst is tolerated, and R sets the long-term average. It needs two numbers per key — the token count and the last refill time — and it expresses a policy humans understand: “you can try four times quickly, then once every ten seconds.” For OTP verification that is often exactly the right shape. A user who fat-fingers a code twice can retry immediately, but an attacker cannot sustain more than R guesses per second.

The leaky bucket is a close relative that smooths output rather than admitting bursts. It is common in traffic shaping and less useful for authentication, where you want to reject excess attempts rather than queue them.

Behaviour under a distributed attacker

All three algorithms are per key. Against an attacker who controls many keys — many IPs, many accounts, many phone numbers — the per-key choice matters less than what you count on, which is the subject of chapter 2. But the algorithm still sets the per-key ceiling. An illustrative example from Quillon’s test harness: with a fixed window of five per thirty seconds, a script hitting one account across boundaries sustained 9.6 attempts per thirty seconds on average. With a sliding window counter, 5.1. With a token bucket of capacity four refilling at one per ten seconds, 3.2. For a six-digit code over a ±1 TOTP window, that is the difference between about 33 and 11 expected years to a successful blind guess — not a crisis either way, but the fixed window quietly halves your margin.

• Edge / CDN: fixed or sliding counters per IP, coarse thresholds, cheap and fast.
• Send endpoint: token bucket per destination and per client, plus a global sliding counter.
• Verify endpoint: token bucket per account and per challenge, small capacity.
• Recovery flows: sliding log per account with long windows (hours, not seconds).

Where to store state

Limiter state must be shared by every instance that serves the endpoint, or each instance enforces its own limit and the effective limit multiplies by the instance count. An in-memory store with atomic operations is the usual choice. Plan for its failure: if the limiter store is unreachable, auth endpoints should fail closed with a clear error and an alert, while low-risk endpoints may fail open. Write that decision in the threat model, because it is a security property, not an implementation detail.

Whichever algorithm you choose, write the policy in words next to the configuration, so reviewers can check that the numbers match the intent.

Then load-test the limiter itself, because a limiter that becomes the bottleneck under attack is its own denial of service.

 function allow(key, now) {
−  const w = Math.floor(now / 30_000);
−  const k = key + ":" + w;
−  const n = (counts.get(k) ?? 0) + 1;
−  counts.set(k, n);
−  return n <= 5;
 }