Repository: cloudflare/boringtun (language: rust)

Issue:
Missing check for message limits, issues with data message counter
The protocol defines the following message limits:
* Rekey-After-Messages 2^64 * 2^16 - 1
* Reject-After-Messages 2^64 − 2^4 − 1

Although unlikely in practice, the implementation must check that these message limits are not reached and avoid a counter wraparound. The implementation of ReceivingKeyCounterValidator in src/noise/session.rs must be updated to check this.

Right now a malicious implementation could produce the following messages sequence which is accepted by boringtun:

* counter=0 (sets next to 1 in `mark_did_receive`)
* counter=2^64 - 1 (sets next to 0 due to integer overflow)
* counter=0 (oops! counter reuse - replay accepted!)

Additionally, going from counter 0 to counter 2^64 will also result in a lot of unnecessary executions which facilitates a DoS:
```rust
        // Packets where dropped, or maybe reordered, skip them and mark unused
        let mut i = self.next; // 1
        while i < counter { // i = 1 .. 2^64 - 1
            self.clear_bit(i);
            i += 1;
        }
```
If the gap is too big, perhaps the whole bitmap should be cleared.

FWIW, the WireGuard kernel implementation uses a window of 2048 bits whereas this one uses 1024.

Another related issue is that `sending_key_counter` and `sending_key_counter` are an [AtomicUsize](https://doc.rust-lang.org/std/sync/atomic/struct.AtomicUsize.html) which may be 32-bit on 32-bit architectures whereas the counter in the protocol is 64-bit.


Discussion / hints:
> Although unlikely in practice

Impossible in practice.

> malicious implementation could produce

But it would only compromise the connection with the malicious implementation itself, not any other connection, I don't really see the problem here.

> If the gap is too big, perhaps the whole bitmap should be cleared.

I could have sworn that I implemented that, but apparently I didn't, good catch



Fix patch:
diff --git a/src/noise/session.rs b/src/noise/session.rs
index b1a096e4..8e37bbdf 100644
--- a/src/noise/session.rs
+++ b/src/noise/session.rs
@@ -81,6 +81,14 @@ impl ReceivingKeyCounterValidator {
         self.bitmap[word] &= !(1u64 << bit);
     }
 
+    // Clear the word that contains idx
+    #[inline(always)]
+    fn clear_word(&mut self, idx: u64) {
+        let bit_idx = idx % N_BITS;
+        let word = (bit_idx / WORD_SIZE) as usize;
+        self.bitmap[word] = 0;
+    }
+
     // Returns true if bit is set, false otherwise
     #[inline(always)]
     fn check_bit(&self, idx: u64) -> bool {
@@ -128,10 +136,28 @@ impl ReceivingKeyCounterValidator {
             return Ok(());
         }
         // Packets where dropped, or maybe reordered, skip them and mark unused
-        let mut i = self.next;
-        while i < counter {
-            self.clear_bit(i);
-            i += 1;
+        if counter - self.next >= N_BITS {
+            // Too far ahead, clear all the bits
+            for c in self.bitmap.iter_mut() {
+                *c = 0;
+            }
+        } else {
+            let mut i = self.next;
+            while i % WORD_SIZE != 0 && i < counter {
+                // Clear until i aligned to word size
+                self.clear_bit(i);
+                i += 1;
+            }
+            while i + WORD_SIZE < counter {
+                // Clear whole word at a time
+                self.clear_word(i);
+                i = (i + WORD_SIZE) & 0u64.wrapping_sub(WORD_SIZE);
+            }
+            while i < counter {
+                // Clear any remaining bits
+                self.clear_bit(i);
+                i += 1;
+            }
         }
         self.set_bit(counter);
         self.next = counter + 1;
@@ -285,3 +311,50 @@ impl Session {
         }
     }
 }
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    #[test]
+    fn test_replay_counter() {
+        let mut c: ReceivingKeyCounterValidator = Default::default();
+
+        assert!(c.mark_did_receive(0).is_ok());
+        assert!(c.mark_did_receive(0).is_err());
+        assert!(c.mark_did_receive(1).is_ok());
+        assert!(c.mark_did_receive(1).is_err());
+        assert!(c.mark_did_receive(63).is_ok());
+        assert!(c.mark_did_receive(63).is_err());
+        assert!(c.mark_did_receive(15).is_ok());
+        assert!(c.mark_did_receive(15).is_err());
+
+        for i in 64..N_BITS + 128 {
+            assert!(c.mark_did_receive(i).is_ok());
+            assert!(c.mark_did_receive(i).is_err());
+        }
+
+        assert!(c.mark_did_receive(N_BITS * 3).is_ok());
+        for i in 0..=N_BITS * 2 {
+            assert!(!c.will_accept(i));
+            assert!(c.mark_did_receive(i).is_err());
+        }
+        for i in N_BITS * 2 + 1..N_BITS * 3 {
+            assert!(c.will_accept(i));
+        }
+
+        for i in (N_BITS * 2 + 1..N_BITS * 3).rev() {
+            assert!(c.mark_did_receive(i).is_ok());
+            assert!(c.mark_did_receive(i).is_err());
+        }
+
+        assert!(c.mark_did_receive(N_BITS * 3 + 70).is_ok());
+        assert!(c.mark_did_receive(N_BITS * 3 + 71).is_ok());
+        assert!(c.mark_did_receive(N_BITS * 3 + 72).is_ok());
+        assert!(c.mark_did_receive(N_BITS * 3 + 72 + 125).is_ok());
+        assert!(c.mark_did_receive(N_BITS * 3 + 63).is_ok());
+
+        assert!(c.mark_did_receive(N_BITS * 3 + 70).is_err());
+        assert!(c.mark_did_receive(N_BITS * 3 + 71).is_err());
+        assert!(c.mark_did_receive(N_BITS * 3 + 72).is_err());
+    }
+}


Test patch: