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