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