/*
  *  OpenVPN -- An application to securely tunnel IP networks
  *             over a single TCP/UDP port, with support for SSL/TLS-based
  *             session authentication and key exchange,
  *             packet encryption, packet authentication, and
  *             packet compression.
  *

  *  Copyright (C) 2002-2018 OpenVPN Inc <sales@openvpn.net>

  *
  *  This program is free software; you can redistribute it and/or modify
  *  it under the terms of the GNU General Public License version 2
  *  as published by the Free Software Foundation.
  *
  *  This program 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 this program; if not, write to the Free Software Foundation, Inc.,
  *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

  */
 
 /*
  * These routines are designed to catch replay attacks,
  * where a man-in-the-middle captures packets and then
  * attempts to replay them back later.
  *
  * We use the "sliding-window" algorithm, similar
  * to IPSec.
  */
 

 #ifdef HAVE_CONFIG_H
 #include "config.h"
 #elif defined(_MSC_VER)
 #include "config-msvc.h"
 #endif
 

 #include "syshead.h"

 
 #include "packet_id.h"
 #include "misc.h"
 #include "integer.h"
 
 #include "memdbg.h"
 

 /* #define PID_SIMULATE_BACKTRACK */
 

 /*
  * Special time_t value that indicates that
  * sequence number has expired.
  */
 #define SEQ_UNSEEN  ((time_t)0)
 #define SEQ_EXPIRED ((time_t)1)
 

 static void packet_id_debug_print(int msglevel,
                                   const struct packet_id_rec *p,
                                   const struct packet_id_net *pin,
                                   const char *message,
                                   int value);

 
 static inline void

 packet_id_debug(int msglevel,
                 const struct packet_id_rec *p,
                 const struct packet_id_net *pin,
                 const char *message,
                 int value)

 {
 #ifdef ENABLE_DEBUG

     if (unlikely(check_debug_level(msglevel)))
     {
         packet_id_debug_print(msglevel, p, pin, message, value);
     }

 #endif
 }
 

 void

 packet_id_init(struct packet_id *p, int seq_backtrack, int time_backtrack, const char *name, int unit)

 {

     dmsg(D_PID_DEBUG, "PID packet_id_init seq_backtrack=%d time_backtrack=%d",
          seq_backtrack,
          time_backtrack);

     ASSERT(p);
     CLEAR(*p);

     p->rec.name = name;
     p->rec.unit = unit;
     if (seq_backtrack)

     {

         ASSERT(MIN_SEQ_BACKTRACK <= seq_backtrack && seq_backtrack <= MAX_SEQ_BACKTRACK);
         ASSERT(MIN_TIME_BACKTRACK <= time_backtrack && time_backtrack <= MAX_TIME_BACKTRACK);
         CIRC_LIST_ALLOC(p->rec.seq_list, struct seq_list, seq_backtrack);
         p->rec.seq_backtrack = seq_backtrack;
         p->rec.time_backtrack = time_backtrack;

     }

     p->rec.initialized = true;

 }
 
 void

 packet_id_free(struct packet_id *p)

 {

     if (p)

     {

         dmsg(D_PID_DEBUG, "PID packet_id_free");
         if (p->rec.seq_list)
         {
             free(p->rec.seq_list);
         }
         CLEAR(*p);

     }
 }
 
 void

 packet_id_add(struct packet_id_rec *p, const struct packet_id_net *pin)

 {

     const time_t local_now = now;
     if (p->seq_list)

     {

         packet_id_type diff;
 
         /*
          * If time value increases, start a new
          * sequence number sequence.
          */
         if (!CIRC_LIST_SIZE(p->seq_list)
             || pin->time > p->time
             || (pin->id >= (packet_id_type)p->seq_backtrack
                 && pin->id - (packet_id_type)p->seq_backtrack > p->id))
         {
             p->time = pin->time;
             p->id = 0;
             if (pin->id > (packet_id_type)p->seq_backtrack)
             {
                 p->id = pin->id - (packet_id_type)p->seq_backtrack;
             }
             CIRC_LIST_RESET(p->seq_list);
         }
 
         while (p->id < pin->id

 #ifdef PID_SIMULATE_BACKTRACK

                || (get_random() % 64) < 31

 #endif

                )
         {
             CIRC_LIST_PUSH(p->seq_list, SEQ_UNSEEN);
             ++p->id;
         }
 
         diff = p->id - pin->id;
         if (diff < (packet_id_type) CIRC_LIST_SIZE(p->seq_list)
             && local_now > SEQ_EXPIRED)
         {
             CIRC_LIST_ITEM(p->seq_list, diff) = local_now;
         }

     }

     else

     {

         p->time = pin->time;
         p->id = pin->id;

     }
 }
 
 /*
  * Expire sequence numbers which can no longer
  * be accepted because they would violate
  * time_backtrack.
  */
 void

 packet_id_reap(struct packet_id_rec *p)

 {

     const time_t local_now = now;
     if (p->time_backtrack)

     {

         int i;
         bool expire = false;
         for (i = 0; i < CIRC_LIST_SIZE(p->seq_list); ++i)
         {
             const time_t t = CIRC_LIST_ITEM(p->seq_list, i);
             if (t == SEQ_EXPIRED)
             {
                 break;
             }
             if (!expire && t && t + p->time_backtrack < local_now)
             {
                 expire = true;
             }
             if (expire)
             {
                 CIRC_LIST_ITEM(p->seq_list, i) = SEQ_EXPIRED;
             }
         }

     }

     p->last_reap = local_now;

 }
 
 /*
  * Return true if packet id is ok, or false if
  * it is a replay.
  */
 bool

 packet_id_test(struct packet_id_rec *p,
                const struct packet_id_net *pin)

 {

     packet_id_type diff;

     packet_id_debug(D_PID_DEBUG, p, pin, "PID_TEST", 0);

     ASSERT(p->initialized);
 
     if (!pin->id)
     {
         return false;
     }

     if (p->seq_backtrack)

     {

         /*
          * In backtrack mode, we allow packet reordering subject
          * to the seq_backtrack and time_backtrack constraints.
          *
          * This mode is used with UDP.
          */
         if (pin->time == p->time)
         {
             /* is packet-id greater than any one we've seen yet? */
             if (pin->id > p->id)
             {
                 return true;
             }
 
             /* check packet-id sliding window for original/replay status */
             diff = p->id - pin->id;
 
             /* keep track of maximum backtrack seen for debugging purposes */
             if ((int)diff > p->max_backtrack_stat)
             {
                 p->max_backtrack_stat = (int)diff;
                 packet_id_debug(D_PID_DEBUG_LOW, p, pin, "PID_ERR replay-window backtrack occurred", p->max_backtrack_stat);
             }
 
             if (diff >= (packet_id_type) CIRC_LIST_SIZE(p->seq_list))
             {
                 packet_id_debug(D_PID_DEBUG_LOW, p, pin, "PID_ERR large diff", diff);
                 return false;
             }
 
             {
                 const time_t v = CIRC_LIST_ITEM(p->seq_list, diff);
                 if (v == 0)
                 {
                     return true;
                 }
                 else
                 {
                     /* raised from D_PID_DEBUG_LOW to reduce verbosity */
                     packet_id_debug(D_PID_DEBUG_MEDIUM, p, pin, "PID_ERR replay", diff);
                     return false;
                 }
             }
         }
         else if (pin->time < p->time) /* if time goes back, reject */
         {
             packet_id_debug(D_PID_DEBUG_LOW, p, pin, "PID_ERR time backtrack", 0);
             return false;
         }
         else                        /* time moved forward */
         {
             return true;
         }

     }

     else

     {

         /*
          * In non-backtrack mode, all sequence number series must
          * begin at some number n > 0 and must increment linearly without gaps.
          *
          * This mode is used with TCP.
          */
         if (pin->time == p->time)
         {
             return !p->id || pin->id == p->id + 1;
         }
         else if (pin->time < p->time) /* if time goes back, reject */
         {
             return false;
         }
         else                        /* time moved forward */
         {
             return pin->id == 1;
         }

     }
 }
 
 /*
  * Read/write a packet ID to/from the buffer.  Short form is sequence number
  * only.  Long form is sequence number and timestamp.
  */
 
 bool

 packet_id_read(struct packet_id_net *pin, struct buffer *buf, bool long_form)

 {

     packet_id_type net_id;
     net_time_t net_time;

     pin->id = 0;
     pin->time = 0;

     if (!buf_read(buf, &net_id, sizeof(net_id)))

     {

         return false;

     }

     pin->id = ntohpid(net_id);
     if (long_form)
     {
         if (!buf_read(buf, &net_time, sizeof(net_time)))
         {
             return false;
         }
         pin->time = ntohtime(net_time);
     }
     return true;

 }
 

 static bool

 packet_id_send_update(struct packet_id_send *p, bool long_form)
 {
     if (!p->time)
     {
         p->time = now;
     }

     if (p->id == PACKET_ID_MAX)

     {

         /* Packet ID only allowed to roll over if using long form and time has
          * moved forward since last roll over.
          */
         if (!long_form || now <= p->time)
         {
             return false;
         }

         p->time = now;

         p->id = 0;

     }

     p->id++;
     return true;

 }
 

 bool

 packet_id_write(struct packet_id_send *p, struct buffer *buf, bool long_form,
         bool prepend)

 {

     if (!packet_id_send_update(p, long_form))
     {
         return false;
     }

     const packet_id_type net_id = htonpid(p->id);
     const net_time_t net_time = htontime(p->time);

     if (prepend)

     {

         if (long_form)
         {
             if (!buf_write_prepend(buf, &net_time, sizeof(net_time)))
             {
                 return false;
             }
         }
         if (!buf_write_prepend(buf, &net_id, sizeof(net_id)))
         {
             return false;
         }

     }

     else

     {

         if (!buf_write(buf, &net_id, sizeof(net_id)))
         {
             return false;
         }
         if (long_form)
         {
             if (!buf_write(buf, &net_time, sizeof(net_time)))
             {
                 return false;
             }
         }

     }

     return true;

 }
 
 const char *

 packet_id_net_print(const struct packet_id_net *pin, bool print_timestamp, struct gc_arena *gc)

 {

     struct buffer out = alloc_buf_gc(256, gc);

     buf_printf(&out, "[ #" packet_id_format, (packet_id_print_type)pin->id);
     if (print_timestamp && pin->time)
     {
         buf_printf(&out, " / time = (" packet_id_format ") %s",
                    (packet_id_print_type)pin->time,
                    time_string(pin->time, 0, false, gc));
     }

     buf_printf(&out, " ]");
     return BSTR(&out);

 }
 
 /* initialize the packet_id_persist structure in a disabled state */
 void

 packet_id_persist_init(struct packet_id_persist *p)

 {

     p->filename = NULL;
     p->fd = -1;
     p->time = p->time_last_written = 0;
     p->id = p->id_last_written = 0;

 }
 
 /* close the file descriptor if it is open, and switch to disabled state */
 void

 packet_id_persist_close(struct packet_id_persist *p)

 {

     if (packet_id_persist_enabled(p))

     {

         if (close(p->fd))
         {
             msg(D_PID_PERSIST | M_ERRNO, "Close error on --replay-persist file %s", p->filename);
         }
         packet_id_persist_init(p);

     }
 }
 
 /* load persisted rec packet_id (time and id) only once from file, and set state to enabled */
 void

 packet_id_persist_load(struct packet_id_persist *p, const char *filename)

 {

     struct gc_arena gc = gc_new();
     if (!packet_id_persist_enabled(p))

     {

         /* open packet-id persist file for both read and write */
         p->fd = platform_open(filename,
                               O_CREAT | O_RDWR | O_BINARY,
                               S_IRUSR | S_IWUSR);
         if (p->fd == -1)
         {
             msg(D_PID_PERSIST | M_ERRNO,
                 "Cannot open --replay-persist file %s for read/write",
                 filename);
         }
         else
         {
             struct packet_id_persist_file_image image;
             ssize_t n;

 
 #if defined(HAVE_FLOCK) && defined(LOCK_EX) && defined(LOCK_NB)

             if (flock(p->fd, LOCK_EX | LOCK_NB))
             {
                 msg(M_ERR, "Cannot obtain exclusive lock on --replay-persist file %s", filename);
             }

 #endif
 

             p->filename = filename;
             n = read(p->fd, &image, sizeof(image));
             if (n == sizeof(image))
             {
                 p->time = p->time_last_written = image.time;
                 p->id = p->id_last_written = image.id;
                 dmsg(D_PID_PERSIST_DEBUG, "PID Persist Read from %s: %s",
                      p->filename, packet_id_persist_print(p, &gc));
             }
             else if (n == -1)
             {
                 msg(D_PID_PERSIST | M_ERRNO,
                     "Read error on --replay-persist file %s",
                     p->filename);
             }
         }

     }

     gc_free(&gc);

 }
 
 /* save persisted rec packet_id (time and id) to file (only if enabled state) */
 void

 packet_id_persist_save(struct packet_id_persist *p)

 {

     if (packet_id_persist_enabled(p) && p->time && (p->time != p->time_last_written
                                                     || p->id != p->id_last_written))

     {

         struct packet_id_persist_file_image image;
         ssize_t n;
         off_t seek_ret;
         struct gc_arena gc = gc_new();
 
         image.time = p->time;
         image.id = p->id;
         seek_ret = lseek(p->fd, (off_t)0, SEEK_SET);
         if (seek_ret == (off_t)0)
         {
             n = write(p->fd, &image, sizeof(image));
             if (n == sizeof(image))
             {
                 p->time_last_written = p->time;
                 p->id_last_written = p->id;
                 dmsg(D_PID_PERSIST_DEBUG, "PID Persist Write to %s: %s",
                      p->filename, packet_id_persist_print(p, &gc));
             }
             else
             {
                 msg(D_PID_PERSIST | M_ERRNO,
                     "Cannot write to --replay-persist file %s",
                     p->filename);
             }
         }
         else
         {
             msg(D_PID_PERSIST | M_ERRNO,
                 "Cannot seek to beginning of --replay-persist file %s",
                 p->filename);
         }
         gc_free(&gc);

     }
 }
 
 /* transfer packet_id_persist -> packet_id */
 void

 packet_id_persist_load_obj(const struct packet_id_persist *p, struct packet_id *pid)

 {

     if (p && pid && packet_id_persist_enabled(p) && p->time)

     {

         pid->rec.time = p->time;
         pid->rec.id = p->id;

     }
 }
 
 const char *

 packet_id_persist_print(const struct packet_id_persist *p, struct gc_arena *gc)

 {

     struct buffer out = alloc_buf_gc(256, gc);

     buf_printf(&out, "[");

     if (packet_id_persist_enabled(p))

     {

         buf_printf(&out, " #" packet_id_format, (packet_id_print_type)p->id);
         if (p->time)
         {
             buf_printf(&out, " / time = (" packet_id_format ") %s",
                        (packet_id_print_type)p->time,
                        time_string(p->time, 0, false, gc));
         }

     }
 

     buf_printf(&out, " ]");
     return (char *)out.data;

 }
 

 #ifdef ENABLE_DEBUG
 
 static void

 packet_id_debug_print(int msglevel,
                       const struct packet_id_rec *p,
                       const struct packet_id_net *pin,
                       const char *message,
                       int value)

 {

     struct gc_arena gc = gc_new();
     struct buffer out = alloc_buf_gc(256, &gc);
     struct timeval tv;
     const time_t prev_now = now;
     const struct seq_list *sl = p->seq_list;
     int i;
 
     CLEAR(tv);
     gettimeofday(&tv, NULL);
 
     buf_printf(&out, "%s [%d]", message, value);
     buf_printf(&out, " [%s-%d] [", p->name, p->unit);
     for (i = 0; sl != NULL && i < sl->x_size; ++i)

     {

         char c;
         time_t v;
         int diff;
 
         v = CIRC_LIST_ITEM(sl, i);
         if (v == SEQ_UNSEEN)
         {
             c = '_';
         }
         else if (v == SEQ_EXPIRED)
         {
             c = 'E';
         }
         else
         {
             diff = (int) prev_now - v;
             if (diff < 0)
             {
                 c = 'N';
             }
             else if (diff < 10)
             {
                 c = '0' + diff;
             }
             else
             {
                 c = '>';
             }
         }
         buf_printf(&out, "%c", c);

     }

     buf_printf(&out, "] %lld:" packet_id_format, (long long)p->time, (packet_id_print_type)p->id);

     if (pin)
     {

         buf_printf(&out, " %lld:" packet_id_format, (long long)pin->time, (packet_id_print_type)pin->id);

     }
 

     buf_printf(&out, " t=%lld[%d]",
                (long long)prev_now,

                (int)(prev_now - tv.tv_sec));
 
     buf_printf(&out, " r=[%d,%d,%d,%d,%d]",
                (int)(p->last_reap - tv.tv_sec),
                p->seq_backtrack,
                p->time_backtrack,
                p->max_backtrack_stat,
                (int)p->initialized);
     if (sl != NULL)

     {

         buf_printf(&out, " sl=[%d,%d,%d,%d]",
                    sl->x_head,
                    sl->x_size,
                    sl->x_cap,
                    sl->x_sizeof);

     }
 

     msg(msglevel, "%s", BSTR(&out));
     gc_free(&gc);

 }
 

 #endif /* ifdef ENABLE_DEBUG */

 #ifdef PID_TEST
 
 void

 packet_id_interactive_test(void)

 {

     struct packet_id pid;
     struct packet_id_net pin;
     bool long_form;
     bool count = 0;
     bool test;
 
     const int seq_backtrack = 10;
     const int time_backtrack = 10;
 
     packet_id_init(&pid, seq_backtrack, time_backtrack);
 

     while (true)
     {

         char buf[80];
         if (!fgets(buf, sizeof(buf), stdin))
         {
             break;
         }
         update_time();
         if (sscanf(buf, "%lu,%u", &pin.time, &pin.id) == 2)
         {
             packet_id_reap_test(&pid.rec);
             test = packet_id_test(&pid.rec, &pin);

             printf("packet_id_test (%lld, " packet_id_format ") returned %d\n",
                    (long long)pin.time,

                    (packet_id_print_type)pin.id,
                    test);
             if (test)
             {
                 packet_id_add(&pid.rec, &pin);
             }
         }
         else
         {
             long_form = (count < 20);
             packet_id_alloc_outgoing(&pid.send, &pin, long_form);

             printf("(%lld(" packet_id_format "), %d)\n",
                    (long long)pin.time,

                    (packet_id_print_type)pin.id,
                    long_form);
             if (pid.send.id == 10)
             {
                 pid.send.id = 0xFFFFFFF8;
             }
             ++count;
         }
     }
     packet_id_free(&pid);

 }

 #endif /* ifdef PID_TEST */