Repository: cloudflare/boringtun (language: rust)

Issue:
Peer indices should be unpredictable and unique per session
Peer indices (sender/receiver IDs) seem to start with zero and are incremented by one:
```rust
impl Device {
    fn next_index(&mut self) -> u32 {
        let next_index = self.next_index;
        self.next_index += 1;
        assert!(next_index < (1 << 24), "Too many peers created");
        next_index
    }
// ...
    fn update_peer(...) {
// ...
        let next_index = self.next_index();
// ...
        let mut tunn = Tunn::new(
// ...
            next_index,
        )
        .unwrap();
// ...
        let peer = Peer::new(tunn, next_index, endpoint, &allowed_ips, preshared_key);
// ...
        self.peers_by_idx.insert(next_index, Arc::clone(&peer));
```

Which are used right here:
```rust
    fn register_udp_handler(&self, udp: Arc<UDPSocket>) -> Result<(), Error> {
                // ...
                while let Ok((addr, packet)) = udp.recvfrom(&mut t.src_buf[..]) {
                    // ...
                    let peer = match (packet[0], packet.len()) {
                        // ...
                        HANDSHAKE_RESPONSE => {
                            let peer_idx = u32::from_le_bytes(make_array(&packet[8..])) >> 8;
                            peers_by_idx.get(&peer_idx)
                        }
                        COOKIE_REPLY => {
                            let peer_idx = u32::from_le_bytes(make_array(&packet[4..])) >> 8;
                            peers_by_idx.get(&peer_idx)
                        }
                        (DATA, DATA_OVERHEAD_SZ...std::usize::MAX) => {
                            // A data packet, with at least a header
                            let peer_idx = u32::from_le_bytes(make_array(&packet[4..])) >> 8;
                            peers_by_idx.get(&peer_idx)
                        }
```

Problems:
 * The receiver/sender ID should be random and unpredictable. Otherwise it could give an attacker an advantage in pulling off a denial of service attack.
 * A monotonically increasing counter from 0 could leak activity and reveal whether a peer has actually connected or not. This kind of side-channel information could potentially be used in another attack.
 * Two sessions (after key rotation) should not have the same sender/receiver ID. That would make them linkable.


Discussion / hints:
I don't think there is a requirement for that in the wireguard specification. Unlinkability is not a property of wireguard 
I can't find "unlinkability" in the WG whitepaper either. Based on the message interactions and IP/ports the protocol is already linkable, but this decision could make it worse by having another way in the protocol to link sessions.

My third "problem" was based on a misinterpretation, I overlooked the `>> 8`. So the top 24 bit is used for the peer ID, the last 8 bits are reserved for the "cyclic session index" (incremented via inc_index in handshake.rs). So actually the session IDs are kind of unique.

Being able to identify a peer based on the sender ID is undesirable though. The WG protocol has a weak form of identity hiding, including a peer identifier violates this property even more.
I am not sure it qualifies as a bug thought 

Fix patch:
diff --git a/boringtun/src/device/mod.rs b/boringtun/src/device/mod.rs
index 6e2131ca..8b00738f 100644
--- a/boringtun/src/device/mod.rs
+++ b/boringtun/src/device/mod.rs
@@ -46,6 +46,7 @@ use allowed_ips::AllowedIps;
 use parking_lot::Mutex;
 use peer::{AllowedIP, Peer};
 use poll::{EventPoll, EventRef, WaitResult};
+use rand_core::{OsRng, RngCore};
 use tun::{errno, errno_str, TunSocket};
 use udp::UDPSocket;
 
@@ -132,7 +133,7 @@ pub struct Device {
     peers: HashMap<x25519_dalek::PublicKey, Arc<Mutex<Peer>>>,
     peers_by_ip: AllowedIps<Arc<Mutex<Peer>>>,
     peers_by_idx: HashMap<u32, Arc<Mutex<Peer>>>,
-    next_index: u32,
+    next_index: IndexLfsr,
 
     config: DeviceConfig,
 
@@ -267,10 +268,7 @@ impl Drop for DeviceHandle {
 
 impl Device {
     fn next_index(&mut self) -> u32 {
-        let next_index = self.next_index;
-        self.next_index += 1;
-        assert!(next_index < (1 << 24), "Too many peers created");
-        next_index
+        self.next_index.next()
     }
 
     fn remove_peer(&mut self, pub_key: &x25519_dalek::PublicKey) {
@@ -824,3 +822,52 @@ impl Device {
         Ok(())
     }
 }
+
+/// A basic linear-feedback shift register implemented as xorshift, used to
+/// distribute peer indexes across the 24-bit address space reserved for peer
+/// identification.
+/// The purpose is to obscure the total number of peers using the system and to
+/// ensure it requires a non-trivial amount of processing power and/or samples
+/// to guess other peers' indices. Anything more ambitious than this is wasted
+/// with only 24 bits of space.
+struct IndexLfsr {
+    initial: u32,
+    lfsr: u32,
+    mask: u32,
+}
+
+impl IndexLfsr {
+    /// Generate a random 24-bit nonzero integer
+    fn random_index() -> u32 {
+        const LFSR_MAX: u32 = 0xffffff; // 24-bit seed
+        loop {
+            let i = OsRng.next_u32() & LFSR_MAX;
+            if i > 0 {
+                // LFSR seed must be non-zero
+                return i;
+            }
+        }
+    }
+
+    /// Generate the next value in the pseudorandom sequence
+    fn next(&mut self) -> u32 {
+        // 24-bit polynomial for randomness. This is arbitrarily chosen to
+        // inject bitflips into the value.
+        const LFSR_POLY: u32 = 0xd80000; // 24-bit polynomial
+        let value = self.lfsr - 1; // lfsr will never have value of 0
+        self.lfsr = (self.lfsr >> 1) ^ ((0u32.wrapping_sub(self.lfsr & 1u32)) & LFSR_POLY);
+        assert!(self.lfsr != self.initial, "Too many peers created");
+        value ^ self.mask
+    }
+}
+
+impl Default for IndexLfsr {
+    fn default() -> Self {
+        let seed = Self::random_index();
+        IndexLfsr {
+            initial: seed,
+            lfsr: seed,
+            mask: Self::random_index(),
+        }
+    }
+}


Test patch: