Design rate limiting for /login to stop credential stuffing

➔? Design rate limiting for a login endpoint to prevent brute-force and credential stuffing attacks

Concepts Involved

Rate Limiting Authentication Redis API Gateway

Problem Statement

Design rate limiting for the /login endpoint to stop credential stuffing attacks, using dual keys (per-account and per-IP), strict exactness with no edge burst tolerance, progressive lockout/backoff behavior, and fail-closed policy.

Core challenge: Login rate limiting is fail-closed (unlike most rate limiters). A false-negative (letting an attacker through) is worse than a false-positive (temporarily locking a legitimate user). Dual keying is essential: per-IP catches botnets rotating usernames; per-account catches distributed attacks targeting one account.

attempts per account

per 15 minutes

attempts per IP

per 15 minutes

Dual Key

per-account + per-IP

both must pass

Fail-Closed

security > availability

block on uncertainty

Functional Requirements

What the system must do · the core login protection behaviours

Must Have (Core)

1. Dual-key rate limiting (per-account + per-IP) — both must pass
2. Progressive lockout escalation (15min → 1hr → 24hr → manual unlock)
3. Fail-closed policy — deny on uncertainty (opposite of normal rate limiters)
4. Timing-safe responses — same latency for valid/invalid accounts (prevent enumeration)
5. Successful login resets per-account counter (legitimate user recovery)
6. Email alert to account owner on persistent attack (Level 3+)

Out of Scope (this design)

✗ CAPTCHA implementation (triggered by this system, implemented separately)
✗ MFA flows (complementary but separate authentication layer)
✗ Device fingerprinting ML (behavioral analysis pipeline)
✗ Geographic anomaly detection (IP reputation / impossible travel)
✗ Password breach database checks (separate credential hygiene service)

Non-Functional Requirements

The quality constraints that shape every architectural decision — security-first

Property	Target	Why It Matters / Design Impact
Accuracy	EXACT count (zero tolerance for boundary burst)	Security critical. Even 1 extra attempt = 20% increase in attack surface on a 5-attempt limit.
Fail mode	Fail-CLOSED (deny on uncertainty)	Opposite of normal rate limiters. A missed attacker is worse than briefly locking a legitimate user.
Latency	<5ms overhead acceptable	Security > speed for /login. Users expect login to take ~500ms anyway. 5ms is invisible.
Storage	Redis Sorted Set (timestamps, not counters)	Sorted set of exact timestamps enables precise sliding window. No approximation allowed.
Privacy	No password logging	Only attempt timestamps stored. No actual credentials, no password hashes in rate limit store.

Key tension: Security vs. Availability. We choose security · if Redis is unreachable, DENY all login attempts (fail-closed). Better to briefly lock everyone than let attackers through during an outage. This is the opposite of API rate limiting which fails open.

Scale Estimation

Given numbers from the question → derive infrastructure sizing for login protection

Given (from question): 10M users · 1% login per hour = 100K login attempts/hour · peak 10x = 280/sec normal, attack: 100K attempts/sec

Step	What to Derive	Calculation	Result	Design Decision
1	Normal login rate	10M users × 1% per hour ÷ 3600	~28 req/sec	Baseline is trivial. The design must handle attack traffic, not normal traffic.
2	Peak normal rate	28 req/sec × 10x peak factor	~280 req/sec	Still very manageable for Redis. Size for attack scenario instead.
3	Attack scenario ops	100K attempts/sec from botnet	100K ops/sec	Each attempt = ZREMRANGEBYSCORE + ZADD + ZCARD = ~3 Redis ops. Total: 300K ops/sec.
4	Redis memory (per-account)	Sorted Set with max 15 entries × 8 bytes per entry (timestamp)	~120 bytes/key	For 1M attacked accounts: 1M × 120 bytes = ~120MB. Comfortable for Redis.
5	Redis memory (per-IP)	100K unique IPs × 20 entries × 8 bytes	~16MB	Trivial. Even 1M IPs would only be 160MB.

Interview tip: Start with normal traffic (trivial), then jump to attack scenario. Show the Redis ops math under attack conditions — this proves the system can handle a botnet without breaking. The key insight: sorted sets have slightly higher memory than counters but give you exact window enforcement.

APIs

Rate limit check runs BEFORE authentication logic · prevents password verification under attack

POST /login

Rate limit check executes BEFORE password verification. On failure: increment both per-account and per-IP counters. On success: reset per-account counter only (ZREMRANGEBYSCORE).

// Request

POST /login

{ "email": "user@example.com", "password": "..." }

// Flow: rate_check → authenticate → response

// If rate limited before auth:

HTTP 429 + Retry-After: 900 (escalating)

429 Rate Limited Response (same format as auth failure)

Returns same error format as authentication failure to prevent account enumeration. Retry-After escalates with lockout level.

// Response (identical format to wrong-password response)

HTTP 429

Retry-After: 900 // escalates: 30 → 60 → 300 → 900

{

  "error": "authentication_failed",

  "message": "Invalid credentials" // same msg as wrong password!

}

// Note: response time is constant (timing-safe) regardless of reason

Data Model

Redis Sorted Sets for exact timestamp tracking + lockout state

Redis · Sliding Window Logs (Sorted Sets)

// Per-account attempt log (score = timestamp, member = timestamp)
login:account:{email_hash} → SORTED SET
  Example: login:account:a1b2c3 → { 1705312100, 1705312130, 1705312145 }
  Trim: ZREMRANGEBYSCORE key -inf (now - 900)  // 15-min window

// Per-IP attempt log
login:ip:{ip_or_subnet} → SORTED SET
  Example: login:ip:203.0.113.0/48 → { 1705312100, 1705312101, ... }
  Trim: ZREMRANGEBYSCORE key -inf (now - 900)  // 15-min window

// Check: ZCARD key → if count ≥ threshold → DENY

Redis · Lockout State

// Progressive lockout level (STRING with TTL)
login:lockout:{email_hash} → "1" | "2" | "3" | "4"
  TTL: Level 1 = 900s, Level 2 = 3600s, Level 3 = 86400s, Level 4 = none (manual)
  Example: login:lockout:a1b2c3 → "2" (TTL: 3600)

// On successful login:
//   DEL login:account:{email_hash}   ← reset per-account
//   DEL login:lockout:{email_hash}   ← clear lockout
//   (per-IP counter NOT reset — still protects against horizontal attacks)

Architecture · Sliding Window Log with Progressive Lockout

Exact timestamp tracking per attempt — no approximation allowed for security-critical paths

Decision	Choice	Why
Algorithm	Sliding window log (sorted set of timestamps)	Exact count — no boundary burst possible. Security requires precision over memory efficiency.
Keys	Dual: login:{account_id} + login:{ip_address}	Per-account catches distributed attacks on one user. Per-IP catches credential stuffing across many accounts.
Storage	Redis Sorted Set (ZADD timestamp, ZRANGEBYSCORE for window)	Exact timestamps, O(log N) insert, window trim via ZREMRANGEBYSCORE.
Lockout	Progressive: 5 fails → 15min lock, 10 fails → 1hr, 15 fails → 24hr + email alert	Escalating penalty deters persistent attackers. Email notification enables account recovery.
Fail mode	Fail-closed (deny on uncertainty)	If Redis is unreachable, reject login attempts. Security-critical path cannot be permissive.
Reset	Successful login resets per-account counter (not per-IP)	Legitimate owner recovers their account. IP counter still protects against horizontal attacks.

Sliding window log: Store each failed attempt timestamp in a Redis sorted set. On new attempt: ZREMRANGEBYSCORE to trim entries older than window, ZCARD to count remaining. If count ≥ threshold → reject. Exact — no approximation, no edge burst.

Progressive backoff response: Don't just return 429. Return increasing Retry-After values: 30s → 60s → 300s → 900s. After threshold, require CAPTCHA or email verification to unlock. Never reveal whether the account exists (timing-safe response).

Why NOT sliding window counter here: Approximate counters can allow 1-2 extra attempts at window boundaries — unacceptable for security. With 5-attempt limit, even 1 extra attempt is a 20% increase in attack surface. Sliding window log guarantees exactness.

Real-world: Auth0 · anomaly detection + brute-force protection (10 attempts/account). Cloudflare · WAF rules for login paths. GitHub · progressive lockout with CAPTCHA. AWS Cognito · configurable lockout policies.

Resilience & Edge Cases

Failure	Impact	Recovery
Redis down	Cannot verify attempt count	Fail-closed: reject all login attempts. Alert ops team. Fallback to local in-memory store with conservative limits.
Distributed botnet (10K IPs)	Per-IP limit ineffective (1 attempt per IP)	Per-account limit still catches it. Add CAPTCHA after 3 failed per-account. Device fingerprinting as additional signal.
Legitimate user locked out	Can't login after forgotten password attempts	Email unlock link. Phone SMS verification. Support override with identity verification.
Account enumeration via timing	Attacker discovers valid accounts	Constant-time response for all login attempts. Same error message for invalid user vs wrong password.
IPv6 rotation	Attacker rotates /64 prefix	Rate limit by /48 or /56 subnet prefix for IPv6, not individual addresses.

Interview Cheat Sheet

Key points for login rate limiting

1. Sliding window log · exact timestamps, no boundary burst (security demands precision)
2. Dual keying · per-account AND per-IP — both must pass for login to proceed
3. Fail-closed · if rate limiter is unavailable, deny login (opposite of most rate limiters)
4. Progressive lockout · escalating penalties: 15min → 1hr → 24hr + email alert
5. Timing-safe responses · same latency/message for valid vs invalid accounts (prevent enumeration)
6. Successful login resets per-account counter · legitimate user recovery doesn't require support intervention

System Design Case Study