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 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}