diff options
author | Mathias Hall-Andersen <mathias@hall-andersen.dk> | 2019-08-12 21:04:19 +0200 |
---|---|---|
committer | Mathias Hall-Andersen <mathias@hall-andersen.dk> | 2019-08-12 21:04:19 +0200 |
commit | 723a1b8e858346ef98559788540915bc0cc93eb0 (patch) | |
tree | 81d9ef0a0dd9042b23a21475845689bafb1d822d /src | |
parent | Work on sketching router interface (diff) | |
download | wireguard-rs-723a1b8e858346ef98559788540915bc0cc93eb0.tar.xz wireguard-rs-723a1b8e858346ef98559788540915bc0cc93eb0.zip |
Port replay filter and sketch router state
Diffstat (limited to 'src')
-rw-r--r-- | src/handshake/device.rs | 44 | ||||
-rw-r--r-- | src/handshake/ratelimiter.rs | 31 | ||||
-rw-r--r-- | src/main.rs | 3 | ||||
-rw-r--r-- | src/mod.rs | 3 | ||||
-rw-r--r-- | src/router/anti_replay.rs | 156 | ||||
-rw-r--r-- | src/router/buffer.rs | 48 | ||||
-rw-r--r-- | src/router/device.rs | 79 | ||||
-rw-r--r-- | src/router/mod.rs | 4 |
8 files changed, 282 insertions, 86 deletions
diff --git a/src/handshake/device.rs b/src/handshake/device.rs index 86a832a..1c7a30d 100644 --- a/src/handshake/device.rs +++ b/src/handshake/device.rs @@ -356,12 +356,14 @@ mod tests { use super::super::messages::*; use super::*; use hex; - use std::thread; use rand::rngs::OsRng; - use std::time::Duration; use std::net::SocketAddr; + use std::thread; + use std::time::Duration; - fn setup_devices<R: RngCore + CryptoRng>(rng : &mut R) -> (PublicKey, Device<usize>, PublicKey, Device<usize>) { + fn setup_devices<R: RngCore + CryptoRng>( + rng: &mut R, + ) -> (PublicKey, Device<usize>, PublicKey, Device<usize>) { // generate new keypairs let sk1 = StaticSecret::new(rng); @@ -390,7 +392,7 @@ mod tests { } /* Test longest possible handshake interaction (7 messages): - * + * * 1. I -> R (initation) * 2. I <- R (cookie reply) * 3. I -> R (initation) @@ -402,28 +404,28 @@ mod tests { #[test] fn handshake_under_load() { let mut rng = OsRng::new().unwrap(); - let (_pk1, dev1, pk2, dev2) = setup_devices(&mut rng); + let (_pk1, dev1, pk2, dev2) = setup_devices(&mut rng); - let src1 : SocketAddr = "172.16.0.1:8080".parse().unwrap(); - let src2 : SocketAddr = "172.16.0.2:7070".parse().unwrap(); + let src1: SocketAddr = "172.16.0.1:8080".parse().unwrap(); + let src2: SocketAddr = "172.16.0.2:7070".parse().unwrap(); // 1. device-1 : create first initation let msg_init = dev1.begin(&mut rng, &pk2).unwrap(); - + // 2. device-2 : responds with CookieReply let msg_cookie = match dev2.process(&mut rng, &msg_init, Some(&src1)).unwrap() { (None, Some(msg), None) => msg, - _ => panic!("unexpected response") + _ => panic!("unexpected response"), }; // device-1 : processes CookieReply (no response) match dev1.process(&mut rng, &msg_cookie, Some(&src2)).unwrap() { (None, None, None) => (), - _ => panic!("unexpected response") + _ => panic!("unexpected response"), } // avoid initation flood - thread::sleep(Duration::from_millis(20)); + thread::sleep(Duration::from_millis(20)); // 3. device-1 : create second initation let msg_init = dev1.begin(&mut rng, &pk2).unwrap(); @@ -433,24 +435,24 @@ mod tests { (Some(_), Some(msg), Some(kp)) => { assert_eq!(kp.confirmed, false); msg - }, - _ => panic!("unexpected response") + } + _ => panic!("unexpected response"), }; // 5. device-1 : responds with CookieReply let msg_cookie = match dev1.process(&mut rng, &msg_response, Some(&src2)).unwrap() { (None, Some(msg), None) => msg, - _ => panic!("unexpected response") + _ => panic!("unexpected response"), }; // device-2 : processes CookieReply (no response) match dev2.process(&mut rng, &msg_cookie, Some(&src1)).unwrap() { (None, None, None) => (), - _ => panic!("unexpected response") + _ => panic!("unexpected response"), } // avoid initation flood - thread::sleep(Duration::from_millis(20)); + thread::sleep(Duration::from_millis(20)); // 6. device-1 : create third initation let msg_init = dev1.begin(&mut rng, &pk2).unwrap(); @@ -460,8 +462,8 @@ mod tests { (Some(_), Some(msg), Some(kp)) => { assert_eq!(kp.confirmed, false); (msg, kp) - }, - _ => panic!("unexpected response") + } + _ => panic!("unexpected response"), }; // device-1 : process noise response @@ -469,8 +471,8 @@ mod tests { (Some(_), None, Some(kp)) => { assert_eq!(kp.confirmed, true); kp - }, - _ => panic!("unexpected response") + } + _ => panic!("unexpected response"), }; assert_eq!(kp1.send, kp2.recv); @@ -480,7 +482,7 @@ mod tests { #[test] fn handshake_no_load() { let mut rng = OsRng::new().unwrap(); - let (pk1, mut dev1, pk2, mut dev2) = setup_devices(&mut rng); + let (pk1, mut dev1, pk2, mut dev2) = setup_devices(&mut rng); // do a few handshakes (every handshake should succeed) diff --git a/src/handshake/ratelimiter.rs b/src/handshake/ratelimiter.rs index 02b82e7..6568b32 100644 --- a/src/handshake/ratelimiter.rs +++ b/src/handshake/ratelimiter.rs @@ -1,10 +1,10 @@ +use spin; use std::collections::HashMap; use std::net::IpAddr; use std::sync::atomic::{AtomicBool, Ordering}; -use std::sync::{Condvar, Mutex, Arc}; +use std::sync::{Arc, Condvar, Mutex}; use std::thread; use std::time::{Duration, Instant}; -use spin; use lazy_static::lazy_static; @@ -24,7 +24,7 @@ struct Entry { pub struct RateLimiter(Arc<RateLimiterInner>); -struct RateLimiterInner{ +struct RateLimiterInner { gc_running: AtomicBool, gc_dropped: (Mutex<bool>, Condvar), table: spin::RwLock<HashMap<IpAddr, spin::Mutex<Entry>>>, @@ -42,13 +42,11 @@ impl Drop for RateLimiter { impl RateLimiter { pub fn new() -> Self { - RateLimiter ( - Arc::new(RateLimiterInner { - gc_dropped: (Mutex::new(false), Condvar::new()), - gc_running: AtomicBool::from(false), - table: spin::RwLock::new(HashMap::new()), - }) - ) + RateLimiter(Arc::new(RateLimiterInner { + gc_dropped: (Mutex::new(false), Condvar::new()), + gc_running: AtomicBool::from(false), + table: spin::RwLock::new(HashMap::new()), + })) } pub fn allow(&self, addr: &IpAddr) -> bool { @@ -60,8 +58,8 @@ impl RateLimiter { let mut entry = entry.lock(); // add tokens earned since last time - entry.tokens = - MAX_TOKENS.min(entry.tokens + u64::from(entry.last_time.elapsed().subsec_nanos())); + entry.tokens = MAX_TOKENS + .min(entry.tokens + u64::from(entry.last_time.elapsed().subsec_nanos())); entry.last_time = Instant::now(); // subtract cost of packet @@ -72,7 +70,7 @@ impl RateLimiter { return false; } } - + // add new entry (write lock) self.0.table.write().insert( *addr, @@ -94,7 +92,9 @@ impl RateLimiter { // garbage collect { let mut tw = limiter.table.write(); - tw.retain(|_, ref mut entry| entry.lock().last_time.elapsed() <= *GC_INTERVAL); + tw.retain(|_, ref mut entry| { + entry.lock().last_time.elapsed() <= *GC_INTERVAL + }); if tw.len() == 0 { limiter.gc_running.store(false, Ordering::Relaxed); return; @@ -102,7 +102,7 @@ impl RateLimiter { } // wait until stopped or new GC (~1 every sec) - let res = cvar.wait_timeout(dropped,*GC_INTERVAL).unwrap(); + let res = cvar.wait_timeout(dropped, *GC_INTERVAL).unwrap(); dropped = res.0; } }); @@ -110,7 +110,6 @@ impl RateLimiter { allowed } - } #[cfg(test)] diff --git a/src/main.rs b/src/main.rs index 26974a7..e49a217 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1,4 +1,7 @@ +#![feature(test)] + mod handshake; +mod router; mod types; use sodiumoxide; diff --git a/src/mod.rs b/src/mod.rs deleted file mode 100644 index 1829e6e..0000000 --- a/src/mod.rs +++ /dev/null @@ -1,3 +0,0 @@ -mod noise; -mod types; -mod router;
\ No newline at end of file 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; |