steid
Sign in

@jamesgill /

steid

steid/src/infrastructure/web/rate_limit.rs
14.2 KBCode·Blame·Raw
1//! In-memory rate limiting for the endpoints where guessing is feasible.
2//!
3//! `/auth/login` and `/auth/setup` are the only places a secret can be attacked by
4//! repetition: a personal access token is 256 bits, but a human-chosen password is
5//! not, and the setup token is worth guessing for exactly as long as the instance is
6//! unclaimed. The limiter also caps how often an anonymous caller can make the server
7//! run Argon2, which is deliberately expensive.
8//!
9//! Fixed windows rather than a token bucket: a window is two integers and a
10//! comparison, it is trivial to reason about when reading a log, and the burst it
11//! permits at a window boundary — twice the limit across two adjacent windows — does
12//! not matter at these rates. A bucket's smoother refill buys nothing here.
13
14use std::{
15 collections::HashMap,
16 sync::Mutex,
17 time::{Duration, Instant},
18};
19
20use topcoat::{
21 context::{Cx, app_context},
22 router::{Body, Response, StatusCode, header::RETRY_AFTER, headers},
23};
24
25/// How long a window lasts.
26const WINDOW: Duration = Duration::from_secs(60);
27
28/// Attempts one client may make per window.
29///
30/// Ten a minute is far above what a person signing in ever needs — a mistyped
31/// password twice, then a password manager — and far below what makes guessing
32/// worthwhile: an online attack against even a weak six-character password would take
33/// centuries at this rate.
34const PER_CLIENT: u32 = 10;
35
36/// Attempts *everyone together* may make per window.
37///
38/// This is the backstop for a forged client key (see [`client_key`]). Without a peer
39/// address there is no way to prove a caller is who its headers claim, so an attacker
40/// who can forge a different `X-Forwarded-For` per request would otherwise get an
41/// unlimited number of per-client budgets. Sixty a minute is six independent people
42/// each hitting their own limit at once, which a single-owner instance will never see,
43/// and it turns key forgery from a bypass into a six-fold speed-up.
44///
45/// The cost is that a flood can lock out a legitimate sign-in for up to a minute.
46/// That is the right way round: a temporary denial of the login form is recoverable,
47/// a guessed password is not.
48const GLOBAL: u32 = 60;
49
50/// Distinct client keys tracked at once.
51///
52/// The map is keyed by something the caller influences, so it must not be allowed to
53/// grow with the number of keys an attacker can invent. Past this many live keys,
54/// expired entries are swept and any still-unknown key falls back to the global
55/// window alone — which is stricter, not laxer, so filling the map is not a way out.
56const MAX_KEYS: usize = 4096;
57
58/// The shared limiter. One per process, held in Topcoat's app context.
59#[derive(Debug)]
60pub struct RateLimiter {
61 window: Duration,
62 per_client: u32,
63 global: u32,
64 max_keys: usize,
65 state: Mutex<State>,
66}
67
68#[derive(Debug)]
69struct State {
70 clients: HashMap<Box<str>, Window>,
71 global: Window,
72}
73
74/// A fixed window: when it opened, and how many attempts have landed in it.
75#[derive(Debug, Clone, Copy)]
76struct Window {
77 opened: Instant,
78 hits: u32,
79}
80
81impl Window {
82 fn new(now: Instant) -> Self {
83 Self {
84 opened: now,
85 hits: 0,
86 }
87 }
88
89 /// Records an attempt, rolling into a fresh window first if this one has expired.
90 fn record(&mut self, now: Instant, window: Duration) -> u32 {
91 if now.duration_since(self.opened) >= window {
92 *self = Self::new(now);
93 }
94
95 self.hits = self.hits.saturating_add(1);
96 self.hits
97 }
98
99 fn expired(&self, now: Instant, window: Duration) -> bool {
100 now.duration_since(self.opened) >= window
101 }
102
103 fn remaining(&self, now: Instant, window: Duration) -> Duration {
104 window.saturating_sub(now.duration_since(self.opened))
105 }
106}
107
108/// What the limiter decided about one attempt.
109#[derive(Debug, Clone, Copy, PartialEq, Eq)]
110pub enum Decision {
111 Allowed,
112 /// Refused, with how long until the window it exhausted rolls over.
113 Throttled(Duration),
114}
115
116impl Default for RateLimiter {
117 fn default() -> Self {
118 Self::new(WINDOW, PER_CLIENT, GLOBAL, MAX_KEYS)
119 }
120}
121
122impl RateLimiter {
123 /// Builds a limiter with explicit limits. Tests use this; `main` uses
124 /// [`Default`].
125 #[must_use]
126 pub fn new(window: Duration, per_client: u32, global: u32, max_keys: usize) -> Self {
127 Self {
128 window,
129 per_client,
130 global,
131 max_keys,
132 state: Mutex::new(State {
133 clients: HashMap::new(),
134 global: Window::new(Instant::now()),
135 }),
136 }
137 }
138
139 /// Records an attempt for `key` and says whether it may proceed.
140 pub fn check(&self, key: &str) -> Decision {
141 self.check_at(key, Instant::now())
142 }
143
144 /// [`check`](Self::check) with the clock supplied, so tests can move time.
145 fn check_at(&self, key: &str, now: Instant) -> Decision {
146 let mut state = self.state.lock().unwrap_or_else(|poisoned| {
147 // A panic while holding the lock would otherwise disable the limiter for
148 // the life of the process, which is the wrong way to fail.
149 self.state.clear_poison();
150 poisoned.into_inner()
151 });
152
153 // Every attempt counts against the global window, including one that is about
154 // to be refused for its own key: an attacker rotating keys still pays here.
155 let global_hits = state.global.record(now, self.window);
156 if global_hits > self.global {
157 return Decision::Throttled(state.global.remaining(now, self.window));
158 }
159
160 if !state.clients.contains_key(key) && state.clients.len() >= self.max_keys {
161 let window = self.window;
162 state.clients.retain(|_, entry| !entry.expired(now, window));
163
164 if state.clients.len() >= self.max_keys {
165 // Still full of live entries, so this attempt is covered by the
166 // global window only. Refusing to grow is what bounds the memory.
167 return Decision::Allowed;
168 }
169 }
170
171 let entry = state
172 .clients
173 .entry(key.into())
174 .or_insert_with(|| Window::new(now));
175
176 if entry.record(now, self.window) > self.per_client {
177 return Decision::Throttled(entry.remaining(now, self.window));
178 }
179
180 Decision::Allowed
181 }
182
183 /// How many client keys are currently held. For tests and diagnostics.
184 #[must_use]
185 pub fn tracked_keys(&self) -> usize {
186 self.state.lock().map_or(0, |state| state.clients.len())
187 }
188}
189
190/// Applies the shared limiter to this request, returning the 429 to send when the
191/// caller has spent its budget.
192///
193/// Call it first in a handler, before any password hashing or token comparison.
194pub fn throttled(cx: &Cx) -> Option<Response> {
195 match app_context::<RateLimiter>(cx).check(&client_key(cx)) {
196 Decision::Allowed => None,
197 Decision::Throttled(retry_after) => {
198 eprintln!("steid: rate limited an auth attempt");
199 Some(too_many_requests(retry_after))
200 }
201 }
202}
203
204/// The 429 itself. Deliberately a bare line of text: it says nothing about which
205/// limit was hit or what the instance is.
206fn too_many_requests(retry_after: Duration) -> Response {
207 let seconds = retry_after.as_secs().max(1);
208
209 let mut response = Response::new(Body::from("too many attempts, try again shortly\n"));
210 *response.status_mut() = StatusCode::TOO_MANY_REQUESTS;
211 response.headers_mut().insert(RETRY_AFTER, seconds.into());
212
213 response
214}
215
216/// What the limiter counts against — an approximation of the client's address.
217///
218/// **Topcoat 0.5 does not expose the peer address.** `internal_serve` discards it at
219/// accept time (`let (stream, _remote) = accepted?;`) and never puts it on the request
220/// extensions, so a handler has nothing but headers to go on. That constrains this
221/// entirely, and it is worth restating rather than rediscovering.
222///
223/// So: the **rightmost** `X-Forwarded-For` entry, then `X-Real-IP`, then a single
224/// shared key.
225///
226/// Rightmost, not leftmost, because a proxy *appends* the address it accepted the
227/// connection from. A client that sends its own `X-Forwarded-For: 1.2.3.4` gets
228/// `1.2.3.4, <real address>` by the time Steid sees it, so the last entry is the one
229/// the nearest proxy wrote and the only one it cannot forge. The leftmost entry —
230/// what "the real client IP" usually means — is exactly the attacker-controlled one.
231/// This assumes a single proxy hop; behind two, the rightmost entry is the inner
232/// proxy, and every client collapses onto one key. Stricter, so safe to be wrong
233/// about.
234///
235/// The trade-off this cannot escape: on an instance exposed **directly** to the
236/// internet, with no proxy appending anything, a caller can invent a fresh
237/// `X-Forwarded-For` per request and get a fresh per-client budget each time. The
238/// global window above is what keeps that from being a total bypass. Closing it
239/// properly needs the peer address, which means a change in Topcoat.
240fn client_key(cx: &Cx) -> String {
241 let headers = headers(cx);
242 let value = |name: &str| headers.get(name).and_then(|value| value.to_str().ok());
243
244 let forwarded = value("x-forwarded-for")
245 .and_then(|list| list.rsplit(',').next())
246 .and_then(address);
247
248 forwarded
249 .or_else(|| value("x-real-ip").and_then(address))
250 // No proxy header at all: everyone shares one window. Right for a directly
251 // exposed instance, where the alternative is no limit; a proxy that forwards
252 // neither header collapses its whole userbase into this key.
253 .unwrap_or_else(|| "direct".to_owned())
254}
255
256/// Accepts a header fragment only if it looks like an address, so a hostile header
257/// cannot become an arbitrarily large or arbitrarily weird map key.
258fn address(raw: &str) -> Option<String> {
259 /// Longest textual IPv6 address, with a zone and an embedded IPv4 tail.
260 const MAX: usize = 64;
261
262 let candidate = raw.trim();
263
264 let plausible = !candidate.is_empty()
265 && candidate.len() <= MAX
266 && candidate
267 .chars()
268 .all(|c| c.is_ascii_hexdigit() || matches!(c, '.' | ':' | '%' | '[' | ']'));
269
270 plausible.then(|| candidate.to_owned())
271}
272
273#[cfg(test)]
274mod tests {
275 use super::*;
276
277 fn limiter() -> RateLimiter {
278 RateLimiter::new(Duration::from_secs(60), 3, 100, 16)
279 }
280
281 #[test]
282 fn allows_attempts_up_to_the_limit() {
283 let limiter = limiter();
284 let now = Instant::now();
285
286 for _ in 0..3 {
287 assert_eq!(limiter.check_at("a", now), Decision::Allowed);
288 }
289 }
290
291 #[test]
292 fn refuses_the_attempt_after_the_limit() {
293 let limiter = limiter();
294 let now = Instant::now();
295
296 for _ in 0..3 {
297 limiter.check_at("a", now);
298 }
299
300 assert!(matches!(limiter.check_at("a", now), Decision::Throttled(_)));
301 }
302
303 #[test]
304 fn reports_how_long_until_the_window_rolls() {
305 let limiter = limiter();
306 let now = Instant::now();
307
308 for _ in 0..4 {
309 limiter.check_at("a", now);
310 }
311
312 let Decision::Throttled(retry_after) = limiter.check_at("a", now + Duration::from_secs(20))
313 else {
314 panic!("the key is over its limit");
315 };
316
317 assert_eq!(retry_after, Duration::from_secs(40));
318 }
319
320 #[test]
321 fn recovers_once_the_window_has_passed() {
322 let limiter = limiter();
323 let now = Instant::now();
324
325 for _ in 0..4 {
326 limiter.check_at("a", now);
327 }
328
329 assert_eq!(
330 limiter.check_at("a", now + Duration::from_secs(60)),
331 Decision::Allowed
332 );
333 }
334
335 #[test]
336 fn keys_are_independent() {
337 let limiter = limiter();
338 let now = Instant::now();
339
340 for _ in 0..4 {
341 limiter.check_at("a", now);
342 }
343
344 assert_eq!(limiter.check_at("b", now), Decision::Allowed);
345 }
346
347 #[test]
348 fn the_global_window_catches_a_caller_rotating_keys() {
349 let limiter = RateLimiter::new(Duration::from_secs(60), 3, 5, 16);
350 let now = Instant::now();
351
352 for index in 0..5 {
353 assert_eq!(
354 limiter.check_at(&format!("k{index}"), now),
355 Decision::Allowed
356 );
357 }
358
359 assert!(matches!(
360 limiter.check_at("k5", now),
361 Decision::Throttled(_)
362 ));
363 }
364
365 #[test]
366 fn the_map_does_not_grow_past_its_cap() {
367 let limiter = RateLimiter::new(Duration::from_secs(60), 3, u32::MAX, 16);
368 let now = Instant::now();
369
370 for index in 0..5_000 {
371 limiter.check_at(&format!("k{index}"), now);
372 }
373
374 assert!(limiter.tracked_keys() <= 16);
375 }
376
377 #[test]
378 fn expired_entries_are_swept_to_make_room() {
379 let limiter = RateLimiter::new(Duration::from_secs(60), 3, u32::MAX, 16);
380 let now = Instant::now();
381
382 for index in 0..16 {
383 limiter.check_at(&format!("old{index}"), now);
384 }
385
386 // A minute later every one of those has expired, so the newcomer is tracked
387 // rather than being waved through on the global window alone.
388 let later = now + Duration::from_secs(61);
389 for _ in 0..4 {
390 limiter.check_at("new", later);
391 }
392
393 assert!(matches!(
394 limiter.check_at("new", later),
395 Decision::Throttled(_)
396 ));
397 assert!(limiter.tracked_keys() <= 16);
398 }
399
400 #[test]
401 fn a_key_beyond_the_cap_is_still_covered_by_the_global_window() {
402 let limiter = RateLimiter::new(Duration::from_secs(60), 3, 20, 2);
403 let now = Instant::now();
404
405 for index in 0..20 {
406 limiter.check_at(&format!("k{index}"), now);
407 }
408
409 assert!(matches!(
410 limiter.check_at("k20", now),
411 Decision::Throttled(_)
412 ));
413 }
414
415 #[test]
416 fn an_address_is_accepted() {
417 assert_eq!(address(" 203.0.113.7 "), Some("203.0.113.7".to_owned()));
418 assert_eq!(address("2001:db8::1"), Some("2001:db8::1".to_owned()));
419 }
420
421 #[test]
422 fn a_hostile_header_value_is_rejected() {
423 assert_eq!(address(""), None);
424 assert_eq!(address("not an address"), None);
425 assert_eq!(address(&"9".repeat(65)), None);
426 }
427}