Port replay filter and sketch router state

4 files changed, 241 insertions, 46 deletions

diff --git a/src/router/anti_replay.rs b/src/router/anti_replay.rs
new file mode 100644
index 0000000..5d898ac
--- /dev/null
+++ b/src/router/anti_replay.rs
@@ -0,0 +1,156 @@
+use std::mem;
+
+// Implementation of RFC 6479.
+// https://tools.ietf.org/html/rfc6479
+
+#[cfg(target_pointer_width = "64")]
+type Word = u64;
+
+#[cfg(target_pointer_width = "64")]
+const REDUNDANT_BIT_SHIFTS: usize = 6;
+
+#[cfg(target_pointer_width = "32")]
+type Word = u32;
+
+#[cfg(target_pointer_width = "32")]
+const REDUNDANT_BIT_SHIFTS: usize = 5;
+
+const SIZE_OF_WORD: usize = mem::size_of::<Word>() * 8;
+
+const BITMAP_BITLEN: usize = 2048;
+const BITMAP_LEN: usize = (BITMAP_BITLEN / SIZE_OF_WORD);
+const BITMAP_INDEX_MASK: u64 = BITMAP_LEN as u64 - 1;
+const BITMAP_LOC_MASK: u64 = (SIZE_OF_WORD - 1) as u64;
+const WINDOW_SIZE: u64 = (BITMAP_BITLEN - SIZE_OF_WORD) as u64;
+
+pub struct AntiReplay {
+    bitmap: [Word; BITMAP_LEN],
+    last: u64,
+}
+
+impl Default for AntiReplay {
+    fn default() -> Self {
+        AntiReplay::new()
+    }
+}
+
+impl AntiReplay {
+    pub fn new() -> Self {
+        debug_assert_eq!(1 << REDUNDANT_BIT_SHIFTS, SIZE_OF_WORD);
+        debug_assert_eq!(BITMAP_BITLEN % SIZE_OF_WORD, 0);
+        AntiReplay {
+            last: 0,
+            bitmap: [0; BITMAP_LEN],
+        }
+    }
+
+    // Returns true if check is passed, i.e., not a replay or too old.
+    //
+    // Unlike RFC 6479, zero is allowed.
+    fn check(&self, seq: u64) -> bool {
+        // Larger is always good.
+        if seq > self.last {
+            return true;
+        }
+
+        if self.last - seq > WINDOW_SIZE {
+            return false;
+        }
+
+        let bit_location = seq & BITMAP_LOC_MASK;
+        let index = (seq >> REDUNDANT_BIT_SHIFTS) & BITMAP_INDEX_MASK;
+
+        self.bitmap[index as usize] & (1 << bit_location) == 0
+    }
+
+    // Should only be called if check returns true.
+    fn update_store(&mut self, seq: u64) {
+        debug_assert!(self.check(seq));
+
+        let index = seq >> REDUNDANT_BIT_SHIFTS;
+
+        if seq > self.last {
+            let index_cur = self.last >> REDUNDANT_BIT_SHIFTS;
+            let diff = index - index_cur;
+
+            if diff >= BITMAP_LEN as u64 {
+                self.bitmap = [0; BITMAP_LEN];
+            } else {
+                for i in 0..diff {
+                    let real_index = (index_cur + i + 1) & BITMAP_INDEX_MASK;
+                    self.bitmap[real_index as usize] = 0;
+                }
+            }
+
+            self.last = seq;
+        }
+
+        let index = index & BITMAP_INDEX_MASK;
+        let bit_location = seq & BITMAP_LOC_MASK;
+        self.bitmap[index as usize] |= 1 << bit_location;
+    }
+
+    /// Checks and marks a sequence number in the replay filter
+    ///
+    /// # Arguments
+    ///
+    /// - seq: Sequence number check for replay and add to filter
+    ///
+    /// # Returns
+    ///
+    /// Ok(()) if sequence number is valid (not marked and not behind the moving window).
+    /// Err if the sequence number is invalid (already marked or "too old").
+    pub fn update(&mut self, seq: u64) -> Result<(), ()> {
+        if self.check(seq) {
+            self.update_store(seq);
+            Ok(())
+        } else {
+            Err(())
+        }
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn anti_replay() {
+        let mut ar = AntiReplay::new();
+
+        for i in 0..20000 {
+            ar.update(i).unwrap();
+        }
+
+        for i in (0..20000).rev() {
+            assert!(!ar.check(i));
+        }
+
+        ar.update(65536).unwrap();
+        for i in (65536 - WINDOW_SIZE)..65535 {
+            ar.update(i).unwrap();
+        }
+        for i in (65536 - 10 * WINDOW_SIZE)..65535 {
+            assert!(!ar.check(i));
+        }
+
+        ar.update(66000).unwrap();
+        for i in 65537..66000 {
+            ar.update(i).unwrap();
+        }
+        for i in 65537..66000 {
+            assert!(ar.update(i).is_err());
+        }
+
+        // Test max u64.
+        let next = u64::max_value();
+        ar.update(next).unwrap();
+        assert!(!ar.check(next));
+        for i in (next - WINDOW_SIZE)..next {
+            ar.update(i).unwrap();
+        }
+        for i in (next - 20 * WINDOW_SIZE)..next {
+            assert!(!ar.check(i));
+        }
+    }
+}
diff --git a/src/router/buffer.rs b/src/router/buffer.rs
index 3f348ea..96b16ab 100644
--- a/src/router/buffer.rs
+++ b/src/router/buffer.rs
@@ -4,20 +4,23 @@
  * 2. Inserting into the buffer always succeeds, but might overwrite the oldest item
  */
 
-const BUFFER_SIZE : usize = 1024;
+const BUFFER_SIZE: usize = 1024;
 
 pub struct DiscardingRingBuffer<T> {
-    buf  : [ Option<T> ; BUFFER_SIZE],
-    idx  : usize,
-    next : usize
+    buf: [Option<T>; BUFFER_SIZE],
+    idx: usize,
+    next: usize,
 }
 
-impl <T>DiscardingRingBuffer<T> where T: Copy {
+impl<T> DiscardingRingBuffer<T>
+where
+    T: Copy,
+{
     pub fn new() -> Self {
-        DiscardingRingBuffer{
-            buf  : [None; BUFFER_SIZE],
-            idx  : 0,
-            next : 0
+        DiscardingRingBuffer {
+            buf: [None; BUFFER_SIZE],
+            idx: 0,
+            next: 0,
         }
     }
 
@@ -29,7 +32,7 @@ impl <T>DiscardingRingBuffer<T> where T: Copy {
         }
     }
 
-    pub fn push(&mut self, val : T) {
+    pub fn push(&mut self, val: T) {
         // assign next slot (free / oldest)
         self.buf[self.idx] = Some(val);
         self.idx += 1;
@@ -57,20 +60,25 @@ impl <T>DiscardingRingBuffer<T> where T: Copy {
     pub fn has_element(&self) -> bool {
         match self.buf[self.next] {
             None => true,
-            _ => false
+            _ => false,
         }
     }
 }
 
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use proptest::prelude::*;
 
-proptest! {
-        #[test]
-        fn test_order(elems: Vec<usize>) {
-            let mut buf = DiscardingRingBuffer<usize>::new();
+    proptest! {
+            #[test]
+            fn test_order(elems: Vec<usize>) {
+                let mut buf = DiscardingRingBuffer::new();
 
-            for e in &elems {
-                buf.push(e);
-            }
+                for e in &elems {
+                    buf.push(e);
+                }
 
-        }
-}
\ No newline at end of file
+            }
+    }
+}
diff --git a/src/router/device.rs b/src/router/device.rs
index 67702cd..1296be6 100644
--- a/src/router/device.rs
+++ b/src/router/device.rs
@@ -1,39 +1,69 @@
-use std::net::SocketAddr;
+use arraydeque::{ArrayDeque, Wrapping};
+use treebitmap::IpLookupTable;
+
+use std::net::{Ipv4Addr, Ipv6Addr, SocketAddr};
+use std::sync::atomic::{AtomicPtr, AtomicU64};
+use std::sync::{Arc, Mutex};
+use std::time::Instant;
+
 use super::super::types::KeyPair;
+use super::anti_replay::AntiReplay;
+
+const MAX_STAGED_PACKETS: usize = 128;
 
 pub struct Device {
+    ipv4: IpLookupTable<Ipv4Addr, Arc<Peer>>,
+    ipv6: IpLookupTable<Ipv6Addr, Arc<Peer>>,
+}
+
+struct KeyState(KeyPair, AntiReplay);
 
+struct EncryptState {
+    key: [u8; 32],    // encryption key
+    id: u64,          // sender id
+    nonce: AtomicU64, // next available nonce
+    death: Instant,   // can must the key no longer be used:
+                      // (birth + reject-after-time - keepalive-timeout - rekey-timeout)
 }
 
-pub struct Peer {
+struct KeyWheel {
+    next: AtomicPtr<Arc<Option<KeyState>>>, // next key state (unconfirmed)
+    current: AtomicPtr<Arc<Option<KeyState>>>, // current key state (used for encryption)
+    previous: AtomicPtr<Arc<Option<KeyState>>>, // old key state (used for decryption)
+}
 
+pub struct Peer {
+    staged_packets: Mutex<ArrayDeque<[Vec<u8>; MAX_STAGED_PACKETS], Wrapping>>, // packets awaiting handshake
+    rx_bytes: AtomicU64,                                                        // received bytes
+    tx_bytes: AtomicU64,                                                        // transmitted bytes
+    keys: KeyWheel,                                                             // key-wheel
+    encryption: AtomicPtr<Arc<EncryptState>>, // current encryption key (starts expired)
 }
 
-pub struct PeerRef {}
+pub struct PeerRef();
 
 impl Device {
-
     pub fn new() -> Device {
         unimplemented!();
     }
 
     /// Adds a new peer to the device
-    /// 
+    ///
     /// # Returns
-    /// 
+    ///
     /// An opaque value representing the peer.
     pub fn add(&self) -> PeerRef {
         unimplemented!();
     }
 
     /// Cryptkey routes and sends a plaintext message (IP packet)
-    /// 
+    ///
     /// # Arguments
-    /// 
+    ///
     /// - pt_msg: IP packet to cryptkey route
-    /// 
+    ///
     /// # Returns
-    /// 
+    ///
     /// A peer reference for the peer if no key-pair is currently valid for the destination.
     /// This indicates that a handshake should be initated (see the handshake module).
     /// If this occurs the packet is copied to an internal buffer
@@ -45,31 +75,30 @@ impl Device {
     /// Sends a message directly to the peer.
     /// The router device takes care of discovering/managing the endpoint.
     /// This is used for handshake initiation/response messages
-    /// 
+    ///
     /// # Arguments
-    /// 
+    ///
     /// - peer: Reference to the destination peer
     /// - msg: Message to transmit
     pub fn send_raw(&self, peer: PeerRef, msg: &mut [u8]) {
         unimplemented!();
     }
-    
 
     /// Flush the queue of buffered messages awaiting transmission
-    /// 
+    ///
     /// # Arguments
-    /// 
+    ///
     /// - peer: Reference for the peer to flush
     pub fn flush_queue(&self, peer: PeerRef) {
         unimplemented!();
     }
-    
+
     /// Attempt to route, encrypt and send all elements buffered in the queue
-    /// 
+    ///
     /// # Arguments
-    /// 
+    ///
     /// # Returns
-    /// 
+    ///
     /// A boolean indicating whether packages where sent.
     /// Note: This is used for implicit confirmation of handshakes.
     pub fn send_run_queue(&self, peer: PeerRef) -> bool {
@@ -77,22 +106,22 @@ impl Device {
     }
 
     /// Receive an encrypted transport message
-    /// 
+    ///
     /// # Arguments
-    /// 
+    ///
     /// - ct_msg: Encrypted transport message
     pub fn recv(&self, ct_msg: &mut [u8]) {
         unimplemented!();
     }
 
     /// Returns the current endpoint known for the peer
-    /// 
+    ///
     /// # Arguments
-    /// 
+    ///
     /// - peer: The peer to retrieve the endpoint for
     pub fn get_endpoint(&self, peer: PeerRef) -> SocketAddr {
         unimplemented!();
-    } 
+    }
 
     pub fn set_endpoint(&self, peer: PeerRef, endpoint: SocketAddr) {
         unimplemented!();
@@ -101,4 +130,4 @@ impl Device {
     pub fn new_keypair(&self, peer: PeerRef, keypair: KeyPair) {
         unimplemented!();
     }
-}
\ No newline at end of file
+}
diff --git a/src/router/mod.rs b/src/router/mod.rs
index 4d29220..646b03b 100644
--- a/src/router/mod.rs
+++ b/src/router/mod.rs
@@ -1,2 +1,4 @@
+mod anti_replay;
 mod buffer;
-pub mod device;
\ No newline at end of file
+
+pub mod device;