Bounding Online Guessing with Rate Limits and Lockouts

Password hashing sets the cost of a guess made offline. It says nothing about how many guesses an attacker gets online, and an attacker who can submit guesses through the login form is playing a different game: they are limited not by the cost of a hash but by the number of requests the service will answer. Rate limiting is the control that sets that number, and its design determines whether the bound is a few thousand attempts or effectively unlimited.

The arithmetic that has to hold

Start with the quantity that matters: the probability that a given account is compromised over a period. For an account whose password is drawn from a distribution with entropy $H$ bits, an attacker making $N$ guesses succeeds with probability roughly $N / 2^H$ for small $N$. A password that appears in a breach corpus is not protected by entropy at all; it is compromised as soon as the attacker tries it, and the only defence is that the attempt never happens.

The useful framing is in attempts per account per unit time. If a service permits ten attempts per account per hour and the account’s password is in the first ten thousand entries of a common list, the attacker needs a thousand hours to exhaust that slice of the space, which is long enough for the account owner or an automated signal to intervene. If the service permits unlimited attempts, the same slice falls in seconds.

The numbers to choose are therefore a budget and a window. A budget in the low tens of failed attempts per account per hour, combined with a per-address budget in the hundreds, is the common shape. The per-account budget bounds a targeted attack; the per-address budget bounds a spraying attack that tries one password against many accounts. Both are needed because they defend against different distributions: a targeted attacker concentrates attempts on one account, while a sprayer distributes them.

NIST SP 800-63B is explicit that the rate limit should be enforced on the verifier’s side and should apply to the account, not only to the network address, because address-based limits are defeated by distributed sources. It also recommends limiting the number of consecutive failed attempts to a small number, on the order of one hundred, before some form of additional control engages.

Counters, keys, and the cost of being wrong

The mechanical part is a counter with a key, a window, and a limit. The key is the interesting decision.

Keying by account bounds a targeted attack precisely and is immune to address rotation. It also creates a denial-of-service primitive: an attacker who knows a username can lock that account by submitting failures, and the lock applies to the legitimate owner. This is not a hypothetical trade; it is the central tension of lockout design. A lockout that lasts an hour and is triggered by ten failures gives an attacker a cheap way to deny access to any account whose username they can guess.

Keying by address bounds a single-source attack and has no per-account denial, but it fails against a distributed attacker and it penalises users behind a shared address. A corporate network, a mobile carrier’s address-sharing, or a household with several users can exhaust a per-address budget with legitimate failures.

The designs that work combine keys and escalate rather than hard-lock. A counter per account with exponential backoff, delaying the next attempt by a duration that grows with the failure count $n$, bounds the rate without ever making the account permanently unavailable. The delay can be enforced as a sleep in the handler, which is expensive and ties up a worker, or as a stored “not before” timestamp that causes the attempt to be rejected cheaply until the time passes. The timestamp is the better mechanism because it does not consume resources while it is in effect.

A cap on the backoff, in the range of minutes to a small number of hours, keeps the denial bounded. An uncapped exponential reaches a duration that is indistinguishable from a permanent lock after a few dozen failures.

The other combination is a per-account counter that does not block, but requires a stronger proof once it is exhausted: a CAPTCHA, a second factor, or an email confirmation. That keeps the account usable for its owner and raises the attacker’s cost. Its weakness is that the stronger proof is often the thing the attacker is trying to reach, so the fallback must not be a path that bypasses the credential being protected. Factor independence covers that failure directly.

What the response must not reveal

A rate limiter that says “this account is locked” has told the attacker the account exists. So has one that says “no such user”, and so has one that takes measurably less time for an unknown user than for a known one with a wrong password.

The timing channel is the one that survives most implementations. A login handler for an existing account performs a KDF over the stored salt, which takes a deliberate amount of time. For an unknown account there is no salt and no stored digest, so a naive handler returns immediately. The difference is large enough to be visible over a network with modest sampling, and it turns the login form into an account oracle. The remedy is to run the same KDF against a fixed dummy record when the account is unknown, so both paths pay the same cost, and to ensure that the resulting comparison fails in the same way. The mechanics of doing that comparison without introducing a second channel are covered in constant-time credential comparison.

The response body is the other channel. A generic failure message is necessary and not sufficient: differing HTTP status codes, differing redirect targets, differing response lengths after compression, and differing set-cookie behaviour all leak the same bit. The discipline is to construct the failure response from a single code path that is chosen before the account lookup, and to modify nothing about it afterwards.

Enumeration also has non-login surfaces. A registration form that reports “this email is already registered” is an oracle; the usual mitigation is to accept the registration and send an email to the address, which tells the owner and not the attacker. A password reset form that reports whether an address exists is the same oracle. A timing difference in the reset path is the same channel again.

Distributed attempts and the limits of per-address counting

Credential stuffing distributes one attempt per account across many addresses, so no per-account counter increments and no per-address counter reaches its limit. The signal is not in any single counter but in the aggregate: many failures, spread across many accounts, from many addresses, in a short period.

The controls that work against this shape are statistical. A global failure rate that rises above a baseline triggers a step-up requirement for all logins, or for logins from addresses not recently seen. Address reputation, derived from prior behaviour, raises the cost for sources that have been seen failing. Device fingerprinting, where the client presents a stable identifier on first sight and is challenged when it changes, gives a cheap continuity signal that does not depend on the address.

All of these have false positives. A new address is normal for a mobile user; a device identifier is lost when a browser clears storage; a shared corporate egress looks like a single source for thousands of legitimate users. The design rule is that the response to a suspicious signal should be a challenge rather than a block, because a challenge costs the legitimate user a small amount and the attacker a real amount, while a block costs the legitimate user everything.

The specific defence against stuffing is a breach-corpus check at registration and at password change. If the password is known to be in a corpus of breached credentials, it is refused regardless of complexity. This is what NIST SP 800-63B recommends in place of composition rules, and it is the only control that addresses the distribution stuffing exploits, since that distribution is precisely the corpus.

Interaction with the KDF and with caching

Rate limiting and password hashing interact through resource consumption. Every accepted attempt runs the KDF at the configured cost, so an attacker who can submit attempts at a high rate can exhaust CPU even if none succeed. The per-address and global limits must therefore sit in front of the KDF, not behind it, and must reject cheaply.

This ordering is a common mistake in implementations that check the rate limit after parsing and hashing the request, or that run the KDF and then discard the result. The counter check has to happen before the expensive work, and the increment has to happen at the point where the attempt is counted, which is before the outcome is known. Incrementing only on failure means an attacker who interleaves a successful attempt with failures can reset the window; incrementing on every attempt is the safer default for a login endpoint.

The counter store itself becomes a hot path. A per-account counter in the primary database puts a write on every login attempt, which is a throughput problem under attack and a lock contention problem under a distributed one. An in-memory counter with periodic persistence is faster and loses state on restart, which reopens the budget after a deploy. The usual compromise is a dedicated store with a short TTL and a replication factor that tolerates a node loss, plus a hard cap enforced in the application so that a lost counter cannot be worse than the cap.

The window semantics need to be chosen deliberately. A fixed window resets the count at a boundary, which allows twice the budget to be spent across the boundary: ten attempts in the last second of one window and ten in the first second of the next. A sliding window, where the counter covers the last $W$ seconds continuously, avoids that and costs more state. A token bucket, which refills at a steady rate and allows a burst up to the bucket size, is the cheapest approximation of a sliding window and is what most implementations converge on.

Detection as a second control

Rate limiting bounds the number of attempts but does not tell anyone that an attack is happening. A service that silently absorbs a million failed logins has defended the accounts and learned nothing.

The signals worth recording are per-account failure counts with the source addresses, the set of addresses that have failed against many distinct accounts, and the set of accounts that have failed from many distinct addresses. The first identifies a targeted attack, the second identifies a sprayer, and the third identifies a stuffing campaign. All three are computable from an append-only log of attempts with timestamps, and all three are cheap if the log is written for this purpose rather than assembled from general request logs after the fact.

The response to a confirmed campaign is usually not to block but to raise the requirement globally for a period: require the second factor for all logins from unseen addresses, or require a password reset for accounts that were targeted. The reason is that the accounts that failed are not necessarily the ones at risk; a sprayer succeeds silently on the accounts whose password matched, and those accounts show a successful login from an unusual address. That success is the signal worth alerting on, and it is the one that per-attempt failure counting does not produce.

Session-level controls complement the attempt-level ones. A new session from an unseen address that immediately accesses sensitive resources is the pattern of a successful stuffing attack, and session rotation at each privilege transition makes the resulting access easier to bound. The attempt budget decides how many guesses the attacker gets; what happens after a correct guess is decided by the session and step-up controls, and neither is a substitute for the other.