| | @@ -0,0 +1,427 @@ |
| 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 | + |
| 14 | +use std::{ |
| 15 | + collections::HashMap, |
| 16 | + sync::Mutex, |
| 17 | + time::{Duration, Instant}, |
| 18 | +}; |
| 19 | + |
| 20 | +use topcoat::{ |
| 21 | + context::{Cx, app_context}, |
| 22 | + router::{Body, Response, StatusCode, header::RETRY_AFTER, headers}, |
| 23 | +}; |
| 24 | + |
| 25 | +/// How long a window lasts. |
| 26 | +const 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. |
| 34 | +const 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. |
| 48 | +const 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. |
| 56 | +const MAX_KEYS: usize = 4096; |
| 57 | + |
| 58 | +/// The shared limiter. One per process, held in Topcoat's app context. |
| 59 | +#[derive(Debug)] |
| 60 | +pub 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)] |
| 69 | +struct 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)] |
| 76 | +struct Window { |
| 77 | + opened: Instant, |
| 78 | + hits: u32, |
| 79 | +} |
| 80 | + |
| 81 | +impl 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)] |
| 110 | +pub enum Decision { |
| 111 | + Allowed, |
| 112 | + /// Refused, with how long until the window it exhausted rolls over. |
| 113 | + Throttled(Duration), |
| 114 | +} |
| 115 | + |
| 116 | +impl Default for RateLimiter { |
| 117 | + fn default() -> Self { |
| 118 | + Self::new(WINDOW, PER_CLIENT, GLOBAL, MAX_KEYS) |
| 119 | + } |
| 120 | +} |
| 121 | + |
| 122 | +impl 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. |
| 194 | +pub 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. |
| 206 | +fn 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. |
| 240 | +fn 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. |
| 258 | +fn 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)] |
| 274 | +mod 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 | +} |