Skip to main content

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}