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