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