throttle.rs 97.4%

111 of 114 lines run, 28 of 30 functions · run #536 on main · run missed

//! Slowing down guessing (oxygenhub#221): password sign-in, the 2FA code
//! step, password reset requests and device codes.
//!
//! Each key (an account or an address, within one action) counts its
//! failures. A few are free; after that each one doubles the wait before the
//! next try, up to a short lockout. A quiet hour forgets the count, and a
//! success clears the account's. Kept in memory: a restart forgets it, which
//! costs an attacker a restart they cannot cause.

use std::collections::HashMap;

/// Failures an account may have before waits start.
const ACCOUNT_FREE: u32 = 5;
/// Failures an address may have before waits start: higher, since many
/// people can share one address.
const ADDRESS_FREE: u32 = 20;
/// The first wait.
const FIRST_WAIT_MS: i64 = 2_000;
/// The longest wait: the lockout.
pub const LOCKOUT_MS: i64 = 15 * 60_000;
/// A key with no failure for this long starts again.
const FORGET_MS: i64 = 60 * 60_000;
/// Keys kept before stale ones are swept.
const SWEEP_AT: usize = 50_000;

#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
pub enum Kind {
    Account,
    Address,
}

/// What is counted: an account or an address, within one action.
#[derive(Clone, PartialEq, Eq, Hash, Debug)]
pub struct Key {
    action: &'static str,
    kind: Kind,
    id: String,
}

impl Key {
    /// An account, by name; names compare without case.
    pub fn account(action: &'static str, name: &str) -> Key {
        Key { action, kind: Kind::Account, id: name.trim().to_lowercase() }
    }

    /// An address. An empty one (unknown) is never counted.
    pub fn address(action: &'static str, addr: &str) -> Key {
        Key { action, kind: Kind::Address, id: addr.to_string() }
    }

    fn free(&self) -> u32 {
        match self.kind {
            Kind::Account => ACCOUNT_FREE,
            Kind::Address => ADDRESS_FREE,
        }
    }
}

#[derive(Default)]
struct Count {
    failures: u32,
    last_ms: i64,
    until_ms: i64,
}

#[derive(Default)]
pub struct Throttle {
    counts: HashMap<Key, Count>,
}

impl Throttle {
    /// How long, in milliseconds, before any of these keys may try again;
    /// `None` when all may try now.
    pub fn wait(&self, keys: &[Key], now_ms: i64) -> Option<i64> {
        keys.iter()
            .filter_map(|k| self.counts.get(k))
            .filter(|c| now_ms - c.last_ms < FORGET_MS)
            .map(|c| c.until_ms - now_ms)
            .filter(|w| *w > 0)
            .max()
    }

    /// Count a failure (or, for an action with no failure, an attempt)
    /// against each key; the wait it leaves, if any.
    pub fn failed(&mut self, keys: &[Key], now_ms: i64) -> Option<i64> {
        if self.counts.len() >= SWEEP_AT {
            self.counts.retain(|_, c| now_ms - c.last_ms < FORGET_MS);
        }
        for key in keys.iter().filter(|k| !k.id.is_empty()) {
            let count = self.counts.entry(key.clone()).or_default();
            if now_ms - count.last_ms >= FORGET_MS {
                *count = Count::default();
            }
            count.failures += 1;
            count.last_ms = now_ms;
            if count.failures > key.free() {
                let doublings = (count.failures - key.free() - 1).min(20);
                count.until_ms = now_ms + (FIRST_WAIT_MS << doublings).min(LOCKOUT_MS);
            }
        }
        self.wait(keys, now_ms)
    }

    /// A success: the key starts again.
    pub fn cleared(&mut self, key: &Key) {
        self.counts.remove(key);
    }
}

/// "Too many tries: try again in 2 minutes." for a wait.
pub fn message(wait_ms: i64) -> String {
    let secs = (wait_ms + 999) / 1000;
    let when = match secs {
        ..=1 => "a second".to_string(),
        2..=59 => format!("{secs} seconds"),
        _ => {
            let mins = (secs + 59) / 60;
            if mins == 1 {
                "a minute".to_string()
            } else {
                format!("{mins} minutes")
            }
        }
    };
    format!("Too many tries: try again in {when}.")
}

#[cfg(test)]
mod tests {
    use super::*;

    const T0: i64 = 1_000_000_000;

    #[test]
    fn an_account_gets_a_few_free_failures_then_doubling_waits_up_to_the_lockout() {
        let mut t = Throttle::default();
        let k = [Key::account("login", "Alice")];
        for _ in 0..ACCOUNT_FREE {
            assert_eq!(t.wait(&k, T0), None);
            t.failed(&k, T0);
        }
        assert_eq!(t.wait(&k, T0), None, "the free failures cost nothing");
        assert_eq!(t.failed(&k, T0), Some(2_000), "the failure says the wait it starts");
        t.failed(&k, T0);
        assert_eq!(t.wait(&k, T0), Some(4_000));
        for _ in 0..20 {
            t.failed(&k, T0);
        }
        assert_eq!(t.wait(&k, T0), Some(LOCKOUT_MS), "capped at the lockout");
        assert_eq!(t.wait(&k, T0 + LOCKOUT_MS), None, "and it ends");
        assert_eq!(t.wait(&[Key::account("login", " alice ")], T0), Some(LOCKOUT_MS), "names compare without case");
    }

    #[test]
    fn a_success_clears_the_account_and_a_quiet_hour_forgets() {
        let mut t = Throttle::default();
        let k = [Key::account("login", "bob")];
        for _ in 0..10 {
            t.failed(&k, T0);
        }
        assert!(t.wait(&k, T0).is_some());
        t.cleared(&k[0]);
        assert_eq!(t.wait(&k, T0), None);

        for _ in 0..10 {
            t.failed(&k, T0);
        }
        let later = T0 + FORGET_MS;
        assert_eq!(t.wait(&k, later), None);
        t.failed(&k, later);
        assert_eq!(t.wait(&k, later), None, "the count started again");
    }

    #[test]
    fn addresses_get_more_room_and_actions_and_unknown_addresses_are_apart() {
        let mut t = Throttle::default();
        let addr = [Key::address("login", "203.0.113.9")];
        for _ in 0..ADDRESS_FREE {
            t.failed(&addr, T0);
        }
        assert_eq!(t.wait(&addr, T0), None);
        t.failed(&addr, T0);
        assert_eq!(t.wait(&addr, T0), Some(2_000));
        assert_eq!(t.wait(&[Key::address("reset", "203.0.113.9")], T0), None, "another action counts apart");

        let unknown = [Key::address("login", "")];
        for _ in 0..100 {
            t.failed(&unknown, T0);
        }
        assert_eq!(t.wait(&unknown, T0), None, "an unknown address is never counted");

        // The longest wait of the keys given is the one that counts.
        let both = [Key::account("login", "carol"), addr[0].clone()];
        assert_eq!(t.wait(&both, T0), Some(2_000));
    }

    #[test]
    fn the_message_says_when() {
        assert_eq!(message(900), "Too many tries: try again in a second.");
        assert_eq!(message(4_000), "Too many tries: try again in 4 seconds.");
        assert_eq!(message(61_000), "Too many tries: try again in 2 minutes.");
        assert_eq!(message(LOCKOUT_MS), "Too many tries: try again in 15 minutes.");
    }
}

`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet

1		//! Slowing down guessing (oxygenhub#221): password sign-in, the 2FA code
2		//! step, password reset requests and device codes.
3		//!
4		//! Each key (an account or an address, within one action) counts its
5		//! failures. A few are free; after that each one doubles the wait before the
6		//! next try, up to a short lockout. A quiet hour forgets the count, and a
7		//! success clears the account's. Kept in memory: a restart forgets it, which
8		//! costs an attacker a restart they cannot cause.
9
10		use std::collections::HashMap;
11
12		/// Failures an account may have before waits start.
13		const ACCOUNT_FREE: u32 = 5;
14		/// Failures an address may have before waits start: higher, since many
15		/// people can share one address.
16		const ADDRESS_FREE: u32 = 20;
17		/// The first wait.
18		const FIRST_WAIT_MS: i64 = 2_000;
19		/// The longest wait: the lockout.
20		pub const LOCKOUT_MS: i64 = 15 * 60_000;
21		/// A key with no failure for this long starts again.
22		const FORGET_MS: i64 = 60 * 60_000;
23		/// Keys kept before stale ones are swept.
24		const SWEEP_AT: usize = 50_000;
25
26		#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
27		pub enum Kind {
28		Account,
29		Address,
30		}
31
32		/// What is counted: an account or an address, within one action.
33		#[derive(Clone, PartialEq, Eq, Hash, Debug)]
34		pub struct Key {
35		action: &'static str,
36		kind: Kind,
37		id: String,
38		}
39
40		impl Key {
41		/// An account, by name; names compare without case.
42	57×	pub fn account(action: &'static str, name: &str) -> Key {
43	57×	Key { action, kind: Kind::Account, id: name.trim().to_lowercase() }
44	57×	}
45
46		/// An address. An empty one (unknown) is never counted.
47	57×	pub fn address(action: &'static str, addr: &str) -> Key {
48	57×	Key { action, kind: Kind::Address, id: addr.to_string() }
49	57×	}
50
51	162×	fn free(&self) -> u32 {
52	162×	match self.kind {
53	112×	Kind::Account => ACCOUNT_FREE,
54	50×	Kind::Address => ADDRESS_FREE,
55		}
56	162×	}
57		}
58
59		#[derive(Default)]
60		struct Count {
61		failures: u32,
62		last_ms: i64,
63		until_ms: i64,
64		}
65
66		#[derive(Default)]
67		pub struct Throttle {
68		counts: HashMap<Key, Count>,
69		}
70
71		impl Throttle {
72		/// How long, in milliseconds, before any of these keys may try again;
73		/// `None` when all may try now.
74	279×	pub fn wait(&self, keys: &[Key], now_ms: i64) -> Option<i64> {
75	279×	keys.iter()
76	360×	.filter_map(\|k\| self.counts.get(k))
77	279×	.filter(\|c\| now_ms - c.last_ms < FORGET_MS)
78	279×	.map(\|c\| c.until_ms - now_ms)
79	279×	.filter(\|w\| *w > 0)
80	279×	.max()
81	279×	}
82
83		/// Count a failure (or, for an action with no failure, an attempt)
84		/// against each key; the wait it leaves, if any.
85	204×	pub fn failed(&mut self, keys: &[Key], now_ms: i64) -> Option<i64> {
86	204×	if self.counts.len() >= SWEEP_AT {
87	0×	self.counts.retain(\|_, c\| now_ms - c.last_ms < FORGET_MS);
88	204×	}
89	234×	for key in keys.iter().filter(\|k\| !k.id.is_empty()) {
90	127×	let count = self.counts.entry(key.clone()).or_default();
91	127×	if now_ms - count.last_ms >= FORGET_MS {
92	33×	*count = Count::default();
93	94×	}
94	127×	count.failures += 1;
95	127×	count.last_ms = now_ms;
96	127×	if count.failures > key.free() {
97	35×	let doublings = (count.failures - key.free() - 1).min(20);
98	35×	count.until_ms = now_ms + (FIRST_WAIT_MS << doublings).min(LOCKOUT_MS);
99	92×	}
100		}
101	204×	self.wait(keys, now_ms)
102	204×	}
103
104		/// A success: the key starts again.
105	11×	pub fn cleared(&mut self, key: &Key) {
106	11×	self.counts.remove(key);
107	11×	}
108		}
109
110		/// "Too many tries: try again in 2 minutes." for a wait.
111	6×	pub fn message(wait_ms: i64) -> String {
112	6×	let secs = (wait_ms + 999) / 1000;
113	6×	let when = match secs {
114	6×	..=1 => "a second".to_string(),
115	5×	2..=59 => format!("{secs} seconds"),
116		_ => {
117	2×	let mins = (secs + 59) / 60;
118	2×	if mins == 1 {
119	0×	"a minute".to_string()
120		} else {
121	2×	format!("{mins} minutes")
122		}
123		}
124		};
125	6×	format!("Too many tries: try again in {when}.")
126	6×	}
127
128		#[cfg(test)]
129		mod tests {
130		use super::*;
131
132		const T0: i64 = 1_000_000_000;
133
134		#[test]
135	1×	fn an_account_gets_a_few_free_failures_then_doubling_waits_up_to_the_lockout() {
136	1×	let mut t = Throttle::default();
137	1×	let k = [Key::account("login", "Alice")];
138	1×	for _ in 0..ACCOUNT_FREE {
139	5×	assert_eq!(t.wait(&k, T0), None);
140	5×	t.failed(&k, T0);
141		}
142	1×	assert_eq!(t.wait(&k, T0), None, "the free failures cost nothing");
143	1×	assert_eq!(t.failed(&k, T0), Some(2_000), "the failure says the wait it starts");
144	1×	t.failed(&k, T0);
145	1×	assert_eq!(t.wait(&k, T0), Some(4_000));
146	20×	for _ in 0..20 {
147	20×	t.failed(&k, T0);
148	20×	}
149	1×	assert_eq!(t.wait(&k, T0), Some(LOCKOUT_MS), "capped at the lockout");
150	1×	assert_eq!(t.wait(&k, T0 + LOCKOUT_MS), None, "and it ends");
151	1×	assert_eq!(t.wait(&[Key::account("login", " alice ")], T0), Some(LOCKOUT_MS), "names compare without case");
152	1×	}
153
154		#[test]
155	1×	fn a_success_clears_the_account_and_a_quiet_hour_forgets() {
156	1×	let mut t = Throttle::default();
157	1×	let k = [Key::account("login", "bob")];
158	10×	for _ in 0..10 {
159	10×	t.failed(&k, T0);
160	10×	}
161	1×	assert!(t.wait(&k, T0).is_some());
162	1×	t.cleared(&k[0]);
163	1×	assert_eq!(t.wait(&k, T0), None);
164
165	10×	for _ in 0..10 {
166	10×	t.failed(&k, T0);
167	10×	}
168	1×	let later = T0 + FORGET_MS;
169	1×	assert_eq!(t.wait(&k, later), None);
170	1×	t.failed(&k, later);
171	1×	assert_eq!(t.wait(&k, later), None, "the count started again");
172	1×	}
173
174		#[test]
175	1×	fn addresses_get_more_room_and_actions_and_unknown_addresses_are_apart() {
176	1×	let mut t = Throttle::default();
177	1×	let addr = [Key::address("login", "203.0.113.9")];
178	20×	for _ in 0..ADDRESS_FREE {
179	20×	t.failed(&addr, T0);
180	20×	}
181	1×	assert_eq!(t.wait(&addr, T0), None);
182	1×	t.failed(&addr, T0);
183	1×	assert_eq!(t.wait(&addr, T0), Some(2_000));
184	1×	assert_eq!(t.wait(&[Key::address("reset", "203.0.113.9")], T0), None, "another action counts apart");
185
186	1×	let unknown = [Key::address("login", "")];
187	100×	for _ in 0..100 {
188	100×	t.failed(&unknown, T0);
189	100×	}
190	1×	assert_eq!(t.wait(&unknown, T0), None, "an unknown address is never counted");
191
192		// The longest wait of the keys given is the one that counts.
193	1×	let both = [Key::account("login", "carol"), addr[0].clone()];
194	1×	assert_eq!(t.wait(&both, T0), Some(2_000));
195	1×	}
196
197		#[test]
198	1×	fn the_message_says_when() {
199	1×	assert_eq!(message(900), "Too many tries: try again in a second.");
200	1×	assert_eq!(message(4_000), "Too many tries: try again in 4 seconds.");
201	1×	assert_eq!(message(61_000), "Too many tries: try again in 2 minutes.");
202	1×	assert_eq!(message(LOCKOUT_MS), "Too many tries: try again in 15 minutes.");
203	1×	}
204		}

Coverage / crates/hub/src/throttle.rs 97.4%

Keyboard