src/net_packet.c

   1 /*
   2     net_packet.c -- Handles in- and outgoing VPN packets
   3     Copyright (C) 1998-2005 Ivo Timmermans,
   4                   2000-2017 Guus Sliepen <guus@tinc-vpn.org>
   5                   2010      Timothy Redaelli <timothy@redaelli.eu>
   6                   2010      Brandon Black <blblack@gmail.com>
   7
   8     This program is free software; you can redistribute it and/or modify
   9     it under the terms of the GNU General Public License as published by
  10     the Free Software Foundation; either version 2 of the License, or
  11     (at your option) any later version.
  12
  13     This program is distributed in the hope that it will be useful,
  14     but WITHOUT ANY WARRANTY; without even the implied warranty of
  15     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16     GNU General Public License for more details.
  17
  18     You should have received a copy of the GNU General Public License along
  19     with this program; if not, write to the Free Software Foundation, Inc.,
  20     51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  21 */
  22
  23 #include "system.h"
  24
  25 #ifdef HAVE_ZLIB
  26 #define ZLIB_CONST
  27 #include <zlib.h>
  28 #endif
  29
  30 #ifdef HAVE_LZO
  31 #include LZO1X_H
  32 #endif
  33
  34 #include "address_cache.h"
  35 #include "cipher.h"
  36 #include "conf.h"
  37 #include "connection.h"
  38 #include "crypto.h"
  39 #include "digest.h"
  40 #include "device.h"
  41 #include "ethernet.h"
  42 #include "ipv4.h"
  43 #include "ipv6.h"
  44 #include "graph.h"
  45 #include "logger.h"
  46 #include "net.h"
  47 #include "netutl.h"
  48 #include "protocol.h"
  49 #include "route.h"
  50 #include "utils.h"
  51 #include "xalloc.h"
  52
  53 #ifndef MAX
  54 #define MAX(a, b) ((a) > (b) ? (a) : (b))
  55 #endif
  56
  57 /* The minimum size of a probe is 14 bytes, but since we normally use CBC mode
  58    encryption, we can add a few extra random bytes without increasing the
  59    resulting packet size. */
  60 #define MIN_PROBE_SIZE 18
  61
  62 int keylifetime = 0;
  63 #ifdef HAVE_LZO
  64 static char lzo_wrkmem[LZO1X_999_MEM_COMPRESS > LZO1X_1_MEM_COMPRESS ? LZO1X_999_MEM_COMPRESS : LZO1X_1_MEM_COMPRESS];
  65 #endif
  66
  67 static void send_udppacket(node_t *, vpn_packet_t *);
  68
  69 unsigned replaywin = 32;
  70 bool localdiscovery = true;
  71 bool udp_discovery = true;
  72 int udp_discovery_keepalive_interval = 10;
  73 int udp_discovery_interval = 2;
  74 int udp_discovery_timeout = 30;
  75
  76 #define MAX_SEQNO 1073741824
  77
  78 static void try_fix_mtu(node_t *n) {
  79         if(n->mtuprobes < 0) {
  80                 return;
  81         }
  82
  83         if(n->mtuprobes == 20 || n->minmtu >= n->maxmtu) {
  84                 if(n->minmtu > n->maxmtu) {
  85                         n->minmtu = n->maxmtu;
  86                 } else {
  87                         n->maxmtu = n->minmtu;
  88                 }
  89
  90                 n->mtu = n->minmtu;
  91                 logger(DEBUG_TRAFFIC, LOG_INFO, "Fixing MTU of %s (%s) to %d after %d probes", n->name, n->hostname, n->mtu, n->mtuprobes);
  92                 n->mtuprobes = -1;
  93         }
  94 }
  95
  96 static void udp_probe_timeout_handler(void *data) {
  97         node_t *n = data;
  98
  99         if(!n->status.udp_confirmed) {
 100                 return;
 101         }
 102
 103         logger(DEBUG_TRAFFIC, LOG_INFO, "Too much time has elapsed since last UDP ping response from %s (%s), stopping UDP communication", n->name, n->hostname);
 104         n->status.udp_confirmed = false;
 105         n->udp_ping_rtt = -1;
 106         n->maxrecentlen = 0;
 107         n->mtuprobes = 0;
 108         n->minmtu = 0;
 109         n->maxmtu = MTU;
 110 }
 111
 112 static void send_udp_probe_reply(node_t *n, vpn_packet_t *packet, length_t len) {
 113         if(!n->status.sptps && !n->status.validkey) {
 114                 logger(DEBUG_TRAFFIC, LOG_INFO, "Trying to send UDP probe reply to %s (%s) but we don't have his key yet", n->name, n->hostname);
 115                 return;
 116         }
 117
 118         /* Type 2 probe replies were introduced in protocol 17.3 */
 119         if((n->options >> 24) >= 3) {
 120                 DATA(packet)[0] = 2;
 121                 uint16_t len16 = htons(len);
 122                 memcpy(DATA(packet) + 1, &len16, 2);
 123                 packet->len = MIN_PROBE_SIZE;
 124                 logger(DEBUG_TRAFFIC, LOG_INFO, "Sending type 2 probe reply length %u to %s (%s)", len, n->name, n->hostname);
 125
 126         } else {
 127                 /* Legacy protocol: n won't understand type 2 probe replies. */
 128                 DATA(packet)[0] = 1;
 129                 logger(DEBUG_TRAFFIC, LOG_INFO, "Sending type 1 probe reply length %u to %s (%s)", len, n->name, n->hostname);
 130         }
 131
 132         /* Temporarily set udp_confirmed, so that the reply is sent
 133            back exactly the way it came in. */
 134
 135         bool udp_confirmed = n->status.udp_confirmed;
 136         n->status.udp_confirmed = true;
 137         send_udppacket(n, packet);
 138         n->status.udp_confirmed = udp_confirmed;
 139 }
 140
 141 static void udp_probe_h(node_t *n, vpn_packet_t *packet, length_t len) {
 142         if(!DATA(packet)[0]) {
 143                 logger(DEBUG_TRAFFIC, LOG_INFO, "Got UDP probe request %d from %s (%s)", packet->len, n->name, n->hostname);
 144                 send_udp_probe_reply(n, packet, len);
 145                 return;
 146         }
 147
 148         if(DATA(packet)[0] == 2) {
 149                 // It's a type 2 probe reply, use the length field inside the packet
 150                 uint16_t len16;
 151                 memcpy(&len16, DATA(packet) + 1, 2);
 152                 len = ntohs(len16);
 153         }
 154
 155         if (n->udp_ping_sent.tv_sec != 0) { // a probe in flight
 156                 gettimeofday(&now, NULL);
 157                 struct timeval rtt;
 158                 timersub(&now, &n->udp_ping_sent, &rtt);
 159                 n->udp_ping_rtt = rtt.tv_sec*1000000 + rtt.tv_usec;
 160                 logger(DEBUG_TRAFFIC, LOG_INFO, "Got type %d UDP probe reply %d from %s (%s) rtt=%d.%03d", DATA(packet)[0], len, n->name, n->hostname, n->udp_ping_rtt / 1000, n->udp_ping_rtt % 1000);
 161         } else {
 162                 logger(DEBUG_TRAFFIC, LOG_INFO, "Got type %d UDP probe reply %d from %s (%s)", DATA(packet)[0], len, n->name, n->hostname);
 163         }
 164
 165         /* It's a valid reply: now we know bidirectional communication
 166            is possible using the address and socket that the reply
 167            packet used. */
 168         if(!n->status.udp_confirmed) {
 169                 n->status.udp_confirmed = true;
 170                 fprintf(stderr, "Updating address cache...\n");
 171
 172                 if(!n->address_cache) {
 173                         n->address_cache = open_address_cache(n);
 174                 }
 175
 176                 reset_address_cache(n->address_cache, &n->address);
 177         }
 178
 179         // Reset the UDP ping timer. (no probe in flight)
 180         n->udp_ping_sent.tv_sec = 0;
 181
 182         if(udp_discovery) {
 183                 timeout_del(&n->udp_ping_timeout);
 184                 timeout_add(&n->udp_ping_timeout, &udp_probe_timeout_handler, n, &(struct timeval) {
 185                         udp_discovery_timeout, 0
 186                 });
 187         }
 188
 189         if(len > n->maxmtu) {
 190                 logger(DEBUG_TRAFFIC, LOG_INFO, "Increase in PMTU to %s (%s) detected, restarting PMTU discovery", n->name, n->hostname);
 191                 n->minmtu = len;
 192                 n->maxmtu = MTU;
 193                 /* Set mtuprobes to 1 so that try_mtu() doesn't reset maxmtu */
 194                 n->mtuprobes = 1;
 195                 return;
 196         } else if(n->mtuprobes < 0 && len == n->maxmtu) {
 197                 /* We got a maxmtu sized packet, confirming the PMTU is still valid. */
 198                 n->mtuprobes = -1;
 199                 n->mtu_ping_sent = now;
 200         }
 201
 202         /* If applicable, raise the minimum supported MTU */
 203
 204         if(n->minmtu < len) {
 205                 n->minmtu = len;
 206                 try_fix_mtu(n);
 207         }
 208 }
 209
 210 static length_t compress_packet(uint8_t *dest, const uint8_t *source, length_t len, int level) {
 211         if(level == 0) {
 212                 memcpy(dest, source, len);
 213                 return len;
 214         } else if(level == 10) {
 215 #ifdef HAVE_LZO
 216                 lzo_uint lzolen = MAXSIZE;
 217                 lzo1x_1_compress(source, len, dest, &lzolen, lzo_wrkmem);
 218                 return lzolen;
 219 #else
 220                 return -1;
 221 #endif
 222         } else if(level < 10) {
 223 #ifdef HAVE_ZLIB
 224                 unsigned long destlen = MAXSIZE;
 225
 226                 if(compress2(dest, &destlen, source, len, level) == Z_OK) {
 227                         return destlen;
 228                 } else
 229 #endif
 230                         return -1;
 231         } else {
 232 #ifdef HAVE_LZO
 233                 lzo_uint lzolen = MAXSIZE;
 234                 lzo1x_999_compress(source, len, dest, &lzolen, lzo_wrkmem);
 235                 return lzolen;
 236 #else
 237                 return -1;
 238 #endif
 239         }
 240
 241         return -1;
 242 }
 243
 244 static length_t uncompress_packet(uint8_t *dest, const uint8_t *source, length_t len, int level) {
 245         if(level == 0) {
 246                 memcpy(dest, source, len);
 247                 return len;
 248         } else if(level > 9) {
 249 #ifdef HAVE_LZO
 250                 lzo_uint lzolen = MAXSIZE;
 251
 252                 if(lzo1x_decompress_safe(source, len, dest, &lzolen, NULL) == LZO_E_OK) {
 253                         return lzolen;
 254                 } else
 255 #endif
 256                         return -1;
 257         }
 258
 259 #ifdef HAVE_ZLIB
 260         else {
 261                 unsigned long destlen = MAXSIZE;
 262                 static z_stream stream;
 263
 264                 if(stream.next_in) {
 265                         inflateReset(&stream);
 266                 } else {
 267                         inflateInit(&stream);
 268                 }
 269
 270                 stream.next_in = source;
 271                 stream.avail_in = len;
 272                 stream.next_out = dest;
 273                 stream.avail_out = destlen;
 274                 stream.total_out = 0;
 275
 276                 if(inflate(&stream, Z_FINISH) == Z_STREAM_END) {
 277                         return stream.total_out;
 278                 } else {
 279                         return -1;
 280                 }
 281         }
 282
 283 #endif
 284
 285         return -1;
 286 }
 287
 288 /* VPN packet I/O */
 289
 290 static void receive_packet(node_t *n, vpn_packet_t *packet) {
 291         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Received packet of %d bytes from %s (%s)",
 292                packet->len, n->name, n->hostname);
 293
 294         n->in_packets++;
 295         n->in_bytes += packet->len;
 296
 297         route(n, packet);
 298 }
 299
 300 static bool try_mac(node_t *n, const vpn_packet_t *inpkt) {
 301         if(n->status.sptps) {
 302                 return sptps_verify_datagram(&n->sptps, DATA(inpkt), inpkt->len);
 303         }
 304
 305 #ifdef DISABLE_LEGACY
 306         return false;
 307 #else
 308
 309         if(!n->status.validkey_in || !digest_active(n->indigest) || inpkt->len < sizeof(seqno_t) + digest_length(n->indigest)) {
 310                 return false;
 311         }
 312
 313         return digest_verify(n->indigest, inpkt->data, inpkt->len - digest_length(n->indigest), inpkt->data + inpkt->len - digest_length(n->indigest));
 314 #endif
 315 }
 316
 317 static bool receive_udppacket(node_t *n, vpn_packet_t *inpkt) {
 318         vpn_packet_t pkt1, pkt2;
 319         vpn_packet_t *pkt[] = { &pkt1, &pkt2, &pkt1, &pkt2 };
 320         int nextpkt = 0;
 321         size_t outlen;
 322         pkt1.offset = DEFAULT_PACKET_OFFSET;
 323         pkt2.offset = DEFAULT_PACKET_OFFSET;
 324
 325         if(n->status.sptps) {
 326                 if(!n->sptps.state) {
 327                         if(!n->status.waitingforkey) {
 328                                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got packet from %s (%s) but we haven't exchanged keys yet", n->name, n->hostname);
 329                                 send_req_key(n);
 330                         } else {
 331                                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got packet from %s (%s) but he hasn't got our key yet", n->name, n->hostname);
 332                         }
 333
 334                         return false;
 335                 }
 336
 337                 n->status.udppacket = true;
 338                 bool result = sptps_receive_data(&n->sptps, DATA(inpkt), inpkt->len);
 339                 n->status.udppacket = false;
 340
 341                 if(!result) {
 342                         /* Uh-oh. It might be that the tunnel is stuck in some corrupted state,
 343                            so let's restart SPTPS in case that helps. But don't do that too often
 344                            to prevent storms, and because that would make life a little too easy
 345                            for external attackers trying to DoS us. */
 346                         if(n->last_req_key < now.tv_sec - 10) {
 347                                 logger(DEBUG_PROTOCOL, LOG_ERR, "Failed to decode raw TCP packet from %s (%s), restarting SPTPS", n->name, n->hostname);
 348                                 send_req_key(n);
 349                         }
 350
 351                         return false;
 352                 }
 353
 354                 return true;
 355         }
 356
 357 #ifdef DISABLE_LEGACY
 358         return false;
 359 #else
 360
 361         if(!n->status.validkey_in) {
 362                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got packet from %s (%s) but he hasn't got our key yet", n->name, n->hostname);
 363                 return false;
 364         }
 365
 366         /* Check packet length */
 367
 368         if(inpkt->len < sizeof(seqno_t) + digest_length(n->indigest)) {
 369                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got too short packet from %s (%s)",
 370                        n->name, n->hostname);
 371                 return false;
 372         }
 373
 374         /* It's a legacy UDP packet, the data starts after the seqno */
 375
 376         inpkt->offset += sizeof(seqno_t);
 377
 378         /* Check the message authentication code */
 379
 380         if(digest_active(n->indigest)) {
 381                 inpkt->len -= digest_length(n->indigest);
 382
 383                 if(!digest_verify(n->indigest, SEQNO(inpkt), inpkt->len, SEQNO(inpkt) + inpkt->len)) {
 384                         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got unauthenticated packet from %s (%s)", n->name, n->hostname);
 385                         return false;
 386                 }
 387         }
 388
 389         /* Decrypt the packet */
 390
 391         if(cipher_active(n->incipher)) {
 392                 vpn_packet_t *outpkt = pkt[nextpkt++];
 393                 outlen = MAXSIZE;
 394
 395                 if(!cipher_decrypt(n->incipher, SEQNO(inpkt), inpkt->len, SEQNO(outpkt), &outlen, true)) {
 396                         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Error decrypting packet from %s (%s)", n->name, n->hostname);
 397                         return false;
 398                 }
 399
 400                 outpkt->len = outlen;
 401                 inpkt = outpkt;
 402         }
 403
 404         /* Check the sequence number */
 405
 406         seqno_t seqno;
 407         memcpy(&seqno, SEQNO(inpkt), sizeof(seqno));
 408         seqno = ntohl(seqno);
 409         inpkt->len -= sizeof(seqno);
 410
 411         if(replaywin) {
 412                 if(seqno != n->received_seqno + 1) {
 413                         if(seqno >= n->received_seqno + replaywin * 8) {
 414                                 if(n->farfuture++ < replaywin >> 2) {
 415                                         logger(DEBUG_TRAFFIC, LOG_WARNING, "Packet from %s (%s) is %d seqs in the future, dropped (%u)",
 416                                                n->name, n->hostname, seqno - n->received_seqno - 1, n->farfuture);
 417                                         return false;
 418                                 }
 419
 420                                 logger(DEBUG_TRAFFIC, LOG_WARNING, "Lost %d packets from %s (%s)",
 421                                        seqno - n->received_seqno - 1, n->name, n->hostname);
 422                                 memset(n->late, 0, replaywin);
 423                         } else if(seqno <= n->received_seqno) {
 424                                 if((n->received_seqno >= replaywin * 8 && seqno <= n->received_seqno - replaywin * 8) || !(n->late[(seqno / 8) % replaywin] & (1 << seqno % 8))) {
 425                                         logger(DEBUG_TRAFFIC, LOG_WARNING, "Got late or replayed packet from %s (%s), seqno %d, last received %d",
 426                                                n->name, n->hostname, seqno, n->received_seqno);
 427                                         return false;
 428                                 }
 429                         } else {
 430                                 for(int i = n->received_seqno + 1; i < seqno; i++) {
 431                                         n->late[(i / 8) % replaywin] |= 1 << i % 8;
 432                                 }
 433                         }
 434                 }
 435
 436                 n->farfuture = 0;
 437                 n->late[(seqno / 8) % replaywin] &= ~(1 << seqno % 8);
 438         }
 439
 440         if(seqno > n->received_seqno) {
 441                 n->received_seqno = seqno;
 442         }
 443
 444         n->received++;
 445
 446         if(n->received_seqno > MAX_SEQNO) {
 447                 regenerate_key();
 448         }
 449
 450         /* Decompress the packet */
 451
 452         length_t origlen = inpkt->len;
 453
 454         if(n->incompression) {
 455                 vpn_packet_t *outpkt = pkt[nextpkt++];
 456
 457                 if((outpkt->len = uncompress_packet(DATA(outpkt), DATA(inpkt), inpkt->len, n->incompression)) < 0) {
 458                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while uncompressing packet from %s (%s)",
 459                                n->name, n->hostname);
 460                         return false;
 461                 }
 462
 463                 inpkt = outpkt;
 464
 465                 origlen -= MTU / 64 + 20;
 466         }
 467
 468         if(inpkt->len > n->maxrecentlen) {
 469                 n->maxrecentlen = inpkt->len;
 470         }
 471
 472         inpkt->priority = 0;
 473
 474         if(!DATA(inpkt)[12] && !DATA(inpkt)[13]) {
 475                 udp_probe_h(n, inpkt, origlen);
 476         } else {
 477                 receive_packet(n, inpkt);
 478         }
 479
 480         return true;
 481 #endif
 482 }
 483
 484 void receive_tcppacket(connection_t *c, const char *buffer, int len) {
 485         vpn_packet_t outpkt;
 486         outpkt.offset = DEFAULT_PACKET_OFFSET;
 487
 488         if(len > sizeof(outpkt.data) - outpkt.offset) {
 489                 return;
 490         }
 491
 492         outpkt.len = len;
 493
 494         if(c->options & OPTION_TCPONLY) {
 495                 outpkt.priority = 0;
 496         } else {
 497                 outpkt.priority = -1;
 498         }
 499
 500         memcpy(DATA(&outpkt), buffer, len);
 501
 502         receive_packet(c->node, &outpkt);
 503 }
 504
 505 bool receive_tcppacket_sptps(connection_t *c, const char *data, int len) {
 506         if(len < sizeof(node_id_t) + sizeof(node_id_t)) {
 507                 logger(DEBUG_PROTOCOL, LOG_ERR, "Got too short TCP SPTPS packet from %s (%s)", c->name, c->hostname);
 508                 return false;
 509         }
 510
 511         node_t *to = lookup_node_id((node_id_t *)data);
 512         data += sizeof(node_id_t);
 513         len -= sizeof(node_id_t);
 514
 515         if(!to) {
 516                 logger(DEBUG_PROTOCOL, LOG_ERR, "Got TCP SPTPS packet from %s (%s) with unknown destination ID", c->name, c->hostname);
 517                 return true;
 518         }
 519
 520         node_t *from = lookup_node_id((node_id_t *)data);
 521         data += sizeof(node_id_t);
 522         len -= sizeof(node_id_t);
 523
 524         if(!from) {
 525                 logger(DEBUG_PROTOCOL, LOG_ERR, "Got TCP SPTPS packet from %s (%s) with unknown source ID", c->name, c->hostname);
 526                 return true;
 527         }
 528
 529         if(!to->status.reachable) {
 530                 /* This can happen in the form of a race condition
 531                    if the node just became unreachable. */
 532                 logger(DEBUG_TRAFFIC, LOG_WARNING, "Cannot relay TCP packet from %s (%s) because the destination, %s (%s), is unreachable", from->name, from->hostname, to->name, to->hostname);
 533                 return true;
 534         }
 535
 536         /* Help the sender reach us over UDP.
 537            Note that we only do this if we're the destination or the static relay;
 538            otherwise every hop would initiate its own UDP info message, resulting in elevated chatter. */
 539         if(to->via == myself) {
 540                 send_udp_info(myself, from);
 541         }
 542
 543         /* If we're not the final recipient, relay the packet. */
 544
 545         if(to != myself) {
 546                 send_sptps_data(to, from, 0, data, len);
 547                 try_tx(to, true);
 548                 return true;
 549         }
 550
 551         /* The packet is for us */
 552
 553         if(!sptps_receive_data(&from->sptps, data, len)) {
 554                 /* Uh-oh. It might be that the tunnel is stuck in some corrupted state,
 555                    so let's restart SPTPS in case that helps. But don't do that too often
 556                    to prevent storms. */
 557                 if(from->last_req_key < now.tv_sec - 10) {
 558                         logger(DEBUG_PROTOCOL, LOG_ERR, "Failed to decode raw TCP packet from %s (%s), restarting SPTPS", from->name, from->hostname);
 559                         send_req_key(from);
 560                 }
 561
 562                 return true;
 563         }
 564
 565         send_mtu_info(myself, from, MTU);
 566         return true;
 567 }
 568
 569 static void send_sptps_packet(node_t *n, vpn_packet_t *origpkt) {
 570         if(!n->status.validkey && !n->connection) {
 571                 return;
 572         }
 573
 574         uint8_t type = 0;
 575         int offset = 0;
 576
 577         if((!(DATA(origpkt)[12] | DATA(origpkt)[13])) && (n->sptps.outstate))  {
 578                 sptps_send_record(&n->sptps, PKT_PROBE, (char *)DATA(origpkt), origpkt->len);
 579                 return;
 580         }
 581
 582         if(routing_mode == RMODE_ROUTER) {
 583                 offset = 14;
 584         } else {
 585                 type = PKT_MAC;
 586         }
 587
 588         if(origpkt->len < offset) {
 589                 return;
 590         }
 591
 592         vpn_packet_t outpkt;
 593
 594         if(n->outcompression) {
 595                 outpkt.offset = 0;
 596                 int len = compress_packet(DATA(&outpkt) + offset, DATA(origpkt) + offset, origpkt->len - offset, n->outcompression);
 597
 598                 if(len < 0) {
 599                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while compressing packet to %s (%s)", n->name, n->hostname);
 600                 } else if(len < origpkt->len - offset) {
 601                         outpkt.len = len + offset;
 602                         origpkt = &outpkt;
 603                         type |= PKT_COMPRESSED;
 604                 }
 605         }
 606
 607         /* If we have a direct metaconnection to n, and we can't use UDP, then
 608            don't bother with SPTPS and just use a "plaintext" PACKET message.
 609            We don't really care about end-to-end security since we're not
 610            sending the message through any intermediate nodes. */
 611         if(n->connection && origpkt->len > n->minmtu) {
 612                 send_tcppacket(n->connection, origpkt);
 613         } else {
 614                 sptps_send_record(&n->sptps, type, DATA(origpkt) + offset, origpkt->len - offset);
 615         }
 616
 617         return;
 618 }
 619
 620 static void adapt_socket(const sockaddr_t *sa, int *sock) {
 621         /* Make sure we have a suitable socket for the chosen address */
 622         if(listen_socket[*sock].sa.sa.sa_family != sa->sa.sa_family) {
 623                 for(int i = 0; i < listen_sockets; i++) {
 624                         if(listen_socket[i].sa.sa.sa_family == sa->sa.sa_family) {
 625                                 *sock = i;
 626                                 break;
 627                         }
 628                 }
 629         }
 630 }
 631
 632 static void choose_udp_address(const node_t *n, const sockaddr_t **sa, int *sock) {
 633         /* Latest guess */
 634         *sa = &n->address;
 635         *sock = n->sock;
 636
 637         /* If the UDP address is confirmed, use it. */
 638         if(n->status.udp_confirmed) {
 639                 return;
 640         }
 641
 642         /* Send every third packet to n->address; that could be set
 643            to the node's reflexive UDP address discovered during key
 644            exchange. */
 645
 646         static int x = 0;
 647
 648         if(++x >= 3) {
 649                 x = 0;
 650                 return;
 651         }
 652
 653         /* Otherwise, address are found in edges to this node.
 654            So we pick a random edge and a random socket. */
 655
 656         int i = 0;
 657         int j = rand() % n->edge_tree->count;
 658         edge_t *candidate = NULL;
 659
 660         for splay_each(edge_t, e, n->edge_tree) {
 661                 if(i++ == j) {
 662                         candidate = e->reverse;
 663                         break;
 664                 }
 665         }
 666
 667         if(candidate) {
 668                 *sa = &candidate->address;
 669                 *sock = rand() % listen_sockets;
 670         }
 671
 672         adapt_socket(*sa, sock);
 673 }
 674
 675 static void choose_local_address(const node_t *n, const sockaddr_t **sa, int *sock) {
 676         *sa = NULL;
 677
 678         /* Pick one of the edges from this node at random, then use its local address. */
 679
 680         int i = 0;
 681         int j = rand() % n->edge_tree->count;
 682         edge_t *candidate = NULL;
 683
 684         for splay_each(edge_t, e, n->edge_tree) {
 685                 if(i++ == j) {
 686                         candidate = e;
 687                         break;
 688                 }
 689         }
 690
 691         if(candidate && candidate->local_address.sa.sa_family) {
 692                 *sa = &candidate->local_address;
 693                 *sock = rand() % listen_sockets;
 694                 adapt_socket(*sa, sock);
 695         }
 696 }
 697
 698 static void send_udppacket(node_t *n, vpn_packet_t *origpkt) {
 699         vpn_packet_t pkt1, pkt2;
 700         vpn_packet_t *pkt[] = { &pkt1, &pkt2, &pkt1, &pkt2 };
 701         vpn_packet_t *inpkt = origpkt;
 702         int nextpkt = 0;
 703         vpn_packet_t *outpkt;
 704         int origlen = origpkt->len;
 705         size_t outlen;
 706         int origpriority = origpkt->priority;
 707
 708         pkt1.offset = DEFAULT_PACKET_OFFSET;
 709         pkt2.offset = DEFAULT_PACKET_OFFSET;
 710
 711         if(!n->status.reachable) {
 712                 logger(DEBUG_TRAFFIC, LOG_INFO, "Trying to send UDP packet to unreachable node %s (%s)", n->name, n->hostname);
 713                 return;
 714         }
 715
 716         if(n->status.sptps) {
 717                 send_sptps_packet(n, origpkt);
 718                 return;
 719         }
 720
 721 #ifdef DISABLE_LEGACY
 722         return;
 723 #else
 724         /* Make sure we have a valid key */
 725
 726         if(!n->status.validkey) {
 727                 logger(DEBUG_TRAFFIC, LOG_INFO,
 728                        "No valid key known yet for %s (%s), forwarding via TCP",
 729                        n->name, n->hostname);
 730                 send_tcppacket(n->nexthop->connection, origpkt);
 731                 return;
 732         }
 733
 734         if(n->options & OPTION_PMTU_DISCOVERY && inpkt->len > n->minmtu && (DATA(inpkt)[12] | DATA(inpkt)[13])) {
 735                 logger(DEBUG_TRAFFIC, LOG_INFO,
 736                        "Packet for %s (%s) larger than minimum MTU, forwarding via %s",
 737                        n->name, n->hostname, n != n->nexthop ? n->nexthop->name : "TCP");
 738
 739                 if(n != n->nexthop) {
 740                         send_packet(n->nexthop, origpkt);
 741                 } else {
 742                         send_tcppacket(n->nexthop->connection, origpkt);
 743                 }
 744
 745                 return;
 746         }
 747
 748         /* Compress the packet */
 749
 750         if(n->outcompression) {
 751                 outpkt = pkt[nextpkt++];
 752
 753                 if((outpkt->len = compress_packet(DATA(outpkt), DATA(inpkt), inpkt->len, n->outcompression)) < 0) {
 754                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while compressing packet to %s (%s)",
 755                                n->name, n->hostname);
 756                         return;
 757                 }
 758
 759                 inpkt = outpkt;
 760         }
 761
 762         /* Add sequence number */
 763
 764         seqno_t seqno = htonl(++(n->sent_seqno));
 765         memcpy(SEQNO(inpkt), &seqno, sizeof(seqno));
 766         inpkt->len += sizeof(seqno);
 767
 768         /* Encrypt the packet */
 769
 770         if(cipher_active(n->outcipher)) {
 771                 outpkt = pkt[nextpkt++];
 772                 outlen = MAXSIZE;
 773
 774                 if(!cipher_encrypt(n->outcipher, SEQNO(inpkt), inpkt->len, SEQNO(outpkt), &outlen, true)) {
 775                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while encrypting packet to %s (%s)", n->name, n->hostname);
 776                         goto end;
 777                 }
 778
 779                 outpkt->len = outlen;
 780                 inpkt = outpkt;
 781         }
 782
 783         /* Add the message authentication code */
 784
 785         if(digest_active(n->outdigest)) {
 786                 if(!digest_create(n->outdigest, SEQNO(inpkt), inpkt->len, SEQNO(inpkt) + inpkt->len)) {
 787                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while encrypting packet to %s (%s)", n->name, n->hostname);
 788                         goto end;
 789                 }
 790
 791                 inpkt->len += digest_length(n->outdigest);
 792         }
 793
 794         /* Send the packet */
 795
 796         const sockaddr_t *sa = NULL;
 797         int sock;
 798
 799         if(n->status.send_locally) {
 800                 choose_local_address(n, &sa, &sock);
 801         }
 802
 803         if(!sa) {
 804                 choose_udp_address(n, &sa, &sock);
 805         }
 806
 807         if(priorityinheritance && origpriority != listen_socket[sock].priority) {
 808                 listen_socket[sock].priority = origpriority;
 809
 810                 switch(sa->sa.sa_family) {
 811 #if defined(IP_TOS)
 812
 813                 case AF_INET:
 814                         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Setting IPv4 outgoing packet priority to %d", origpriority);
 815
 816                         if(setsockopt(listen_socket[sock].udp.fd, IPPROTO_IP, IP_TOS, (void *)&origpriority, sizeof(origpriority))) { /* SO_PRIORITY doesn't seem to work */
 817                                 logger(DEBUG_ALWAYS, LOG_ERR, "System call `%s' failed: %s", "setsockopt", sockstrerror(sockerrno));
 818                         }
 819
 820                         break;
 821 #endif
 822 #if defined(IPV6_TCLASS)
 823
 824                 case AF_INET6:
 825                         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Setting IPv6 outgoing packet priority to %d", origpriority);
 826
 827                         if(setsockopt(listen_socket[sock].udp.fd, IPPROTO_IPV6, IPV6_TCLASS, (void *)&origpriority, sizeof(origpriority))) { /* SO_PRIORITY doesn't seem to work */
 828                                 logger(DEBUG_ALWAYS, LOG_ERR, "System call `%s' failed: %s", "setsockopt", sockstrerror(sockerrno));
 829                         }
 830
 831                         break;
 832 #endif
 833
 834                 default:
 835                         break;
 836                 }
 837         }
 838
 839         if(sendto(listen_socket[sock].udp.fd, (void *)SEQNO(inpkt), inpkt->len, 0, &sa->sa, SALEN(sa->sa)) < 0 && !sockwouldblock(sockerrno)) {
 840                 if(sockmsgsize(sockerrno)) {
 841                         if(n->maxmtu >= origlen) {
 842                                 n->maxmtu = origlen - 1;
 843                         }
 844
 845                         if(n->mtu >= origlen) {
 846                                 n->mtu = origlen - 1;
 847                         }
 848
 849                         try_fix_mtu(n);
 850                 } else {
 851                         logger(DEBUG_TRAFFIC, LOG_WARNING, "Error sending packet to %s (%s): %s", n->name, n->hostname, sockstrerror(sockerrno));
 852                 }
 853         }
 854
 855 end:
 856         origpkt->len = origlen;
 857 #endif
 858 }
 859
 860 bool send_sptps_data(node_t *to, node_t *from, int type, const void *data, size_t len) {
 861         node_t *relay = (to->via != myself && (type == PKT_PROBE || (len - SPTPS_DATAGRAM_OVERHEAD) <= to->via->minmtu)) ? to->via : to->nexthop;
 862         bool direct = from == myself && to == relay;
 863         bool relay_supported = (relay->options >> 24) >= 4;
 864         bool tcponly = (myself->options | relay->options) & OPTION_TCPONLY;
 865
 866         /* Send it via TCP if it is a handshake packet, TCPOnly is in use, this is a relay packet that the other node cannot understand, or this packet is larger than the MTU. */
 867
 868         if(type == SPTPS_HANDSHAKE || tcponly || (!direct && !relay_supported) || (type != PKT_PROBE && (len - SPTPS_DATAGRAM_OVERHEAD) > relay->minmtu)) {
 869                 if(type != SPTPS_HANDSHAKE && (to->nexthop->connection->options >> 24) >= 7) {
 870                         char buf[len + sizeof(to->id) + sizeof(from->id)];
 871                         char *buf_ptr = buf;
 872                         memcpy(buf_ptr, &to->id, sizeof(to->id));
 873                         buf_ptr += sizeof(to->id);
 874                         memcpy(buf_ptr, &from->id, sizeof(from->id));
 875                         buf_ptr += sizeof(from->id);
 876                         memcpy(buf_ptr, data, len);
 877                         logger(DEBUG_TRAFFIC, LOG_INFO, "Sending packet from %s (%s) to %s (%s) via %s (%s) (TCP)", from->name, from->hostname, to->name, to->hostname, to->nexthop->name, to->nexthop->hostname);
 878                         return send_sptps_tcppacket(to->nexthop->connection, buf, sizeof(buf));
 879                 }
 880
 881                 char buf[len * 4 / 3 + 5];
 882                 b64encode(data, buf, len);
 883
 884                 /* If this is a handshake packet, use ANS_KEY instead of REQ_KEY, for two reasons:
 885                     - We don't want intermediate nodes to switch to UDP to relay these packets;
 886                     - ANS_KEY allows us to learn the reflexive UDP address. */
 887                 if(type == SPTPS_HANDSHAKE) {
 888                         to->incompression = myself->incompression;
 889                         return send_request(to->nexthop->connection, "%d %s %s %s -1 -1 -1 %d", ANS_KEY, from->name, to->name, buf, to->incompression);
 890                 } else {
 891                         return send_request(to->nexthop->connection, "%d %s %s %d %s", REQ_KEY, from->name, to->name, SPTPS_PACKET, buf);
 892                 }
 893         }
 894
 895         size_t overhead = 0;
 896
 897         if(relay_supported) {
 898                 overhead += sizeof(to->id) + sizeof(from->id);
 899         }
 900
 901         char buf[len + overhead];
 902         char *buf_ptr = buf;
 903
 904         if(relay_supported) {
 905                 if(direct) {
 906                         /* Inform the recipient that this packet was sent directly. */
 907                         node_id_t nullid = {{0}};
 908                         memcpy(buf_ptr, &nullid, sizeof(nullid));
 909                         buf_ptr += sizeof(nullid);
 910                 } else {
 911                         memcpy(buf_ptr, &to->id, sizeof(to->id));
 912                         buf_ptr += sizeof(to->id);
 913                 }
 914
 915                 memcpy(buf_ptr, &from->id, sizeof(from->id));
 916                 buf_ptr += sizeof(from->id);
 917
 918         }
 919
 920         /* TODO: if this copy turns out to be a performance concern, change sptps_send_record() to add some "pre-padding" to the buffer and use that instead */
 921         memcpy(buf_ptr, data, len);
 922         buf_ptr += len;
 923
 924         const sockaddr_t *sa = NULL;
 925         int sock;
 926
 927         if(relay->status.send_locally) {
 928                 choose_local_address(relay, &sa, &sock);
 929         }
 930
 931         if(!sa) {
 932                 choose_udp_address(relay, &sa, &sock);
 933         }
 934
 935         logger(DEBUG_TRAFFIC, LOG_INFO, "Sending packet from %s (%s) to %s (%s) via %s (%s) (UDP)", from->name, from->hostname, to->name, to->hostname, relay->name, relay->hostname);
 936
 937         if(sendto(listen_socket[sock].udp.fd, buf, buf_ptr - buf, 0, &sa->sa, SALEN(sa->sa)) < 0 && !sockwouldblock(sockerrno)) {
 938                 if(sockmsgsize(sockerrno)) {
 939                         // Compensate for SPTPS overhead
 940                         len -= SPTPS_DATAGRAM_OVERHEAD;
 941
 942                         if(relay->maxmtu >= len) {
 943                                 relay->maxmtu = len - 1;
 944                         }
 945
 946                         if(relay->mtu >= len) {
 947                                 relay->mtu = len - 1;
 948                         }
 949
 950                         try_fix_mtu(relay);
 951                 } else {
 952                         logger(DEBUG_TRAFFIC, LOG_WARNING, "Error sending UDP SPTPS packet to %s (%s): %s", relay->name, relay->hostname, sockstrerror(sockerrno));
 953                         return false;
 954                 }
 955         }
 956
 957         return true;
 958 }
 959
 960 bool receive_sptps_record(void *handle, uint8_t type, const void *data, uint16_t len) {
 961         node_t *from = handle;
 962
 963         if(type == SPTPS_HANDSHAKE) {
 964                 if(!from->status.validkey) {
 965                         from->status.validkey = true;
 966                         from->status.waitingforkey = false;
 967                         logger(DEBUG_META, LOG_INFO, "SPTPS key exchange with %s (%s) successful", from->name, from->hostname);
 968                 }
 969
 970                 return true;
 971         }
 972
 973         if(len > MTU) {
 974                 logger(DEBUG_ALWAYS, LOG_ERR, "Packet from %s (%s) larger than maximum supported size (%d > %d)", from->name, from->hostname, len, MTU);
 975                 return false;
 976         }
 977
 978         vpn_packet_t inpkt;
 979         inpkt.offset = DEFAULT_PACKET_OFFSET;
 980         inpkt.priority = 0;
 981
 982         if(type == PKT_PROBE) {
 983                 if(!from->status.udppacket) {
 984                         logger(DEBUG_ALWAYS, LOG_ERR, "Got SPTPS PROBE packet from %s (%s) via TCP", from->name, from->hostname);
 985                         return false;
 986                 }
 987
 988                 inpkt.len = len;
 989                 memcpy(DATA(&inpkt), data, len);
 990
 991                 if(inpkt.len > from->maxrecentlen) {
 992                         from->maxrecentlen = inpkt.len;
 993                 }
 994
 995                 udp_probe_h(from, &inpkt, len);
 996                 return true;
 997         }
 998
 999         if(type & ~(PKT_COMPRESSED | PKT_MAC)) {
1000                 logger(DEBUG_ALWAYS, LOG_ERR, "Unexpected SPTPS record type %d len %d from %s (%s)", type, len, from->name, from->hostname);
1001                 return false;
1002         }
1003
1004         /* Check if we have the headers we need */
1005         if(routing_mode != RMODE_ROUTER && !(type & PKT_MAC)) {
1006                 logger(DEBUG_TRAFFIC, LOG_ERR, "Received packet from %s (%s) without MAC header (maybe Mode is not set correctly)", from->name, from->hostname);
1007                 return false;
1008         } else if(routing_mode == RMODE_ROUTER && (type & PKT_MAC)) {
1009                 logger(DEBUG_TRAFFIC, LOG_WARNING, "Received packet from %s (%s) with MAC header (maybe Mode is not set correctly)", from->name, from->hostname);
1010         }
1011
1012         int offset = (type & PKT_MAC) ? 0 : 14;
1013
1014         if(type & PKT_COMPRESSED) {
1015                 length_t ulen = uncompress_packet(DATA(&inpkt) + offset, (const uint8_t *)data, len, from->incompression);
1016
1017                 if(ulen < 0) {
1018                         return false;
1019                 } else {
1020                         inpkt.len = ulen + offset;
1021                 }
1022
1023                 if(inpkt.len > MAXSIZE) {
1024                         abort();
1025                 }
1026         } else {
1027                 memcpy(DATA(&inpkt) + offset, data, len);
1028                 inpkt.len = len + offset;
1029         }
1030
1031         /* Generate the Ethernet packet type if necessary */
1032         if(offset) {
1033                 switch(DATA(&inpkt)[14] >> 4) {
1034                 case 4:
1035                         DATA(&inpkt)[12] = 0x08;
1036                         DATA(&inpkt)[13] = 0x00;
1037                         break;
1038
1039                 case 6:
1040                         DATA(&inpkt)[12] = 0x86;
1041                         DATA(&inpkt)[13] = 0xDD;
1042                         break;
1043
1044                 default:
1045                         logger(DEBUG_TRAFFIC, LOG_ERR,
1046                                "Unknown IP version %d while reading packet from %s (%s)",
1047                                DATA(&inpkt)[14] >> 4, from->name, from->hostname);
1048                         return false;
1049                 }
1050         }
1051
1052         if(from->status.udppacket && inpkt.len > from->maxrecentlen) {
1053                 from->maxrecentlen = inpkt.len;
1054         }
1055
1056         receive_packet(from, &inpkt);
1057         return true;
1058 }
1059
1060 // This function tries to get SPTPS keys, if they aren't already known.
1061 // This function makes no guarantees - it is up to the caller to check the node's state to figure out if the keys are available.
1062 static void try_sptps(node_t *n) {
1063         if(n->status.validkey) {
1064                 return;
1065         }
1066
1067         logger(DEBUG_TRAFFIC, LOG_INFO, "No valid key known yet for %s (%s)", n->name, n->hostname);
1068
1069         if(!n->status.waitingforkey) {
1070                 send_req_key(n);
1071         } else if(n->last_req_key + 10 < now.tv_sec) {
1072                 logger(DEBUG_ALWAYS, LOG_DEBUG, "No key from %s after 10 seconds, restarting SPTPS", n->name);
1073                 sptps_stop(&n->sptps);
1074                 n->status.waitingforkey = false;
1075                 send_req_key(n);
1076         }
1077
1078         return;
1079 }
1080
1081 static void send_udp_probe_packet(node_t *n, int len) {
1082         vpn_packet_t packet;
1083         packet.offset = DEFAULT_PACKET_OFFSET;
1084         memset(DATA(&packet), 0, 14);
1085         randomize(DATA(&packet) + 14, len - 14);
1086         packet.len = len;
1087         packet.priority = 0;
1088
1089         logger(DEBUG_TRAFFIC, LOG_INFO, "Sending UDP probe length %d to %s (%s)", len, n->name, n->hostname);
1090
1091         send_udppacket(n, &packet);
1092 }
1093
1094 // This function tries to establish a UDP tunnel to a node so that packets can be sent.
1095 // If a tunnel is already established, it makes sure it stays up.
1096 // This function makes no guarantees - it is up to the caller to check the node's state to figure out if UDP is usable.
1097 static void try_udp(node_t *n) {
1098         if(!udp_discovery) {
1099                 return;
1100         }
1101
1102         /* Send gratuitous probe replies to 1.1 nodes. */
1103
1104         if((n->options >> 24) >= 3 && n->status.udp_confirmed) {
1105                 struct timeval ping_tx_elapsed;
1106                 timersub(&now, &n->udp_reply_sent, &ping_tx_elapsed);
1107
1108                 if(ping_tx_elapsed.tv_sec >= udp_discovery_keepalive_interval - 1) {
1109                         n->udp_reply_sent = now;
1110
1111                         if(n->maxrecentlen) {
1112                                 vpn_packet_t pkt;
1113                                 pkt.len = n->maxrecentlen;
1114                                 pkt.offset = DEFAULT_PACKET_OFFSET;
1115                                 memset(DATA(&pkt), 0, 14);
1116                                 randomize(DATA(&pkt) + 14, MIN_PROBE_SIZE - 14);
1117                                 send_udp_probe_reply(n, &pkt, pkt.len);
1118                                 n->maxrecentlen = 0;
1119                         }
1120                 }
1121         }
1122
1123         /* Probe request */
1124
1125         struct timeval ping_tx_elapsed;
1126         timersub(&now, &n->udp_ping_sent, &ping_tx_elapsed);
1127
1128         int interval = n->status.udp_confirmed ? udp_discovery_keepalive_interval : udp_discovery_interval;
1129
1130         if(ping_tx_elapsed.tv_sec >= interval) {
1131                 gettimeofday(&now, NULL);
1132                 n->udp_ping_sent = now; // a probe in flight
1133                 send_udp_probe_packet(n, MIN_PROBE_SIZE);
1134
1135                 if(localdiscovery && !n->status.udp_confirmed && n->prevedge) {
1136                         n->status.send_locally = true;
1137                         send_udp_probe_packet(n, MIN_PROBE_SIZE);
1138                         n->status.send_locally = false;
1139                 }
1140         }
1141 }
1142
1143 static length_t choose_initial_maxmtu(node_t *n) {
1144 #ifdef IP_MTU
1145
1146         int sock = -1;
1147
1148         const sockaddr_t *sa = NULL;
1149         int sockindex;
1150         choose_udp_address(n, &sa, &sockindex);
1151
1152         if(!sa) {
1153                 return MTU;
1154         }
1155
1156         sock = socket(sa->sa.sa_family, SOCK_DGRAM, IPPROTO_UDP);
1157
1158         if(sock < 0) {
1159                 logger(DEBUG_TRAFFIC, LOG_ERR, "Creating MTU assessment socket for %s (%s) failed: %s", n->name, n->hostname, sockstrerror(sockerrno));
1160                 return MTU;
1161         }
1162
1163         if(connect(sock, &sa->sa, SALEN(sa->sa))) {
1164                 logger(DEBUG_TRAFFIC, LOG_ERR, "Connecting MTU assessment socket for %s (%s) failed: %s", n->name, n->hostname, sockstrerror(sockerrno));
1165                 close(sock);
1166                 return MTU;
1167         }
1168
1169         int ip_mtu;
1170         socklen_t ip_mtu_len = sizeof(ip_mtu);
1171
1172         if(getsockopt(sock, IPPROTO_IP, IP_MTU, &ip_mtu, &ip_mtu_len)) {
1173                 logger(DEBUG_TRAFFIC, LOG_ERR, "getsockopt(IP_MTU) on %s (%s) failed: %s", n->name, n->hostname, sockstrerror(sockerrno));
1174                 close(sock);
1175                 return MTU;
1176         }
1177
1178         close(sock);
1179
1180         /* getsockopt(IP_MTU) returns the MTU of the physical interface.
1181            We need to remove various overheads to get to the tinc MTU. */
1182         length_t mtu = ip_mtu;
1183         mtu -= (sa->sa.sa_family == AF_INET6) ? sizeof(struct ip6_hdr) : sizeof(struct ip);
1184         mtu -= 8; /* UDP */
1185
1186         if(n->status.sptps) {
1187                 mtu -= SPTPS_DATAGRAM_OVERHEAD;
1188
1189                 if((n->options >> 24) >= 4) {
1190                         mtu -= sizeof(node_id_t) + sizeof(node_id_t);
1191                 }
1192
1193 #ifndef DISABLE_LEGACY
1194         } else {
1195                 mtu -= digest_length(n->outdigest);
1196
1197                 /* Now it's tricky. We use CBC mode, so the length of the
1198                    encrypted payload must be a multiple of the blocksize. The
1199                    sequence number is also part of the encrypted payload, so we
1200                    must account for it after correcting for the blocksize.
1201                    Furthermore, the padding in the last block must be at least
1202                    1 byte. */
1203
1204                 length_t blocksize = cipher_blocksize(n->outcipher);
1205
1206                 if(blocksize > 1) {
1207                         mtu /= blocksize;
1208                         mtu *= blocksize;
1209                         mtu--;
1210                 }
1211
1212                 mtu -= 4; // seqno
1213 #endif
1214         }
1215
1216         if(mtu < 512) {
1217                 logger(DEBUG_TRAFFIC, LOG_ERR, "getsockopt(IP_MTU) on %s (%s) returned absurdly small value: %d", n->name, n->hostname, ip_mtu);
1218                 return MTU;
1219         }
1220
1221         if(mtu > MTU) {
1222                 return MTU;
1223         }
1224
1225         logger(DEBUG_TRAFFIC, LOG_INFO, "Using system-provided maximum tinc MTU for %s (%s): %hd", n->name, n->hostname, mtu);
1226         return mtu;
1227
1228 #else
1229
1230         return MTU;
1231
1232 #endif
1233 }
1234
1235 /* This function tries to determines the MTU of a node.
1236    By calling this function repeatedly, n->minmtu will be progressively
1237    increased, and at some point, n->mtu will be fixed to n->minmtu.  If the MTU
1238    is already fixed, this function checks if it can be increased.
1239 */
1240
1241 static void try_mtu(node_t *n) {
1242         if(!(n->options & OPTION_PMTU_DISCOVERY)) {
1243                 return;
1244         }
1245
1246         if(udp_discovery && !n->status.udp_confirmed) {
1247                 n->maxrecentlen = 0;
1248                 n->mtuprobes = 0;
1249                 n->minmtu = 0;
1250                 n->maxmtu = MTU;
1251                 return;
1252         }
1253
1254         /* mtuprobes == 0..19: initial discovery, send bursts with 1 second interval, mtuprobes++
1255            mtuprobes ==    20: fix MTU, and go to -1
1256            mtuprobes ==    -1: send one maxmtu and one maxmtu+1 probe every pinginterval
1257            mtuprobes ==-2..-3: send one maxmtu probe every second
1258            mtuprobes ==    -4: maxmtu no longer valid, reset minmtu and maxmtu and go to 0 */
1259
1260         struct timeval elapsed;
1261         timersub(&now, &n->mtu_ping_sent, &elapsed);
1262
1263         if(n->mtuprobes >= 0) {
1264                 if(n->mtuprobes != 0 && elapsed.tv_sec == 0 && elapsed.tv_usec < 333333) {
1265                         return;
1266                 }
1267         } else {
1268                 if(n->mtuprobes < -1) {
1269                         if(elapsed.tv_sec < 1) {
1270                                 return;
1271                         }
1272                 } else {
1273                         if(elapsed.tv_sec < pinginterval) {
1274                                 return;
1275                         }
1276                 }
1277         }
1278
1279         n->mtu_ping_sent = now;
1280
1281         try_fix_mtu(n);
1282
1283         if(n->mtuprobes < -3) {
1284                 /* We lost three MTU probes, restart discovery */
1285                 logger(DEBUG_TRAFFIC, LOG_INFO, "Decrease in PMTU to %s (%s) detected, restarting PMTU discovery", n->name, n->hostname);
1286                 n->mtuprobes = 0;
1287                 n->minmtu = 0;
1288         }
1289
1290         if(n->mtuprobes < 0) {
1291                 /* After the initial discovery, we only send one maxmtu and one
1292                    maxmtu+1 probe to detect PMTU increases. */
1293                 send_udp_probe_packet(n, n->maxmtu);
1294
1295                 if(n->mtuprobes == -1 && n->maxmtu + 1 < MTU) {
1296                         send_udp_probe_packet(n, n->maxmtu + 1);
1297                 }
1298
1299                 n->mtuprobes--;
1300         } else {
1301                 /* Before initial discovery begins, set maxmtu to the most likely value.
1302                    If it's underestimated, we will correct it after initial discovery. */
1303                 if(n->mtuprobes == 0) {
1304                         n->maxmtu = choose_initial_maxmtu(n);
1305                 }
1306
1307                 for(;;) {
1308                         /* Decreasing the number of probes per cycle might make the algorithm react faster to lost packets,
1309                            but it will typically increase convergence time in the no-loss case. */
1310                         const length_t probes_per_cycle = 8;
1311
1312                         /* This magic value was determined using math simulations.
1313                            It will result in a 1329-byte first probe, followed (if there was a reply) by a 1407-byte probe.
1314                            Since 1407 is just below the range of tinc MTUs over typical networks,
1315                            this fine-tuning allows tinc to cover a lot of ground very quickly.
1316                            This fine-tuning is only valid for maxmtu = MTU; if maxmtu is smaller,
1317                            then it's better to use a multiplier of 1. Indeed, this leads to an interesting scenario
1318                            if choose_initial_maxmtu() returns the actual MTU value - it will get confirmed with one single probe. */
1319                         const float multiplier = (n->maxmtu == MTU) ? 0.97 : 1;
1320
1321                         const float cycle_position = probes_per_cycle - (n->mtuprobes % probes_per_cycle) - 1;
1322                         const length_t minmtu = MAX(n->minmtu, 512);
1323                         const float interval = n->maxmtu - minmtu;
1324
1325                         /* The core of the discovery algorithm is this exponential.
1326                            It produces very large probes early in the cycle, and then it very quickly decreases the probe size.
1327                            This reflects the fact that in the most difficult cases, we don't get any feedback for probes that
1328                            are too large, and therefore we need to concentrate on small offsets so that we can quickly converge
1329                            on the precise MTU as we are approaching it.
1330                            The last probe of the cycle is always 1 byte in size - this is to make sure we'll get at least one
1331                            reply per cycle so that we can make progress. */
1332                         const length_t offset = powf(interval, multiplier * cycle_position / (probes_per_cycle - 1));
1333
1334                         length_t maxmtu = n->maxmtu;
1335                         send_udp_probe_packet(n, minmtu + offset);
1336
1337                         /* If maxmtu changed, it means the probe was rejected by the system because it was too large.
1338                            In that case, we recalculate with the new maxmtu and try again. */
1339                         if(n->mtuprobes < 0 || maxmtu == n->maxmtu) {
1340                                 break;
1341                         }
1342                 }
1343
1344                 if(n->mtuprobes >= 0) {
1345                         n->mtuprobes++;
1346                 }
1347         }
1348 }
1349
1350 /* These functions try to establish a tunnel to a node (or its relay) so that
1351    packets can be sent (e.g. exchange keys).
1352    If a tunnel is already established, it tries to improve it (e.g. by trying
1353    to establish a UDP tunnel instead of TCP).  This function makes no
1354    guarantees - it is up to the caller to check the node's state to figure out
1355    if TCP and/or UDP is usable.  By calling this function repeatedly, the
1356    tunnel is gradually improved until we hit the wall imposed by the underlying
1357    network environment.  It is recommended to call this function every time a
1358    packet is sent (or intended to be sent) to a node, so that the tunnel keeps
1359    improving as packets flow, and then gracefully downgrades itself as it goes
1360    idle.
1361 */
1362
1363 static void try_tx_sptps(node_t *n, bool mtu) {
1364         /* If n is a TCP-only neighbor, we'll only use "cleartext" PACKET
1365            messages anyway, so there's no need for SPTPS at all. */
1366
1367         if(n->connection && ((myself->options | n->options) & OPTION_TCPONLY)) {
1368                 return;
1369         }
1370
1371         /* Otherwise, try to do SPTPS authentication with n if necessary. */
1372
1373         try_sptps(n);
1374
1375         /* Do we need to statically relay packets? */
1376
1377         node_t *via = (n->via == myself) ? n->nexthop : n->via;
1378
1379         /* If we do have a static relay, try everything with that one instead, if it supports relaying. */
1380
1381         if(via != n) {
1382                 if((via->options >> 24) < 4) {
1383                         return;
1384                 }
1385
1386                 try_tx(via, mtu);
1387                 return;
1388         }
1389
1390         /* Otherwise, try to establish UDP connectivity. */
1391
1392         try_udp(n);
1393
1394         if(mtu) {
1395                 try_mtu(n);
1396         }
1397
1398         /* If we don't have UDP connectivity (yet), we need to use a dynamic relay (nexthop)
1399            while we try to establish direct connectivity. */
1400
1401         if(!n->status.udp_confirmed && n != n->nexthop && (n->nexthop->options >> 24) >= 4) {
1402                 try_tx(n->nexthop, mtu);
1403         }
1404 }
1405
1406 static void try_tx_legacy(node_t *n, bool mtu) {
1407         /* Does he have our key? If not, send one. */
1408
1409         if(!n->status.validkey_in) {
1410                 send_ans_key(n);
1411         }
1412
1413         /* Check if we already have a key, or request one. */
1414
1415         if(!n->status.validkey) {
1416                 if(n->last_req_key + 10 <= now.tv_sec) {
1417                         send_req_key(n);
1418                         n->last_req_key = now.tv_sec;
1419                 }
1420
1421                 return;
1422         }
1423
1424         try_udp(n);
1425
1426         if(mtu) {
1427                 try_mtu(n);
1428         }
1429 }
1430
1431 void try_tx(node_t *n, bool mtu) {
1432         if(!n->status.reachable) {
1433                 return;
1434         }
1435
1436         if(n->status.sptps) {
1437                 try_tx_sptps(n, mtu);
1438         } else {
1439                 try_tx_legacy(n, mtu);
1440         }
1441 }
1442
1443 void send_packet(node_t *n, vpn_packet_t *packet) {
1444         // If it's for myself, write it to the tun/tap device.
1445
1446         if(n == myself) {
1447                 if(overwrite_mac) {
1448                         memcpy(DATA(packet), mymac.x, ETH_ALEN);
1449                         // Use an arbitrary fake source address.
1450                         memcpy(DATA(packet) + ETH_ALEN, DATA(packet), ETH_ALEN);
1451                         DATA(packet)[ETH_ALEN * 2 - 1] ^= 0xFF;
1452                 }
1453
1454                 n->out_packets++;
1455                 n->out_bytes += packet->len;
1456                 devops.write(packet);
1457                 return;
1458         }
1459
1460         logger(DEBUG_TRAFFIC, LOG_ERR, "Sending packet of %d bytes to %s (%s)", packet->len, n->name, n->hostname);
1461
1462         // If the node is not reachable, drop it.
1463
1464         if(!n->status.reachable) {
1465                 logger(DEBUG_TRAFFIC, LOG_INFO, "Node %s (%s) is not reachable", n->name, n->hostname);
1466                 return;
1467         }
1468
1469         // Keep track of packet statistics.
1470
1471         n->out_packets++;
1472         n->out_bytes += packet->len;
1473
1474         // Check if it should be sent as an SPTPS packet.
1475
1476         if(n->status.sptps) {
1477                 send_sptps_packet(n, packet);
1478                 try_tx(n, true);
1479                 return;
1480         }
1481
1482         // Determine which node to actually send it to.
1483
1484         node_t *via = (packet->priority == -1 || n->via == myself) ? n->nexthop : n->via;
1485
1486         if(via != n) {
1487                 logger(DEBUG_TRAFFIC, LOG_INFO, "Sending packet to %s via %s (%s)", n->name, via->name, n->via->hostname);
1488         }
1489
1490         // Try to send via UDP, unless TCP is forced.
1491
1492         if(packet->priority == -1 || ((myself->options | via->options) & OPTION_TCPONLY)) {
1493                 if(!send_tcppacket(via->connection, packet)) {
1494                         terminate_connection(via->connection, true);
1495                 }
1496
1497                 return;
1498         }
1499
1500         send_udppacket(via, packet);
1501         try_tx(via, true);
1502 }
1503
1504 void broadcast_packet(const node_t *from, vpn_packet_t *packet) {
1505         // Always give ourself a copy of the packet.
1506         if(from != myself) {
1507                 send_packet(myself, packet);
1508         }
1509
1510         // In TunnelServer mode, do not forward broadcast packets.
1511         // The MST might not be valid and create loops.
1512         if(tunnelserver || broadcast_mode == BMODE_NONE) {
1513                 return;
1514         }
1515
1516         logger(DEBUG_TRAFFIC, LOG_INFO, "Broadcasting packet of %d bytes from %s (%s)",
1517                packet->len, from->name, from->hostname);
1518
1519         switch(broadcast_mode) {
1520         // In MST mode, broadcast packets travel via the Minimum Spanning Tree.
1521         // This guarantees all nodes receive the broadcast packet, and
1522         // usually distributes the sending of broadcast packets over all nodes.
1523         case BMODE_MST:
1524                 for list_each(connection_t, c, connection_list)
1525                         if(c->edge && c->status.mst && c != from->nexthop->connection) {
1526                                 send_packet(c->node, packet);
1527                         }
1528
1529                 break;
1530
1531         // In direct mode, we send copies to each node we know of.
1532         // However, this only reaches nodes that can be reached in a single hop.
1533         // We don't have enough information to forward broadcast packets in this case.
1534         case BMODE_DIRECT:
1535                 if(from != myself) {
1536                         break;
1537                 }
1538
1539                 for splay_each(node_t, n, node_tree)
1540                         if(n->status.reachable && n != myself && ((n->via == myself && n->nexthop == n) || n->via == n)) {
1541                                 send_packet(n, packet);
1542                         }
1543
1544                 break;
1545
1546         default:
1547                 break;
1548         }
1549 }
1550
1551 /* We got a packet from some IP address, but we don't know who sent it.  Try to
1552    verify the message authentication code against all active session keys.
1553    Since this is actually an expensive operation, we only do a full check once
1554    a minute, the rest of the time we only check against nodes for which we know
1555    an IP address that matches the one from the packet.  */
1556
1557 static node_t *try_harder(const sockaddr_t *from, const vpn_packet_t *pkt) {
1558         node_t *match = NULL;
1559         bool hard = false;
1560         static time_t last_hard_try = 0;
1561
1562         for splay_each(node_t, n, node_tree) {
1563                 if(!n->status.reachable || n == myself) {
1564                         continue;
1565                 }
1566
1567                 if(!n->status.validkey_in && !(n->status.sptps && n->sptps.instate)) {
1568                         continue;
1569                 }
1570
1571                 bool soft = false;
1572
1573                 for splay_each(edge_t, e, n->edge_tree) {
1574                         if(!e->reverse) {
1575                                 continue;
1576                         }
1577
1578                         if(!sockaddrcmp_noport(from, &e->reverse->address)) {
1579                                 soft = true;
1580                                 break;
1581                         }
1582                 }
1583
1584                 if(!soft) {
1585                         if(last_hard_try == now.tv_sec) {
1586                                 continue;
1587                         }
1588
1589                         hard = true;
1590                 }
1591
1592                 if(!try_mac(n, pkt)) {
1593                         continue;
1594                 }
1595
1596                 match = n;
1597                 break;
1598         }
1599
1600         if(hard) {
1601                 last_hard_try = now.tv_sec;
1602         }
1603
1604         return match;
1605 }
1606
1607 static void handle_incoming_vpn_packet(listen_socket_t *ls, vpn_packet_t *pkt, sockaddr_t *addr) {
1608         char *hostname;
1609         node_id_t nullid = {{0}};
1610         node_t *from, *to;
1611         bool direct = false;
1612
1613         sockaddrunmap(addr); /* Some braindead IPv6 implementations do stupid things. */
1614
1615         // Try to figure out who sent this packet.
1616
1617         node_t *n = lookup_node_udp(addr);
1618
1619         if(n && !n->status.udp_confirmed) {
1620                 n = NULL;        // Don't believe it if we don't have confirmation yet.
1621         }
1622
1623         if(!n) {
1624                 // It might be from a 1.1 node, which might have a source ID in the packet.
1625                 pkt->offset = 2 * sizeof(node_id_t);
1626                 from = lookup_node_id(SRCID(pkt));
1627
1628                 if(from && !memcmp(DSTID(pkt), &nullid, sizeof(nullid)) && from->status.sptps) {
1629                         if(sptps_verify_datagram(&from->sptps, DATA(pkt), pkt->len - 2 * sizeof(node_id_t))) {
1630                                 n = from;
1631                         } else {
1632                                 goto skip_harder;
1633                         }
1634                 }
1635         }
1636
1637         if(!n) {
1638                 pkt->offset = 0;
1639                 n = try_harder(addr, pkt);
1640         }
1641
1642 skip_harder:
1643
1644         if(!n) {
1645                 if(debug_level >= DEBUG_PROTOCOL) {
1646                         hostname = sockaddr2hostname(addr);
1647                         logger(DEBUG_PROTOCOL, LOG_WARNING, "Received UDP packet from unknown source %s", hostname);
1648                         free(hostname);
1649                 }
1650
1651                 return;
1652         }
1653
1654         pkt->offset = 0;
1655
1656         if(n->status.sptps) {
1657                 bool relay_enabled = (n->options >> 24) >= 4;
1658
1659                 if(relay_enabled) {
1660                         pkt->offset = 2 * sizeof(node_id_t);
1661                         pkt->len -= pkt->offset;
1662                 }
1663
1664                 if(!memcmp(DSTID(pkt), &nullid, sizeof(nullid)) || !relay_enabled) {
1665                         direct = true;
1666                         from = n;
1667                         to = myself;
1668                 } else {
1669                         from = lookup_node_id(SRCID(pkt));
1670                         to = lookup_node_id(DSTID(pkt));
1671                 }
1672
1673                 if(!from || !to) {
1674                         logger(DEBUG_PROTOCOL, LOG_WARNING, "Received UDP packet from %s (%s) with unknown source and/or destination ID", n->name, n->hostname);
1675                         return;
1676                 }
1677
1678                 if(!to->status.reachable) {
1679                         /* This can happen in the form of a race condition
1680                            if the node just became unreachable. */
1681                         logger(DEBUG_TRAFFIC, LOG_WARNING, "Cannot relay packet from %s (%s) because the destination, %s (%s), is unreachable", from->name, from->hostname, to->name, to->hostname);
1682                         return;
1683                 }
1684
1685                 /* The packet is supposed to come from the originator or its static relay
1686                    (i.e. with no dynamic relays in between).
1687                    If it did not, "help" the static relay by sending it UDP info.
1688                    Note that we only do this if we're the destination or the static relay;
1689                    otherwise every hop would initiate its own UDP info message, resulting in elevated chatter. */
1690
1691                 if(n != from->via && to->via == myself) {
1692                         send_udp_info(myself, from);
1693                 }
1694
1695                 /* If we're not the final recipient, relay the packet. */
1696
1697                 if(to != myself) {
1698                         send_sptps_data(to, from, 0, DATA(pkt), pkt->len);
1699                         try_tx(to, true);
1700                         return;
1701                 }
1702         } else {
1703                 direct = true;
1704                 from = n;
1705         }
1706
1707         if(!receive_udppacket(from, pkt)) {
1708                 return;
1709         }
1710
1711         n->sock = ls - listen_socket;
1712
1713         if(direct && sockaddrcmp(addr, &n->address)) {
1714                 update_node_udp(n, addr);
1715         }
1716
1717         /* If the packet went through a relay, help the sender find the appropriate MTU
1718            through the relay path. */
1719
1720         if(!direct) {
1721                 send_mtu_info(myself, n, MTU);
1722         }
1723 }
1724
1725 void handle_incoming_vpn_data(void *data, int flags) {
1726         listen_socket_t *ls = data;
1727
1728 #ifdef HAVE_RECVMMSG
1729 #define MAX_MSG 64
1730         static int num = MAX_MSG;
1731         static vpn_packet_t pkt[MAX_MSG];
1732         static sockaddr_t addr[MAX_MSG];
1733         static struct mmsghdr msg[MAX_MSG];
1734         static struct iovec iov[MAX_MSG];
1735
1736         for(int i = 0; i < num; i++) {
1737                 pkt[i].offset = 0;
1738
1739                 iov[i] = (struct iovec) {
1740                         .iov_base = DATA(&pkt[i]),
1741                         .iov_len = MAXSIZE,
1742                 };
1743
1744                 msg[i].msg_hdr = (struct msghdr) {
1745                         .msg_name = &addr[i].sa,
1746                         .msg_namelen = sizeof(addr)[i],
1747                         .msg_iov = &iov[i],
1748                         .msg_iovlen = 1,
1749                 };
1750         }
1751
1752         num = recvmmsg(ls->udp.fd, msg, MAX_MSG, MSG_DONTWAIT, NULL);
1753
1754         if(num < 0) {
1755                 if(!sockwouldblock(sockerrno)) {
1756                         logger(DEBUG_ALWAYS, LOG_ERR, "Receiving packet failed: %s", sockstrerror(sockerrno));
1757                 }
1758
1759                 return;
1760         }
1761
1762         for(int i = 0; i < num; i++) {
1763                 pkt[i].len = msg[i].msg_len;
1764
1765                 if(pkt[i].len <= 0 || pkt[i].len > MAXSIZE) {
1766                         continue;
1767                 }
1768
1769                 handle_incoming_vpn_packet(ls, &pkt[i], &addr[i]);
1770         }
1771
1772 #else
1773         vpn_packet_t pkt;
1774         sockaddr_t addr = {};
1775         socklen_t addrlen = sizeof(addr);
1776
1777         pkt.offset = 0;
1778         int len = recvfrom(ls->udp.fd, (void *)DATA(&pkt), MAXSIZE, 0, &addr.sa, &addrlen);
1779
1780         if(len <= 0 || len > MAXSIZE) {
1781                 if(!sockwouldblock(sockerrno)) {
1782                         logger(DEBUG_ALWAYS, LOG_ERR, "Receiving packet failed: %s", sockstrerror(sockerrno));
1783                 }
1784
1785                 return;
1786         }
1787
1788         pkt.len = len;
1789
1790         handle_incoming_vpn_packet(ls, &pkt, &addr);
1791 #endif
1792 }
1793
1794 void handle_device_data(void *data, int flags) {
1795         vpn_packet_t packet;
1796         packet.offset = DEFAULT_PACKET_OFFSET;
1797         packet.priority = 0;
1798         static int errors = 0;
1799
1800         if(devops.read(&packet)) {
1801                 errors = 0;
1802                 myself->in_packets++;
1803                 myself->in_bytes += packet.len;
1804                 route(myself, &packet);
1805         } else {
1806                 usleep(errors * 50000);
1807                 errors++;
1808
1809                 if(errors > 10) {
1810                         logger(DEBUG_ALWAYS, LOG_ERR, "Too many errors from %s, exiting!", device);
1811                         event_exit();
1812                 }
1813         }
1814 }