matter_kit/msg/counter.rs
1//! Message counters and duplicate detection (Core §4.6).
2//!
3//! Every message carries a 32-bit counter that does two jobs: it is part of the
4//! encryption nonce, and it is how a receiver notices it has seen this message before.
5//! The second job is the one with teeth — "a malicious third party attempted to replay an
6//! old message to gain some advantage" — and it is done with a *lossy* history: the
7//! largest counter seen, plus a 32-bit bitmap of which of the 32 counters immediately
8//! before it have arrived (§4.6.5.1).
9//!
10//! That compression is what makes the state affordable: 8 octets per peer instead of a set
11//! of every counter ever seen. The cost is that a message more than
12//! [`MSG_COUNTER_WINDOW_SIZE`] behind the maximum is treated as a duplicate even if it is
13//! genuinely new, which is exactly the trade the specification makes.
14//!
15//! # Two rules, because there are two counter spaces
16//!
17//! A secure unicast session's counter never rolls over: the session is rekeyed long before
18//! 2³² messages. So "new" simply means "greater than the maximum" (§4.6.5.2.1).
19//!
20//! A group counter is global and free-running, and does roll over. So "new" means "within
21//! the next 2³¹ counters, modulo 2³²" — the counter space is cut in half, ahead and
22//! behind (§4.6.5.2.2).
23//!
24//! Getting these two the wrong way round is a security bug in one direction (a replay
25//! accepted) and an interoperability bug in the other (a live peer locked out), which is
26//! why they are separate variants rather than a flag.
27
28use crate::error::{Error, ErrorCode, Result};
29
30/// "Maximum number of previously processed messages" a receiver remembers per peer
31/// (Core Table 20).
32pub const MSG_COUNTER_WINDOW_SIZE: u32 = 32;
33
34/// Which duplicate-detection rule applies to a counter space (§4.6.5.2).
35#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
36pub enum CounterKind {
37 /// A secure unicast session, whose counter does not roll over (§4.6.5.2.1).
38 ///
39 /// "any arriving message with a counter in the range `[(max_message_counter + 1) to
40 /// (2³² - 1)]` SHALL be considered new".
41 SecureUnicast,
42 /// A group session, or an unencrypted peer — a free-running counter that rolls over
43 /// (§4.6.5.2.2).
44 ///
45 /// "any arriving message with a counter in the range `[(max_message_counter + 1) to
46 /// (max_message_counter + 2³¹ - 1)]` (modulo 2³²) SHALL be considered new".
47 Rollover,
48}
49
50/// What a receiver should do with an arriving counter.
51#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
52pub enum Verdict {
53 /// Not seen before: process it, and the window has been updated to record it.
54 New,
55 /// Seen before, or too far behind to tell.
56 ///
57 /// §4.12.2.2 is emphatic about what happens next for a *reliable* message: "The
58 /// receiver SHALL send an acknowledgment message to the sender for each instance of
59 /// an authenticated, reliable message, including duplicates. The reliability layer
60 /// SHALL only propagate the first instance of a message to the next higher layer."
61 /// So a duplicate is acknowledged and then dropped — never silently ignored, or the
62 /// sender retransmits until it gives up.
63 Duplicate,
64}
65
66/// The message reception state for one peer or session (§4.6.5.1).
67///
68/// Eight octets: the largest counter seen, and a bitmap of the 32 before it. Bit 0 stands
69/// for `max - 1`, bit 1 for `max - 2`, and so on.
70#[derive(Debug, Clone, Copy, PartialEq, Eq)]
71pub struct CounterWindow {
72 kind: CounterKind,
73 max: u32,
74 bitmap: u32,
75 /// Whether anything has been received yet. A fresh window must accept whatever
76 /// counter arrives first, since the peer chose its starting value at random
77 /// (§4.6.1.1) and there is nothing to compare against.
78 primed: bool,
79}
80
81impl CounterWindow {
82 /// An empty window that will accept the first counter it sees.
83 #[must_use]
84 pub const fn new(kind: CounterKind) -> Self {
85 Self {
86 kind,
87 max: 0,
88 bitmap: 0,
89 primed: false,
90 }
91 }
92
93 /// A window that has already seen `max` and nothing before it.
94 ///
95 /// This is how a session resumed from storage starts: the counter it left off at is
96 /// known, the 32 before it are not, so they are treated as already seen — which is
97 /// the safe direction.
98 #[must_use]
99 pub const fn primed_at(kind: CounterKind, max: u32) -> Self {
100 Self {
101 kind,
102 max,
103 bitmap: u32::MAX,
104 primed: true,
105 }
106 }
107
108 /// The largest counter accepted so far.
109 #[must_use]
110 pub const fn max(&self) -> u32 {
111 self.max
112 }
113
114 /// Which rule this window applies.
115 #[must_use]
116 pub const fn kind(&self) -> CounterKind {
117 self.kind
118 }
119
120 /// Judges `counter`, and records it when it is new.
121 pub fn accept(&mut self, counter: u32) -> Verdict {
122 if !self.primed {
123 self.primed = true;
124 self.max = counter;
125 self.bitmap = 0;
126 return Verdict::New;
127 }
128
129 if counter == self.max {
130 // "A message counter equal to max_message_counter SHALL be considered
131 // duplicate."
132 return Verdict::Duplicate;
133 }
134
135 let ahead = match self.kind {
136 // No rollover: strictly greater is ahead, full stop.
137 CounterKind::SecureUnicast => counter > self.max,
138 // Rollover: ahead means within the next 2³¹ - 1, modulo 2³².
139 CounterKind::Rollover => {
140 let delta = counter.wrapping_sub(self.max);
141 delta != 0 && delta < 0x8000_0000
142 }
143 };
144
145 if ahead {
146 let shift = counter.wrapping_sub(self.max);
147 // Shift the history along by however far the maximum moved, then record that
148 // the old maximum was itself received.
149 self.bitmap = if shift >= MSG_COUNTER_WINDOW_SIZE {
150 // Everything the bitmap held is now outside the window.
151 if shift == MSG_COUNTER_WINDOW_SIZE {
152 // The old maximum lands exactly on the last bit.
153 1u32.checked_shl(MSG_COUNTER_WINDOW_SIZE.saturating_sub(1))
154 .unwrap_or(0)
155 } else {
156 0
157 }
158 } else {
159 // `shift` is in 1..32 here, so both shifts are in range.
160 let moved = self.bitmap.checked_shl(shift).unwrap_or(0);
161 let old_max_bit = 1u32.checked_shl(shift.saturating_sub(1)).unwrap_or(0);
162 moved | old_max_bit
163 };
164 self.max = counter;
165 return Verdict::New;
166 }
167
168 // Behind the maximum. Inside the bitmap it is a duplicate if the bit is set and
169 // new otherwise; outside it, "All other message counters SHALL be considered
170 // duplicate."
171 let behind = self.max.wrapping_sub(counter);
172 if behind == 0 || behind > MSG_COUNTER_WINDOW_SIZE {
173 return Verdict::Duplicate;
174 }
175 let Some(bit) = 1u32.checked_shl(behind.saturating_sub(1)) else {
176 return Verdict::Duplicate;
177 };
178 if self.bitmap & bit != 0 {
179 Verdict::Duplicate
180 } else {
181 self.bitmap |= bit;
182 Verdict::New
183 }
184 }
185
186 /// Whether `counter` would be accepted, without recording it.
187 #[must_use]
188 pub fn would_accept(&self, counter: u32) -> Verdict {
189 let mut probe = *self;
190 probe.accept(counter)
191 }
192}
193
194/// A sender's own counter for one key (§4.6.1).
195///
196/// "The message counter is generated based on the Session Type and increases
197/// monotonically for each unique message generated." A retransmission reuses its
198/// counter — "logical retransmission is of a given message as identified by its message
199/// counter" (§4.4.1.4) — so the counter is taken once, when the message is first built,
200/// and not again.
201///
202/// §4.6.1.1's `Crypto_DRBG(len = 28) + 1`, applied to a full-width random word.
203///
204/// "All message counters SHALL be initialized with a random value using the
205/// `Crypto_DRBG(len = 28) + 1` primitive" — *all*, which is four counters in this crate with
206/// four different lifetimes: a secure session's (§4.6.2, randomised at establishment), the
207/// global unencrypted one (§4.6.1.2, randomised at startup), the two global group ones
208/// (§4.6.1.3) and the Check-In counter (§4.6.3), both randomised at factory reset and persisted
209/// after that. They share one rule, so they share one implementation: a counter that starts
210/// anywhere in `u32` is a rule broken four times over, or not at all.
211///
212/// The result is in `1..=2^28`. §4.6.1.1 gives the reason for the ceiling in its own words —
213/// the range is narrow "in order to maximize initial entropy while still reserving the vast
214/// majority of the range to actual counter values (roughly 2³² - 2²⁸)".
215///
216/// ```
217/// use matter_kit::msg::initial_counter;
218///
219/// assert_eq!(initial_counter(0), 1);
220/// assert_eq!(initial_counter(u32::MAX), 1 << 28);
221/// assert!((1..=(1 << 28)).contains(&initial_counter(0xDEAD_BEEF)));
222/// ```
223#[must_use]
224pub const fn initial_counter(randomness: u32) -> u32 {
225 // `& 0x0FFF_FFFF` is `Crypto_DRBG(len = 28)`: twenty-eight bits. `+ 1` moves it off zero,
226 // which §4.6.1.1 excludes, and makes 2²⁸ itself reachable.
227 (randomness & 0x0FFF_FFFF).saturating_add(1)
228}
229
230/// The initial value is random (§4.6.1.1), which is why [`MessageCounter::new`] takes one
231/// rather than starting at zero: a counter that always starts at 1 leaks how many times a
232/// device has rebooted, and makes nonce reuse across a factory reset far too easy.
233#[derive(Debug, Clone, Copy, PartialEq, Eq)]
234pub struct MessageCounter {
235 next: u32,
236 /// Set once [`u32::MAX`] has been handed out. Without it the increment fails on the
237 /// call that should return the last legal counter, throwing one away.
238 exhausted: bool,
239}
240
241impl MessageCounter {
242 /// §4.6.1.1's initialisation, from `randomness` — which should come from
243 /// [`crate::platform::Rng`].
244 ///
245 /// "All message counters SHALL be initialized with a random value using the
246 /// `Crypto_DRBG(len = 28) + 1` primitive", so the starting value is in `1..=2^28` and not
247 /// anywhere in `u32`. The specification gives the reason in the next sentence: the range is
248 /// deliberately narrow "in order to maximize initial entropy while still reserving the vast
249 /// majority of the range to actual counter values (roughly 2³² - 2²⁸)".
250 ///
251 /// That reservation is load-bearing rather than decorative. [`take`](Self::take) refuses on
252 /// exhaustion instead of rolling over — §4.6.2 has a secure session "discarded and
253 /// re-established before any Secure Session Message Counter overflow or repetition occurs"
254 /// — so the initial value is also the size of the session's supply. Seeded from the full
255 /// `u32` a session begins on average half-way through its own lifetime, and one in four
256 /// thousand begins with under a million counters left: it stops working early, and nothing
257 /// anywhere says why.
258 ///
259 /// The narrowing lives here rather than at each caller for the same reason the peer and the
260 /// report cursor do (D82, D83). [`at`](Self::at) is for an exact value — a persisted
261 /// counter, or the end of the range in a test.
262 #[must_use]
263 pub const fn new(randomness: u32) -> Self {
264 Self::at(initial_counter(randomness))
265 }
266
267 /// A counter at exactly `value`, bypassing §4.6.1.1.
268 ///
269 /// For restoring a counter that was persisted — a group sender's counters outlive a reboot
270 /// — and for tests that need to stand at a particular point in the range. A counter for a
271 /// *new* session comes from [`new`](Self::new).
272 #[must_use]
273 pub const fn at(value: u32) -> Self {
274 Self {
275 next: value,
276 exhausted: false,
277 }
278 }
279
280 /// The value the next message will carry.
281 #[must_use]
282 pub const fn peek(&self) -> u32 {
283 self.next
284 }
285
286 /// Takes the next counter.
287 ///
288 /// Returns [`ErrorCode::InvalidState`] on exhaustion rather than rolling over: for a
289 /// secure unicast session, reusing a counter means reusing a nonce, which is a
290 /// catastrophic failure of the encryption rather than a wrap to handle. A session that
291 /// reaches 2³² messages must be re-established, and the caller is told so.
292 pub fn take(&mut self) -> Result<u32> {
293 if self.exhausted {
294 return Err(Error::new(ErrorCode::InvalidState));
295 }
296 let value = self.next;
297 match self.next.checked_add(1) {
298 Some(n) => self.next = n,
299 // `value` is still legal and is returned; it is the *next* call that fails.
300 None => self.exhausted = true,
301 }
302 Ok(value)
303 }
304
305 /// Takes the next counter, rolling over at 2³².
306 ///
307 /// For the group counter space, which §4.6.5.2.2 defines as "a free running message
308 /// counter that monotonically increases, but rolls over to zero when it exceeds the
309 /// maximum value of the counter".
310 pub fn take_with_rollover(&mut self) -> u32 {
311 let value = self.next;
312 self.next = self.next.wrapping_add(1);
313 self.exhausted = false;
314 value
315 }
316}
317
318#[cfg(test)]
319mod tests {
320 use super::*;
321
322 #[test]
323 fn the_first_counter_is_always_accepted() {
324 // A peer picks its initial counter at random (§4.6.1.1), so there is nothing to
325 // compare the first one against.
326 let mut w = CounterWindow::new(CounterKind::SecureUnicast);
327 assert_eq!(w.accept(0x8000_0000), Verdict::New);
328 assert_eq!(w.max(), 0x8000_0000);
329 }
330
331 #[test]
332 fn a_repeat_of_the_maximum_is_a_duplicate() {
333 let mut w = CounterWindow::new(CounterKind::SecureUnicast);
334 assert_eq!(w.accept(100), Verdict::New);
335 assert_eq!(w.accept(100), Verdict::Duplicate);
336 }
337
338 #[test]
339 fn in_order_delivery_is_all_new() {
340 let mut w = CounterWindow::new(CounterKind::SecureUnicast);
341 for c in 1..1000 {
342 assert_eq!(w.accept(c), Verdict::New, "counter {c}");
343 }
344 assert_eq!(w.max(), 999);
345 }
346
347 #[test]
348 fn out_of_order_inside_the_window_is_accepted_once() {
349 let mut w = CounterWindow::new(CounterKind::SecureUnicast);
350 assert_eq!(w.accept(100), Verdict::New);
351 assert_eq!(w.accept(105), Verdict::New);
352 // The four that were skipped are still new the first time they arrive.
353 for c in [101, 102, 103, 104] {
354 assert_eq!(w.accept(c), Verdict::New, "counter {c}");
355 assert_eq!(w.accept(c), Verdict::Duplicate, "counter {c} again");
356 }
357 assert_eq!(w.max(), 105, "a late arrival does not move the maximum");
358 }
359
360 #[test]
361 fn beyond_the_window_is_a_duplicate_even_if_it_is_new() {
362 // The documented cost of the lossy history (§4.6.5.1).
363 let mut w = CounterWindow::new(CounterKind::SecureUnicast);
364 assert_eq!(w.accept(1000), Verdict::New);
365 // One past the far edge of the window: genuinely new, reported as a duplicate.
366 assert_eq!(
367 w.accept(1000 - MSG_COUNTER_WINDOW_SIZE - 1),
368 Verdict::Duplicate
369 );
370 assert_eq!(w.accept(1), Verdict::Duplicate);
371 }
372
373 #[test]
374 fn the_window_edge_is_where_the_spec_puts_it() {
375 // §4.6.5.1: the window is "between [(max - MSG_COUNTER_WINDOW_SIZE) to
376 // (max - 1)]", and bit i stands for `max - 1 - i`. So `max - 32` is the *last*
377 // bit, inside the window, and `max - 33` is the first one outside it.
378 let mut w = CounterWindow::new(CounterKind::SecureUnicast);
379 assert_eq!(w.accept(1000), Verdict::New);
380 assert_eq!(
381 w.accept(1000 - 32),
382 Verdict::New,
383 "32 behind is the last bit"
384 );
385 assert_eq!(w.accept(1000 - 32), Verdict::Duplicate, "and now it is set");
386 assert_eq!(w.accept(1000 - 33), Verdict::Duplicate, "33 behind is out");
387 assert_eq!(
388 w.accept(1000 - 1),
389 Verdict::New,
390 "1 behind is the first bit"
391 );
392 }
393
394 #[test]
395 fn a_big_jump_forward_clears_the_history() {
396 let mut w = CounterWindow::new(CounterKind::SecureUnicast);
397 assert_eq!(w.accept(100), Verdict::New);
398 assert_eq!(w.accept(99), Verdict::New);
399 assert_eq!(w.accept(10_000), Verdict::New);
400 // 99 is now far behind, so it reads as a duplicate — which it is.
401 assert_eq!(w.accept(99), Verdict::Duplicate);
402 }
403
404 #[test]
405 fn a_secure_unicast_counter_does_not_roll_over() {
406 // §4.6.5.2.1: new is "[(max + 1) to (2³² - 1)]" — nothing wraps.
407 let mut w = CounterWindow::new(CounterKind::SecureUnicast);
408 assert_eq!(w.accept(u32::MAX - 1), Verdict::New);
409 assert_eq!(w.accept(u32::MAX), Verdict::New);
410 assert_eq!(w.accept(0), Verdict::Duplicate, "0 is behind, not ahead");
411 assert_eq!(w.accept(5), Verdict::Duplicate);
412 }
413
414 #[test]
415 fn a_group_counter_does_roll_over() {
416 // §4.6.5.2.2: new is "[(max + 1) to (max + 2³¹ - 1)] (modulo 2³²)".
417 let mut w = CounterWindow::new(CounterKind::Rollover);
418 assert_eq!(w.accept(u32::MAX), Verdict::New);
419 assert_eq!(w.accept(0), Verdict::New, "0 is one past u32::MAX");
420 assert_eq!(w.accept(1), Verdict::New);
421 assert_eq!(w.accept(u32::MAX), Verdict::Duplicate, "and back is behind");
422 }
423
424 #[test]
425 fn the_group_space_is_cut_in_half() {
426 let mut w = CounterWindow::new(CounterKind::Rollover);
427 assert_eq!(w.accept(1000), Verdict::New);
428 // Just under half the space ahead is new.
429 assert_eq!(w.accept(1000u32.wrapping_add(0x7FFF_FFFF)), Verdict::New);
430 let mut w = CounterWindow::new(CounterKind::Rollover);
431 assert_eq!(w.accept(1000), Verdict::New);
432 // Exactly half is behind, not ahead.
433 assert_eq!(
434 w.accept(1000u32.wrapping_add(0x8000_0000)),
435 Verdict::Duplicate
436 );
437 }
438
439 #[test]
440 fn a_window_restored_from_storage_rejects_everything_behind_it() {
441 let mut w = CounterWindow::primed_at(CounterKind::SecureUnicast, 5000);
442 for c in [4999, 4990, 4969, 1] {
443 assert_eq!(w.accept(c), Verdict::Duplicate, "counter {c}");
444 }
445 assert_eq!(w.accept(5001), Verdict::New);
446 }
447
448 #[test]
449 fn would_accept_does_not_record() {
450 let mut w = CounterWindow::new(CounterKind::SecureUnicast);
451 assert_eq!(w.accept(100), Verdict::New);
452 assert_eq!(w.would_accept(101), Verdict::New);
453 assert_eq!(w.would_accept(101), Verdict::New, "still new");
454 assert_eq!(w.accept(101), Verdict::New);
455 assert_eq!(w.would_accept(101), Verdict::Duplicate, "now it is not");
456 }
457
458 #[test]
459 fn a_replay_of_an_entire_window_is_caught() {
460 let mut w = CounterWindow::new(CounterKind::SecureUnicast);
461 for c in 1..=64u32 {
462 assert_eq!(w.accept(c), Verdict::New);
463 }
464 // An attacker replays the lot.
465 for c in 1..=64u32 {
466 assert_eq!(w.accept(c), Verdict::Duplicate, "replayed counter {c}");
467 }
468 }
469
470 #[test]
471 fn the_sender_counter_refuses_to_reuse_a_nonce() {
472 let mut c = MessageCounter::at(u32::MAX - 1);
473 assert_eq!(c.take().expect("one left"), u32::MAX - 1);
474 assert_eq!(
475 c.take().expect("the last counter is usable"),
476 u32::MAX,
477 "giving up at u32::MAX - 1 throws away a legal counter"
478 );
479 assert_eq!(
480 c.take().unwrap_err().code(),
481 ErrorCode::InvalidState,
482 "a unicast counter must not wrap: that reuses a nonce"
483 );
484 }
485
486 #[test]
487 fn the_group_sender_counter_does_roll_over() {
488 let mut c = MessageCounter::at(u32::MAX);
489 assert_eq!(c.take_with_rollover(), u32::MAX);
490 assert_eq!(c.take_with_rollover(), 0);
491 assert_eq!(c.peek(), 1);
492 }
493
494 /// §4.6.1.1: "All message counters SHALL be initialized with a random value using the
495 /// `Crypto_DRBG(len = 28) + 1` primitive."
496 ///
497 /// A production counter is seeded from `Rng::next_u32`, so the whole `u32` is what it can
498 /// be handed; the sweep is over the boundaries of the mask plus every top-byte pattern,
499 /// which is where a wrong mask or a missing `+ 1` shows.
500 #[test]
501 fn an_initial_counter_is_inside_the_twenty_eight_bit_range() {
502 const CEILING: u32 = 1 << 28;
503 let mut seen_top = false;
504 for high in 0..=u8::MAX {
505 for low in [0x00u32, 0x01, 0x7F, 0x80, 0xFE, 0xFF] {
506 let randomness = (u32::from(high) << 24) | (low << 16) | (low << 8) | low;
507 let start = MessageCounter::new(randomness).peek();
508 assert!(
509 (1..=CEILING).contains(&start),
510 "{randomness:#010x} started at {start:#010x}"
511 );
512 seen_top |= start == CEILING;
513 }
514 }
515 // `+ 1` makes 2²⁸ itself reachable; a mask alone would stop one short.
516 assert!(seen_top, "the top of the range is never reached");
517 // And zero is not in it, which is the whole point of the `+ 1`.
518 assert_eq!(MessageCounter::new(0).peek(), 1);
519 assert_eq!(MessageCounter::new(u32::MAX).peek(), CEILING);
520 }
521
522 /// The counter a session is given has to leave it room to run.
523 ///
524 /// `take` refuses on exhaustion rather than rolling over (§4.6.2), so the initial value
525 /// is also the size of the session's supply. Seeding from the full `u32` left one session
526 /// in four thousand with under a million counters, which is a session that stops working
527 /// early and says nothing about why.
528 #[test]
529 fn an_initial_counter_leaves_the_session_its_supply() {
530 const RESERVED: u32 = u32::MAX - (1 << 28);
531 for randomness in [0, 1, u32::MAX, u32::MAX - 1, 0xFFFF_0000, 0x8000_0000] {
532 let remaining = u32::MAX - MessageCounter::new(randomness).peek();
533 assert!(
534 remaining >= RESERVED,
535 "{randomness:#010x} left only {remaining} counters"
536 );
537 }
538 }
539
540 /// `at` is the escape hatch, and it really does bypass the narrowing — otherwise the tests
541 /// that stand at the end of the range would be standing somewhere else.
542 #[test]
543 fn at_takes_the_value_it_is_given() {
544 assert_eq!(MessageCounter::at(u32::MAX).peek(), u32::MAX);
545 assert_eq!(MessageCounter::at(0).peek(), 0);
546 }
547}