tinc-vpn.org Git - tinc/blob - src/net_packet.c

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