1 /*
2 * OpenVPN -- An application to securely tunnel IP networks
3 * over a single TCP/UDP port, with support for SSL/TLS-based
4 * session authentication and key exchange,
5 * packet encryption, packet authentication, and
6 * packet compression.
7 *
8 * Copyright (C) 2002-2018 OpenVPN Inc <sales@openvpn.net>
9 *
10 * This program is free software; you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License version 2
12 * as published by the Free Software Foundation.
13 *
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License along
20 * with this program; if not, write to the Free Software Foundation, Inc.,
21 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
22 */
23
24 /*
25 * These routines are designed to catch replay attacks,
26 * where a man-in-the-middle captures packets and then
27 * attempts to replay them back later.
28 *
29 * We use the "sliding-window" algorithm, similar
30 * to IPSec.
31 */
32
33 #ifdef HAVE_CONFIG_H
34 #include "config.h"
35 #elif defined(_MSC_VER)
36 #include "config-msvc.h"
37 #endif
38
39 #include "syshead.h"
40
41 #include "packet_id.h"
42 #include "misc.h"
43 #include "integer.h"
44
45 #include "memdbg.h"
46
47 /* #define PID_SIMULATE_BACKTRACK */
48
49 /*
50 * Special time_t value that indicates that
51 * sequence number has expired.
52 */
53 #define SEQ_UNSEEN ((time_t)0)
54 #define SEQ_EXPIRED ((time_t)1)
55
56 static void packet_id_debug_print(int msglevel,
57 const struct packet_id_rec *p,
58 const struct packet_id_net *pin,
59 const char *message,
60 int value);
61
62 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)63 packet_id_debug(int msglevel,
64 const struct packet_id_rec *p,
65 const struct packet_id_net *pin,
66 const char *message,
67 int value)
68 {
69 #ifdef ENABLE_DEBUG
70 if (unlikely(check_debug_level(msglevel)))
71 {
72 packet_id_debug_print(msglevel, p, pin, message, value);
73 }
74 #endif
75 }
76
77 void
packet_id_init(struct packet_id * p,int seq_backtrack,int time_backtrack,const char * name,int unit)78 packet_id_init(struct packet_id *p, int seq_backtrack, int time_backtrack, const char *name, int unit)
79 {
80 dmsg(D_PID_DEBUG, "PID packet_id_init seq_backtrack=%d time_backtrack=%d",
81 seq_backtrack,
82 time_backtrack);
83
84 ASSERT(p);
85 CLEAR(*p);
86
87 p->rec.name = name;
88 p->rec.unit = unit;
89 if (seq_backtrack)
90 {
91 ASSERT(MIN_SEQ_BACKTRACK <= seq_backtrack && seq_backtrack <= MAX_SEQ_BACKTRACK);
92 ASSERT(MIN_TIME_BACKTRACK <= time_backtrack && time_backtrack <= MAX_TIME_BACKTRACK);
93 CIRC_LIST_ALLOC(p->rec.seq_list, struct seq_list, seq_backtrack);
94 p->rec.seq_backtrack = seq_backtrack;
95 p->rec.time_backtrack = time_backtrack;
96 }
97 p->rec.initialized = true;
98 }
99
100 void
packet_id_free(struct packet_id * p)101 packet_id_free(struct packet_id *p)
102 {
103 if (p)
104 {
105 dmsg(D_PID_DEBUG, "PID packet_id_free");
106 free(p->rec.seq_list);
107 CLEAR(*p);
108 }
109 }
110
111 void
packet_id_add(struct packet_id_rec * p,const struct packet_id_net * pin)112 packet_id_add(struct packet_id_rec *p, const struct packet_id_net *pin)
113 {
114 const time_t local_now = now;
115 if (p->seq_list)
116 {
117 packet_id_type diff;
118
119 /*
120 * If time value increases, start a new
121 * sequence number sequence.
122 */
123 if (!CIRC_LIST_SIZE(p->seq_list)
124 || pin->time > p->time
125 || (pin->id >= (packet_id_type)p->seq_backtrack
126 && pin->id - (packet_id_type)p->seq_backtrack > p->id))
127 {
128 p->time = pin->time;
129 p->id = 0;
130 if (pin->id > (packet_id_type)p->seq_backtrack)
131 {
132 p->id = pin->id - (packet_id_type)p->seq_backtrack;
133 }
134 CIRC_LIST_RESET(p->seq_list);
135 }
136
137 while (p->id < pin->id
138 #ifdef PID_SIMULATE_BACKTRACK
139 || (get_random() % 64) < 31
140 #endif
141 )
142 {
143 CIRC_LIST_PUSH(p->seq_list, SEQ_UNSEEN);
144 ++p->id;
145 }
146
147 diff = p->id - pin->id;
148 if (diff < (packet_id_type) CIRC_LIST_SIZE(p->seq_list)
149 && local_now > SEQ_EXPIRED)
150 {
151 CIRC_LIST_ITEM(p->seq_list, diff) = local_now;
152 }
153 }
154 else
155 {
156 p->time = pin->time;
157 p->id = pin->id;
158 }
159 }
160
161 /*
162 * Expire sequence numbers which can no longer
163 * be accepted because they would violate
164 * time_backtrack.
165 */
166 void
packet_id_reap(struct packet_id_rec * p)167 packet_id_reap(struct packet_id_rec *p)
168 {
169 const time_t local_now = now;
170 if (p->time_backtrack)
171 {
172 int i;
173 bool expire = false;
174 for (i = 0; i < CIRC_LIST_SIZE(p->seq_list); ++i)
175 {
176 const time_t t = CIRC_LIST_ITEM(p->seq_list, i);
177 if (t == SEQ_EXPIRED)
178 {
179 break;
180 }
181 if (!expire && t && t + p->time_backtrack < local_now)
182 {
183 expire = true;
184 }
185 if (expire)
186 {
187 CIRC_LIST_ITEM(p->seq_list, i) = SEQ_EXPIRED;
188 }
189 }
190 }
191 p->last_reap = local_now;
192 }
193
194 /*
195 * Return true if packet id is ok, or false if
196 * it is a replay.
197 */
198 bool
packet_id_test(struct packet_id_rec * p,const struct packet_id_net * pin)199 packet_id_test(struct packet_id_rec *p,
200 const struct packet_id_net *pin)
201 {
202 packet_id_type diff;
203
204 packet_id_debug(D_PID_DEBUG, p, pin, "PID_TEST", 0);
205
206 ASSERT(p->initialized);
207
208 if (!pin->id)
209 {
210 return false;
211 }
212
213 if (p->seq_backtrack)
214 {
215 /*
216 * In backtrack mode, we allow packet reordering subject
217 * to the seq_backtrack and time_backtrack constraints.
218 *
219 * This mode is used with UDP.
220 */
221 if (pin->time == p->time)
222 {
223 /* is packet-id greater than any one we've seen yet? */
224 if (pin->id > p->id)
225 {
226 return true;
227 }
228
229 /* check packet-id sliding window for original/replay status */
230 diff = p->id - pin->id;
231
232 /* keep track of maximum backtrack seen for debugging purposes */
233 if ((int)diff > p->max_backtrack_stat)
234 {
235 p->max_backtrack_stat = (int)diff;
236 packet_id_debug(D_PID_DEBUG_LOW, p, pin, "PID_ERR replay-window backtrack occurred", p->max_backtrack_stat);
237 }
238
239 if (diff >= (packet_id_type) CIRC_LIST_SIZE(p->seq_list))
240 {
241 packet_id_debug(D_PID_DEBUG_LOW, p, pin, "PID_ERR large diff", diff);
242 return false;
243 }
244
245 {
246 const time_t v = CIRC_LIST_ITEM(p->seq_list, diff);
247 if (v == 0)
248 {
249 return true;
250 }
251 else
252 {
253 /* raised from D_PID_DEBUG_LOW to reduce verbosity */
254 packet_id_debug(D_PID_DEBUG_MEDIUM, p, pin, "PID_ERR replay", diff);
255 return false;
256 }
257 }
258 }
259 else if (pin->time < p->time) /* if time goes back, reject */
260 {
261 packet_id_debug(D_PID_DEBUG_LOW, p, pin, "PID_ERR time backtrack", 0);
262 return false;
263 }
264 else /* time moved forward */
265 {
266 return true;
267 }
268 }
269 else
270 {
271 /*
272 * In non-backtrack mode, all sequence number series must
273 * begin at some number n > 0 and must increment linearly without gaps.
274 *
275 * This mode is used with TCP.
276 */
277 if (pin->time == p->time)
278 {
279 return !p->id || pin->id == p->id + 1;
280 }
281 else if (pin->time < p->time) /* if time goes back, reject */
282 {
283 return false;
284 }
285 else /* time moved forward */
286 {
287 return pin->id == 1;
288 }
289 }
290 }
291
292 /*
293 * Read/write a packet ID to/from the buffer. Short form is sequence number
294 * only. Long form is sequence number and timestamp.
295 */
296
297 bool
packet_id_read(struct packet_id_net * pin,struct buffer * buf,bool long_form)298 packet_id_read(struct packet_id_net *pin, struct buffer *buf, bool long_form)
299 {
300 packet_id_type net_id;
301 net_time_t net_time;
302
303 pin->id = 0;
304 pin->time = 0;
305
306 if (!buf_read(buf, &net_id, sizeof(net_id)))
307 {
308 return false;
309 }
310 pin->id = ntohpid(net_id);
311 if (long_form)
312 {
313 if (!buf_read(buf, &net_time, sizeof(net_time)))
314 {
315 return false;
316 }
317 pin->time = ntohtime(net_time);
318 }
319 return true;
320 }
321
322 static bool
packet_id_send_update(struct packet_id_send * p,bool long_form)323 packet_id_send_update(struct packet_id_send *p, bool long_form)
324 {
325 if (!p->time)
326 {
327 p->time = now;
328 }
329 if (p->id == PACKET_ID_MAX)
330 {
331 /* Packet ID only allowed to roll over if using long form and time has
332 * moved forward since last roll over.
333 */
334 if (!long_form || now <= p->time)
335 {
336 return false;
337 }
338 p->time = now;
339 p->id = 0;
340 }
341 p->id++;
342 return true;
343 }
344
345 bool
packet_id_write(struct packet_id_send * p,struct buffer * buf,bool long_form,bool prepend)346 packet_id_write(struct packet_id_send *p, struct buffer *buf, bool long_form,
347 bool prepend)
348 {
349 if (!packet_id_send_update(p, long_form))
350 {
351 return false;
352 }
353
354 const packet_id_type net_id = htonpid(p->id);
355 const net_time_t net_time = htontime(p->time);
356 if (prepend)
357 {
358 if (long_form)
359 {
360 if (!buf_write_prepend(buf, &net_time, sizeof(net_time)))
361 {
362 return false;
363 }
364 }
365 if (!buf_write_prepend(buf, &net_id, sizeof(net_id)))
366 {
367 return false;
368 }
369 }
370 else
371 {
372 if (!buf_write(buf, &net_id, sizeof(net_id)))
373 {
374 return false;
375 }
376 if (long_form)
377 {
378 if (!buf_write(buf, &net_time, sizeof(net_time)))
379 {
380 return false;
381 }
382 }
383 }
384 return true;
385 }
386
387 const char *
packet_id_net_print(const struct packet_id_net * pin,bool print_timestamp,struct gc_arena * gc)388 packet_id_net_print(const struct packet_id_net *pin, bool print_timestamp, struct gc_arena *gc)
389 {
390 struct buffer out = alloc_buf_gc(256, gc);
391
392 buf_printf(&out, "[ #" packet_id_format, (packet_id_print_type)pin->id);
393 if (print_timestamp && pin->time)
394 {
395 buf_printf(&out, " / time = (" packet_id_format ") %s",
396 (packet_id_print_type)pin->time,
397 time_string(pin->time, 0, false, gc));
398 }
399
400 buf_printf(&out, " ]");
401 return BSTR(&out);
402 }
403
404 /* initialize the packet_id_persist structure in a disabled state */
405 void
packet_id_persist_init(struct packet_id_persist * p)406 packet_id_persist_init(struct packet_id_persist *p)
407 {
408 p->filename = NULL;
409 p->fd = -1;
410 p->time = p->time_last_written = 0;
411 p->id = p->id_last_written = 0;
412 }
413
414 /* close the file descriptor if it is open, and switch to disabled state */
415 void
packet_id_persist_close(struct packet_id_persist * p)416 packet_id_persist_close(struct packet_id_persist *p)
417 {
418 if (packet_id_persist_enabled(p))
419 {
420 if (close(p->fd))
421 {
422 msg(D_PID_PERSIST | M_ERRNO, "Close error on --replay-persist file %s", p->filename);
423 }
424 packet_id_persist_init(p);
425 }
426 }
427
428 /* load persisted rec packet_id (time and id) only once from file, and set state to enabled */
429 void
packet_id_persist_load(struct packet_id_persist * p,const char * filename)430 packet_id_persist_load(struct packet_id_persist *p, const char *filename)
431 {
432 struct gc_arena gc = gc_new();
433 if (!packet_id_persist_enabled(p))
434 {
435 /* open packet-id persist file for both read and write */
436 p->fd = platform_open(filename,
437 O_CREAT | O_RDWR | O_BINARY,
438 S_IRUSR | S_IWUSR);
439 if (p->fd == -1)
440 {
441 msg(D_PID_PERSIST | M_ERRNO,
442 "Cannot open --replay-persist file %s for read/write",
443 filename);
444 }
445 else
446 {
447 struct packet_id_persist_file_image image;
448 ssize_t n;
449
450 #if defined(HAVE_FLOCK) && defined(LOCK_EX) && defined(LOCK_NB)
451 if (flock(p->fd, LOCK_EX | LOCK_NB))
452 {
453 msg(M_ERR, "Cannot obtain exclusive lock on --replay-persist file %s", filename);
454 }
455 #endif
456
457 p->filename = filename;
458 n = read(p->fd, &image, sizeof(image));
459 if (n == sizeof(image))
460 {
461 p->time = p->time_last_written = image.time;
462 p->id = p->id_last_written = image.id;
463 dmsg(D_PID_PERSIST_DEBUG, "PID Persist Read from %s: %s",
464 p->filename, packet_id_persist_print(p, &gc));
465 }
466 else if (n == -1)
467 {
468 msg(D_PID_PERSIST | M_ERRNO,
469 "Read error on --replay-persist file %s",
470 p->filename);
471 }
472 }
473 }
474 gc_free(&gc);
475 }
476
477 /* save persisted rec packet_id (time and id) to file (only if enabled state) */
478 void
packet_id_persist_save(struct packet_id_persist * p)479 packet_id_persist_save(struct packet_id_persist *p)
480 {
481 if (packet_id_persist_enabled(p) && p->time && (p->time != p->time_last_written
482 || p->id != p->id_last_written))
483 {
484 struct packet_id_persist_file_image image;
485 ssize_t n;
486 off_t seek_ret;
487 struct gc_arena gc = gc_new();
488
489 image.time = p->time;
490 image.id = p->id;
491 seek_ret = lseek(p->fd, (off_t)0, SEEK_SET);
492 if (seek_ret == (off_t)0)
493 {
494 n = write(p->fd, &image, sizeof(image));
495 if (n == sizeof(image))
496 {
497 p->time_last_written = p->time;
498 p->id_last_written = p->id;
499 dmsg(D_PID_PERSIST_DEBUG, "PID Persist Write to %s: %s",
500 p->filename, packet_id_persist_print(p, &gc));
501 }
502 else
503 {
504 msg(D_PID_PERSIST | M_ERRNO,
505 "Cannot write to --replay-persist file %s",
506 p->filename);
507 }
508 }
509 else
510 {
511 msg(D_PID_PERSIST | M_ERRNO,
512 "Cannot seek to beginning of --replay-persist file %s",
513 p->filename);
514 }
515 gc_free(&gc);
516 }
517 }
518
519 /* transfer packet_id_persist -> packet_id */
520 void
packet_id_persist_load_obj(const struct packet_id_persist * p,struct packet_id * pid)521 packet_id_persist_load_obj(const struct packet_id_persist *p, struct packet_id *pid)
522 {
523 if (p && pid && packet_id_persist_enabled(p) && p->time)
524 {
525 pid->rec.time = p->time;
526 pid->rec.id = p->id;
527 }
528 }
529
530 const char *
packet_id_persist_print(const struct packet_id_persist * p,struct gc_arena * gc)531 packet_id_persist_print(const struct packet_id_persist *p, struct gc_arena *gc)
532 {
533 struct buffer out = alloc_buf_gc(256, gc);
534
535 buf_printf(&out, "[");
536
537 if (packet_id_persist_enabled(p))
538 {
539 buf_printf(&out, " #" packet_id_format, (packet_id_print_type)p->id);
540 if (p->time)
541 {
542 buf_printf(&out, " / time = (" packet_id_format ") %s",
543 (packet_id_print_type)p->time,
544 time_string(p->time, 0, false, gc));
545 }
546 }
547
548 buf_printf(&out, " ]");
549 return (char *)out.data;
550 }
551
552 #ifdef ENABLE_DEBUG
553
554 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)555 packet_id_debug_print(int msglevel,
556 const struct packet_id_rec *p,
557 const struct packet_id_net *pin,
558 const char *message,
559 int value)
560 {
561 struct gc_arena gc = gc_new();
562 struct buffer out = alloc_buf_gc(256, &gc);
563 struct timeval tv;
564 const time_t prev_now = now;
565 const struct seq_list *sl = p->seq_list;
566 int i;
567
568 CLEAR(tv);
569 gettimeofday(&tv, NULL);
570
571 buf_printf(&out, "%s [%d]", message, value);
572 buf_printf(&out, " [%s-%d] [", p->name, p->unit);
573 for (i = 0; sl != NULL && i < sl->x_size; ++i)
574 {
575 char c;
576 time_t v;
577 int diff;
578
579 v = CIRC_LIST_ITEM(sl, i);
580 if (v == SEQ_UNSEEN)
581 {
582 c = '_';
583 }
584 else if (v == SEQ_EXPIRED)
585 {
586 c = 'E';
587 }
588 else
589 {
590 diff = (int) prev_now - v;
591 if (diff < 0)
592 {
593 c = 'N';
594 }
595 else if (diff < 10)
596 {
597 c = '0' + diff;
598 }
599 else
600 {
601 c = '>';
602 }
603 }
604 buf_printf(&out, "%c", c);
605 }
606 buf_printf(&out, "] %" PRIi64 ":" packet_id_format, (int64_t)p->time, (packet_id_print_type)p->id);
607 if (pin)
608 {
609 buf_printf(&out, " %" PRIi64 ":" packet_id_format, (int64_t)pin->time, (packet_id_print_type)pin->id);
610 }
611
612 buf_printf(&out, " t=%" PRIi64 "[%d]",
613 (int64_t)prev_now,
614 (int)(prev_now - tv.tv_sec));
615
616 buf_printf(&out, " r=[%d,%d,%d,%d,%d]",
617 (int)(p->last_reap - tv.tv_sec),
618 p->seq_backtrack,
619 p->time_backtrack,
620 p->max_backtrack_stat,
621 (int)p->initialized);
622 if (sl != NULL)
623 {
624 buf_printf(&out, " sl=[%d,%d,%d,%d]",
625 sl->x_head,
626 sl->x_size,
627 sl->x_cap,
628 sl->x_sizeof);
629 }
630
631
632 msg(msglevel, "%s", BSTR(&out));
633 gc_free(&gc);
634 }
635
636 #endif /* ifdef ENABLE_DEBUG */
637
638 #ifdef PID_TEST
639
640 void
packet_id_interactive_test(void)641 packet_id_interactive_test(void)
642 {
643 struct packet_id pid;
644 struct packet_id_net pin;
645 bool long_form;
646 bool count = 0;
647 bool test;
648
649 const int seq_backtrack = 10;
650 const int time_backtrack = 10;
651
652 packet_id_init(&pid, seq_backtrack, time_backtrack);
653
654 while (true)
655 {
656 char buf[80];
657 if (!fgets(buf, sizeof(buf), stdin))
658 {
659 break;
660 }
661 update_time();
662 if (sscanf(buf, "%lu,%u", &pin.time, &pin.id) == 2)
663 {
664 packet_id_reap_test(&pid.rec);
665 test = packet_id_test(&pid.rec, &pin);
666 printf("packet_id_test (%" PRIi64 ", " packet_id_format ") returned %d\n",
667 (int64_t)pin.time,
668 (packet_id_print_type)pin.id,
669 test);
670 if (test)
671 {
672 packet_id_add(&pid.rec, &pin);
673 }
674 }
675 else
676 {
677 long_form = (count < 20);
678 packet_id_alloc_outgoing(&pid.send, &pin, long_form);
679 printf("(%" PRIi64 "(" packet_id_format "), %d)\n",
680 (int64_t)pin.time,
681 (packet_id_print_type)pin.id,
682 long_form);
683 if (pid.send.id == 10)
684 {
685 pid.send.id = 0xFFFFFFF8;
686 }
687 ++count;
688 }
689 }
690 packet_id_free(&pid);
691 }
692 #endif /* ifdef PID_TEST */
693