added sequence window

6 files changed, 321 insertions, 8 deletions

diff --git a/src/Makefile b/src/Makefile
index 740373c..9ed3363 100644
--- a/src/Makefile
+++ b/src/Makefile
@@ -53,6 +53,7 @@ OBJS = log.o \
        udp.o \
        plain_packet.o \
        encrypted_packet.o \
+       seq_window.o \
        cipher.o \
        uanytun.o
 
@@ -87,6 +88,9 @@ plain_packet.o: plain_packet.c plain_packet.h
 encrypted_packet.o: encrypted_packet.c encrypted_packet.h
 	$(CC) $(CCFLAGS) $< -c
 
+seq_window.o: seq_window.c seq_window.h
+	$(CC) $(CCFLAGS) $< -c
+
 cipher.o: cipher.c cipher.h
 	$(CC) $(CCFLAGS) $< -c
 
diff --git a/src/datatypes.h b/src/datatypes.h
index 6d22d59..e88001f 100644
--- a/src/datatypes.h
+++ b/src/datatypes.h
@@ -51,6 +51,7 @@ typedef u_int32_t window_size_t;
 typedef u_int32_t seq_nr_t;
 #define SEQ_NR_T_NTOH(a) ntohl(a)
 #define SEQ_NR_T_HTON(a) htonl(a)
+#define SEQ_NR_MAX UINT32_MAX
 
 typedef u_int16_t sender_id_t;
 #define SENDER_ID_T_NTOH(a) ntohs(a)
diff --git a/src/seq_window.c b/src/seq_window.c
new file mode 100644
index 0000000..f5c0bf8
--- /dev/null
+++ b/src/seq_window.c
@@ -0,0 +1,223 @@
+/*
+ *  ľAnytun
+ *
+ *  ľAnytun is a tiny implementation of SATP. Unlike Anytun which is a full
+ *  featured implementation ľAnytun has no support for multiple connections
+ *  or synchronisation. It is a small single threaded implementation intended
+ *  to act as a client on small platforms.
+ *  The secure anycast tunneling protocol (satp) defines a protocol used
+ *  for communication between any combination of unicast and anycast
+ *  tunnel endpoints.  It has less protocol overhead than IPSec in Tunnel
+ *  mode and allows tunneling of every ETHER TYPE protocol (e.g.
+ *  ethernet, ip, arp ...). satp directly includes cryptography and
+ *  message authentication based on the methodes used by SRTP.  It is
+ *  intended to deliver a generic, scaleable and secure solution for
+ *  tunneling and relaying of packets of any protocol.
+ *  
+ *
+ *  Copyright (C) 2007-2008 Christian Pointner <equinox@anytun.org>
+ *
+ *  This file is part of ľAnytun.
+ *
+ *  ľAnytun is free software: you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License version 3 as
+ *  published by the Free Software Foundation.
+ *
+ *  ľAnytun is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with ľAnytun. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "datatypes.h"
+
+#include "seq_window.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+#include <stdio.h>
+
+void seq_win_init(seq_win_t** win, window_size_t size)
+{
+  if(!win)
+    return;
+
+  *win = malloc(sizeof(seq_win_t));
+  if(!*win)
+    return;
+
+  (*win)->size_ = size;
+  (*win)->first_ = NULL;
+}
+
+void seq_win_clear(seq_win_t** win)
+{
+  if(!win || !(*win))
+    return;
+
+  seq_win_element_t* ptr = (*win)->first_;
+  while(ptr) {
+    seq_win_element_t* to_free = ptr;
+    ptr = ptr->next_;
+    if(to_free->window_)
+      free(to_free->window_);
+
+    free(to_free);
+  }
+
+  free(*win);
+  *win = NULL;
+}
+
+seq_win_element_t* seq_win_new_element(sender_id_t sender_id, seq_nr_t max, window_size_t size)
+{
+  if(!size)
+    return NULL;
+
+  seq_win_element_t* e = malloc(sizeof(seq_win_element_t));
+  if(!e)
+    return NULL;
+
+  e->sender_id_ = sender_id;
+  e->max_ = max;
+  e->pos_ = 0;
+  e->window_ = malloc(sizeof(seq_nr_t)*size);
+  if(!e->window_) {
+    free(e);
+    return NULL;
+  }
+  memset(e->window_, 0, size);
+  e->window_[e->pos_] = 1;
+  e->next_ = NULL;
+
+  return e;
+}
+
+int seq_win_check_and_add(seq_win_t* win, sender_id_t sender_id, seq_nr_t seq_nr)
+{
+  if(!win)
+    return -1;
+
+  if(!win->size_)
+    return 0;
+
+  seq_win_element_t* ptr = win->first_;
+  while(ptr) {
+    if(ptr->sender_id_ == sender_id) {
+
+      int shifted = 0;
+      if(ptr->max_ < win->size_) {
+        ptr->max_ += SEQ_NR_MAX/2;
+        seq_nr += SEQ_NR_MAX/2;
+        shifted = 1;
+      }
+      else if(ptr->max_ > (SEQ_NR_MAX - win->size_)) {
+        ptr->max_ -= SEQ_NR_MAX/2;
+        seq_nr -= SEQ_NR_MAX/2;
+        shifted = 2;
+      }
+
+      seq_nr_t min = ptr->max_ - win->size_ + 1;
+      if(seq_nr < min || seq_nr == ptr->max_) {
+        if(shifted == 1)
+          ptr->max_ -= SEQ_NR_MAX/2;
+        else if(shifted == 2)
+          ptr->max_ += SEQ_NR_MAX/2;
+        return 1;
+      }
+
+      if(seq_nr > ptr->max_) {
+        seq_nr_t diff = seq_nr - ptr->max_;
+        if(diff >= win->size_)
+          diff = win->size_;
+
+        window_size_t new_pos = ptr->pos_ + diff;
+
+        if(new_pos >= win->size_) {
+          new_pos -= win->size_;
+
+          if(ptr->pos_ < win->size_ - 1)
+            memset(&(ptr->window_[ptr->pos_ + 1]), 0, win->size_ - ptr->pos_ - 1);
+
+          memset(ptr->window_, 0, new_pos);
+        }
+        else {
+          memset(&(ptr->window_[ptr->pos_ + 1]), 0, diff);
+        }
+        ptr->pos_ = new_pos;
+        ptr->window_[ptr->pos_] = 1;
+        ptr->max_ = seq_nr;
+
+        if(shifted == 1)
+          ptr->max_ -= SEQ_NR_MAX/2;
+        else if(shifted == 2)
+          ptr->max_ += SEQ_NR_MAX/2;
+        
+        return 0;
+      }
+      
+      seq_nr_t diff = ptr->max_ - seq_nr;
+      window_size_t pos = diff > ptr->pos_ ? ptr->pos_ + win->size_ : ptr->pos_; 
+      pos -= diff;
+
+      if(shifted == 1)
+        ptr->max_ -= SEQ_NR_MAX/2;
+      else if(shifted == 2)
+        ptr->max_ += SEQ_NR_MAX/2;
+
+      int ret = ptr->window_[pos];
+      ptr->window_[pos] = 1;
+      return ret;
+    }
+    ptr = ptr->next_;
+  }  
+  if(!win->first_) {
+    win->first_ = seq_win_new_element(sender_id, seq_nr, win->size_);
+    if(!win->first_)
+      return -2;
+  }
+  else {
+    ptr = win->first_;
+    while(ptr->next_)
+      ptr = ptr->next_;
+    ptr->next_ = seq_win_new_element(sender_id, seq_nr, win->size_);
+    if(!ptr->next_)
+      return -2;
+  }
+  
+  return 0;
+}
+
+void seq_win_print(seq_win_t* win)
+{
+  printf("Sequence Window:\n");
+
+  if(!win)
+    return;
+
+  seq_win_element_t* ptr = win->first_;
+  while(ptr) {
+    printf(" [%u]: (%u)-", ptr->sender_id_, ptr->max_, ptr->pos_);
+    window_size_t i = ptr->pos_;
+    while(1) {
+      if(ptr->window_[i])
+        printf("O");
+      else
+        printf(".");
+      
+      if(i)
+        i--;
+      else
+        i = win->size_ - 1;
+
+      if(i == ptr->pos_)
+        break;
+    }
+    printf("\n");
+    ptr = ptr->next_;
+  }
+}
diff --git a/src/seq_window.h b/src/seq_window.h
new file mode 100644
index 0000000..9832372
--- /dev/null
+++ b/src/seq_window.h
@@ -0,0 +1,60 @@
+/*
+ *  ľAnytun
+ *
+ *  ľAnytun is a tiny implementation of SATP. Unlike Anytun which is a full
+ *  featured implementation ľAnytun has no support for multiple connections
+ *  or synchronisation. It is a small single threaded implementation intended
+ *  to act as a client on small platforms.
+ *  The secure anycast tunneling protocol (satp) defines a protocol used
+ *  for communication between any combination of unicast and anycast
+ *  tunnel endpoints.  It has less protocol overhead than IPSec in Tunnel
+ *  mode and allows tunneling of every ETHER TYPE protocol (e.g.
+ *  ethernet, ip, arp ...). satp directly includes cryptography and
+ *  message authentication based on the methodes used by SRTP.  It is
+ *  intended to deliver a generic, scaleable and secure solution for
+ *  tunneling and relaying of packets of any protocol.
+ *  
+ *
+ *  Copyright (C) 2007-2008 Christian Pointner <equinox@anytun.org>
+ *
+ *  This file is part of ľAnytun.
+ *
+ *  ľAnytun is free software: you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License version 3 as
+ *  published by the Free Software Foundation.
+ *
+ *  ľAnytun is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with ľAnytun. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef _SEQ_WINDOW_H_
+#define _SEQ_WINDOW_H_
+
+struct seq_win_element_struct {
+  sender_id_t sender_id_;
+  seq_nr_t max_;
+  window_size_t pos_;
+  u_int8_t* window_;
+  struct seq_win_element_struct* next_;
+};
+typedef struct seq_win_element_struct seq_win_element_t;
+
+struct seq_win_struct {
+  window_size_t size_;
+  seq_win_element_t* first_;
+};
+typedef struct seq_win_struct seq_win_t;
+
+void seq_win_init(seq_win_t** win, window_size_t size);
+void seq_win_clear(seq_win_t** win);
+seq_win_element_t* seq_win_new_element(sender_id_t sender_id, seq_nr_t max, window_size_t size);
+int seq_win_check_and_add(seq_win_t* win, sender_id_t sender_id, seq_nr_t seq_nr);
+
+void seq_win_print(seq_win_t* win);
+
+#endif
diff --git a/src/uanytun.c b/src/uanytun.c
index 7c49934..df6a629 100644
--- a/src/uanytun.c
+++ b/src/uanytun.c
@@ -49,6 +49,7 @@
 #include "plain_packet.h"
 #include "encrypted_packet.h"
 
+#include "seq_window.h"
 #include "cipher.h"
 
 #include "daemon.h"
@@ -56,6 +57,7 @@
 
 int main_loop(tun_device_t* dev, udp_socket_t* sock, options_t* opt)
 {
+  int return_value = 0;
   log_printf(INFO, "entering main loop");
 
   plain_packet_t plain_packet;
@@ -71,10 +73,17 @@ int main_loop(tun_device_t* dev, udp_socket_t* sock, options_t* opt)
   cipher_init(&c, opt->cipher_);
   if(!c) {
     log_printf(ERR, "could not initialize cipher of type %s", opt->cipher_);
-    return -1;
+    return_value -1;
   }
 
-  while(1) {
+  seq_win_t* seq_win;
+  seq_win_init(&seq_win, opt->seq_window_size_);
+  if(!seq_win) {
+    printf("could not initialize sequence window");
+    return_value = -1;
+  }
+
+  while(!return_value) {
     plain_packet_set_payload_length(&plain_packet, -1);
     encrypted_packet_set_length(&encrypted_packet, -1);
 
@@ -86,15 +95,15 @@ int main_loop(tun_device_t* dev, udp_socket_t* sock, options_t* opt)
     int ret = select(nfds, &readfds, NULL, NULL, NULL);
     if(ret == -1 && errno != EINTR) {
       log_printf(ERR, "select returned with error: %m");
-      cipher_close(&c);      
-      return -1;
+      return_value = -1;
+      break;
     }
     if(!ret)
       continue;
 
     if(signal_exit) {
-      cipher_close(&c);
-      return 1;
+      return_value = 1;
+      break;
     }
 
     if(FD_ISSET(dev->fd_, &readfds)) {
@@ -137,8 +146,18 @@ int main_loop(tun_device_t* dev, udp_socket_t* sock, options_t* opt)
       if(encrypted_packet_get_mux(&encrypted_packet) != opt->mux_)
         continue;
       
-          // TODO: check seq nr for sender id
+      int result = seq_win_check_and_add(seq_win, encrypted_packet_get_sender_id(&encrypted_packet), encrypted_packet_get_seq_nr(&encrypted_packet));
+      if(result > 0) {
+        log_printf(WARNING, "detected replay attack, discarding packet");
+        continue;
+      }
+      else if(result < 0) {
+        log_printf(ERR, "memory error at sequence window");
+        return_value -1;
+        break;
+      }
       
+
       if(memcmp(&remote, &(sock->remote_end_), sizeof(remote))) {
         memcpy(&(sock->remote_end_), &remote, sizeof(remote));
         char* addrstring = udp_endpoint_to_string(remote);
@@ -155,8 +174,9 @@ int main_loop(tun_device_t* dev, udp_socket_t* sock, options_t* opt)
   }
 
   cipher_close(&c);
+  seq_win_clear(&seq_win);
 
-  return 0;
+  return return_value;
 }
 
 void print_hex_dump(const u_int8_t* buf, u_int32_t len)
@@ -200,6 +220,7 @@ int main(int argc, char* argv[])
   tun_init(&dev, opt->dev_name_, opt->dev_type_, opt->ifconfig_param_local_, opt->ifconfig_param_remote_netmask_);
   if(!dev) {
     log_printf(ERR, "error on tun_init, exitting");
+    options_clear(&opt);
     exit(-1);
   }
   log_printf(NOTICE, "dev of type '%s' opened, actual name is '%s'", tun_get_type_string(dev), dev->actual_name_);
@@ -214,6 +235,8 @@ int main(int argc, char* argv[])
   udp_init(&sock, opt->local_addr_, opt->local_port_);
   if(!sock) {
     log_printf(ERR, "error on udp_init, exitting");
+    options_clear(&opt);
+    tun_close(&dev);
     exit(-1);
   }
   char* local_string = udp_get_local_end_string(sock);
diff --git a/src/udp.c b/src/udp.c
index 2ffeab6..ca83561 100644
--- a/src/udp.c
+++ b/src/udp.c
@@ -81,6 +81,7 @@ void udp_init(udp_socket_t** sock, const char* local_addr, const char* port)
   (*sock)->fd_ = socket(res->ai_family, SOCK_DGRAM, 0);
   if((*sock)->fd_ < 0) {
     log_printf(ERR, "Error on opening udp socket: %m");
+    freeaddrinfo(res);
     free(*sock);
     *sock = NULL;
     return;
@@ -89,6 +90,7 @@ void udp_init(udp_socket_t** sock, const char* local_addr, const char* port)
   errcode = bind((*sock)->fd_, res->ai_addr, res->ai_addrlen);
   if(errcode) {
     log_printf(ERR, "Error on binding udp socket: %m");
+    freeaddrinfo(res);
     free(*sock);
     *sock = NULL;
     return;