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