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, (char *)&inpkt->seqno, 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, &inpkt->seqno, inpkt->len - digest_length(n->indigest), (const char *)&inpkt->seqno + inpkt->len - digest_length(n->indigest));
 357 }
 358
 359 static void 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;
 374                 }
 375                 sptps_receive_data(&n->sptps, (char *)&inpkt->seqno, inpkt->len);
 376                 return;
 377         }
 378
 379         if(!n->status.validkey) {
 380                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got packet from %s (%s) but he hasn't got our key yet", n->name, n->hostname);
 381                 return;
 382         }
 383
 384         /* Check packet length */
 385
 386         if(inpkt->len < sizeof inpkt->seqno + digest_length(n->indigest)) {
 387                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got too short packet from %s (%s)",
 388                                         n->name, n->hostname);
 389                 return;
 390         }
 391
 392         /* Check the message authentication code */
 393
 394         if(digest_active(n->indigest)) {
 395                 inpkt->len -= digest_length(n->indigest);
 396                 if(!digest_verify(n->indigest, &inpkt->seqno, inpkt->len, (const char *)&inpkt->seqno + inpkt->len)) {
 397                         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got unauthenticated packet from %s (%s)", n->name, n->hostname);
 398                         return;
 399                 }
 400         }
 401         /* Decrypt the packet */
 402
 403         if(cipher_active(n->incipher)) {
 404                 vpn_packet_t *outpkt = pkt[nextpkt++];
 405                 outlen = MAXSIZE;
 406
 407                 if(!cipher_decrypt(n->incipher, &inpkt->seqno, inpkt->len, &outpkt->seqno, &outlen, true)) {
 408                         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Error decrypting packet from %s (%s)", n->name, n->hostname);
 409                         return;
 410                 }
 411
 412                 outpkt->len = outlen;
 413                 inpkt = outpkt;
 414         }
 415
 416         /* Check the sequence number */
 417
 418         inpkt->len -= sizeof inpkt->seqno;
 419         uint32_t seqno;
 420         memcpy(&seqno, inpkt->seqno, sizeof seqno);
 421         seqno = ntohl(seqno);
 422
 423         if(replaywin) {
 424                 if(seqno != n->received_seqno + 1) {
 425                         if(seqno >= n->received_seqno + replaywin * 8) {
 426                                 if(n->farfuture++ < replaywin >> 2) {
 427                                         logger(DEBUG_ALWAYS, LOG_WARNING, "Packet from %s (%s) is %d seqs in the future, dropped (%u)",
 428                                                 n->name, n->hostname, seqno - n->received_seqno - 1, n->farfuture);
 429                                         return;
 430                                 }
 431                                 logger(DEBUG_ALWAYS, LOG_WARNING, "Lost %d packets from %s (%s)",
 432                                                 seqno - n->received_seqno - 1, n->name, n->hostname);
 433                                 memset(n->late, 0, replaywin);
 434                         } else if (seqno <= n->received_seqno) {
 435                                 if((n->received_seqno >= replaywin * 8 && seqno <= n->received_seqno - replaywin * 8) || !(n->late[(seqno / 8) % replaywin] & (1 << seqno % 8))) {
 436                                         logger(DEBUG_ALWAYS, LOG_WARNING, "Got late or replayed packet from %s (%s), seqno %d, last received %d",
 437                                                 n->name, n->hostname, seqno, n->received_seqno);
 438                                         return;
 439                                 }
 440                         } else {
 441                                 for(int i = n->received_seqno + 1; i < seqno; i++)
 442                                         n->late[(i / 8) % replaywin] |= 1 << i % 8;
 443                         }
 444                 }
 445
 446                 n->farfuture = 0;
 447                 n->late[(seqno / 8) % replaywin] &= ~(1 << seqno % 8);
 448         }
 449
 450         if(seqno > n->received_seqno)
 451                 n->received_seqno = seqno;
 452
 453         n->received++;
 454
 455         if(n->received_seqno > MAX_SEQNO)
 456                 regenerate_key();
 457
 458         /* Decompress the packet */
 459
 460         length_t origlen = inpkt->len;
 461
 462         if(n->incompression) {
 463                 vpn_packet_t *outpkt = pkt[nextpkt++];
 464
 465                 if((outpkt->len = uncompress_packet(outpkt->data, inpkt->data, inpkt->len, n->incompression)) < 0) {
 466                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while uncompressing packet from %s (%s)",
 467                                                  n->name, n->hostname);
 468                         return;
 469                 }
 470
 471                 inpkt = outpkt;
 472
 473                 origlen -= MTU/64 + 20;
 474         }
 475
 476         inpkt->priority = 0;
 477
 478         if(!inpkt->data[12] && !inpkt->data[13])
 479                 mtu_probe_h(n, inpkt, origlen);
 480         else
 481                 receive_packet(n, inpkt);
 482 }
 483
 484 void receive_tcppacket(connection_t *c, const char *buffer, int len) {
 485         vpn_packet_t outpkt;
 486
 487         if(len > sizeof outpkt.data)
 488                 return;
 489
 490         outpkt.len = len;
 491         if(c->options & OPTION_TCPONLY)
 492                 outpkt.priority = 0;
 493         else
 494                 outpkt.priority = -1;
 495         memcpy(outpkt.data, buffer, len);
 496
 497         receive_packet(c->node, &outpkt);
 498 }
 499
 500 static void send_sptps_packet(node_t *n, vpn_packet_t *origpkt) {
 501         if(!n->status.validkey) {
 502                 logger(DEBUG_TRAFFIC, LOG_INFO, "No valid key known yet for %s (%s)", n->name, n->hostname);
 503                 if(!n->status.waitingforkey)
 504                         send_req_key(n);
 505                 else if(n->last_req_key + 10 < now.tv_sec) {
 506                         logger(DEBUG_ALWAYS, LOG_DEBUG, "No key from %s after 10 seconds, restarting SPTPS", n->name);
 507                         sptps_stop(&n->sptps);
 508                         n->status.waitingforkey = false;
 509                         send_req_key(n);
 510                 }
 511                 return;
 512         }
 513
 514         uint8_t type = 0;
 515         int offset = 0;
 516
 517         if(!(origpkt->data[12] | origpkt->data[13])) {
 518                 sptps_send_record(&n->sptps, PKT_PROBE, (char *)origpkt->data, origpkt->len);
 519                 return;
 520         }
 521
 522         if(routing_mode == RMODE_ROUTER)
 523                 offset = 14;
 524         else
 525                 type = PKT_MAC;
 526
 527         if(origpkt->len < offset)
 528                 return;
 529
 530         vpn_packet_t outpkt;
 531
 532         if(n->outcompression) {
 533                 int len = compress_packet(outpkt.data + offset, origpkt->data + offset, origpkt->len - offset, n->outcompression);
 534                 if(len < 0) {
 535                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while compressing packet to %s (%s)", n->name, n->hostname);
 536                 } else if(len < origpkt->len - offset) {
 537                         outpkt.len = len + offset;
 538                         origpkt = &outpkt;
 539                         type |= PKT_COMPRESSED;
 540                 }
 541         }
 542
 543         sptps_send_record(&n->sptps, type, (char *)origpkt->data + offset, origpkt->len - offset);
 544         return;
 545 }
 546
 547 static void adapt_socket(const sockaddr_t *sa, int *sock) {
 548         /* Make sure we have a suitable socket for the chosen address */
 549         if(listen_socket[*sock].sa.sa.sa_family != sa->sa.sa_family) {
 550                 for(int i = 0; i < listen_sockets; i++) {
 551                         if(listen_socket[i].sa.sa.sa_family == sa->sa.sa_family) {
 552                                 *sock = i;
 553                                 break;
 554                         }
 555                 }
 556         }
 557 }
 558
 559 static void choose_udp_address(const node_t *n, const sockaddr_t **sa, int *sock) {
 560         /* Latest guess */
 561         *sa = &n->address;
 562         *sock = n->sock;
 563
 564         /* If the UDP address is confirmed, use it. */
 565         if(n->status.udp_confirmed)
 566                 return;
 567
 568         /* Send every third packet to n->address; that could be set
 569            to the node's reflexive UDP address discovered during key
 570            exchange. */
 571
 572         static int x = 0;
 573         if(++x >= 3) {
 574                 x = 0;
 575                 return;
 576         }
 577
 578         /* Otherwise, address are found in edges to this node.
 579            So we pick a random edge and a random socket. */
 580
 581         int i = 0;
 582         int j = rand() % n->edge_tree->count;
 583         edge_t *candidate = NULL;
 584
 585         for splay_each(edge_t, e, n->edge_tree) {
 586                 if(i++ == j) {
 587                         candidate = e->reverse;
 588                         break;
 589                 }
 590         }
 591
 592         if(candidate) {
 593                 *sa = &candidate->address;
 594                 *sock = rand() % listen_sockets;
 595         }
 596
 597         adapt_socket(*sa, sock);
 598 }
 599
 600 static void choose_local_address(const node_t *n, const sockaddr_t **sa, int *sock) {
 601         *sa = NULL;
 602
 603         /* Pick one of the edges from this node at random, then use its local address. */
 604
 605         int i = 0;
 606         int j = rand() % n->edge_tree->count;
 607         edge_t *candidate = NULL;
 608
 609         for splay_each(edge_t, e, n->edge_tree) {
 610                 if(i++ == j) {
 611                         candidate = e;
 612                         break;
 613                 }
 614         }
 615
 616         if (candidate && candidate->local_address.sa.sa_family) {
 617                 *sa = &candidate->local_address;
 618                 *sock = rand() % listen_sockets;
 619                 adapt_socket(*sa, sock);
 620         }
 621 }
 622
 623 static void send_udppacket(node_t *n, vpn_packet_t *origpkt) {
 624         vpn_packet_t pkt1, pkt2;
 625         vpn_packet_t *pkt[] = { &pkt1, &pkt2, &pkt1, &pkt2 };
 626         vpn_packet_t *inpkt = origpkt;
 627         int nextpkt = 0;
 628         vpn_packet_t *outpkt;
 629         int origlen = origpkt->len;
 630         size_t outlen;
 631 #if defined(SOL_IP) && defined(IP_TOS)
 632         static int priority = 0;
 633         int origpriority = origpkt->priority;
 634 #endif
 635
 636         if(!n->status.reachable) {
 637                 logger(DEBUG_TRAFFIC, LOG_INFO, "Trying to send UDP packet to unreachable node %s (%s)", n->name, n->hostname);
 638                 return;
 639         }
 640
 641         if(n->status.sptps)
 642                 return send_sptps_packet(n, origpkt);
 643
 644         /* Make sure we have a valid key */
 645
 646         if(!n->status.validkey) {
 647                 logger(DEBUG_TRAFFIC, LOG_INFO,
 648                                    "No valid key known yet for %s (%s), forwarding via TCP",
 649                                    n->name, n->hostname);
 650
 651                 if(n->last_req_key + 10 <= now.tv_sec) {
 652                         send_req_key(n);
 653                         n->last_req_key = now.tv_sec;
 654                 }
 655
 656                 send_tcppacket(n->nexthop->connection, origpkt);
 657
 658                 return;
 659         }
 660
 661         if(n->options & OPTION_PMTU_DISCOVERY && inpkt->len > n->minmtu && (inpkt->data[12] | inpkt->data[13])) {
 662                 logger(DEBUG_TRAFFIC, LOG_INFO,
 663                                 "Packet for %s (%s) larger than minimum MTU, forwarding via %s",
 664                                 n->name, n->hostname, n != n->nexthop ? n->nexthop->name : "TCP");
 665
 666                 if(n != n->nexthop)
 667                         send_packet(n->nexthop, origpkt);
 668                 else
 669                         send_tcppacket(n->nexthop->connection, origpkt);
 670
 671                 return;
 672         }
 673
 674         /* Compress the packet */
 675
 676         if(n->outcompression) {
 677                 outpkt = pkt[nextpkt++];
 678
 679                 if((outpkt->len = compress_packet(outpkt->data, inpkt->data, inpkt->len, n->outcompression)) < 0) {
 680                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while compressing packet to %s (%s)",
 681                                    n->name, n->hostname);
 682                         return;
 683                 }
 684
 685                 inpkt = outpkt;
 686         }
 687
 688         /* Add sequence number */
 689
 690         uint32_t seqno = htonl(++(n->sent_seqno));
 691         memcpy(inpkt->seqno, &seqno, sizeof inpkt->seqno);
 692         inpkt->len += sizeof inpkt->seqno;
 693
 694         /* Encrypt the packet */
 695
 696         if(cipher_active(n->outcipher)) {
 697                 outpkt = pkt[nextpkt++];
 698                 outlen = MAXSIZE;
 699
 700                 if(!cipher_encrypt(n->outcipher, inpkt->seqno, inpkt->len, outpkt->seqno, &outlen, true)) {
 701                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while encrypting packet to %s (%s)", n->name, n->hostname);
 702                         goto end;
 703                 }
 704
 705                 outpkt->len = outlen;
 706                 inpkt = outpkt;
 707         }
 708
 709         /* Add the message authentication code */
 710
 711         if(digest_active(n->outdigest)) {
 712                 if(!digest_create(n->outdigest, inpkt->seqno, inpkt->len, inpkt->seqno + inpkt->len)) {
 713                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while encrypting packet to %s (%s)", n->name, n->hostname);
 714                         goto end;
 715                 }
 716
 717                 inpkt->len += digest_length(n->outdigest);
 718         }
 719
 720         /* Send the packet */
 721
 722         const sockaddr_t *sa = NULL;
 723         int sock;
 724
 725         if(n->status.send_locally)
 726                 choose_local_address(n, &sa, &sock);
 727         if(!sa)
 728                 choose_udp_address(n, &sa, &sock);
 729
 730 #if defined(SOL_IP) && defined(IP_TOS)
 731         if(priorityinheritance && origpriority != priority
 732            && listen_socket[n->sock].sa.sa.sa_family == AF_INET) {
 733                 priority = origpriority;
 734                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Setting outgoing packet priority to %d", priority);
 735                 if(setsockopt(listen_socket[n->sock].udp.fd, SOL_IP, IP_TOS, &priority, sizeof(priority))) /* SO_PRIORITY doesn't seem to work */
 736                         logger(DEBUG_ALWAYS, LOG_ERR, "System call `%s' failed: %s", "setsockopt", sockstrerror(sockerrno));
 737         }
 738 #endif
 739
 740         if(sendto(listen_socket[sock].udp.fd, inpkt->seqno, inpkt->len, 0, &sa->sa, SALEN(sa->sa)) < 0 && !sockwouldblock(sockerrno)) {
 741                 if(sockmsgsize(sockerrno)) {
 742                         if(n->maxmtu >= origlen)
 743                                 n->maxmtu = origlen - 1;
 744                         if(n->mtu >= origlen)
 745                                 n->mtu = origlen - 1;
 746                 } else
 747                         logger(DEBUG_TRAFFIC, LOG_WARNING, "Error sending packet to %s (%s): %s", n->name, n->hostname, sockstrerror(sockerrno));
 748         }
 749
 750 end:
 751         origpkt->len = origlen;
 752 }
 753
 754 bool send_sptps_data(void *handle, uint8_t type, const char *data, size_t len) {
 755         node_t *to = handle;
 756
 757         /* Send it via TCP if it is a handshake packet, TCPOnly is in use, or this packet is larger than the MTU. */
 758
 759         if(type >= SPTPS_HANDSHAKE || ((myself->options | to->options) & OPTION_TCPONLY) || (type != PKT_PROBE && (len - SPTPS_DATAGRAM_OVERHEAD) > to->minmtu)) {
 760                 char buf[len * 4 / 3 + 5];
 761                 b64encode(data, buf, len);
 762                 /* If no valid key is known yet, send the packets using ANS_KEY requests,
 763                    to ensure we get to learn the reflexive UDP address. */
 764                 if(!to->status.validkey) {
 765                         to->incompression = myself->incompression;
 766                         return send_request(to->nexthop->connection, "%d %s %s %s -1 -1 -1 %d", ANS_KEY, myself->name, to->name, buf, to->incompression);
 767                 } else {
 768                         return send_request(to->nexthop->connection, "%d %s %s %d %s", REQ_KEY, myself->name, to->name, REQ_SPTPS, buf);
 769                 }
 770         }
 771
 772         /* Otherwise, send the packet via UDP */
 773
 774         const sockaddr_t *sa = NULL;
 775         int sock;
 776
 777         if(to->status.send_locally)
 778                 choose_local_address(to, &sa, &sock);
 779         if(!sa)
 780                 choose_udp_address(to, &sa, &sock);
 781
 782         if(sendto(listen_socket[sock].udp.fd, data, len, 0, &sa->sa, SALEN(sa->sa)) < 0 && !sockwouldblock(sockerrno)) {
 783                 if(sockmsgsize(sockerrno)) {
 784                         // Compensate for SPTPS overhead
 785                         len -= SPTPS_DATAGRAM_OVERHEAD;
 786                         if(to->maxmtu >= len)
 787                                 to->maxmtu = len - 1;
 788                         if(to->mtu >= len)
 789                                 to->mtu = len - 1;
 790                 } else {
 791                         logger(DEBUG_TRAFFIC, LOG_WARNING, "Error sending UDP SPTPS packet to %s (%s): %s", to->name, to->hostname, sockstrerror(sockerrno));
 792                         return false;
 793                 }
 794         }
 795
 796         return true;
 797 }
 798
 799 bool receive_sptps_record(void *handle, uint8_t type, const char *data, uint16_t len) {
 800         node_t *from = handle;
 801
 802         if(type == SPTPS_HANDSHAKE) {
 803                 if(!from->status.validkey) {
 804                         from->status.validkey = true;
 805                         from->status.waitingforkey = false;
 806                         logger(DEBUG_META, LOG_INFO, "SPTPS key exchange with %s (%s) succesful", from->name, from->hostname);
 807                 }
 808                 return true;
 809         }
 810
 811         if(len > MTU) {
 812                 logger(DEBUG_ALWAYS, LOG_ERR, "Packet from %s (%s) larger than maximum supported size (%d > %d)", from->name, from->hostname, len, MTU);
 813                 return false;
 814         }
 815
 816         vpn_packet_t inpkt;
 817
 818         if(type == PKT_PROBE) {
 819                 inpkt.len = len;
 820                 memcpy(inpkt.data, data, len);
 821                 mtu_probe_h(from, &inpkt, len);
 822                 return true;
 823         }
 824
 825         if(type & ~(PKT_COMPRESSED | PKT_MAC)) {
 826                 logger(DEBUG_ALWAYS, LOG_ERR, "Unexpected SPTPS record type %d len %d from %s (%s)", type, len, from->name, from->hostname);
 827                 return false;
 828         }
 829
 830         /* Check if we have the headers we need */
 831         if(routing_mode != RMODE_ROUTER && !(type & PKT_MAC)) {
 832                 logger(DEBUG_TRAFFIC, LOG_ERR, "Received packet from %s (%s) without MAC header (maybe Mode is not set correctly)", from->name, from->hostname);
 833                 return false;
 834         } else if(routing_mode == RMODE_ROUTER && (type & PKT_MAC)) {
 835                 logger(DEBUG_TRAFFIC, LOG_WARNING, "Received packet from %s (%s) with MAC header (maybe Mode is not set correctly)", from->name, from->hostname);
 836         }
 837
 838         int offset = (type & PKT_MAC) ? 0 : 14;
 839         if(type & PKT_COMPRESSED) {
 840                 length_t ulen = uncompress_packet(inpkt.data + offset, (const uint8_t *)data, len, from->incompression);
 841                 if(ulen < 0) {
 842                         return false;
 843                 } else {
 844                         inpkt.len = ulen + offset;
 845                 }
 846                 if(inpkt.len > MAXSIZE)
 847                         abort();
 848         } else {
 849                 memcpy(inpkt.data + offset, data, len);
 850                 inpkt.len = len + offset;
 851         }
 852
 853         /* Generate the Ethernet packet type if necessary */
 854         if(offset) {
 855                 switch(inpkt.data[14] >> 4) {
 856                         case 4:
 857                                 inpkt.data[12] = 0x08;
 858                                 inpkt.data[13] = 0x00;
 859                                 break;
 860                         case 6:
 861                                 inpkt.data[12] = 0x86;
 862                                 inpkt.data[13] = 0xDD;
 863                                 break;
 864                         default:
 865                                 logger(DEBUG_TRAFFIC, LOG_ERR,
 866                                                    "Unknown IP version %d while reading packet from %s (%s)",
 867                                                    inpkt.data[14] >> 4, from->name, from->hostname);
 868                                 return false;
 869                 }
 870         }
 871
 872         receive_packet(from, &inpkt);
 873         return true;
 874 }
 875
 876 /*
 877   send a packet to the given vpn ip.
 878 */
 879 void send_packet(node_t *n, vpn_packet_t *packet) {
 880         node_t *via;
 881
 882         if(n == myself) {
 883                 if(overwrite_mac)
 884                          memcpy(packet->data, mymac.x, ETH_ALEN);
 885                 n->out_packets++;
 886                 n->out_bytes += packet->len;
 887                 devops.write(packet);
 888                 return;
 889         }
 890
 891         logger(DEBUG_TRAFFIC, LOG_ERR, "Sending packet of %d bytes to %s (%s)",
 892                            packet->len, n->name, n->hostname);
 893
 894         if(!n->status.reachable) {
 895                 logger(DEBUG_TRAFFIC, LOG_INFO, "Node %s (%s) is not reachable",
 896                                    n->name, n->hostname);
 897                 return;
 898         }
 899
 900         n->out_packets++;
 901         n->out_bytes += packet->len;
 902
 903         if(n->status.sptps) {
 904                 send_sptps_packet(n, packet);
 905                 return;
 906         }
 907
 908         via = (packet->priority == -1 || n->via == myself) ? n->nexthop : n->via;
 909
 910         if(via != n)
 911                 logger(DEBUG_TRAFFIC, LOG_INFO, "Sending packet to %s via %s (%s)",
 912                            n->name, via->name, n->via->hostname);
 913
 914         if(packet->priority == -1 || ((myself->options | via->options) & OPTION_TCPONLY)) {
 915                 if(!send_tcppacket(via->connection, packet))
 916                         terminate_connection(via->connection, true);
 917         } else
 918                 send_udppacket(via, packet);
 919 }
 920
 921 /* Broadcast a packet using the minimum spanning tree */
 922
 923 void broadcast_packet(const node_t *from, vpn_packet_t *packet) {
 924         // Always give ourself a copy of the packet.
 925         if(from != myself)
 926                 send_packet(myself, packet);
 927
 928         // In TunnelServer mode, do not forward broadcast packets.
 929         // The MST might not be valid and create loops.
 930         if(tunnelserver || broadcast_mode == BMODE_NONE)
 931                 return;
 932
 933         logger(DEBUG_TRAFFIC, LOG_INFO, "Broadcasting packet of %d bytes from %s (%s)",
 934                            packet->len, from->name, from->hostname);
 935
 936         switch(broadcast_mode) {
 937                 // In MST mode, broadcast packets travel via the Minimum Spanning Tree.
 938                 // This guarantees all nodes receive the broadcast packet, and
 939                 // usually distributes the sending of broadcast packets over all nodes.
 940                 case BMODE_MST:
 941                         for list_each(connection_t, c, connection_list)
 942                                 if(c->edge && c->status.mst && c != from->nexthop->connection)
 943                                         send_packet(c->node, packet);
 944                         break;
 945
 946                 // In direct mode, we send copies to each node we know of.
 947                 // However, this only reaches nodes that can be reached in a single hop.
 948                 // We don't have enough information to forward broadcast packets in this case.
 949                 case BMODE_DIRECT:
 950                         if(from != myself)
 951                                 break;
 952
 953                         for splay_each(node_t, n, node_tree)
 954                                 if(n->status.reachable && n != myself && ((n->via == myself && n->nexthop == n) || n->via == n))
 955                                         send_packet(n, packet);
 956                         break;
 957
 958                 default:
 959                         break;
 960         }
 961 }
 962
 963 static node_t *try_harder(const sockaddr_t *from, const vpn_packet_t *pkt) {
 964         node_t *n = NULL;
 965         bool hard = false;
 966         static time_t last_hard_try = 0;
 967
 968         for splay_each(edge_t, e, edge_weight_tree) {
 969                 if(!e->to->status.reachable || e->to == myself)
 970                         continue;
 971
 972                 if(sockaddrcmp_noport(from, &e->address)) {
 973                         if(last_hard_try == now.tv_sec)
 974                                 continue;
 975                         hard = true;
 976                 }
 977
 978                 if(!try_mac(e->to, pkt))
 979                         continue;
 980
 981                 n = e->to;
 982                 break;
 983         }
 984
 985         if(hard)
 986                 last_hard_try = now.tv_sec;
 987
 988         last_hard_try = now.tv_sec;
 989         return n;
 990 }
 991
 992 void handle_incoming_vpn_data(void *data, int flags) {
 993         listen_socket_t *ls = data;
 994         vpn_packet_t pkt;
 995         char *hostname;
 996         sockaddr_t from = {{0}};
 997         socklen_t fromlen = sizeof from;
 998         node_t *n;
 999         int len;
1000
1001         len = recvfrom(ls->udp.fd, pkt.seqno, MAXSIZE, 0, &from.sa, &fromlen);
1002
1003         if(len <= 0 || len > MAXSIZE) {
1004                 if(!sockwouldblock(sockerrno))
1005                         logger(DEBUG_ALWAYS, LOG_ERR, "Receiving packet failed: %s", sockstrerror(sockerrno));
1006                 return;
1007         }
1008
1009         pkt.len = len;
1010
1011         sockaddrunmap(&from); /* Some braindead IPv6 implementations do stupid things. */
1012
1013         n = lookup_node_udp(&from);
1014
1015         if(!n) {
1016                 n = try_harder(&from, &pkt);
1017                 if(n)
1018                         update_node_udp(n, &from);
1019                 else if(debug_level >= DEBUG_PROTOCOL) {
1020                         hostname = sockaddr2hostname(&from);
1021                         logger(DEBUG_PROTOCOL, LOG_WARNING, "Received UDP packet from unknown source %s", hostname);
1022                         free(hostname);
1023                         return;
1024                 }
1025                 else
1026                         return;
1027         }
1028
1029         n->sock = ls - listen_socket;
1030
1031         receive_udppacket(n, &pkt);
1032 }
1033
1034 void handle_device_data(void *data, int flags) {
1035         vpn_packet_t packet;
1036
1037         packet.priority = 0;
1038
1039         if(devops.read(&packet)) {
1040                 myself->in_packets++;
1041                 myself->in_bytes += packet.len;
1042                 route(myself, &packet);
1043         }
1044 }