Skip to main content

tuwunel_service/login_ratelimit/
mod.rs

1//! Password throttles by account and client address.
2//!
3//! Each attempt spends an address token and reserves an account/address failure
4//! token before verification; only a wrong password keeps the reservation.
5//! Verified sign-ins also spend an account token, while UIAA uses separate
6//! attempt tables so public login traffic cannot exhaust its allowance. When the
7//! client address is the TCP peer, a loopback peer stands for everyone behind a
8//! local proxy and is not limited by address.
9
10use std::{
11	borrow::Borrow,
12	collections::BTreeMap,
13	net::{IpAddr, Ipv6Addr},
14	ops::Bound::{Excluded, Included, Unbounded},
15	sync::{Arc, Mutex},
16	time::{Duration, Instant},
17};
18
19use http::StatusCode;
20use ruma::{
21	UserId,
22	api::error::{ErrorKind, LimitExceededErrorData, RetryAfter},
23};
24use tuwunel_core::{
25	Error, Result, Server, implement, smallstr::SmallString, smallvec::SmallVec, warn,
26};
27
28/// Password login and reauthentication throttles.
29///
30/// The tables live here rather than on [`crate::users::Service`] so that the
31/// interior mutability they need stays out of a type whose `&self` methods are
32/// linted as taking nothing mutable.
33pub struct Service {
34	server: Arc<Server>,
35	account: Ratelimiter<AccountKey>,
36	login: Attempts,
37	uiaa: Attempts,
38}
39
40/// A failed-attempt token reserved for one password attempt.
41///
42/// Dropping it keeps the token, as a wrong password does; other outcomes pass it
43/// to [`Service::refund_login_attempt`] or [`Service::record_login`]. The scope
44/// keeps public login refunds separate from UIAA refunds.
45#[derive(Debug)]
46#[must_use]
47pub struct Reservation {
48	key: FailedKey,
49	hold: Hold,
50	scope: Scope,
51}
52
53type AccountKey = SmallString<[u8; 48]>;
54type FailedKey = (AccountKey, IpAddr);
55type Ratelimiter<K = String> = Mutex<Table<K>>;
56type Buckets<K> = BTreeMap<K, (Instant, f64)>;
57type Pruned<K> = SmallVec<[K; 1]>;
58
59#[derive(Default)]
60struct Attempts {
61	/// Refilled buckets expire on admission or refund; each table holds at most 65536 keys.
62	failed: Ratelimiter<FailedKey>,
63
64	/// Refilled buckets expire on admission; each table holds at most 65536 addresses.
65	address: Ratelimiter<IpAddr>,
66}
67
68struct Table<K = String> {
69	buckets: Buckets<K>,
70	cursor: Option<K>,
71}
72
73#[derive(Clone, Copy, Debug)]
74enum Scope {
75	Login,
76	Uiaa,
77}
78
79impl<K> Default for Table<K> {
80	fn default() -> Self { Self { buckets: BTreeMap::new(), cursor: None } }
81}
82
83impl crate::Service for Service {
84	fn build(args: &crate::Args<'_>) -> Result<Arc<Self>> {
85		Ok(Arc::new(Self {
86			server: args.server.clone(),
87			account: Ratelimiter::default(),
88			login: Attempts::default(),
89			uiaa: Attempts::default(),
90		}))
91	}
92
93	fn name(&self) -> &str { crate::service::make_name(std::module_path!()) }
94}
95
96/// Cap on the number of accounts each bucket table holds.
97///
98/// A full table never evicts a bucket that is still limiting; [`Axis`] decides
99/// what happens to an account it cannot admit.
100const RATELIMIT_MAP_CAP: usize = 1 << 16;
101
102/// How many entries one admission inspects when the table is full.
103const PRUNE_SAMPLE: usize = 64;
104
105/// The longest `retry_after` a refusal will state, whatever the rate.
106const MAX_RETRY_AFTER: Duration = Duration::from_hours(24);
107
108/// How often each table's full-table warning may repeat while it stays full.
109const FULL_WARNING_INTERVAL: Duration = Duration::from_mins(1);
110
111static FAILED_FULL_WARNING: Mutex<Option<Instant>> = Mutex::new(None);
112
113static ADDRESS_FULL_WARNING: Mutex<Option<Instant>> = Mutex::new(None);
114
115static ACCOUNT_FULL_WARNING: Mutex<Option<Instant>> = Mutex::new(None);
116
117#[cfg(test)]
118mod tests;
119
120/// One bucket's configuration: refill rate per second and burst depth.
121#[derive(Clone, Copy)]
122struct Limit {
123	rate: f64,
124	burst: u32,
125}
126
127impl Limit {
128	const OFF: Self = Self { rate: 0.0, burst: 0 };
129
130	/// A zero burst, or a rate that is zero, negative or not a number, turns
131	/// the bucket off rather than making it one that never refills.
132	fn enabled(self) -> bool { self.burst > 0 && self.rate > 0.0 && self.rate.is_finite() }
133
134	fn burst(self) -> f64 { f64::from(self.burst) }
135}
136
137/// Whether a reservation actually took a token.
138#[derive(Clone, Copy, Debug, PartialEq, Eq)]
139enum Hold {
140	/// A token was taken and is owed back unless a wrong password keeps it.
141	Held,
142
143	/// No token was taken: the limit is off, or a full table could not track
144	/// the account.
145	Untracked,
146}
147
148/// Which bucket table a debit addresses, deciding its full-table policy.
149///
150/// A bucket that is still limiting is never evicted to make room, since that
151/// would hand the account being guessed a fresh burst.
152#[derive(Clone, Copy, Debug)]
153enum Axis {
154	/// Wrong passwords; an account the full table cannot admit goes untracked.
155	Failed,
156
157	/// All password attempts by address; a full table admits untracked addresses.
158	Address,
159
160	/// Verified sign-ins; an account the full table cannot admit is refused.
161	Account,
162}
163
164impl Axis {
165	fn when_full(self) -> Result<Hold> {
166		match self {
167			| Self::Failed | Self::Address => Ok(Hold::Untracked),
168			| Self::Account => Err(limit_exceeded(None)),
169		}
170	}
171
172	fn last_full_warning(self) -> &'static Mutex<Option<Instant>> {
173		match self {
174			| Self::Failed => &FAILED_FULL_WARNING,
175			| Self::Address => &ADDRESS_FULL_WARNING,
176			| Self::Account => &ACCOUNT_FULL_WARNING,
177		}
178	}
179}
180
181/// Reserve an account/address failure token before checking a login password.
182///
183/// The address budget is spent first and is never refunded. Atomic reservations
184/// prevent simultaneous guesses from sharing the last failure token.
185#[implement(Service)]
186pub fn reserve_login_attempt(&self, user_id: &UserId, address: IpAddr) -> Result<Reservation> {
187	self.reserve_attempt(user_id, address, Scope::Login)
188}
189
190/// Reserve a password reauthentication attempt independently of public login.
191///
192/// Both the address and failed-attempt budgets are separate from sign-in budgets.
193#[implement(Service)]
194pub fn reserve_uiaa_attempt(&self, user_id: &UserId, address: IpAddr) -> Result<Reservation> {
195	self.reserve_attempt(user_id, address, Scope::Uiaa)
196}
197
198#[implement(Service)]
199fn reserve_attempt(
200	&self,
201	user_id: &UserId,
202	address: IpAddr,
203	scope: Scope,
204) -> Result<Reservation> {
205	reserve_at(
206		self.attempts(scope),
207		(user_id, address),
208		(self.failed_limit(), self.address_limit(address)),
209		scope,
210		Instant::now(),
211	)
212}
213
214#[implement(Service)]
215fn attempts(&self, scope: Scope) -> &Attempts {
216	match scope {
217		| Scope::Login => &self.login,
218		| Scope::Uiaa => &self.uiaa,
219	}
220}
221
222/// Record a sign-in by a verified password.
223///
224/// Refund its failure token before spending the account's successful-login
225/// allowance; a correct password never consumes a failed-attempt token.
226#[implement(Service)]
227pub fn record_login(&self, reservation: Reservation) -> Result {
228	let Reservation { key, hold, scope } = reservation;
229	let now = Instant::now();
230
231	refund_at(&self.attempts(scope).failed, &key, hold, self.failed_limit(), now)?;
232	debit_at(
233		&self.account,
234		&key.0,
235		self.account_limit(),
236		Axis::Account,
237		now,
238		RATELIMIT_MAP_CAP,
239	)?;
240
241	Ok(())
242}
243
244/// Refund an attempt that found no wrong password.
245///
246/// The reservation selects its original login or UIAA failure table; the
247/// address budget still counts the request.
248#[implement(Service)]
249pub fn refund_login_attempt(&self, reservation: Reservation) -> Result {
250	let Reservation { key, hold, scope } = reservation;
251
252	refund_at(&self.attempts(scope).failed, &key, hold, self.failed_limit(), Instant::now())
253}
254
255#[implement(Service)]
256fn failed_limit(&self) -> Limit {
257	let failed = &self.server.config.rate_limiting.login.failed;
258
259	Limit {
260		rate: failed.per_second,
261		burst: failed.burst_count,
262	}
263}
264
265#[implement(Service)]
266fn account_limit(&self) -> Limit {
267	let account = &self.server.config.rate_limiting.login.account;
268
269	Limit {
270		rate: account.per_second,
271		burst: account.burst_count,
272	}
273}
274
275/// The address budget, off for an address that identifies no single client.
276///
277/// Budgeting a loopback socket peer would give everyone behind a local proxy
278/// or the Unix listener one shared allowance, which a single client could
279/// exhaust; those attempts keep their failed-attempt and account limits.
280#[implement(Service)]
281fn address_limit(&self, address: IpAddr) -> Limit {
282	let config = &self.server.config;
283	let budget = &config.rate_limiting.login.address;
284	let source = config.http.ip_source.unwrap_or_default();
285
286	if !source.identifies_client(address) {
287		return Limit::OFF;
288	}
289
290	Limit {
291		rate: budget.per_second,
292		burst: budget.burst_count,
293	}
294}
295
296fn reserve_at(
297	attempts: &Attempts,
298	(user_id, address): (&UserId, IpAddr),
299	(failed, limit): (Limit, Limit),
300	scope: Scope,
301	now: Instant,
302) -> Result<Reservation> {
303	let address = address_key(address);
304
305	debit_at(&attempts.address, &address, limit, Axis::Address, now, RATELIMIT_MAP_CAP)?;
306
307	let key = (account_key(user_id), address);
308	let hold = debit_at(&attempts.failed, &key, failed, Axis::Failed, now, RATELIMIT_MAP_CAP)?;
309
310	Ok(Reservation { key, hold, scope })
311}
312
313fn address_key(address: IpAddr) -> IpAddr {
314	match address.to_canonical() {
315		| IpAddr::V4(address) => address.into(),
316		| IpAddr::V6(address) => {
317			let [a, b, c, d, ..] = address.segments();
318
319			Ipv6Addr::new(a, b, c, d, 0, 0, 0, 0).into()
320		},
321	}
322}
323
324fn account_key(user_id: &UserId) -> AccountKey {
325	let account = user_id.as_str();
326
327	if account.is_ascii() {
328		account
329			.chars()
330			.map(|ch| ch.to_ascii_lowercase())
331			.collect()
332	} else {
333		AccountKey::from_str(&account.to_lowercase())
334	}
335}
336
337/// Take one token from an account's bucket, refusing when none is left.
338///
339/// An account the table does not hold starts with a full bucket. When the
340/// table holds `cap` accounts and nothing can be pruned, the axis decides
341/// whether such an account is refused or let through untracked.
342fn debit_at<K, Q>(
343	table: &Ratelimiter<K>,
344	key: &Q,
345	limit: Limit,
346	axis: Axis,
347	now: Instant,
348	cap: usize,
349) -> Result<Hold>
350where
351	K: Borrow<Q> + Clone + Ord,
352	Q: Ord + ToOwned<Owned = K> + ?Sized,
353{
354	if !limit.enabled() {
355		return Ok(Hold::Untracked);
356	}
357
358	let Limit { rate, .. } = limit;
359	let burst = limit.burst();
360	let mut table = table.lock()?;
361	let Table { buckets, cursor } = &mut *table;
362
363	debug_assert!(cap > 0, "rate-limit table cap must be positive");
364
365	let Some(bucket) = buckets.get_mut(key) else {
366		if buckets.len() >= cap {
367			prune_sample(buckets, cursor, rate, burst, now);
368		}
369
370		if buckets.len() >= cap {
371			drop(table);
372			warn_table_full(axis, now);
373			return axis.when_full();
374		}
375
376		buckets.insert(key.to_owned(), (now, burst - 1.0));
377		return Ok(Hold::Held);
378	};
379
380	let (last_time, tokens) = bucket;
381	let refilled = refill(*last_time, *tokens, rate, burst, now);
382
383	if refilled < 1.0 {
384		return Err(limit_exceeded(retry_after(rate, refilled)));
385	}
386
387	*last_time = now;
388	*tokens = refilled - 1.0;
389
390	Ok(Hold::Held)
391}
392
393/// Give a held reservation's token back, never past the burst.
394///
395/// A bucket refunded back to full carries no information and is removed, so
396/// ordinary sign-ins do not fill the table. An untracked reservation took
397/// nothing and gets nothing back.
398fn refund_at<K, Q>(
399	table: &Ratelimiter<K>,
400	key: &Q,
401	hold: Hold,
402	limit: Limit,
403	now: Instant,
404) -> Result
405where
406	K: Borrow<Q> + Ord,
407	Q: Ord + ?Sized,
408{
409	if hold == Hold::Untracked || !limit.enabled() {
410		return Ok(());
411	}
412
413	let burst = limit.burst();
414	let mut table = table.lock()?;
415	let Table { buckets, .. } = &mut *table;
416
417	let Some((last_time, tokens)) = buckets.get_mut(key) else {
418		return Ok(());
419	};
420
421	let level = burst.min(refill(*last_time, *tokens, limit.rate, burst, now) + 1.0);
422
423	if level >= burst {
424		buckets.remove(key);
425	} else {
426		*last_time = now;
427		*tokens = level;
428	}
429
430	Ok(())
431}
432
433fn refill(last: Instant, tokens: f64, rate: f64, burst: f64, now: Instant) -> f64 {
434	now.saturating_duration_since(last)
435		.as_secs_f64()
436		.mul_add(rate, tokens)
437		.min(burst)
438}
439
440/// Remove, from the next bounded sample of the table, the buckets that have
441/// refilled completely.
442///
443/// Each sample starts after the last account the previous one inspected and
444/// wraps around at the end, so successive samples reach every bucket even
445/// while the leading ones stay restricted. A bucket that is still restricted
446/// is never removed.
447fn prune_sample<K: Clone + Ord>(
448	buckets: &mut Buckets<K>,
449	cursor: &mut Option<K>,
450	rate: f64,
451	burst: f64,
452	now: Instant,
453) {
454	let after = (cursor.as_ref().map_or(Unbounded, Excluded), Unbounded);
455	let wrapped = (Unbounded, cursor.as_ref().map_or(Unbounded, Included));
456	let sample = buckets
457		.range::<K, _>(after)
458		.chain(
459			buckets
460				.range::<K, _>(wrapped)
461				.take(if cursor.is_some() { PRUNE_SAMPLE } else { 0 }),
462		)
463		.take(PRUNE_SAMPLE);
464
465	if let Some((key, _)) = sample.clone().last() {
466		match cursor {
467			| None => *cursor = Some(key.clone()),
468			| Some(cursor) => cursor.clone_from(key),
469		}
470	}
471
472	let refilled: Pruned<K> = sample
473		.filter(|(_, (last, tokens))| refill(*last, *tokens, rate, burst, now) >= burst)
474		.map(|(key, _)| key.clone())
475		.collect();
476
477	for key in refilled {
478		buckets.remove(&key);
479	}
480}
481
482/// Warn that the table for `axis` cannot admit another account.
483///
484/// At most once per [`FULL_WARNING_INTERVAL`] for each table, so a spray that
485/// keeps one table full neither floods the log nor hides the other's warning.
486fn warn_table_full(axis: Axis, now: Instant) {
487	let Ok(mut last) = axis.last_full_warning().lock() else {
488		return;
489	};
490
491	if last.is_some_and(|last| now.saturating_duration_since(last) < FULL_WARNING_INTERVAL) {
492		return;
493	}
494
495	*last = Some(now);
496
497	match axis {
498		| Axis::Failed | Axis::Address => warn!(
499			table = ?axis,
500			cap = RATELIMIT_MAP_CAP,
501			"Password rate-limit table is full of keys still being limited; attempts for \
502			 keys not already in it go untracked."
503		),
504		| Axis::Account => warn!(
505			table = ?axis,
506			cap = RATELIMIT_MAP_CAP,
507			"Login rate-limit table is full of accounts still being limited; sign-ins for \
508			 accounts not already in it are refused."
509		),
510	}
511}
512
513/// Seconds until one token is back, rounded up and capped. `None` when it
514/// cannot be stated, which the error then simply omits.
515fn retry_after(rate: f64, tokens: f64) -> Option<Duration> {
516	let secs = ((1.0 - tokens) / rate).ceil();
517
518	// Capped before converting: a tiny rate gives a figure too large for a
519	// `Duration`, and the cap is the honest answer to it, not an omission.
520	Duration::try_from_secs_f64(secs.min(MAX_RETRY_AFTER.as_secs_f64())).ok()
521}
522
523fn limit_exceeded(retry_after: Option<Duration>) -> Error {
524	Error::Request(
525		ErrorKind::LimitExceeded(LimitExceededErrorData {
526			retry_after: retry_after.map(RetryAfter::Delay),
527		}),
528		"Too many password authentication attempts.".into(),
529		StatusCode::TOO_MANY_REQUESTS,
530	)
531}