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-2013 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 #include <zlib.h>
  27 #endif
  28
  29 #ifdef HAVE_LZO
  30 #include LZO1X_H
  31 #endif
  32
  33 #include "cipher.h"
  34 #include "conf.h"
  35 #include "connection.h"
  36 #include "crypto.h"
  37 #include "digest.h"
  38 #include "device.h"
  39 #include "ethernet.h"
  40 #include "graph.h"
  41 #include "logger.h"
  42 #include "net.h"
  43 #include "netutl.h"
  44 #include "protocol.h"
  45 #include "route.h"
  46 #include "utils.h"
  47 #include "xalloc.h"
  48
  49 int keylifetime = 0;
  50 #ifdef HAVE_LZO
  51 static char lzo_wrkmem[LZO1X_999_MEM_COMPRESS > LZO1X_1_MEM_COMPRESS ? LZO1X_999_MEM_COMPRESS : LZO1X_1_MEM_COMPRESS];
  52 #endif
  53
  54 static void send_udppacket(node_t *, vpn_packet_t *);
  55
  56 unsigned replaywin = 16;
  57 bool localdiscovery = true;
  58
  59 #define MAX_SEQNO 1073741824
  60
  61 /* mtuprobes == 1..30: initial discovery, send bursts with 1 second interval
  62    mtuprobes ==    31: sleep pinginterval seconds
  63    mtuprobes ==    32: send 1 burst, sleep pingtimeout second
  64    mtuprobes ==    33: no response from other side, restart PMTU discovery process
  65
  66    Probes are sent in batches of at least three, with random sizes between the
  67    lower and upper boundaries for the MTU thus far discovered.
  68
  69    After the initial discovery, a fourth packet is added to each batch with a
  70    size larger than the currently known PMTU, to test if the PMTU has increased.
  71
  72    In case local discovery is enabled, another packet is added to each batch,
  73    which will be broadcast to the local network.
  74
  75 */
  76
  77 static void send_mtu_probe_handler(void *data) {
  78         node_t *n = data;
  79         int timeout = 1;
  80
  81         n->mtuprobes++;
  82
  83         if(!n->status.reachable || !n->status.validkey) {
  84                 logger(DEBUG_TRAFFIC, LOG_INFO, "Trying to send MTU probe to unreachable or rekeying node %s (%s)", n->name, n->hostname);
  85                 n->mtuprobes = 0;
  86                 return;
  87         }
  88
  89         if(n->mtuprobes > 32) {
  90                 if(!n->minmtu) {
  91                         n->mtuprobes = 31;
  92                         timeout = pinginterval;
  93                         goto end;
  94                 }
  95
  96                 logger(DEBUG_TRAFFIC, LOG_INFO, "%s (%s) did not respond to UDP ping, restarting PMTU discovery", n->name, n->hostname);
  97                 n->status.udp_confirmed = false;
  98                 n->mtuprobes = 1;
  99                 n->minmtu = 0;
 100                 n->maxmtu = MTU;
 101         }
 102
 103         if(n->mtuprobes >= 10 && n->mtuprobes < 32 && !n->minmtu) {
 104                 logger(DEBUG_TRAFFIC, LOG_INFO, "No response to MTU probes from %s (%s)", n->name, n->hostname);
 105                 n->mtuprobes = 31;
 106         }
 107
 108         if(n->mtuprobes == 30 || (n->mtuprobes < 30 && n->minmtu >= n->maxmtu)) {
 109                 if(n->minmtu > n->maxmtu)
 110                         n->minmtu = n->maxmtu;
 111                 else
 112                         n->maxmtu = n->minmtu;
 113                 n->mtu = n->minmtu;
 114                 logger(DEBUG_TRAFFIC, LOG_INFO, "Fixing MTU of %s (%s) to %d after %d probes", n->name, n->hostname, n->mtu, n->mtuprobes);
 115                 n->mtuprobes = 31;
 116         }
 117
 118         if(n->mtuprobes == 31) {
 119                 timeout = pinginterval;
 120                 goto end;
 121         } else if(n->mtuprobes == 32) {
 122                 timeout = pingtimeout;
 123         }
 124
 125         for(int i = 0; i < 4 + localdiscovery; i++) {
 126                 int len;
 127
 128                 if(i == 0) {
 129                         if(n->mtuprobes < 30 || n->maxmtu + 8 >= MTU)
 130                                 continue;
 131                         len = n->maxmtu + 8;
 132                 } else if(n->maxmtu <= n->minmtu) {
 133                         len = n->maxmtu;
 134                 } else {
 135                         len = n->minmtu + 1 + rand() % (n->maxmtu - n->minmtu);
 136                 }
 137
 138                 if(len < 64)
 139                         len = 64;
 140
 141                 vpn_packet_t packet;
 142                 memset(packet.data, 0, 14);
 143                 randomize(packet.data + 14, len - 14);
 144                 packet.len = len;
 145                 packet.priority = 0;
 146                 n->status.send_locally = i >= 4 && n->mtuprobes <= 10 && n->prevedge;
 147
 148                 logger(DEBUG_TRAFFIC, LOG_INFO, "Sending MTU probe length %d to %s (%s)", len, n->name, n->hostname);
 149
 150                 send_udppacket(n, &packet);
 151         }
 152
 153         n->status.send_locally = false;
 154         n->probe_counter = 0;
 155         gettimeofday(&n->probe_time, NULL);
 156
 157         /* Calculate the packet loss of incoming traffic by comparing the rate of
 158            packets received to the rate with which the sequence number has increased.
 159          */
 160
 161         if(n->received > n->prev_received)
 162                 n->packetloss = 1.0 - (n->received - n->prev_received) / (float)(n->received_seqno - n->prev_received_seqno);
 163         else
 164                 n->packetloss = n->received_seqno <= n->prev_received_seqno;
 165
 166         n->prev_received_seqno = n->received_seqno;
 167         n->prev_received = n->received;
 168
 169 end:
 170         timeout_set(&n->mtutimeout, &(struct timeval){timeout, rand() % 100000});
 171 }
 172
 173 void send_mtu_probe(node_t *n) {
 174         timeout_add(&n->mtutimeout, send_mtu_probe_handler, n, &(struct timeval){1, 0});
 175         send_mtu_probe_handler(n);
 176 }
 177
 178 static void mtu_probe_h(node_t *n, vpn_packet_t *packet, length_t len) {
 179         if(!packet->data[0]) {
 180                 logger(DEBUG_TRAFFIC, LOG_INFO, "Got MTU probe request %d from %s (%s)", packet->len, n->name, n->hostname);
 181
 182                 /* It's a probe request, send back a reply */
 183
 184                 /* Type 2 probe replies were introduced in protocol 17.3 */
 185                 if ((n->options >> 24) >= 3) {
 186                         uint8_t* data = packet->data;
 187                         *data++ = 2;
 188                         uint16_t len16 = htons(len); memcpy(data, &len16, 2); data += 2;
 189                         struct timeval now;
 190                         gettimeofday(&now, NULL);
 191                         uint32_t sec = htonl(now.tv_sec); memcpy(data, &sec, 4); data += 4;
 192                         uint32_t usec = htonl(now.tv_usec); memcpy(data, &usec, 4); data += 4;
 193                         packet->len = data - packet->data;
 194                 } else {
 195                         /* Legacy protocol: n won't understand type 2 probe replies. */
 196                         packet->data[0] = 1;
 197                 }
 198
 199                 /* Temporarily set udp_confirmed, so that the reply is sent
 200                    back exactly the way it came in. */
 201
 202                 bool udp_confirmed = n->status.udp_confirmed;
 203                 n->status.udp_confirmed = true;
 204                 send_udppacket(n, packet);
 205                 n->status.udp_confirmed = udp_confirmed;
 206         } else {
 207                 length_t probelen = len;
 208                 if (packet->data[0] == 2) {
 209                         if (len < 3)
 210                                 logger(DEBUG_TRAFFIC, LOG_WARNING, "Received invalid (too short) MTU probe reply from %s (%s)", n->name, n->hostname);
 211                         else {
 212                                 uint16_t probelen16; memcpy(&probelen16, packet->data + 1, 2); probelen = ntohs(probelen16);
 213                         }
 214                 }
 215                 logger(DEBUG_TRAFFIC, LOG_INFO, "Got type %d MTU probe reply %d from %s (%s)", packet->data[0], probelen, n->name, n->hostname);
 216
 217                 /* It's a valid reply: now we know bidirectional communication
 218                    is possible using the address and socket that the reply
 219                    packet used. */
 220
 221                 n->status.udp_confirmed = true;
 222
 223                 /* If we haven't established the PMTU yet, restart the discovery process. */
 224
 225                 if(n->mtuprobes > 30) {
 226                         if (probelen == n->maxmtu + 8) {
 227                                 logger(DEBUG_TRAFFIC, LOG_INFO, "Increase in PMTU to %s (%s) detected, restarting PMTU discovery", n->name, n->hostname);
 228                                 n->maxmtu = MTU;
 229                                 n->mtuprobes = 10;
 230                                 return;
 231                         }
 232
 233                         if(n->minmtu)
 234                                 n->mtuprobes = 30;
 235                         else
 236                                 n->mtuprobes = 1;
 237                 }
 238
 239                 /* If applicable, raise the minimum supported MTU */
 240
 241                 if(probelen > n->maxmtu)
 242                         probelen = n->maxmtu;
 243                 if(n->minmtu < probelen)
 244                         n->minmtu = probelen;
 245
 246                 /* Calculate RTT and bandwidth.
 247                    The RTT is the time between the MTU probe burst was sent and the first
 248                    reply is received. The bandwidth is measured using the time between the
 249                    arrival of the first and third probe reply (or type 2 probe requests).
 250                  */
 251
 252                 struct timeval now, diff;
 253                 gettimeofday(&now, NULL);
 254                 timersub(&now, &n->probe_time, &diff);
 255
 256                 struct timeval probe_timestamp = now;
 257                 if (packet->data[0] == 2 && packet->len >= 11) {
 258                         uint32_t sec; memcpy(&sec, packet->data + 3, 4);
 259                         uint32_t usec; memcpy(&usec, packet->data + 7, 4);
 260                         probe_timestamp.tv_sec = ntohl(sec);
 261                         probe_timestamp.tv_usec = ntohl(usec);
 262                 }
 263
 264                 n->probe_counter++;
 265
 266                 if(n->probe_counter == 1) {
 267                         n->rtt = diff.tv_sec + diff.tv_usec * 1e-6;
 268                         n->probe_time = probe_timestamp;
 269                 } else if(n->probe_counter == 3) {
 270                         struct timeval probe_timestamp_diff;
 271                         timersub(&probe_timestamp, &n->probe_time, &probe_timestamp_diff);
 272                         n->bandwidth = 2.0 * probelen / (probe_timestamp_diff.tv_sec + probe_timestamp_diff.tv_usec * 1e-6);
 273                         logger(DEBUG_TRAFFIC, LOG_DEBUG, "%s (%s) RTT %.2f ms, burst bandwidth %.3f Mbit/s, rx packet loss %.2f %%", n->name, n->hostname, n->rtt * 1e3, n->bandwidth * 8e-6, n->packetloss * 1e2);
 274                 }
 275         }
 276 }
 277
 278 static length_t compress_packet(uint8_t *dest, const uint8_t *source, length_t len, int level) {
 279         if(level == 0) {
 280                 memcpy(dest, source, len);
 281                 return len;
 282         } else if(level == 10) {
 283 #ifdef HAVE_LZO
 284                 lzo_uint lzolen = MAXSIZE;
 285                 lzo1x_1_compress(source, len, dest, &lzolen, lzo_wrkmem);
 286                 return lzolen;
 287 #else
 288                 return -1;
 289 #endif
 290         } else if(level < 10) {
 291 #ifdef HAVE_ZLIB
 292                 unsigned long destlen = MAXSIZE;
 293                 if(compress2(dest, &destlen, source, len, level) == Z_OK)
 294                         return destlen;
 295                 else
 296 #endif
 297                         return -1;
 298         } else {
 299 #ifdef HAVE_LZO
 300                 lzo_uint lzolen = MAXSIZE;
 301                 lzo1x_999_compress(source, len, dest, &lzolen, lzo_wrkmem);
 302                 return lzolen;
 303 #else
 304                 return -1;
 305 #endif
 306         }
 307
 308         return -1;
 309 }
 310
 311 static length_t uncompress_packet(uint8_t *dest, const uint8_t *source, length_t len, int level) {
 312         if(level == 0) {
 313                 memcpy(dest, source, len);
 314                 return len;
 315         } else if(level > 9) {
 316 #ifdef HAVE_LZO
 317                 lzo_uint lzolen = MAXSIZE;
 318                 if(lzo1x_decompress_safe(source, len, dest, &lzolen, NULL) == LZO_E_OK)
 319                         return lzolen;
 320                 else
 321 #endif
 322                         return -1;
 323         }
 324 #ifdef HAVE_ZLIB
 325         else {
 326                 unsigned long destlen = MAXSIZE;
 327                 if(uncompress(dest, &destlen, source, len) == Z_OK)
 328                         return destlen;
 329                 else
 330                         return -1;
 331         }
 332 #endif
 333
 334         return -1;
 335 }
 336
 337 /* VPN packet I/O */
 338
 339 static void receive_packet(node_t *n, vpn_packet_t *packet) {
 340         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Received packet of %d bytes from %s (%s)",
 341                            packet->len, n->name, n->hostname);
 342
 343         n->in_packets++;
 344         n->in_bytes += packet->len;
 345
 346         route(n, packet);
 347 }
 348
 349 static bool try_mac(node_t *n, const vpn_packet_t *inpkt) {
 350         if(n->status.sptps)
 351                 return sptps_verify_datagram(&n->sptps, ((sptps_packet_t *)inpkt)->data, inpkt->len);
 352
 353         if(!digest_active(n->indigest) || inpkt->len < sizeof inpkt->seqno + digest_length(n->indigest))
 354                 return false;
 355
 356         return digest_verify(n->indigest, (const char *)&inpkt->seqno, inpkt->len - digest_length(n->indigest), (const char *)&inpkt->seqno + inpkt->len - digest_length(n->indigest));
 357 }
 358
 359 static bool receive_udppacket(node_t *n, vpn_packet_t *inpkt) {
 360         vpn_packet_t pkt1, pkt2;
 361         vpn_packet_t *pkt[] = { &pkt1, &pkt2, &pkt1, &pkt2 };
 362         int nextpkt = 0;
 363         size_t outlen;
 364
 365         if(n->status.sptps) {
 366                 if(!n->sptps.state) {
 367                         if(!n->status.waitingforkey) {
 368                                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got packet from %s (%s) but we haven't exchanged keys yet", n->name, n->hostname);
 369                                 send_req_key(n);
 370                         } else {
 371                                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got packet from %s (%s) but he hasn't got our key yet", n->name, n->hostname);
 372                         }
 373                         return false;
 374                 }
 375                 if(!sptps_receive_data(&n->sptps, ((sptps_packet_t *)&inpkt)->data, inpkt->len)) {
 376                         logger(DEBUG_TRAFFIC, LOG_ERR, "Got bad packet from %s (%s)", n->name, n->hostname);
 377                         return false;
 378                 }
 379                 return true;
 380         }
 381
 382         if(!n->status.validkey) {
 383                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got packet from %s (%s) but he hasn't got our key yet", n->name, n->hostname);
 384                 return false;
 385         }
 386
 387         /* Check packet length */
 388
 389         if(inpkt->len < sizeof inpkt->seqno + digest_length(n->indigest)) {
 390                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got too short packet from %s (%s)",
 391                                         n->name, n->hostname);
 392                 return false;
 393         }
 394
 395         /* Check the message authentication code */
 396
 397         if(digest_active(n->indigest)) {
 398                 inpkt->len -= digest_length(n->indigest);
 399                 if(!digest_verify(n->indigest, &inpkt->seqno, inpkt->len, (const char *)&inpkt->seqno + inpkt->len)) {
 400                         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got unauthenticated packet from %s (%s)", n->name, n->hostname);
 401                         return false;
 402                 }
 403         }
 404         /* Decrypt the packet */
 405
 406         if(cipher_active(n->incipher)) {
 407                 vpn_packet_t *outpkt = pkt[nextpkt++];
 408                 outlen = MAXSIZE;
 409
 410                 if(!cipher_decrypt(n->incipher, &inpkt->seqno, inpkt->len, &outpkt->seqno, &outlen, true)) {
 411                         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Error decrypting packet from %s (%s)", n->name, n->hostname);
 412                         return false;
 413                 }
 414
 415                 outpkt->len = outlen;
 416                 inpkt = outpkt;
 417         }
 418
 419         /* Check the sequence number */
 420
 421         inpkt->len -= sizeof inpkt->seqno;
 422         uint32_t seqno = ntohl(inpkt->seqno);
 423
 424         if(replaywin) {
 425                 if(seqno != n->received_seqno + 1) {
 426                         if(seqno >= n->received_seqno + replaywin * 8) {
 427                                 if(n->farfuture++ < replaywin >> 2) {
 428                                         logger(DEBUG_ALWAYS, LOG_WARNING, "Packet from %s (%s) is %d seqs in the future, dropped (%u)",
 429                                                 n->name, n->hostname, seqno - n->received_seqno - 1, n->farfuture);
 430                                         return false;
 431                                 }
 432                                 logger(DEBUG_ALWAYS, LOG_WARNING, "Lost %d packets from %s (%s)",
 433                                                 seqno - n->received_seqno - 1, n->name, n->hostname);
 434                                 memset(n->late, 0, replaywin);
 435                         } else if (seqno <= n->received_seqno) {
 436                                 if((n->received_seqno >= replaywin * 8 && seqno <= n->received_seqno - replaywin * 8) || !(n->late[(seqno / 8) % replaywin] & (1 << seqno % 8))) {
 437                                         logger(DEBUG_ALWAYS, LOG_WARNING, "Got late or replayed packet from %s (%s), seqno %d, last received %d",
 438                                                 n->name, n->hostname, seqno, n->received_seqno);
 439                                         return false;
 440                                 }
 441                         } else {
 442                                 for(int i = n->received_seqno + 1; i < seqno; i++)
 443                                         n->late[(i / 8) % replaywin] |= 1 << i % 8;
 444                         }
 445                 }
 446
 447                 n->farfuture = 0;
 448                 n->late[(seqno / 8) % replaywin] &= ~(1 << seqno % 8);
 449         }
 450
 451         if(seqno > n->received_seqno)
 452                 n->received_seqno = seqno;
 453
 454         n->received++;
 455
 456         if(n->received_seqno > MAX_SEQNO)
 457                 regenerate_key();
 458
 459         /* Decompress the packet */
 460
 461         length_t origlen = inpkt->len;
 462
 463         if(n->incompression) {
 464                 vpn_packet_t *outpkt = pkt[nextpkt++];
 465
 466                 if((outpkt->len = uncompress_packet(outpkt->data, inpkt->data, inpkt->len, n->incompression)) < 0) {
 467                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while uncompressing packet from %s (%s)",
 468                                                  n->name, n->hostname);
 469                         return false;
 470                 }
 471
 472                 inpkt = outpkt;
 473
 474                 origlen -= MTU/64 + 20;
 475         }
 476
 477         inpkt->priority = 0;
 478
 479         if(!inpkt->data[12] && !inpkt->data[13])
 480                 mtu_probe_h(n, inpkt, origlen);
 481         else
 482                 receive_packet(n, inpkt);
 483         return true;
 484 }
 485
 486 void receive_tcppacket(connection_t *c, const char *buffer, int len) {
 487         vpn_packet_t outpkt;
 488
 489         if(len > sizeof outpkt.data)
 490                 return;
 491
 492         outpkt.len = len;
 493         if(c->options & OPTION_TCPONLY)
 494                 outpkt.priority = 0;
 495         else
 496                 outpkt.priority = -1;
 497         memcpy(outpkt.data, buffer, len);
 498
 499         receive_packet(c->node, &outpkt);
 500 }
 501
 502 static bool try_sptps(node_t *n) {
 503         if(n->status.validkey)
 504                 return true;
 505
 506         logger(DEBUG_TRAFFIC, LOG_INFO, "No valid key known yet for %s (%s)", n->name, n->hostname);
 507
 508         if(!n->status.waitingforkey)
 509                 send_req_key(n);
 510         else if(n->last_req_key + 10 < now.tv_sec) {
 511                 logger(DEBUG_ALWAYS, LOG_DEBUG, "No key from %s after 10 seconds, restarting SPTPS", n->name);
 512                 sptps_stop(&n->sptps);
 513                 n->status.waitingforkey = false;
 514                 send_req_key(n);
 515         }
 516
 517         return false;
 518 }
 519
 520 static void send_sptps_packet(node_t *n, vpn_packet_t *origpkt) {
 521         if (!try_sptps(n))
 522                 return;
 523
 524         uint8_t type = 0;
 525         int offset = 0;
 526
 527         if(!(origpkt->data[12] | origpkt->data[13])) {
 528                 sptps_send_record(&n->sptps, PKT_PROBE, (char *)origpkt->data, origpkt->len);
 529                 return;
 530         }
 531
 532         if(routing_mode == RMODE_ROUTER)
 533                 offset = 14;
 534         else
 535                 type = PKT_MAC;
 536
 537         if(origpkt->len < offset)
 538                 return;
 539
 540         vpn_packet_t outpkt;
 541
 542         if(n->outcompression) {
 543                 int len = compress_packet(outpkt.data + offset, origpkt->data + offset, origpkt->len - offset, n->outcompression);
 544                 if(len < 0) {
 545                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while compressing packet to %s (%s)", n->name, n->hostname);
 546                 } else if(len < origpkt->len - offset) {
 547                         outpkt.len = len + offset;
 548                         origpkt = &outpkt;
 549                         type |= PKT_COMPRESSED;
 550                 }
 551         }
 552
 553         sptps_send_record(&n->sptps, type, (char *)origpkt->data + offset, origpkt->len - offset);
 554         return;
 555 }
 556
 557 static void adapt_socket(const sockaddr_t *sa, int *sock) {
 558         /* Make sure we have a suitable socket for the chosen address */
 559         if(listen_socket[*sock].sa.sa.sa_family != sa->sa.sa_family) {
 560                 for(int i = 0; i < listen_sockets; i++) {
 561                         if(listen_socket[i].sa.sa.sa_family == sa->sa.sa_family) {
 562                                 *sock = i;
 563                                 break;
 564                         }
 565                 }
 566         }
 567 }
 568
 569 static void choose_udp_address(const node_t *n, const sockaddr_t **sa, int *sock) {
 570         /* Latest guess */
 571         *sa = &n->address;
 572         *sock = n->sock;
 573
 574         /* If the UDP address is confirmed, use it. */
 575         if(n->status.udp_confirmed)
 576                 return;
 577
 578         /* Send every third packet to n->address; that could be set
 579            to the node's reflexive UDP address discovered during key
 580            exchange. */
 581
 582         static int x = 0;
 583         if(++x >= 3) {
 584                 x = 0;
 585                 return;
 586         }
 587
 588         /* Otherwise, address are found in edges to this node.
 589            So we pick a random edge and a random socket. */
 590
 591         int i = 0;
 592         int j = rand() % n->edge_tree->count;
 593         edge_t *candidate = NULL;
 594
 595         for splay_each(edge_t, e, n->edge_tree) {
 596                 if(i++ == j) {
 597                         candidate = e->reverse;
 598                         break;
 599                 }
 600         }
 601
 602         if(candidate) {
 603                 *sa = &candidate->address;
 604                 *sock = rand() % listen_sockets;
 605         }
 606
 607         adapt_socket(*sa, sock);
 608 }
 609
 610 static void choose_local_address(const node_t *n, const sockaddr_t **sa, int *sock) {
 611         *sa = NULL;
 612
 613         /* Pick one of the edges from this node at random, then use its local address. */
 614
 615         int i = 0;
 616         int j = rand() % n->edge_tree->count;
 617         edge_t *candidate = NULL;
 618
 619         for splay_each(edge_t, e, n->edge_tree) {
 620                 if(i++ == j) {
 621                         candidate = e;
 622                         break;
 623                 }
 624         }
 625
 626         if (candidate && candidate->local_address.sa.sa_family) {
 627                 *sa = &candidate->local_address;
 628                 *sock = rand() % listen_sockets;
 629                 adapt_socket(*sa, sock);
 630         }
 631 }
 632
 633 static void send_udppacket(node_t *n, vpn_packet_t *origpkt) {
 634         vpn_packet_t pkt1, pkt2;
 635         vpn_packet_t *pkt[] = { &pkt1, &pkt2, &pkt1, &pkt2 };
 636         vpn_packet_t *inpkt = origpkt;
 637         int nextpkt = 0;
 638         vpn_packet_t *outpkt;
 639         int origlen = origpkt->len;
 640         size_t outlen;
 641 #if defined(SOL_IP) && defined(IP_TOS)
 642         static int priority = 0;
 643         int origpriority = origpkt->priority;
 644 #endif
 645
 646         if(!n->status.reachable) {
 647                 logger(DEBUG_TRAFFIC, LOG_INFO, "Trying to send UDP packet to unreachable node %s (%s)", n->name, n->hostname);
 648                 return;
 649         }
 650
 651         if(n->status.sptps)
 652                 return send_sptps_packet(n, origpkt);
 653
 654         /* Make sure we have a valid key */
 655
 656         if(!n->status.validkey) {
 657                 logger(DEBUG_TRAFFIC, LOG_INFO,
 658                                    "No valid key known yet for %s (%s), forwarding via TCP",
 659                                    n->name, n->hostname);
 660
 661                 if(n->last_req_key + 10 <= now.tv_sec) {
 662                         send_req_key(n);
 663                         n->last_req_key = now.tv_sec;
 664                 }
 665
 666                 send_tcppacket(n->nexthop->connection, origpkt);
 667
 668                 return;
 669         }
 670
 671         if(n->options & OPTION_PMTU_DISCOVERY && inpkt->len > n->minmtu && (inpkt->data[12] | inpkt->data[13])) {
 672                 logger(DEBUG_TRAFFIC, LOG_INFO,
 673                                 "Packet for %s (%s) larger than minimum MTU, forwarding via %s",
 674                                 n->name, n->hostname, n != n->nexthop ? n->nexthop->name : "TCP");
 675
 676                 if(n != n->nexthop)
 677                         send_packet(n->nexthop, origpkt);
 678                 else
 679                         send_tcppacket(n->nexthop->connection, origpkt);
 680
 681                 return;
 682         }
 683
 684         /* Compress the packet */
 685
 686         if(n->outcompression) {
 687                 outpkt = pkt[nextpkt++];
 688
 689                 if((outpkt->len = compress_packet(outpkt->data, inpkt->data, inpkt->len, n->outcompression)) < 0) {
 690                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while compressing packet to %s (%s)",
 691                                    n->name, n->hostname);
 692                         return;
 693                 }
 694
 695                 inpkt = outpkt;
 696         }
 697
 698         /* Add sequence number */
 699
 700         inpkt->seqno = htonl(++(n->sent_seqno));
 701         inpkt->len += sizeof inpkt->seqno;
 702
 703         /* Encrypt the packet */
 704
 705         if(cipher_active(n->outcipher)) {
 706                 outpkt = pkt[nextpkt++];
 707                 outlen = MAXSIZE;
 708
 709                 if(!cipher_encrypt(n->outcipher, &inpkt->seqno, inpkt->len, &outpkt->seqno, &outlen, true)) {
 710                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while encrypting packet to %s (%s)", n->name, n->hostname);
 711                         goto end;
 712                 }
 713
 714                 outpkt->len = outlen;
 715                 inpkt = outpkt;
 716         }
 717
 718         /* Add the message authentication code */
 719
 720         if(digest_active(n->outdigest)) {
 721                 if(!digest_create(n->outdigest, &inpkt->seqno, inpkt->len, &inpkt->seqno + inpkt->len)) {
 722                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while encrypting packet to %s (%s)", n->name, n->hostname);
 723                         goto end;
 724                 }
 725
 726                 inpkt->len += digest_length(n->outdigest);
 727         }
 728
 729         /* Send the packet */
 730
 731         const sockaddr_t *sa = NULL;
 732         int sock;
 733
 734         if(n->status.send_locally)
 735                 choose_local_address(n, &sa, &sock);
 736         if(!sa)
 737                 choose_udp_address(n, &sa, &sock);
 738
 739 #if defined(SOL_IP) && defined(IP_TOS)
 740         if(priorityinheritance && origpriority != priority
 741            && listen_socket[n->sock].sa.sa.sa_family == AF_INET) {
 742                 priority = origpriority;
 743                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Setting outgoing packet priority to %d", priority);
 744                 if(setsockopt(listen_socket[n->sock].udp.fd, SOL_IP, IP_TOS, &priority, sizeof(priority))) /* SO_PRIORITY doesn't seem to work */
 745                         logger(DEBUG_ALWAYS, LOG_ERR, "System call `%s' failed: %s", "setsockopt", sockstrerror(sockerrno));
 746         }
 747 #endif
 748
 749         if(sendto(listen_socket[sock].udp.fd, &inpkt->seqno, inpkt->len, 0, &sa->sa, SALEN(sa->sa)) < 0 && !sockwouldblock(sockerrno)) {
 750                 if(sockmsgsize(sockerrno)) {
 751                         if(n->maxmtu >= origlen)
 752                                 n->maxmtu = origlen - 1;
 753                         if(n->mtu >= origlen)
 754                                 n->mtu = origlen - 1;
 755                 } else
 756                         logger(DEBUG_TRAFFIC, LOG_WARNING, "Error sending packet to %s (%s): %s", n->name, n->hostname, sockstrerror(sockerrno));
 757         }
 758
 759 end:
 760         origpkt->len = origlen;
 761 }
 762
 763 static bool send_sptps_data_priv(node_t *to, node_t *from, int type, const void *data, size_t len) {
 764         node_t *relay = (to->via != myself && (type == PKT_PROBE || (len - SPTPS_DATAGRAM_OVERHEAD) <= to->via->minmtu)) ? to->via : to->nexthop;
 765         bool direct = from == myself && to == relay;
 766         bool relay_supported = (relay->options >> 24) >= 4;
 767         bool tcponly = (myself->options | relay->options) & OPTION_TCPONLY;
 768
 769         /* We don't really need the relay's key, but we need to establish a UDP tunnel with it and discover its MTU. */
 770         if (!direct && relay_supported && !tcponly)
 771                 try_sptps(relay);
 772
 773         /* 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.
 774            TODO: When relaying, the original sender does not know the end-to-end PMTU (it only knows the PMTU of the first hop).
 775                  This can lead to scenarios where large packets are sent over UDP to relay, but then relay has no choice but fall back to TCP. */
 776
 777         if(type == SPTPS_HANDSHAKE || tcponly || (!direct && !relay_supported) || (type != PKT_PROBE && (len - SPTPS_DATAGRAM_OVERHEAD) > relay->minmtu)) {
 778                 char buf[len * 4 / 3 + 5];
 779                 b64encode(data, buf, len);
 780                 /* If no valid key is known yet, send the packets using ANS_KEY requests,
 781                    to ensure we get to learn the reflexive UDP address. */
 782                 if(from == myself && !to->status.validkey) {
 783                         to->incompression = myself->incompression;
 784                         return send_request(to->nexthop->connection, "%d %s %s %s -1 -1 -1 %d", ANS_KEY, from->name, to->name, buf, to->incompression);
 785                 } else {
 786                         return send_request(to->nexthop->connection, "%d %s %s %d %s", REQ_KEY, from->name, to->name, REQ_SPTPS, buf);
 787                 }
 788         }
 789
 790         size_t overhead = 0;
 791         if(relay_supported) overhead += sizeof to->id + sizeof from->id;
 792         char buf[len + overhead]; char* buf_ptr = buf;
 793         if(relay_supported) {
 794                 if(direct) {
 795                         /* Inform the recipient that this packet was sent directly. */
 796                         node_id_t nullid = {};
 797                         memcpy(buf_ptr, &nullid, sizeof nullid); buf_ptr += sizeof nullid;
 798                 } else {
 799                         memcpy(buf_ptr, &to->id, sizeof to->id); buf_ptr += sizeof to->id;
 800                 }
 801                 memcpy(buf_ptr, &from->id, sizeof from->id); buf_ptr += sizeof from->id;
 802
 803         }
 804         /* 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 */
 805         memcpy(buf_ptr, data, len); buf_ptr += len;
 806
 807         const sockaddr_t *sa = NULL;
 808         int sock;
 809         if(relay->status.send_locally)
 810                 choose_local_address(relay, &sa, &sock);
 811         if(!sa)
 812                 choose_udp_address(relay, &sa, &sock);
 813         logger(DEBUG_TRAFFIC, LOG_INFO, "Sending packet from %s (%s) to %s (%s) via %s (%s)", from->name, from->hostname, to->name, to->hostname, relay->name, relay->hostname);
 814         if(sendto(listen_socket[sock].udp.fd, buf, buf_ptr - buf, 0, &sa->sa, SALEN(sa->sa)) < 0 && !sockwouldblock(sockerrno)) {
 815                 if(sockmsgsize(sockerrno)) {
 816                         // Compensate for SPTPS overhead
 817                         len -= SPTPS_DATAGRAM_OVERHEAD;
 818                         if(relay->maxmtu >= len)
 819                                 relay->maxmtu = len - 1;
 820                         if(relay->mtu >= len)
 821                                 relay->mtu = len - 1;
 822                 } else {
 823                         logger(DEBUG_TRAFFIC, LOG_WARNING, "Error sending UDP SPTPS packet to %s (%s): %s", relay->name, relay->hostname, sockstrerror(sockerrno));
 824                         return false;
 825                 }
 826         }
 827
 828         return true;
 829 }
 830
 831 bool send_sptps_data(void *handle, uint8_t type, const char *data, size_t len) {
 832         return send_sptps_data_priv(handle, myself, type, data, len);
 833 }
 834
 835 bool receive_sptps_record(void *handle, uint8_t type, const char *data, uint16_t len) {
 836         node_t *from = handle;
 837
 838         if(type == SPTPS_HANDSHAKE) {
 839                 if(!from->status.validkey) {
 840                         from->status.validkey = true;
 841                         from->status.waitingforkey = false;
 842                         logger(DEBUG_META, LOG_INFO, "SPTPS key exchange with %s (%s) succesful", from->name, from->hostname);
 843                 }
 844                 return true;
 845         }
 846
 847         if(len > MTU) {
 848                 logger(DEBUG_ALWAYS, LOG_ERR, "Packet from %s (%s) larger than maximum supported size (%d > %d)", from->name, from->hostname, len, MTU);
 849                 return false;
 850         }
 851
 852         vpn_packet_t inpkt;
 853
 854         if(type == PKT_PROBE) {
 855                 inpkt.len = len;
 856                 memcpy(inpkt.data, data, len);
 857                 mtu_probe_h(from, &inpkt, len);
 858                 return true;
 859         }
 860
 861         if(type & ~(PKT_COMPRESSED | PKT_MAC)) {
 862                 logger(DEBUG_ALWAYS, LOG_ERR, "Unexpected SPTPS record type %d len %d from %s (%s)", type, len, from->name, from->hostname);
 863                 return false;
 864         }
 865
 866         /* Check if we have the headers we need */
 867         if(routing_mode != RMODE_ROUTER && !(type & PKT_MAC)) {
 868                 logger(DEBUG_TRAFFIC, LOG_ERR, "Received packet from %s (%s) without MAC header (maybe Mode is not set correctly)", from->name, from->hostname);
 869                 return false;
 870         } else if(routing_mode == RMODE_ROUTER && (type & PKT_MAC)) {
 871                 logger(DEBUG_TRAFFIC, LOG_WARNING, "Received packet from %s (%s) with MAC header (maybe Mode is not set correctly)", from->name, from->hostname);
 872         }
 873
 874         int offset = (type & PKT_MAC) ? 0 : 14;
 875         if(type & PKT_COMPRESSED) {
 876                 length_t ulen = uncompress_packet(inpkt.data + offset, (const uint8_t *)data, len, from->incompression);
 877                 if(ulen < 0) {
 878                         return false;
 879                 } else {
 880                         inpkt.len = ulen + offset;
 881                 }
 882                 if(inpkt.len > MAXSIZE)
 883                         abort();
 884         } else {
 885                 memcpy(inpkt.data + offset, data, len);
 886                 inpkt.len = len + offset;
 887         }
 888
 889         /* Generate the Ethernet packet type if necessary */
 890         if(offset) {
 891                 switch(inpkt.data[14] >> 4) {
 892                         case 4:
 893                                 inpkt.data[12] = 0x08;
 894                                 inpkt.data[13] = 0x00;
 895                                 break;
 896                         case 6:
 897                                 inpkt.data[12] = 0x86;
 898                                 inpkt.data[13] = 0xDD;
 899                                 break;
 900                         default:
 901                                 logger(DEBUG_TRAFFIC, LOG_ERR,
 902                                                    "Unknown IP version %d while reading packet from %s (%s)",
 903                                                    inpkt.data[14] >> 4, from->name, from->hostname);
 904                                 return false;
 905                 }
 906         }
 907
 908         receive_packet(from, &inpkt);
 909         return true;
 910 }
 911
 912 /*
 913   send a packet to the given vpn ip.
 914 */
 915 void send_packet(node_t *n, vpn_packet_t *packet) {
 916         node_t *via;
 917
 918         if(n == myself) {
 919                 if(overwrite_mac)
 920                          memcpy(packet->data, mymac.x, ETH_ALEN);
 921                 n->out_packets++;
 922                 n->out_bytes += packet->len;
 923                 devops.write(packet);
 924                 return;
 925         }
 926
 927         logger(DEBUG_TRAFFIC, LOG_ERR, "Sending packet of %d bytes to %s (%s)",
 928                            packet->len, n->name, n->hostname);
 929
 930         if(!n->status.reachable) {
 931                 logger(DEBUG_TRAFFIC, LOG_INFO, "Node %s (%s) is not reachable",
 932                                    n->name, n->hostname);
 933                 return;
 934         }
 935
 936         n->out_packets++;
 937         n->out_bytes += packet->len;
 938
 939         if(n->status.sptps) {
 940                 send_sptps_packet(n, packet);
 941                 return;
 942         }
 943
 944         via = (packet->priority == -1 || n->via == myself) ? n->nexthop : n->via;
 945
 946         if(via != n)
 947                 logger(DEBUG_TRAFFIC, LOG_INFO, "Sending packet to %s via %s (%s)",
 948                            n->name, via->name, n->via->hostname);
 949
 950         if(packet->priority == -1 || ((myself->options | via->options) & OPTION_TCPONLY)) {
 951                 if(!send_tcppacket(via->connection, packet))
 952                         terminate_connection(via->connection, true);
 953         } else
 954                 send_udppacket(via, packet);
 955 }
 956
 957 /* Broadcast a packet using the minimum spanning tree */
 958
 959 void broadcast_packet(const node_t *from, vpn_packet_t *packet) {
 960         // Always give ourself a copy of the packet.
 961         if(from != myself)
 962                 send_packet(myself, packet);
 963
 964         // In TunnelServer mode, do not forward broadcast packets.
 965         // The MST might not be valid and create loops.
 966         if(tunnelserver || broadcast_mode == BMODE_NONE)
 967                 return;
 968
 969         logger(DEBUG_TRAFFIC, LOG_INFO, "Broadcasting packet of %d bytes from %s (%s)",
 970                            packet->len, from->name, from->hostname);
 971
 972         switch(broadcast_mode) {
 973                 // In MST mode, broadcast packets travel via the Minimum Spanning Tree.
 974                 // This guarantees all nodes receive the broadcast packet, and
 975                 // usually distributes the sending of broadcast packets over all nodes.
 976                 case BMODE_MST:
 977                         for list_each(connection_t, c, connection_list)
 978                                 if(c->edge && c->status.mst && c != from->nexthop->connection)
 979                                         send_packet(c->node, packet);
 980                         break;
 981
 982                 // In direct mode, we send copies to each node we know of.
 983                 // However, this only reaches nodes that can be reached in a single hop.
 984                 // We don't have enough information to forward broadcast packets in this case.
 985                 case BMODE_DIRECT:
 986                         if(from != myself)
 987                                 break;
 988
 989                         for splay_each(node_t, n, node_tree)
 990                                 if(n->status.reachable && n != myself && ((n->via == myself && n->nexthop == n) || n->via == n))
 991                                         send_packet(n, packet);
 992                         break;
 993
 994                 default:
 995                         break;
 996         }
 997 }
 998
 999 static node_t *try_harder(const sockaddr_t *from, const vpn_packet_t *pkt) {
1000         node_t *n = NULL;
1001         bool hard = false;
1002         static time_t last_hard_try = 0;
1003
1004         for splay_each(edge_t, e, edge_weight_tree) {
1005                 if(!e->to->status.reachable || e->to == myself)
1006                         continue;
1007
1008                 if(sockaddrcmp_noport(from, &e->address)) {
1009                         if(last_hard_try == now.tv_sec)
1010                                 continue;
1011                         hard = true;
1012                 }
1013
1014                 if(!try_mac(e->to, pkt))
1015                         continue;
1016
1017                 n = e->to;
1018                 break;
1019         }
1020
1021         if(hard)
1022                 last_hard_try = now.tv_sec;
1023
1024         last_hard_try = now.tv_sec;
1025         return n;
1026 }
1027
1028 void handle_incoming_vpn_data(void *data, int flags) {
1029         listen_socket_t *ls = data;
1030         vpn_packet_t pkt;
1031         sptps_packet_t *spkt = (sptps_packet_t *)&pkt;
1032         char *hostname;
1033         node_id_t nullid = {};
1034         sockaddr_t addr = {};
1035         socklen_t addrlen = sizeof addr;
1036         node_t *from, *to;
1037         bool direct = false;
1038
1039         int len = recvfrom(ls->udp.fd, &pkt.seqno, MAXSIZE, 0, &addr.sa, &addrlen);
1040
1041         if(len <= 0 || len > MAXSIZE) {
1042                 if(!sockwouldblock(sockerrno))
1043                         logger(DEBUG_ALWAYS, LOG_ERR, "Receiving packet failed: %s", sockstrerror(sockerrno));
1044                 return;
1045         }
1046
1047         pkt.len = len;
1048
1049         sockaddrunmap(&addr); /* Some braindead IPv6 implementations do stupid things. */
1050
1051         // Try to figure out who sent this packet.
1052
1053         node_t *n = lookup_node_udp(&addr);
1054
1055         if(!n) {
1056                 // It might be from a 1.1 node, which might have a source ID in the packet.
1057                 from = lookup_node_id(&spkt->srcid);
1058                 if(from && !memcmp(&spkt->dstid, &nullid, sizeof nullid) && from->status.sptps) {
1059                         if(sptps_verify_datagram(&from->sptps, spkt->data, spkt->len - sizeof(spkt->srcid) - sizeof(spkt->dstid)))
1060                                 n = from;
1061                         else
1062                                 goto skip_harder;
1063                 }
1064         }
1065
1066         if(!n)
1067                 n = try_harder(&addr, &pkt);
1068
1069 skip_harder:
1070         if(!n) {
1071                 if(debug_level >= DEBUG_PROTOCOL) {
1072                         hostname = sockaddr2hostname(&addr);
1073                         logger(DEBUG_PROTOCOL, LOG_WARNING, "Received UDP packet from unknown source %s", hostname);
1074                         free(hostname);
1075                 }
1076                 return;
1077         }
1078
1079         if(n->status.sptps) {
1080                 if(memcmp(&spkt->dstid, &nullid, sizeof nullid)) {
1081                         direct = true;
1082                         from = n;
1083                         to = myself;
1084                 } else {
1085                         from = lookup_node_id(&spkt->srcid);
1086                         to = lookup_node_id(&spkt->dstid);
1087                 }
1088                 if(!from || !to) {
1089                         logger(DEBUG_PROTOCOL, LOG_WARNING, "Received UDP packet from %s (%s) with unknown source and/or destination ID", n->name, n->hostname);
1090                         return;
1091                 }
1092
1093                 spkt->len -= sizeof spkt->dstid + sizeof spkt->srcid;
1094                 if(to != myself) {
1095                         send_sptps_data_priv(to, n, 0, spkt->data, spkt->len);
1096                         return;
1097                 }
1098         } else {
1099                 direct = true;
1100                 from = n;
1101         }
1102
1103         if(!receive_udppacket(from, &pkt))
1104                 return;
1105
1106         n->sock = ls - listen_socket;
1107         if(direct && sockaddrcmp(&addr, &n->address))
1108                 update_node_udp(n, &addr);
1109 }
1110
1111 void handle_device_data(void *data, int flags) {
1112         vpn_packet_t packet;
1113
1114         packet.priority = 0;
1115
1116         if(devops.read(&packet)) {
1117                 myself->in_packets++;
1118                 myself->in_bytes += packet.len;
1119                 route(myself, &packet);
1120         }
1121 }