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 a session
260 /// remembers its peer and a subscription its report cursor: per-interaction state belongs
261 /// to the thing it describes. [`at`](Self::at) is for an exact value — a persisted
262 /// counter, or the end of the range in a test.
263 #[must_use]
264 pub const fn new(randomness: u32) -> Self {
265 Self::at(initial_counter(randomness))
266 }
267
268 /// A counter at exactly `value`, bypassing §4.6.1.1.
269 ///
270 /// For restoring a counter that was persisted — a group sender's counters outlive a reboot
271 /// — and for tests that need to stand at a particular point in the range. A counter for a
272 /// *new* session comes from [`new`](Self::new).
273 #[must_use]
274 pub const fn at(value: u32) -> Self {
275 Self {
276 next: value,
277 exhausted: false,
278 }
279 }
280
281 /// The value the next message will carry.
282 #[must_use]
283 pub const fn peek(&self) -> u32 {
284 self.next
285 }
286
287 /// Takes the next counter.
288 ///
289 /// Returns [`ErrorCode::InvalidState`] on exhaustion rather than rolling over: for a
290 /// secure unicast session, reusing a counter means reusing a nonce, which is a
291 /// catastrophic failure of the encryption rather than a wrap to handle. A session that
292 /// reaches 2³² messages must be re-established, and the caller is told so.
293 pub fn take(&mut self) -> Result<u32> {
294 if self.exhausted {
295 return Err(Error::new(ErrorCode::InvalidState));
296 }
297 let value = self.next;
298 match self.next.checked_add(1) {
299 Some(n) => self.next = n,
300 // `value` is still legal and is returned; it is the *next* call that fails.
301 None => self.exhausted = true,
302 }
303 Ok(value)
304 }
305
306 /// Takes the next counter, rolling over at 2³².
307 ///
308 /// For the group counter space, which §4.6.5.2.2 defines as "a free running message
309 /// counter that monotonically increases, but rolls over to zero when it exceeds the
310 /// maximum value of the counter".
311 pub fn take_with_rollover(&mut self) -> u32 {
312 let value = self.next;
313 self.next = self.next.wrapping_add(1);
314 self.exhausted = false;
315 value
316 }
317}
318
319#[cfg(test)]
320mod tests {
321 use super::*;
322
323 #[test]
324 fn the_first_counter_is_always_accepted() {
325 // A peer picks its initial counter at random (§4.6.1.1), so there is nothing to
326 // compare the first one against.
327 let mut w = CounterWindow::new(CounterKind::SecureUnicast);
328 assert_eq!(w.accept(0x8000_0000), Verdict::New);
329 assert_eq!(w.max(), 0x8000_0000);
330 }
331
332 #[test]
333 fn a_repeat_of_the_maximum_is_a_duplicate() {
334 let mut w = CounterWindow::new(CounterKind::SecureUnicast);
335 assert_eq!(w.accept(100), Verdict::New);
336 assert_eq!(w.accept(100), Verdict::Duplicate);
337 }
338
339 #[test]
340 fn in_order_delivery_is_all_new() {
341 let mut w = CounterWindow::new(CounterKind::SecureUnicast);
342 for c in 1..1000 {
343 assert_eq!(w.accept(c), Verdict::New, "counter {c}");
344 }
345 assert_eq!(w.max(), 999);
346 }
347
348 #[test]
349 fn out_of_order_inside_the_window_is_accepted_once() {
350 let mut w = CounterWindow::new(CounterKind::SecureUnicast);
351 assert_eq!(w.accept(100), Verdict::New);
352 assert_eq!(w.accept(105), Verdict::New);
353 // The four that were skipped are still new the first time they arrive.
354 for c in [101, 102, 103, 104] {
355 assert_eq!(w.accept(c), Verdict::New, "counter {c}");
356 assert_eq!(w.accept(c), Verdict::Duplicate, "counter {c} again");
357 }
358 assert_eq!(w.max(), 105, "a late arrival does not move the maximum");
359 }
360
361 #[test]
362 fn beyond_the_window_is_a_duplicate_even_if_it_is_new() {
363 // The documented cost of the lossy history (§4.6.5.1).
364 let mut w = CounterWindow::new(CounterKind::SecureUnicast);
365 assert_eq!(w.accept(1000), Verdict::New);
366 // One past the far edge of the window: genuinely new, reported as a duplicate.
367 assert_eq!(
368 w.accept(1000 - MSG_COUNTER_WINDOW_SIZE - 1),
369 Verdict::Duplicate
370 );
371 assert_eq!(w.accept(1), Verdict::Duplicate);
372 }
373
374 #[test]
375 fn the_window_edge_is_where_the_spec_puts_it() {
376 // §4.6.5.1: the window is "between [(max - MSG_COUNTER_WINDOW_SIZE) to
377 // (max - 1)]", and bit i stands for `max - 1 - i`. So `max - 32` is the *last*
378 // bit, inside the window, and `max - 33` is the first one outside it.
379 let mut w = CounterWindow::new(CounterKind::SecureUnicast);
380 assert_eq!(w.accept(1000), Verdict::New);
381 assert_eq!(
382 w.accept(1000 - 32),
383 Verdict::New,
384 "32 behind is the last bit"
385 );
386 assert_eq!(w.accept(1000 - 32), Verdict::Duplicate, "and now it is set");
387 assert_eq!(w.accept(1000 - 33), Verdict::Duplicate, "33 behind is out");
388 assert_eq!(
389 w.accept(1000 - 1),
390 Verdict::New,
391 "1 behind is the first bit"
392 );
393 }
394
395 #[test]
396 fn a_big_jump_forward_clears_the_history() {
397 let mut w = CounterWindow::new(CounterKind::SecureUnicast);
398 assert_eq!(w.accept(100), Verdict::New);
399 assert_eq!(w.accept(99), Verdict::New);
400 assert_eq!(w.accept(10_000), Verdict::New);
401 // 99 is now far behind, so it reads as a duplicate — which it is.
402 assert_eq!(w.accept(99), Verdict::Duplicate);
403 }
404
405 #[test]
406 fn a_secure_unicast_counter_does_not_roll_over() {
407 // §4.6.5.2.1: new is "[(max + 1) to (2³² - 1)]" — nothing wraps.
408 let mut w = CounterWindow::new(CounterKind::SecureUnicast);
409 assert_eq!(w.accept(u32::MAX - 1), Verdict::New);
410 assert_eq!(w.accept(u32::MAX), Verdict::New);
411 assert_eq!(w.accept(0), Verdict::Duplicate, "0 is behind, not ahead");
412 assert_eq!(w.accept(5), Verdict::Duplicate);
413 }
414
415 #[test]
416 fn a_group_counter_does_roll_over() {
417 // §4.6.5.2.2: new is "[(max + 1) to (max + 2³¹ - 1)] (modulo 2³²)".
418 let mut w = CounterWindow::new(CounterKind::Rollover);
419 assert_eq!(w.accept(u32::MAX), Verdict::New);
420 assert_eq!(w.accept(0), Verdict::New, "0 is one past u32::MAX");
421 assert_eq!(w.accept(1), Verdict::New);
422 assert_eq!(w.accept(u32::MAX), Verdict::Duplicate, "and back is behind");
423 }
424
425 #[test]
426 fn the_group_space_is_cut_in_half() {
427 let mut w = CounterWindow::new(CounterKind::Rollover);
428 assert_eq!(w.accept(1000), Verdict::New);
429 // Just under half the space ahead is new.
430 assert_eq!(w.accept(1000u32.wrapping_add(0x7FFF_FFFF)), Verdict::New);
431 let mut w = CounterWindow::new(CounterKind::Rollover);
432 assert_eq!(w.accept(1000), Verdict::New);
433 // Exactly half is behind, not ahead.
434 assert_eq!(
435 w.accept(1000u32.wrapping_add(0x8000_0000)),
436 Verdict::Duplicate
437 );
438 }
439
440 #[test]
441 fn a_window_restored_from_storage_rejects_everything_behind_it() {
442 let mut w = CounterWindow::primed_at(CounterKind::SecureUnicast, 5000);
443 for c in [4999, 4990, 4969, 1] {
444 assert_eq!(w.accept(c), Verdict::Duplicate, "counter {c}");
445 }
446 assert_eq!(w.accept(5001), Verdict::New);
447 }
448
449 #[test]
450 fn would_accept_does_not_record() {
451 let mut w = CounterWindow::new(CounterKind::SecureUnicast);
452 assert_eq!(w.accept(100), Verdict::New);
453 assert_eq!(w.would_accept(101), Verdict::New);
454 assert_eq!(w.would_accept(101), Verdict::New, "still new");
455 assert_eq!(w.accept(101), Verdict::New);
456 assert_eq!(w.would_accept(101), Verdict::Duplicate, "now it is not");
457 }
458
459 #[test]
460 fn a_replay_of_an_entire_window_is_caught() {
461 let mut w = CounterWindow::new(CounterKind::SecureUnicast);
462 for c in 1..=64u32 {
463 assert_eq!(w.accept(c), Verdict::New);
464 }
465 // An attacker replays the lot.
466 for c in 1..=64u32 {
467 assert_eq!(w.accept(c), Verdict::Duplicate, "replayed counter {c}");
468 }
469 }
470
471 #[test]
472 fn the_sender_counter_refuses_to_reuse_a_nonce() {
473 let mut c = MessageCounter::at(u32::MAX - 1);
474 assert_eq!(c.take().expect("one left"), u32::MAX - 1);
475 assert_eq!(
476 c.take().expect("the last counter is usable"),
477 u32::MAX,
478 "giving up at u32::MAX - 1 throws away a legal counter"
479 );
480 assert_eq!(
481 c.take().unwrap_err().code(),
482 ErrorCode::InvalidState,
483 "a unicast counter must not wrap: that reuses a nonce"
484 );
485 }
486
487 #[test]
488 fn the_group_sender_counter_does_roll_over() {
489 let mut c = MessageCounter::at(u32::MAX);
490 assert_eq!(c.take_with_rollover(), u32::MAX);
491 assert_eq!(c.take_with_rollover(), 0);
492 assert_eq!(c.peek(), 1);
493 }
494
495 /// §4.6.1.1: "All message counters SHALL be initialized with a random value using the
496 /// `Crypto_DRBG(len = 28) + 1` primitive."
497 ///
498 /// A production counter is seeded from `Rng::next_u32`, so the whole `u32` is what it can
499 /// be handed; the sweep is over the boundaries of the mask plus every top-byte pattern,
500 /// which is where a wrong mask or a missing `+ 1` shows.
501 #[test]
502 fn an_initial_counter_is_inside_the_twenty_eight_bit_range() {
503 const CEILING: u32 = 1 << 28;
504 let mut seen_top = false;
505 for high in 0..=u8::MAX {
506 for low in [0x00u32, 0x01, 0x7F, 0x80, 0xFE, 0xFF] {
507 let randomness = (u32::from(high) << 24) | (low << 16) | (low << 8) | low;
508 let start = MessageCounter::new(randomness).peek();
509 assert!(
510 (1..=CEILING).contains(&start),
511 "{randomness:#010x} started at {start:#010x}"
512 );
513 seen_top |= start == CEILING;
514 }
515 }
516 // `+ 1` makes 2²⁸ itself reachable; a mask alone would stop one short.
517 assert!(seen_top, "the top of the range is never reached");
518 // And zero is not in it, which is the whole point of the `+ 1`.
519 assert_eq!(MessageCounter::new(0).peek(), 1);
520 assert_eq!(MessageCounter::new(u32::MAX).peek(), CEILING);
521 }
522
523 /// The counter a session is given has to leave it room to run.
524 ///
525 /// `take` refuses on exhaustion rather than rolling over (§4.6.2), so the initial value
526 /// is also the size of the session's supply. Seeding from the full `u32` left one session
527 /// in four thousand with under a million counters, which is a session that stops working
528 /// early and says nothing about why.
529 #[test]
530 fn an_initial_counter_leaves_the_session_its_supply() {
531 const RESERVED: u32 = u32::MAX - (1 << 28);
532 for randomness in [0, 1, u32::MAX, u32::MAX - 1, 0xFFFF_0000, 0x8000_0000] {
533 let remaining = u32::MAX - MessageCounter::new(randomness).peek();
534 assert!(
535 remaining >= RESERVED,
536 "{randomness:#010x} left only {remaining} counters"
537 );
538 }
539 }
540
541 /// `at` is the escape hatch, and it really does bypass the narrowing — otherwise the tests
542 /// that stand at the end of the range would be standing somewhere else.
543 #[test]
544 fn at_takes_the_value_it_is_given() {
545 assert_eq!(MessageCounter::at(u32::MAX).peek(), u32::MAX);
546 assert_eq!(MessageCounter::at(0).peek(), 0);
547 }
548}