Add AES-256-GCM support to SPTPS.
[tinc] / src / net_packet.c
1 /*
2     net_packet.c -- Handles in- and outgoing VPN packets
3     Copyright (C) 1998-2005 Ivo Timmermans,
4                   2000-2022 Guus Sliepen <guus@tinc-vpn.org>
5                   2010      Timothy Redaelli <timothy@redaelli.eu>
6                   2010      Brandon Black <blblack@gmail.com>
7
8     This program is free software; you can redistribute it and/or modify
9     it under the terms of the GNU General Public License as published by
10     the Free Software Foundation; either version 2 of the License, or
11     (at your option) any later version.
12
13     This program is distributed in the hope that it will be useful,
14     but WITHOUT ANY WARRANTY; without even the implied warranty of
15     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16     GNU General Public License for more details.
17
18     You should have received a copy of the GNU General Public License along
19     with this program; if not, write to the Free Software Foundation, Inc.,
20     51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
21 */
22
23 #include "system.h"
24
25 #ifdef HAVE_ZLIB
26 #define ZLIB_CONST
27 #include <zlib.h>
28
29 #endif
30
31 #ifdef HAVE_LZO
32 #include LZO1X_H
33 #endif
34
35 #ifdef HAVE_LZ4
36 #include <lz4.h>
37 #endif
38
39 #include "address_cache.h"
40 #include "cipher.h"
41 #include "conf.h"
42 #include "connection.h"
43 #include "compression.h"
44 #include "crypto.h"
45 #include "digest.h"
46 #include "device.h"
47 #include "ethernet.h"
48 #include "ipv4.h"
49 #include "ipv6.h"
50 #include "logger.h"
51 #include "net.h"
52 #include "netutl.h"
53 #include "protocol.h"
54 #include "route.h"
55 #include "utils.h"
56 #include "random.h"
57
58 /* The minimum size of a probe is 14 bytes, but since we normally use CBC mode
59    encryption, we can add a few extra random bytes without increasing the
60    resulting packet size. */
61 #define MIN_PROBE_SIZE 18
62
63 int keylifetime = 0;
64 #ifdef HAVE_LZO
65 static char lzo_wrkmem[LZO1X_999_MEM_COMPRESS > LZO1X_1_MEM_COMPRESS ? LZO1X_999_MEM_COMPRESS : LZO1X_1_MEM_COMPRESS];
66 #endif
67
68 #ifdef HAVE_LZ4
69
70 #ifdef HAVE_LZ4_BUILTIN
71 static LZ4_stream_t lz4_stream;
72 #else
73 static void *lz4_state = NULL;
74 #endif // HAVE_LZ4_BUILTIN
75
76 #endif // HAVE_LZ4
77
78 static void send_udppacket(node_t *, vpn_packet_t *);
79
80 unsigned replaywin = 32;
81 bool localdiscovery = true;
82 bool udp_discovery = true;
83 int udp_discovery_keepalive_interval = 10;
84 int udp_discovery_interval = 2;
85 int udp_discovery_timeout = 30;
86
87 #define MAX_SEQNO 1073741824
88
89 static void try_fix_mtu(node_t *n) {
90         if(n->mtuprobes < 0) {
91                 return;
92         }
93
94         if(n->mtuprobes == 20 || n->minmtu >= n->maxmtu) {
95                 if(n->minmtu > n->maxmtu) {
96                         n->minmtu = n->maxmtu;
97                 } else {
98                         n->maxmtu = n->minmtu;
99                 }
100
101                 n->mtu = n->minmtu;
102                 logger(DEBUG_TRAFFIC, LOG_INFO, "Fixing MTU of %s (%s) to %d after %d probes", n->name, n->hostname, n->mtu, n->mtuprobes);
103                 n->mtuprobes = -1;
104         }
105 }
106
107 static void reduce_mtu(node_t *n, int mtu) {
108         if(mtu < MINMTU) {
109                 mtu = MINMTU;
110         }
111
112         if(n->maxmtu > mtu) {
113                 n->maxmtu = mtu;
114         }
115
116         if(n->mtu > mtu) {
117                 n->mtu = mtu;
118         }
119
120         try_fix_mtu(n);
121 }
122
123 static void udp_probe_timeout_handler(void *data) {
124         node_t *n = data;
125
126         if(!n->status.udp_confirmed) {
127                 return;
128         }
129
130         logger(DEBUG_TRAFFIC, LOG_INFO, "Too much time has elapsed since last UDP ping response from %s (%s), stopping UDP communication", n->name, n->hostname);
131         n->status.udp_confirmed = false;
132         n->udp_ping_rtt = -1;
133         n->maxrecentlen = 0;
134         n->mtuprobes = 0;
135         n->minmtu = 0;
136         n->maxmtu = MTU;
137 }
138
139 static void send_udp_probe_reply(node_t *n, vpn_packet_t *packet, length_t len) {
140         if(!n->status.sptps && !n->status.validkey) {
141                 logger(DEBUG_TRAFFIC, LOG_INFO, "Trying to send UDP probe reply to %s (%s) but we don't have his key yet", n->name, n->hostname);
142                 return;
143         }
144
145         /* Type 2 probe replies were introduced in protocol 17.3 */
146         if((n->options >> 24) >= 3) {
147                 DATA(packet)[0] = 2;
148                 uint16_t len16 = htons(len);
149                 memcpy(DATA(packet) + 1, &len16, 2);
150                 packet->len = MIN_PROBE_SIZE;
151                 logger(DEBUG_TRAFFIC, LOG_INFO, "Sending type 2 probe reply length %u to %s (%s)", len, n->name, n->hostname);
152
153         } else {
154                 /* Legacy protocol: n won't understand type 2 probe replies. */
155                 DATA(packet)[0] = 1;
156                 logger(DEBUG_TRAFFIC, LOG_INFO, "Sending type 1 probe reply length %u to %s (%s)", len, n->name, n->hostname);
157         }
158
159         /* Temporarily set udp_confirmed, so that the reply is sent
160            back exactly the way it came in. */
161
162         bool udp_confirmed = n->status.udp_confirmed;
163         n->status.udp_confirmed = true;
164         send_udppacket(n, packet);
165         n->status.udp_confirmed = udp_confirmed;
166 }
167
168 static void udp_probe_h(node_t *n, vpn_packet_t *packet, length_t len) {
169         if(!DATA(packet)[0]) {
170                 logger(DEBUG_TRAFFIC, LOG_INFO, "Got UDP probe request %d from %s (%s)", packet->len, n->name, n->hostname);
171                 send_udp_probe_reply(n, packet, len);
172                 return;
173         }
174
175         if(DATA(packet)[0] == 2) {
176                 // It's a type 2 probe reply, use the length field inside the packet
177                 uint16_t len16;
178                 memcpy(&len16, DATA(packet) + 1, 2);
179                 len = ntohs(len16);
180         }
181
182         if(n->status.ping_sent) {  // a probe in flight
183                 gettimeofday(&now, NULL);
184                 struct timeval rtt;
185                 timersub(&now, &n->udp_ping_sent, &rtt);
186                 n->udp_ping_rtt = (int)(rtt.tv_sec * 1000000 + rtt.tv_usec);
187                 n->status.ping_sent = false;
188                 logger(DEBUG_TRAFFIC, LOG_INFO, "Got type %d UDP probe reply %d from %s (%s) rtt=%d.%03d", DATA(packet)[0], len, n->name, n->hostname, n->udp_ping_rtt / 1000, n->udp_ping_rtt % 1000);
189         } else {
190                 logger(DEBUG_TRAFFIC, LOG_INFO, "Got type %d UDP probe reply %d from %s (%s)", DATA(packet)[0], len, n->name, n->hostname);
191         }
192
193         /* It's a valid reply: now we know bidirectional communication
194            is possible using the address and socket that the reply
195            packet used. */
196         if(!n->status.udp_confirmed) {
197                 n->status.udp_confirmed = true;
198
199                 if(!n->address_cache) {
200                         n->address_cache = open_address_cache(n);
201                 }
202
203                 if(n->connection && n->connection->edge) {
204                         reset_address_cache(n->address_cache);
205                         add_recent_address(n->address_cache, &n->connection->edge->address);
206                 }
207         }
208
209         // Reset the UDP ping timer.
210
211         if(udp_discovery) {
212                 timeout_del(&n->udp_ping_timeout);
213                 timeout_add(&n->udp_ping_timeout, &udp_probe_timeout_handler, n, &(struct timeval) {
214                         udp_discovery_timeout, 0
215                 });
216         }
217
218         if(len > n->maxmtu) {
219                 logger(DEBUG_TRAFFIC, LOG_INFO, "Increase in PMTU to %s (%s) detected, restarting PMTU discovery", n->name, n->hostname);
220                 n->minmtu = len;
221                 n->maxmtu = MTU;
222                 /* Set mtuprobes to 1 so that try_mtu() doesn't reset maxmtu */
223                 n->mtuprobes = 1;
224                 return;
225         } else if(n->mtuprobes < 0 && len == n->maxmtu) {
226                 /* We got a maxmtu sized packet, confirming the PMTU is still valid. */
227                 n->mtuprobes = -1;
228                 n->mtu_ping_sent = now;
229         }
230
231         /* If applicable, raise the minimum supported MTU */
232
233         if(n->minmtu < len) {
234                 n->minmtu = len;
235                 try_fix_mtu(n);
236         }
237 }
238
239 #ifdef HAVE_LZ4
240 static length_t compress_packet_lz4(uint8_t *dest, const uint8_t *source, length_t len) {
241 #ifdef HAVE_LZ4_BUILTIN
242         return LZ4_compress_fast_extState(&lz4_stream, (const char *) source, (char *) dest, len, MAXSIZE, 0);
243 #else
244
245         /* @FIXME: Put this in a better place, and free() it too. */
246         if(lz4_state == NULL) {
247                 lz4_state = malloc(LZ4_sizeofState());
248         }
249
250         if(lz4_state == NULL) {
251                 logger(DEBUG_ALWAYS, LOG_ERR, "Failed to allocate lz4_state, error: %i", errno);
252                 return 0;
253         }
254
255         return LZ4_compress_fast_extState(lz4_state, (const char *) source, (char *) dest, len, MAXSIZE, 0);
256 #endif /* HAVE_LZ4_BUILTIN */
257 }
258 #endif /* HAVE_LZ4 */
259
260 #ifdef HAVE_LZO
261 static length_t compress_packet_lzo(uint8_t *dest, const uint8_t *source, length_t len, compression_level_t level) {
262         lzo_uint lzolen = MAXSIZE;
263         int result;
264
265         if(level == COMPRESS_LZO_HI) {
266                 result = lzo1x_999_compress(source, len, dest, &lzolen, lzo_wrkmem);
267         } else { // level == COMPRESS_LZO_LO
268                 result = lzo1x_1_compress(source, len, dest, &lzolen, lzo_wrkmem);
269         }
270
271         if(result == LZO_E_OK) {
272                 return lzolen;
273         } else {
274                 return 0;
275         }
276 }
277 #endif
278
279 static length_t compress_packet(uint8_t *dest, const uint8_t *source, length_t len, compression_level_t level) {
280         switch(level) {
281 #ifdef HAVE_LZ4
282
283         case COMPRESS_LZ4:
284                 return compress_packet_lz4(dest, source, len);
285 #endif
286
287 #ifdef HAVE_LZO
288
289         case COMPRESS_LZO_HI:
290         case COMPRESS_LZO_LO:
291                 return compress_packet_lzo(dest, source, len, level);
292 #endif
293 #ifdef HAVE_ZLIB
294
295         case COMPRESS_ZLIB_9:
296         case COMPRESS_ZLIB_8:
297         case COMPRESS_ZLIB_7:
298         case COMPRESS_ZLIB_6:
299         case COMPRESS_ZLIB_5:
300         case COMPRESS_ZLIB_4:
301         case COMPRESS_ZLIB_3:
302         case COMPRESS_ZLIB_2:
303         case COMPRESS_ZLIB_1: {
304                 unsigned long dest_len = MAXSIZE;
305
306                 if(compress2(dest, &dest_len, source, len, level) == Z_OK) {
307                         return dest_len;
308                 } else {
309                         return 0;
310                 }
311         }
312
313 #endif
314
315         case COMPRESS_NONE:
316                 memcpy(dest, source, len);
317                 return len;
318
319         default:
320                 return 0;
321         }
322 }
323
324 static length_t uncompress_packet(uint8_t *dest, const uint8_t *source, length_t len, compression_level_t level) {
325         switch(level) {
326 #ifdef HAVE_LZ4
327
328         case COMPRESS_LZ4:
329                 return LZ4_decompress_safe((char *)source, (char *) dest, len, MAXSIZE);
330
331 #endif
332 #ifdef HAVE_LZO
333
334         case COMPRESS_LZO_HI:
335         case COMPRESS_LZO_LO: {
336                 lzo_uint dst_len = MAXSIZE;
337
338                 if(lzo1x_decompress_safe(source, len, dest, &dst_len, NULL) == LZO_E_OK) {
339                         return dst_len;
340                 } else {
341                         return 0;
342                 }
343         }
344
345 #endif
346 #ifdef HAVE_ZLIB
347
348         case COMPRESS_ZLIB_9:
349         case COMPRESS_ZLIB_8:
350         case COMPRESS_ZLIB_7:
351         case COMPRESS_ZLIB_6:
352         case COMPRESS_ZLIB_5:
353         case COMPRESS_ZLIB_4:
354         case COMPRESS_ZLIB_3:
355         case COMPRESS_ZLIB_2:
356         case COMPRESS_ZLIB_1: {
357                 unsigned long destlen = MAXSIZE;
358                 static z_stream stream;
359
360                 if(stream.next_in) {
361                         inflateReset(&stream);
362                 } else {
363                         inflateInit(&stream);
364                 }
365
366                 stream.next_in = source;
367                 stream.avail_in = len;
368                 stream.next_out = dest;
369                 stream.avail_out = destlen;
370                 stream.total_out = 0;
371
372                 if(inflate(&stream, Z_FINISH) == Z_STREAM_END) {
373                         return stream.total_out;
374                 } else {
375                         return 0;
376                 }
377         }
378
379 #endif
380
381         case COMPRESS_NONE:
382                 memcpy(dest, source, len);
383                 return len;
384
385         default:
386                 return 0;
387         }
388 }
389
390 /* VPN packet I/O */
391
392 static void receive_packet(node_t *n, vpn_packet_t *packet) {
393         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Received packet of %d bytes from %s (%s)",
394                packet->len, n->name, n->hostname);
395
396         n->in_packets++;
397         n->in_bytes += packet->len;
398
399         route(n, packet);
400 }
401
402 static bool try_mac(node_t *n, const vpn_packet_t *inpkt) {
403         if(n->status.sptps) {
404                 return sptps_verify_datagram(&n->sptps, DATA(inpkt), inpkt->len);
405         }
406
407 #ifdef DISABLE_LEGACY
408         return false;
409 #else
410
411         if(!n->status.validkey_in || !digest_active(n->indigest) || (size_t)inpkt->len < sizeof(seqno_t) + digest_length(n->indigest)) {
412                 return false;
413         }
414
415         return digest_verify(n->indigest, inpkt->data, inpkt->len - digest_length(n->indigest), inpkt->data + inpkt->len - digest_length(n->indigest));
416 #endif
417 }
418
419 static bool receive_udppacket(node_t *n, vpn_packet_t *inpkt) {
420         if(n->status.sptps) {
421                 if(!n->sptps.state) {
422                         if(!n->status.waitingforkey) {
423                                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got packet from %s (%s) but we haven't exchanged keys yet", n->name, n->hostname);
424                                 send_req_key(n);
425                         } else {
426                                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got packet from %s (%s) but he hasn't got our key yet", n->name, n->hostname);
427                         }
428
429                         return false;
430                 }
431
432                 n->status.udppacket = true;
433                 bool result = sptps_receive_data(&n->sptps, DATA(inpkt), inpkt->len);
434                 n->status.udppacket = false;
435
436                 if(!result) {
437                         /* Uh-oh. It might be that the tunnel is stuck in some corrupted state,
438                            so let's restart SPTPS in case that helps. But don't do that too often
439                            to prevent storms, and because that would make life a little too easy
440                            for external attackers trying to DoS us. */
441                         if(n->last_req_key < now.tv_sec - 10) {
442                                 logger(DEBUG_PROTOCOL, LOG_ERR, "Failed to decode raw TCP packet from %s (%s), restarting SPTPS", n->name, n->hostname);
443                                 send_req_key(n);
444                         }
445
446                         return false;
447                 }
448
449                 return true;
450         }
451
452 #ifdef DISABLE_LEGACY
453         return false;
454 #else
455         vpn_packet_t pkt1, pkt2;
456         vpn_packet_t *pkt[] = { &pkt1, &pkt2, &pkt1, &pkt2 };
457         int nextpkt = 0;
458         size_t outlen;
459         pkt1.offset = DEFAULT_PACKET_OFFSET;
460         pkt2.offset = DEFAULT_PACKET_OFFSET;
461
462         if(!n->status.validkey_in) {
463                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got packet from %s (%s) but he hasn't got our key yet", n->name, n->hostname);
464                 return false;
465         }
466
467         /* Check packet length */
468
469         if((size_t)inpkt->len < sizeof(seqno_t) + digest_length(n->indigest)) {
470                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got too short packet from %s (%s)",
471                        n->name, n->hostname);
472                 return false;
473         }
474
475         /* It's a legacy UDP packet, the data starts after the seqno */
476
477         inpkt->offset += sizeof(seqno_t);
478
479         /* Check the message authentication code */
480
481         if(digest_active(n->indigest)) {
482                 inpkt->len -= digest_length(n->indigest);
483
484                 if(!digest_verify(n->indigest, SEQNO(inpkt), inpkt->len, SEQNO(inpkt) + inpkt->len)) {
485                         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got unauthenticated packet from %s (%s)", n->name, n->hostname);
486                         return false;
487                 }
488         }
489
490         /* Decrypt the packet */
491
492         if(cipher_active(n->incipher)) {
493                 vpn_packet_t *outpkt = pkt[nextpkt++];
494                 outlen = MAXSIZE;
495
496                 if(!cipher_decrypt(n->incipher, SEQNO(inpkt), inpkt->len, SEQNO(outpkt), &outlen, true)) {
497                         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Error decrypting packet from %s (%s)", n->name, n->hostname);
498                         return false;
499                 }
500
501                 outpkt->len = outlen;
502                 inpkt = outpkt;
503         }
504
505         /* Check the sequence number */
506
507         seqno_t seqno;
508         memcpy(&seqno, SEQNO(inpkt), sizeof(seqno));
509         seqno = ntohl(seqno);
510         inpkt->len -= sizeof(seqno);
511
512         if(replaywin) {
513                 if(seqno != n->received_seqno + 1) {
514                         if(seqno >= n->received_seqno + replaywin * 8) {
515                                 if(n->farfuture++ < replaywin >> 2) {
516                                         logger(DEBUG_TRAFFIC, LOG_WARNING, "Packet from %s (%s) is %d seqs in the future, dropped (%u)",
517                                                n->name, n->hostname, seqno - n->received_seqno - 1, n->farfuture);
518                                         return false;
519                                 }
520
521                                 logger(DEBUG_TRAFFIC, LOG_WARNING, "Lost %d packets from %s (%s)",
522                                        seqno - n->received_seqno - 1, n->name, n->hostname);
523                                 memset(n->late, 0, replaywin);
524                         } else if(seqno <= n->received_seqno) {
525                                 if((n->received_seqno >= replaywin * 8 && seqno <= n->received_seqno - replaywin * 8) || !(n->late[(seqno / 8) % replaywin] & (1 << seqno % 8))) {
526                                         logger(DEBUG_TRAFFIC, LOG_WARNING, "Got late or replayed packet from %s (%s), seqno %d, last received %d",
527                                                n->name, n->hostname, seqno, n->received_seqno);
528                                         return false;
529                                 }
530                         } else {
531                                 for(seqno_t i = n->received_seqno + 1; i < seqno; i++) {
532                                         n->late[(i / 8) % replaywin] |= 1 << i % 8;
533                                 }
534                         }
535                 }
536
537                 n->farfuture = 0;
538                 n->late[(seqno / 8) % replaywin] &= ~(1 << seqno % 8);
539         }
540
541         if(seqno > n->received_seqno) {
542                 n->received_seqno = seqno;
543         }
544
545         n->received++;
546
547         if(n->received_seqno > MAX_SEQNO) {
548                 regenerate_key();
549         }
550
551         /* Decompress the packet */
552
553         length_t origlen = inpkt->len;
554
555         if(n->incompression != COMPRESS_NONE) {
556                 vpn_packet_t *outpkt = pkt[nextpkt++];
557
558                 if(!(outpkt->len = uncompress_packet(DATA(outpkt), DATA(inpkt), inpkt->len, n->incompression))) {
559                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while uncompressing packet from %s (%s)",
560                                n->name, n->hostname);
561                         return false;
562                 }
563
564                 inpkt = outpkt;
565
566                 if(origlen > MTU / 64 + 20) {
567                         origlen -= MTU / 64 + 20;
568                 } else {
569                         origlen = 0;
570                 }
571         }
572
573         if(inpkt->len > n->maxrecentlen) {
574                 n->maxrecentlen = inpkt->len;
575         }
576
577         inpkt->priority = 0;
578
579         if(!DATA(inpkt)[12] && !DATA(inpkt)[13]) {
580                 udp_probe_h(n, inpkt, origlen);
581         } else {
582                 receive_packet(n, inpkt);
583         }
584
585         return true;
586 #endif
587 }
588
589 void receive_tcppacket(connection_t *c, const char *buffer, size_t len) {
590         vpn_packet_t outpkt;
591         outpkt.offset = DEFAULT_PACKET_OFFSET;
592
593         if(len > sizeof(outpkt.data) - outpkt.offset) {
594                 return;
595         }
596
597         outpkt.len = len;
598
599         if(c->options & OPTION_TCPONLY) {
600                 outpkt.priority = 0;
601         } else {
602                 outpkt.priority = -1;
603         }
604
605         memcpy(DATA(&outpkt), buffer, len);
606
607         receive_packet(c->node, &outpkt);
608 }
609
610 bool receive_tcppacket_sptps(connection_t *c, const char *data, size_t len) {
611         if(len < sizeof(node_id_t) + sizeof(node_id_t)) {
612                 logger(DEBUG_PROTOCOL, LOG_ERR, "Got too short TCP SPTPS packet from %s (%s)", c->name, c->hostname);
613                 return false;
614         }
615
616         node_t *to = lookup_node_id((node_id_t *)data);
617         data += sizeof(node_id_t);
618         len -= sizeof(node_id_t);
619
620         if(!to) {
621                 logger(DEBUG_PROTOCOL, LOG_ERR, "Got TCP SPTPS packet from %s (%s) with unknown destination ID", c->name, c->hostname);
622                 return true;
623         }
624
625         node_t *from = lookup_node_id((node_id_t *)data);
626         data += sizeof(node_id_t);
627         len -= sizeof(node_id_t);
628
629         if(!from) {
630                 logger(DEBUG_PROTOCOL, LOG_ERR, "Got TCP SPTPS packet from %s (%s) with unknown source ID", c->name, c->hostname);
631                 return true;
632         }
633
634         if(!to->status.reachable) {
635                 /* This can happen in the form of a race condition
636                    if the node just became unreachable. */
637                 logger(DEBUG_TRAFFIC, LOG_WARNING, "Cannot relay TCP packet from %s (%s) because the destination, %s (%s), is unreachable", from->name, from->hostname, to->name, to->hostname);
638                 return true;
639         }
640
641         /* Help the sender reach us over UDP.
642            Note that we only do this if we're the destination or the static relay;
643            otherwise every hop would initiate its own UDP info message, resulting in elevated chatter. */
644         if(to->via == myself) {
645                 send_udp_info(myself, from);
646         }
647
648         /* If we're not the final recipient, relay the packet. */
649
650         if(to != myself) {
651                 if(to->status.validkey) {
652                         send_sptps_data(to, from, 0, data, len);
653                 }
654
655                 try_tx(to, true);
656                 return true;
657         }
658
659         /* The packet is for us */
660
661         if(!sptps_receive_data(&from->sptps, data, len)) {
662                 /* Uh-oh. It might be that the tunnel is stuck in some corrupted state,
663                    so let's restart SPTPS in case that helps. But don't do that too often
664                    to prevent storms. */
665                 if(from->last_req_key < now.tv_sec - 10) {
666                         logger(DEBUG_PROTOCOL, LOG_ERR, "Failed to decode raw TCP packet from %s (%s), restarting SPTPS", from->name, from->hostname);
667                         send_req_key(from);
668                 }
669
670                 return true;
671         }
672
673         send_mtu_info(myself, from, MTU);
674         return true;
675 }
676
677 static void send_sptps_packet(node_t *n, vpn_packet_t *origpkt) {
678         if(!n->status.validkey && !n->connection) {
679                 return;
680         }
681
682         uint8_t type = 0;
683         int offset = 0;
684
685         if((!(DATA(origpkt)[12] | DATA(origpkt)[13])) && (n->sptps.outstate))  {
686                 sptps_send_record(&n->sptps, PKT_PROBE, DATA(origpkt), origpkt->len);
687                 return;
688         }
689
690         if(routing_mode == RMODE_ROUTER) {
691                 offset = 14;
692         } else {
693                 type = PKT_MAC;
694         }
695
696         if(origpkt->len < offset) {
697                 return;
698         }
699
700         vpn_packet_t outpkt;
701
702         if(n->outcompression != COMPRESS_NONE) {
703                 outpkt.offset = 0;
704                 length_t len = compress_packet(DATA(&outpkt) + offset, DATA(origpkt) + offset, origpkt->len - offset, n->outcompression);
705
706                 if(!len) {
707                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while compressing packet to %s (%s)", n->name, n->hostname);
708                 } else if(len < origpkt->len - offset) {
709                         outpkt.len = len + offset;
710                         origpkt = &outpkt;
711                         type |= PKT_COMPRESSED;
712                 }
713         }
714
715         /* If we have a direct metaconnection to n, and we can't use UDP, then
716            don't bother with SPTPS and just use a "plaintext" PACKET message.
717            We don't really care about end-to-end security since we're not
718            sending the message through any intermediate nodes. */
719         if(n->connection && origpkt->len > n->minmtu) {
720                 send_tcppacket(n->connection, origpkt);
721         } else {
722                 sptps_send_record(&n->sptps, type, DATA(origpkt) + offset, origpkt->len - offset);
723         }
724 }
725
726 static void adapt_socket(const sockaddr_t *sa, size_t *sock) {
727         /* Make sure we have a suitable socket for the chosen address */
728         if(listen_socket[*sock].sa.sa.sa_family != sa->sa.sa_family) {
729                 for(int i = 0; i < listen_sockets; i++) {
730                         if(listen_socket[i].sa.sa.sa_family == sa->sa.sa_family) {
731                                 *sock = i;
732                                 break;
733                         }
734                 }
735         }
736 }
737
738 static void choose_udp_address(const node_t *n, const sockaddr_t **sa, size_t *sock) {
739         /* Latest guess */
740         *sa = &n->address;
741         *sock = n->sock;
742
743         /* If the UDP address is confirmed, use it. */
744         if(n->status.udp_confirmed) {
745                 return;
746         }
747
748         /* Send every third packet to n->address; that could be set
749            to the node's reflexive UDP address discovered during key
750            exchange. */
751
752         static int x = 0;
753
754         if(++x >= 3) {
755                 x = 0;
756                 return;
757         }
758
759         /* Otherwise, address are found in edges to this node.
760            So we pick a random edge and a random socket. */
761
762         unsigned int i = 0;
763         unsigned int j = prng(n->edge_tree.count);
764         edge_t *candidate = NULL;
765
766         for splay_each(edge_t, e, &n->edge_tree) {
767                 if(i++ == j) {
768                         candidate = e->reverse;
769                         break;
770                 }
771         }
772
773         if(candidate) {
774                 *sa = &candidate->address;
775                 *sock = prng(listen_sockets);
776         }
777
778         adapt_socket(*sa, sock);
779 }
780
781 static void choose_local_address(const node_t *n, const sockaddr_t **sa, size_t *sock) {
782         *sa = NULL;
783
784         /* Pick one of the edges from this node at random, then use its local address. */
785
786         unsigned int i = 0;
787         unsigned int j = prng(n->edge_tree.count);
788         edge_t *candidate = NULL;
789
790         for splay_each(edge_t, e, &n->edge_tree) {
791                 if(i++ == j) {
792                         candidate = e;
793                         break;
794                 }
795         }
796
797         if(candidate && candidate->local_address.sa.sa_family) {
798                 *sa = &candidate->local_address;
799                 *sock = prng(listen_sockets);
800                 adapt_socket(*sa, sock);
801         }
802 }
803
804 static void send_udppacket(node_t *n, vpn_packet_t *origpkt) {
805         if(!n->status.reachable) {
806                 logger(DEBUG_TRAFFIC, LOG_INFO, "Trying to send UDP packet to unreachable node %s (%s)", n->name, n->hostname);
807                 return;
808         }
809
810         if(n->status.sptps) {
811                 send_sptps_packet(n, origpkt);
812                 return;
813         }
814
815 #ifdef DISABLE_LEGACY
816         return;
817 #else
818         vpn_packet_t pkt1, pkt2;
819         vpn_packet_t *pkt[] = { &pkt1, &pkt2, &pkt1, &pkt2 };
820         vpn_packet_t *inpkt = origpkt;
821         int nextpkt = 0;
822         vpn_packet_t *outpkt;
823         int origlen = origpkt->len;
824         size_t outlen;
825         int origpriority = origpkt->priority;
826
827         pkt1.offset = DEFAULT_PACKET_OFFSET;
828         pkt2.offset = DEFAULT_PACKET_OFFSET;
829
830         /* Make sure we have a valid key */
831
832         if(!n->status.validkey) {
833                 logger(DEBUG_TRAFFIC, LOG_INFO,
834                        "No valid key known yet for %s (%s), forwarding via TCP",
835                        n->name, n->hostname);
836                 send_tcppacket(n->nexthop->connection, origpkt);
837                 return;
838         }
839
840         if(n->options & OPTION_PMTU_DISCOVERY && inpkt->len > n->minmtu && (DATA(inpkt)[12] | DATA(inpkt)[13])) {
841                 logger(DEBUG_TRAFFIC, LOG_INFO,
842                        "Packet for %s (%s) larger than minimum MTU, forwarding via %s",
843                        n->name, n->hostname, n != n->nexthop ? n->nexthop->name : "TCP");
844
845                 if(n != n->nexthop) {
846                         send_packet(n->nexthop, origpkt);
847                 } else {
848                         send_tcppacket(n->nexthop->connection, origpkt);
849                 }
850
851                 return;
852         }
853
854         /* Compress the packet */
855
856         if(n->outcompression != COMPRESS_NONE) {
857                 outpkt = pkt[nextpkt++];
858
859                 if(!(outpkt->len = compress_packet(DATA(outpkt), DATA(inpkt), inpkt->len, n->outcompression))) {
860                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while compressing packet to %s (%s)",
861                                n->name, n->hostname);
862                         return;
863                 }
864
865                 inpkt = outpkt;
866         }
867
868         /* Add sequence number */
869
870         seqno_t seqno = htonl(++(n->sent_seqno));
871         memcpy(SEQNO(inpkt), &seqno, sizeof(seqno));
872         inpkt->len += sizeof(seqno);
873
874         /* Encrypt the packet */
875
876         if(cipher_active(n->outcipher)) {
877                 outpkt = pkt[nextpkt++];
878                 outlen = MAXSIZE;
879
880                 if(!cipher_encrypt(n->outcipher, SEQNO(inpkt), inpkt->len, SEQNO(outpkt), &outlen, true)) {
881                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while encrypting packet to %s (%s)", n->name, n->hostname);
882                         goto end;
883                 }
884
885                 outpkt->len = outlen;
886                 inpkt = outpkt;
887         }
888
889         /* Add the message authentication code */
890
891         if(digest_active(n->outdigest)) {
892                 if(!digest_create(n->outdigest, SEQNO(inpkt), inpkt->len, SEQNO(inpkt) + inpkt->len)) {
893                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while encrypting packet to %s (%s)", n->name, n->hostname);
894                         goto end;
895                 }
896
897                 inpkt->len += digest_length(n->outdigest);
898         }
899
900         /* Send the packet */
901
902         const sockaddr_t *sa = NULL;
903         size_t sock;
904
905         if(n->status.send_locally) {
906                 choose_local_address(n, &sa, &sock);
907         }
908
909         if(!sa) {
910                 choose_udp_address(n, &sa, &sock);
911         }
912
913         if(priorityinheritance && origpriority != listen_socket[sock].priority) {
914                 listen_socket[sock].priority = origpriority;
915
916                 switch(sa->sa.sa_family) {
917 #if defined(IP_TOS)
918
919                 case AF_INET:
920                         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Setting IPv4 outgoing packet priority to %d", origpriority);
921
922                         if(setsockopt(listen_socket[sock].udp.fd, IPPROTO_IP, IP_TOS, (void *)&origpriority, sizeof(origpriority))) { /* SO_PRIORITY doesn't seem to work */
923                                 logger(DEBUG_ALWAYS, LOG_ERR, "System call `%s' failed: %s", "setsockopt", sockstrerror(sockerrno));
924                         }
925
926                         break;
927 #endif
928 #if defined(IPV6_TCLASS)
929
930                 case AF_INET6:
931                         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Setting IPv6 outgoing packet priority to %d", origpriority);
932
933                         if(setsockopt(listen_socket[sock].udp.fd, IPPROTO_IPV6, IPV6_TCLASS, (void *)&origpriority, sizeof(origpriority))) { /* SO_PRIORITY doesn't seem to work */
934                                 logger(DEBUG_ALWAYS, LOG_ERR, "System call `%s' failed: %s", "setsockopt", sockstrerror(sockerrno));
935                         }
936
937                         break;
938 #endif
939
940                 default:
941                         break;
942                 }
943         }
944
945         if(sendto(listen_socket[sock].udp.fd, (void *)SEQNO(inpkt), inpkt->len, 0, &sa->sa, SALEN(sa->sa)) < 0 && !sockwouldblock(sockerrno)) {
946                 if(sockmsgsize(sockerrno)) {
947                         reduce_mtu(n, origlen - 1);
948                 } else {
949                         logger(DEBUG_TRAFFIC, LOG_WARNING, "Error sending packet to %s (%s): %s", n->name, n->hostname, sockstrerror(sockerrno));
950                 }
951         }
952
953 end:
954         origpkt->len = origlen;
955 #endif
956 }
957
958 bool send_sptps_data(node_t *to, node_t *from, int type, const void *data, size_t len) {
959         size_t origlen = len - SPTPS_DATAGRAM_OVERHEAD;
960         node_t *relay = (to->via != myself && (type == PKT_PROBE || origlen <= to->via->minmtu)) ? to->via : to->nexthop;
961         bool direct = from == myself && to == relay;
962         bool relay_supported = (relay->options >> 24) >= 4;
963         bool tcponly = (myself->options | relay->options) & OPTION_TCPONLY;
964
965         /* 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. */
966
967         if(type == SPTPS_HANDSHAKE || tcponly || (!direct && !relay_supported) || (type != PKT_PROBE && origlen > relay->minmtu)) {
968                 if(type != SPTPS_HANDSHAKE && (to->nexthop->connection->options >> 24) >= 7) {
969                         const size_t buflen = len + sizeof(to->id) + sizeof(from->id);
970                         uint8_t *buf = alloca(buflen);
971                         uint8_t *buf_ptr = buf;
972                         memcpy(buf_ptr, &to->id, sizeof(to->id));
973                         buf_ptr += sizeof(to->id);
974                         memcpy(buf_ptr, &from->id, sizeof(from->id));
975                         buf_ptr += sizeof(from->id);
976                         memcpy(buf_ptr, data, len);
977                         logger(DEBUG_TRAFFIC, LOG_INFO, "Sending packet from %s (%s) to %s (%s) via %s (%s) (TCP)", from->name, from->hostname, to->name, to->hostname, to->nexthop->name, to->nexthop->hostname);
978                         return send_sptps_tcppacket(to->nexthop->connection, buf, buflen);
979                 }
980
981                 char *buf = alloca(B64_SIZE(len));
982                 b64encode_tinc(data, buf, len);
983
984                 /* If this is a handshake packet, use ANS_KEY instead of REQ_KEY, for two reasons:
985                     - We don't want intermediate nodes to switch to UDP to relay these packets;
986                     - ANS_KEY allows us to learn the reflexive UDP address. */
987                 if(type == SPTPS_HANDSHAKE) {
988                         to->incompression = myself->incompression;
989                         return send_request(to->nexthop->connection, "%d %s %s %s -1 -1 -1 %d", ANS_KEY, from->name, to->name, buf, to->incompression);
990                 } else {
991                         return send_request(to->nexthop->connection, "%d %s %s %d %s", REQ_KEY, from->name, to->name, SPTPS_PACKET, buf);
992                 }
993         }
994
995         size_t overhead = 0;
996
997         if(relay_supported) {
998                 overhead += sizeof(to->id) + sizeof(from->id);
999         }
1000
1001         char *buf = alloca(len + overhead);
1002         char *buf_ptr = buf;
1003
1004         if(relay_supported) {
1005                 if(direct) {
1006                         /* Inform the recipient that this packet was sent directly. */
1007                         node_id_t nullid = {0};
1008                         memcpy(buf_ptr, &nullid, sizeof(nullid));
1009                         buf_ptr += sizeof(nullid);
1010                 } else {
1011                         memcpy(buf_ptr, &to->id, sizeof(to->id));
1012                         buf_ptr += sizeof(to->id);
1013                 }
1014
1015                 memcpy(buf_ptr, &from->id, sizeof(from->id));
1016                 buf_ptr += sizeof(from->id);
1017
1018         }
1019
1020         /* 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 */
1021         memcpy(buf_ptr, data, len);
1022         buf_ptr += len;
1023
1024         const sockaddr_t *sa = NULL;
1025         size_t sock;
1026
1027         if(relay->status.send_locally) {
1028                 choose_local_address(relay, &sa, &sock);
1029         }
1030
1031         if(!sa) {
1032                 choose_udp_address(relay, &sa, &sock);
1033         }
1034
1035         logger(DEBUG_TRAFFIC, LOG_INFO, "Sending packet from %s (%s) to %s (%s) via %s (%s) (UDP)", from->name, from->hostname, to->name, to->hostname, relay->name, relay->hostname);
1036
1037         if(sendto(listen_socket[sock].udp.fd, buf, buf_ptr - buf, 0, &sa->sa, SALEN(sa->sa)) < 0 && !sockwouldblock(sockerrno)) {
1038                 if(sockmsgsize(sockerrno)) {
1039                         reduce_mtu(relay, (int)origlen - 1);
1040                 } else {
1041                         logger(DEBUG_TRAFFIC, LOG_WARNING, "Error sending UDP SPTPS packet to %s (%s): %s", relay->name, relay->hostname, sockstrerror(sockerrno));
1042                         return false;
1043                 }
1044         }
1045
1046         return true;
1047 }
1048
1049 bool receive_sptps_record(void *handle, uint8_t type, const void *data, uint16_t len) {
1050         node_t *from = handle;
1051
1052         if(type == SPTPS_HANDSHAKE) {
1053                 if(!from->status.validkey) {
1054                         from->status.validkey = true;
1055                         from->status.waitingforkey = false;
1056                         logger(DEBUG_META, LOG_INFO, "SPTPS key exchange with %s (%s) successful", from->name, from->hostname);
1057                 }
1058
1059                 return true;
1060         }
1061
1062         if(len > MTU) {
1063                 logger(DEBUG_ALWAYS, LOG_ERR, "Packet from %s (%s) larger than maximum supported size (%d > %d)", from->name, from->hostname, len, MTU);
1064                 return false;
1065         }
1066
1067         vpn_packet_t inpkt;
1068         inpkt.offset = DEFAULT_PACKET_OFFSET;
1069         inpkt.priority = 0;
1070
1071         if(type == PKT_PROBE) {
1072                 if(!from->status.udppacket) {
1073                         logger(DEBUG_ALWAYS, LOG_ERR, "Got SPTPS PROBE packet from %s (%s) via TCP", from->name, from->hostname);
1074                         return false;
1075                 }
1076
1077                 inpkt.len = len;
1078                 memcpy(DATA(&inpkt), data, len);
1079
1080                 if(inpkt.len > from->maxrecentlen) {
1081                         from->maxrecentlen = inpkt.len;
1082                 }
1083
1084                 udp_probe_h(from, &inpkt, len);
1085                 return true;
1086         }
1087
1088         if(type & ~(PKT_COMPRESSED | PKT_MAC)) {
1089                 logger(DEBUG_ALWAYS, LOG_ERR, "Unexpected SPTPS record type %d len %d from %s (%s)", type, len, from->name, from->hostname);
1090                 return false;
1091         }
1092
1093         /* Check if we have the headers we need */
1094         if(routing_mode != RMODE_ROUTER && !(type & PKT_MAC)) {
1095                 logger(DEBUG_TRAFFIC, LOG_ERR, "Received packet from %s (%s) without MAC header (maybe Mode is not set correctly)", from->name, from->hostname);
1096                 return false;
1097         } else if(routing_mode == RMODE_ROUTER && (type & PKT_MAC)) {
1098                 logger(DEBUG_TRAFFIC, LOG_WARNING, "Received packet from %s (%s) with MAC header (maybe Mode is not set correctly)", from->name, from->hostname);
1099         }
1100
1101         int offset = (type & PKT_MAC) ? 0 : 14;
1102
1103         if(type & PKT_COMPRESSED) {
1104                 length_t ulen = uncompress_packet(DATA(&inpkt) + offset, (const uint8_t *)data, len, from->incompression);
1105
1106                 if(!ulen) {
1107                         return false;
1108                 } else {
1109                         inpkt.len = ulen + offset;
1110                 }
1111
1112                 if(inpkt.len > MAXSIZE) {
1113                         abort();
1114                 }
1115         } else {
1116                 memcpy(DATA(&inpkt) + offset, data, len);
1117                 inpkt.len = len + offset;
1118         }
1119
1120         /* Generate the Ethernet packet type if necessary */
1121         if(offset) {
1122                 switch(DATA(&inpkt)[14] >> 4) {
1123                 case 4:
1124                         DATA(&inpkt)[12] = 0x08;
1125                         DATA(&inpkt)[13] = 0x00;
1126                         break;
1127
1128                 case 6:
1129                         DATA(&inpkt)[12] = 0x86;
1130                         DATA(&inpkt)[13] = 0xDD;
1131                         break;
1132
1133                 default:
1134                         logger(DEBUG_TRAFFIC, LOG_ERR,
1135                                "Unknown IP version %d while reading packet from %s (%s)",
1136                                DATA(&inpkt)[14] >> 4, from->name, from->hostname);
1137                         return false;
1138                 }
1139         }
1140
1141         if(from->status.udppacket && inpkt.len > from->maxrecentlen) {
1142                 from->maxrecentlen = inpkt.len;
1143         }
1144
1145         receive_packet(from, &inpkt);
1146         return true;
1147 }
1148
1149 // This function tries to get SPTPS keys, if they aren't already known.
1150 // This function makes no guarantees - it is up to the caller to check the node's state to figure out if the keys are available.
1151 static void try_sptps(node_t *n) {
1152         if(n->status.validkey) {
1153                 return;
1154         }
1155
1156         logger(DEBUG_TRAFFIC, LOG_INFO, "No valid key known yet for %s (%s)", n->name, n->hostname);
1157
1158         if(!n->status.waitingforkey) {
1159                 send_req_key(n);
1160         } else if(n->last_req_key + 10 < now.tv_sec) {
1161                 logger(DEBUG_ALWAYS, LOG_DEBUG, "No key from %s after 10 seconds, restarting SPTPS", n->name);
1162                 sptps_stop(&n->sptps);
1163                 n->status.waitingforkey = false;
1164                 send_req_key(n);
1165         }
1166
1167         return;
1168 }
1169
1170 static void send_udp_probe_packet(node_t *n, size_t len) {
1171         vpn_packet_t packet;
1172
1173         if(len > sizeof(packet.data)) {
1174                 logger(DEBUG_TRAFFIC, LOG_INFO, "Truncating probe length %lu to %s (%s)", (unsigned long)len, n->name, n->hostname);
1175                 len = sizeof(packet.data);
1176         }
1177
1178         len = MAX(len, MIN_PROBE_SIZE);
1179         packet.offset = DEFAULT_PACKET_OFFSET;
1180         memset(DATA(&packet), 0, 14);
1181         randomize(DATA(&packet) + 14, len - 14);
1182         packet.len = len;
1183         packet.priority = 0;
1184
1185         logger(DEBUG_TRAFFIC, LOG_INFO, "Sending UDP probe length %lu to %s (%s)", (unsigned long)len, n->name, n->hostname);
1186
1187         send_udppacket(n, &packet);
1188 }
1189
1190 // This function tries to establish a UDP tunnel to a node so that packets can be sent.
1191 // If a tunnel is already established, it makes sure it stays up.
1192 // This function makes no guarantees - it is up to the caller to check the node's state to figure out if UDP is usable.
1193 static void try_udp(node_t *n) {
1194         if(!udp_discovery) {
1195                 return;
1196         }
1197
1198         /* Send gratuitous probe replies to 1.1 nodes. */
1199
1200         if((n->options >> 24) >= 3 && n->status.udp_confirmed) {
1201                 struct timeval ping_tx_elapsed;
1202                 timersub(&now, &n->udp_reply_sent, &ping_tx_elapsed);
1203
1204                 if(ping_tx_elapsed.tv_sec >= udp_discovery_keepalive_interval - 1) {
1205                         n->udp_reply_sent = now;
1206
1207                         if(n->maxrecentlen) {
1208                                 vpn_packet_t pkt;
1209                                 pkt.len = n->maxrecentlen;
1210                                 pkt.offset = DEFAULT_PACKET_OFFSET;
1211                                 memset(DATA(&pkt), 0, 14);
1212                                 randomize(DATA(&pkt) + 14, MIN_PROBE_SIZE - 14);
1213                                 send_udp_probe_reply(n, &pkt, pkt.len);
1214                                 n->maxrecentlen = 0;
1215                         }
1216                 }
1217         }
1218
1219         /* Probe request */
1220
1221         struct timeval ping_tx_elapsed;
1222         timersub(&now, &n->udp_ping_sent, &ping_tx_elapsed);
1223
1224         int interval = n->status.udp_confirmed
1225                        ? udp_discovery_keepalive_interval
1226                        : udp_discovery_interval;
1227
1228         if(ping_tx_elapsed.tv_sec >= interval) {
1229                 gettimeofday(&now, NULL);
1230                 n->udp_ping_sent = now; // a probe in flight
1231                 n->status.ping_sent = true;
1232                 send_udp_probe_packet(n, MIN_PROBE_SIZE);
1233
1234                 if(localdiscovery && !n->status.udp_confirmed && n->prevedge) {
1235                         n->status.send_locally = true;
1236                         send_udp_probe_packet(n, MIN_PROBE_SIZE);
1237                         n->status.send_locally = false;
1238                 }
1239         }
1240 }
1241
1242 static length_t choose_initial_maxmtu(node_t *n) {
1243 #ifdef IP_MTU
1244
1245         int sock = -1;
1246
1247         const sockaddr_t *sa = NULL;
1248         size_t sockindex;
1249         choose_udp_address(n, &sa, &sockindex);
1250
1251         if(!sa) {
1252                 return MTU;
1253         }
1254
1255         sock = socket(sa->sa.sa_family, SOCK_DGRAM, IPPROTO_UDP);
1256
1257         if(sock < 0) {
1258                 logger(DEBUG_TRAFFIC, LOG_ERR, "Creating MTU assessment socket for %s (%s) failed: %s", n->name, n->hostname, sockstrerror(sockerrno));
1259                 return MTU;
1260         }
1261
1262         if(connect(sock, &sa->sa, SALEN(sa->sa))) {
1263                 logger(DEBUG_TRAFFIC, LOG_ERR, "Connecting MTU assessment socket for %s (%s) failed: %s", n->name, n->hostname, sockstrerror(sockerrno));
1264                 closesocket(sock);
1265                 return MTU;
1266         }
1267
1268         int ip_mtu;
1269         socklen_t ip_mtu_len = sizeof(ip_mtu);
1270
1271         if(getsockopt(sock, IPPROTO_IP, IP_MTU, (void *)&ip_mtu, &ip_mtu_len)) {
1272                 logger(DEBUG_TRAFFIC, LOG_ERR, "getsockopt(IP_MTU) on %s (%s) failed: %s", n->name, n->hostname, sockstrerror(sockerrno));
1273                 closesocket(sock);
1274                 return MTU;
1275         }
1276
1277         closesocket(sock);
1278
1279         if(ip_mtu < MINMTU) {
1280                 logger(DEBUG_TRAFFIC, LOG_ERR, "getsockopt(IP_MTU) on %s (%s) returned absurdly small value: %d", n->name, n->hostname, ip_mtu);
1281                 return MTU;
1282         }
1283
1284         /* getsockopt(IP_MTU) returns the MTU of the physical interface.
1285            We need to remove various overheads to get to the tinc MTU. */
1286         length_t mtu = ip_mtu;
1287         mtu -= (sa->sa.sa_family == AF_INET6) ? sizeof(struct ip6_hdr) : sizeof(struct ip);
1288         mtu -= 8; /* UDP */
1289
1290         if(n->status.sptps) {
1291                 mtu -= SPTPS_DATAGRAM_OVERHEAD;
1292
1293                 if((n->options >> 24) >= 4) {
1294                         mtu -= sizeof(node_id_t) + sizeof(node_id_t);
1295                 }
1296
1297 #ifndef DISABLE_LEGACY
1298         } else {
1299                 mtu -= digest_length(n->outdigest);
1300
1301                 /* Now it's tricky. We use CBC mode, so the length of the
1302                    encrypted payload must be a multiple of the blocksize. The
1303                    sequence number is also part of the encrypted payload, so we
1304                    must account for it after correcting for the blocksize.
1305                    Furthermore, the padding in the last block must be at least
1306                    1 byte. */
1307
1308                 length_t blocksize = cipher_blocksize(n->outcipher);
1309
1310                 if(blocksize > 1) {
1311                         mtu /= blocksize;
1312                         mtu *= blocksize;
1313                         mtu--;
1314                 }
1315
1316                 mtu -= 4; // seqno
1317 #endif
1318         }
1319
1320         if(mtu > MTU) {
1321                 return MTU;
1322         }
1323
1324         logger(DEBUG_TRAFFIC, LOG_INFO, "Using system-provided maximum tinc MTU for %s (%s): %hd", n->name, n->hostname, mtu);
1325         return mtu;
1326
1327 #else
1328         (void)n;
1329         return MTU;
1330 #endif
1331 }
1332
1333 /* This function tries to determines the MTU of a node.
1334    By calling this function repeatedly, n->minmtu will be progressively
1335    increased, and at some point, n->mtu will be fixed to n->minmtu.  If the MTU
1336    is already fixed, this function checks if it can be increased.
1337 */
1338
1339 static void try_mtu(node_t *n) {
1340         if(!(n->options & OPTION_PMTU_DISCOVERY)) {
1341                 return;
1342         }
1343
1344         if(udp_discovery && !n->status.udp_confirmed) {
1345                 n->maxrecentlen = 0;
1346                 n->mtuprobes = 0;
1347                 n->minmtu = 0;
1348                 n->maxmtu = MTU;
1349                 return;
1350         }
1351
1352         /* mtuprobes == 0..19: initial discovery, send bursts with 1 second interval, mtuprobes++
1353            mtuprobes ==    20: fix MTU, and go to -1
1354            mtuprobes ==    -1: send one maxmtu and one maxmtu+1 probe every pinginterval
1355            mtuprobes ==-2..-3: send one maxmtu probe every second
1356            mtuprobes ==    -4: maxmtu no longer valid, reset minmtu and maxmtu and go to 0 */
1357
1358         struct timeval elapsed;
1359         timersub(&now, &n->mtu_ping_sent, &elapsed);
1360
1361         if(n->mtuprobes >= 0) {
1362                 if(n->mtuprobes != 0 && elapsed.tv_sec == 0 && elapsed.tv_usec < 333333) {
1363                         return;
1364                 }
1365         } else {
1366                 if(n->mtuprobes < -1) {
1367                         if(elapsed.tv_sec < 1) {
1368                                 return;
1369                         }
1370                 } else {
1371                         if(elapsed.tv_sec < pinginterval) {
1372                                 return;
1373                         }
1374                 }
1375         }
1376
1377         n->mtu_ping_sent = now;
1378
1379         try_fix_mtu(n);
1380
1381         if(n->mtuprobes < -3) {
1382                 /* We lost three MTU probes, restart discovery */
1383                 logger(DEBUG_TRAFFIC, LOG_INFO, "Decrease in PMTU to %s (%s) detected, restarting PMTU discovery", n->name, n->hostname);
1384                 n->mtuprobes = 0;
1385                 n->minmtu = 0;
1386         }
1387
1388         if(n->mtuprobes < 0) {
1389                 /* After the initial discovery, we only send one maxmtu and one
1390                    maxmtu+1 probe to detect PMTU increases. */
1391                 send_udp_probe_packet(n, n->maxmtu);
1392
1393                 if(n->mtuprobes == -1 && n->maxmtu + 1 < MTU) {
1394                         send_udp_probe_packet(n, n->maxmtu + 1);
1395                 }
1396
1397                 n->mtuprobes--;
1398         } else {
1399                 /* Before initial discovery begins, set maxmtu to the most likely value.
1400                    If it's underestimated, we will correct it after initial discovery. */
1401                 if(n->mtuprobes == 0) {
1402                         n->maxmtu = choose_initial_maxmtu(n);
1403                 }
1404
1405                 for(;;) {
1406                         /* Decreasing the number of probes per cycle might make the algorithm react faster to lost packets,
1407                            but it will typically increase convergence time in the no-loss case. */
1408                         const length_t probes_per_cycle = 8;
1409
1410                         /* This magic value was determined using math simulations.
1411                            It will result in a 1329-byte first probe, followed (if there was a reply) by a 1407-byte probe.
1412                            Since 1407 is just below the range of tinc MTUs over typical networks,
1413                            this fine-tuning allows tinc to cover a lot of ground very quickly.
1414                            This fine-tuning is only valid for maxmtu = MTU; if maxmtu is smaller,
1415                            then it's better to use a multiplier of 1. Indeed, this leads to an interesting scenario
1416                            if choose_initial_maxmtu() returns the actual MTU value - it will get confirmed with one single probe. */
1417                         const float multiplier = (n->maxmtu == MTU) ? 0.97f : 1.0f;
1418
1419                         const float cycle_position = (float) probes_per_cycle - (float)(n->mtuprobes % probes_per_cycle) - 1.0f;
1420                         const length_t minmtu = MAX(n->minmtu, MINMTU);
1421                         const float interval = (float)(n->maxmtu - minmtu);
1422
1423                         length_t offset = 0;
1424
1425                         /* powf can be underflowed if n->maxmtu is less than 512 due to the minmtu MAX bound */
1426                         if(interval > 0) {
1427                                 /* The core of the discovery algorithm is this exponential.
1428                                         It produces very large probes early in the cycle, and then it very quickly decreases the probe size.
1429                                         This reflects the fact that in the most difficult cases, we don't get any feedback for probes that
1430                                         are too large, and therefore we need to concentrate on small offsets so that we can quickly converge
1431                                         on the precise MTU as we are approaching it.
1432                                         The last probe of the cycle is always 1 byte in size - this is to make sure we'll get at least one
1433                                         reply per cycle so that we can make progress. */
1434                                 offset = lrintf(powf(interval, multiplier * cycle_position / (float)(probes_per_cycle - 1)));
1435                         }
1436
1437                         length_t maxmtu = n->maxmtu;
1438                         send_udp_probe_packet(n, minmtu + offset);
1439
1440                         /* If maxmtu changed, it means the probe was rejected by the system because it was too large.
1441                            In that case, we recalculate with the new maxmtu and try again. */
1442                         if(n->mtuprobes < 0 || maxmtu == n->maxmtu) {
1443                                 break;
1444                         }
1445                 }
1446
1447                 if(n->mtuprobes >= 0) {
1448                         n->mtuprobes++;
1449                 }
1450         }
1451 }
1452
1453 /* These functions try to establish a tunnel to a node (or its relay) so that
1454    packets can be sent (e.g. exchange keys).
1455    If a tunnel is already established, it tries to improve it (e.g. by trying
1456    to establish a UDP tunnel instead of TCP).  This function makes no
1457    guarantees - it is up to the caller to check the node's state to figure out
1458    if TCP and/or UDP is usable.  By calling this function repeatedly, the
1459    tunnel is gradually improved until we hit the wall imposed by the underlying
1460    network environment.  It is recommended to call this function every time a
1461    packet is sent (or intended to be sent) to a node, so that the tunnel keeps
1462    improving as packets flow, and then gracefully downgrades itself as it goes
1463    idle.
1464 */
1465
1466 static void try_tx_sptps(node_t *n, bool mtu) {
1467         /* If n is a TCP-only neighbor, we'll only use "cleartext" PACKET
1468            messages anyway, so there's no need for SPTPS at all. */
1469
1470         if(n->connection && ((myself->options | n->options) & OPTION_TCPONLY)) {
1471                 return;
1472         }
1473
1474         /* Otherwise, try to do SPTPS authentication with n if necessary. */
1475
1476         try_sptps(n);
1477
1478         /* Do we need to statically relay packets? */
1479
1480         node_t *via = (n->via == myself) ? n->nexthop : n->via;
1481
1482         /* If we do have a static relay, try everything with that one instead, if it supports relaying. */
1483
1484         if(via != n) {
1485                 if((via->options >> 24) < 4) {
1486                         return;
1487                 }
1488
1489                 try_tx(via, mtu);
1490                 return;
1491         }
1492
1493         /* Otherwise, try to establish UDP connectivity. */
1494
1495         try_udp(n);
1496
1497         if(mtu) {
1498                 try_mtu(n);
1499         }
1500
1501         /* If we don't have UDP connectivity (yet), we need to use a dynamic relay (nexthop)
1502            while we try to establish direct connectivity. */
1503
1504         if(!n->status.udp_confirmed && n != n->nexthop && (n->nexthop->options >> 24) >= 4) {
1505                 try_tx(n->nexthop, mtu);
1506         }
1507 }
1508
1509 static void try_tx_legacy(node_t *n, bool mtu) {
1510         /* Does he have our key? If not, send one. */
1511
1512         if(!n->status.validkey_in) {
1513                 send_ans_key(n);
1514         }
1515
1516         /* Check if we already have a key, or request one. */
1517
1518         if(!n->status.validkey) {
1519                 if(n->last_req_key + 10 <= now.tv_sec) {
1520                         send_req_key(n);
1521                         n->last_req_key = now.tv_sec;
1522                 }
1523
1524                 return;
1525         }
1526
1527         try_udp(n);
1528
1529         if(mtu) {
1530                 try_mtu(n);
1531         }
1532 }
1533
1534 void try_tx(node_t *n, bool mtu) {
1535         if(!n->status.reachable) {
1536                 return;
1537         }
1538
1539         if(n->status.sptps) {
1540                 try_tx_sptps(n, mtu);
1541         } else {
1542                 try_tx_legacy(n, mtu);
1543         }
1544 }
1545
1546 void send_packet(node_t *n, vpn_packet_t *packet) {
1547         // If it's for myself, write it to the tun/tap device.
1548
1549         if(n == myself) {
1550                 if(overwrite_mac) {
1551                         memcpy(DATA(packet), mymac.x, ETH_ALEN);
1552                         // Use an arbitrary fake source address.
1553                         memcpy(DATA(packet) + ETH_ALEN, DATA(packet), ETH_ALEN);
1554                         DATA(packet)[ETH_ALEN * 2 - 1] ^= 0xFF;
1555                 }
1556
1557                 n->out_packets++;
1558                 n->out_bytes += packet->len;
1559                 devops.write(packet);
1560                 return;
1561         }
1562
1563         logger(DEBUG_TRAFFIC, LOG_ERR, "Sending packet of %d bytes to %s (%s)", packet->len, n->name, n->hostname);
1564
1565         // If the node is not reachable, drop it.
1566
1567         if(!n->status.reachable) {
1568                 logger(DEBUG_TRAFFIC, LOG_INFO, "Node %s (%s) is not reachable", n->name, n->hostname);
1569                 return;
1570         }
1571
1572         // Keep track of packet statistics.
1573
1574         n->out_packets++;
1575         n->out_bytes += packet->len;
1576
1577         // Check if it should be sent as an SPTPS packet.
1578
1579         if(n->status.sptps) {
1580                 send_sptps_packet(n, packet);
1581                 try_tx(n, true);
1582                 return;
1583         }
1584
1585         // Determine which node to actually send it to.
1586
1587         node_t *via = (packet->priority == -1 || n->via == myself) ? n->nexthop : n->via;
1588
1589         if(via != n) {
1590                 logger(DEBUG_TRAFFIC, LOG_INFO, "Sending packet to %s via %s (%s)", n->name, via->name, n->via->hostname);
1591         }
1592
1593         // Try to send via UDP, unless TCP is forced.
1594
1595         if(packet->priority == -1 || ((myself->options | via->options) & OPTION_TCPONLY)) {
1596                 if(!send_tcppacket(via->connection, packet)) {
1597                         terminate_connection(via->connection, true);
1598                 }
1599
1600                 return;
1601         }
1602
1603         send_udppacket(via, packet);
1604         try_tx(via, true);
1605 }
1606
1607 void broadcast_packet(const node_t *from, vpn_packet_t *packet) {
1608         // Always give ourself a copy of the packet.
1609         if(from != myself) {
1610                 send_packet(myself, packet);
1611         }
1612
1613         // In TunnelServer mode, do not forward broadcast packets.
1614         // The MST might not be valid and create loops.
1615         if(tunnelserver || broadcast_mode == BMODE_NONE) {
1616                 return;
1617         }
1618
1619         logger(DEBUG_TRAFFIC, LOG_INFO, "Broadcasting packet of %d bytes from %s (%s)",
1620                packet->len, from->name, from->hostname);
1621
1622         switch(broadcast_mode) {
1623         // In MST mode, broadcast packets travel via the Minimum Spanning Tree.
1624         // This guarantees all nodes receive the broadcast packet, and
1625         // usually distributes the sending of broadcast packets over all nodes.
1626         case BMODE_MST:
1627                 for list_each(connection_t, c, &connection_list)
1628                         if(c->edge && c->status.mst && c != from->nexthop->connection) {
1629                                 send_packet(c->node, packet);
1630                         }
1631
1632                 break;
1633
1634         // In direct mode, we send copies to each node we know of.
1635         // However, this only reaches nodes that can be reached in a single hop.
1636         // We don't have enough information to forward broadcast packets in this case.
1637         case BMODE_DIRECT:
1638                 if(from != myself) {
1639                         break;
1640                 }
1641
1642                 for splay_each(node_t, n, &node_tree)
1643                         if(n->status.reachable && n != myself && ((n->via == myself && n->nexthop == n) || n->via == n)) {
1644                                 send_packet(n, packet);
1645                         }
1646
1647                 break;
1648
1649         case BMODE_NONE:
1650         default:
1651                 break;
1652         }
1653 }
1654
1655 /* We got a packet from some IP address, but we don't know who sent it.  Try to
1656    verify the message authentication code against all active session keys.
1657    Since this is actually an expensive operation, we only do a full check once
1658    a minute, the rest of the time we only check against nodes for which we know
1659    an IP address that matches the one from the packet.  */
1660
1661 static node_t *try_harder(const sockaddr_t *from, const vpn_packet_t *pkt) {
1662         node_t *match = NULL;
1663         bool hard = false;
1664         static time_t last_hard_try = 0;
1665
1666         for splay_each(node_t, n, &node_tree) {
1667                 if(!n->status.reachable || n == myself) {
1668                         continue;
1669                 }
1670
1671                 if(!n->status.validkey_in && !(n->status.sptps && n->sptps.instate)) {
1672                         continue;
1673                 }
1674
1675                 bool soft = false;
1676
1677                 for splay_each(edge_t, e, &n->edge_tree) {
1678                         if(!e->reverse) {
1679                                 continue;
1680                         }
1681
1682                         if(!sockaddrcmp_noport(from, &e->reverse->address)) {
1683                                 soft = true;
1684                                 break;
1685                         }
1686                 }
1687
1688                 if(!soft) {
1689                         if(last_hard_try == now.tv_sec) {
1690                                 continue;
1691                         }
1692
1693                         hard = true;
1694                 }
1695
1696                 if(!try_mac(n, pkt)) {
1697                         continue;
1698                 }
1699
1700                 match = n;
1701                 break;
1702         }
1703
1704         if(hard) {
1705                 last_hard_try = now.tv_sec;
1706         }
1707
1708         return match;
1709 }
1710
1711 static void handle_incoming_vpn_packet(listen_socket_t *ls, vpn_packet_t *pkt, sockaddr_t *addr) {
1712         char *hostname;
1713         node_id_t nullid = {0};
1714         node_t *from, *to;
1715         bool direct = false;
1716
1717         sockaddrunmap(addr); /* Some braindead IPv6 implementations do stupid things. */
1718
1719         // Try to figure out who sent this packet.
1720
1721         node_t *n = lookup_node_udp(addr);
1722
1723         if(n && !n->status.udp_confirmed) {
1724                 n = NULL;        // Don't believe it if we don't have confirmation yet.
1725         }
1726
1727         if(!n) {
1728                 // It might be from a 1.1 node, which might have a source ID in the packet.
1729                 pkt->offset = 2 * sizeof(node_id_t);
1730                 from = lookup_node_id(SRCID(pkt));
1731
1732                 if(from && from->status.sptps && !memcmp(DSTID(pkt), &nullid, sizeof(nullid))) {
1733                         if(sptps_verify_datagram(&from->sptps, DATA(pkt), pkt->len - 2 * sizeof(node_id_t))) {
1734                                 n = from;
1735                         } else {
1736                                 goto skip_harder;
1737                         }
1738                 }
1739         }
1740
1741         if(!n) {
1742                 pkt->offset = 0;
1743                 n = try_harder(addr, pkt);
1744         }
1745
1746 skip_harder:
1747
1748         if(!n) {
1749                 if(debug_level >= DEBUG_PROTOCOL) {
1750                         hostname = sockaddr2hostname(addr);
1751                         logger(DEBUG_PROTOCOL, LOG_WARNING, "Received UDP packet from unknown source %s", hostname);
1752                         free(hostname);
1753                 }
1754
1755                 return;
1756         }
1757
1758         pkt->offset = 0;
1759
1760         if(n->status.sptps) {
1761                 bool relay_enabled = (n->options >> 24) >= 4;
1762
1763                 if(relay_enabled) {
1764                         pkt->offset = 2 * sizeof(node_id_t);
1765                         pkt->len -= pkt->offset;
1766                 }
1767
1768                 if(!relay_enabled || !memcmp(DSTID(pkt), &nullid, sizeof(nullid))) {
1769                         direct = true;
1770                         from = n;
1771                         to = myself;
1772                 } else {
1773                         from = lookup_node_id(SRCID(pkt));
1774                         to = lookup_node_id(DSTID(pkt));
1775                 }
1776
1777                 if(!from || !to) {
1778                         logger(DEBUG_PROTOCOL, LOG_WARNING, "Received UDP packet from %s (%s) with unknown source and/or destination ID", n->name, n->hostname);
1779                         return;
1780                 }
1781
1782                 if(!to->status.reachable) {
1783                         /* This can happen in the form of a race condition
1784                            if the node just became unreachable. */
1785                         logger(DEBUG_TRAFFIC, LOG_WARNING, "Cannot relay packet from %s (%s) because the destination, %s (%s), is unreachable", from->name, from->hostname, to->name, to->hostname);
1786                         return;
1787                 }
1788
1789                 /* The packet is supposed to come from the originator or its static relay
1790                    (i.e. with no dynamic relays in between).
1791                    If it did not, "help" the static relay by sending it UDP info.
1792                    Note that we only do this if we're the destination or the static relay;
1793                    otherwise every hop would initiate its own UDP info message, resulting in elevated chatter. */
1794
1795                 if(n != from->via && to->via == myself) {
1796                         send_udp_info(myself, from);
1797                 }
1798
1799                 /* If we're not the final recipient, relay the packet. */
1800
1801                 if(to != myself) {
1802                         send_sptps_data(to, from, 0, DATA(pkt), pkt->len);
1803                         try_tx(to, true);
1804                         return;
1805                 }
1806         } else {
1807                 direct = true;
1808                 from = n;
1809         }
1810
1811         if(!receive_udppacket(from, pkt)) {
1812                 return;
1813         }
1814
1815         n->sock = ls - listen_socket;
1816
1817         if(direct && sockaddrcmp(addr, &n->address)) {
1818                 update_node_udp(n, addr);
1819         }
1820
1821         /* If the packet went through a relay, help the sender find the appropriate MTU
1822            through the relay path. */
1823
1824         if(!direct) {
1825                 send_mtu_info(myself, n, MTU);
1826         }
1827 }
1828
1829 void handle_incoming_vpn_data(void *data, int flags) {
1830         (void)data;
1831         (void)flags;
1832         listen_socket_t *ls = data;
1833
1834 #ifdef HAVE_RECVMMSG
1835 #define MAX_MSG 64
1836         static ssize_t num = MAX_MSG;
1837         static vpn_packet_t pkt[MAX_MSG];
1838         static sockaddr_t addr[MAX_MSG];
1839         static struct mmsghdr msg[MAX_MSG];
1840         static struct iovec iov[MAX_MSG];
1841
1842         for(int i = 0; i < num; i++) {
1843                 pkt[i].offset = 0;
1844
1845                 iov[i] = (struct iovec) {
1846                         .iov_base = DATA(&pkt[i]),
1847                         .iov_len = MAXSIZE,
1848                 };
1849
1850                 msg[i].msg_hdr = (struct msghdr) {
1851                         .msg_name = &addr[i].sa,
1852                         .msg_namelen = sizeof(addr)[i],
1853                         .msg_iov = &iov[i],
1854                         .msg_iovlen = 1,
1855                 };
1856         }
1857
1858         num = recvmmsg(ls->udp.fd, msg, MAX_MSG, MSG_DONTWAIT, NULL);
1859
1860         if(num < 0) {
1861                 if(!sockwouldblock(sockerrno)) {
1862                         logger(DEBUG_ALWAYS, LOG_ERR, "Receiving packet failed: %s", sockstrerror(sockerrno));
1863                 }
1864
1865                 return;
1866         }
1867
1868         for(int i = 0; i < num; i++) {
1869                 pkt[i].len = msg[i].msg_len;
1870
1871                 if(pkt[i].len <= 0 || pkt[i].len > MAXSIZE) {
1872                         continue;
1873                 }
1874
1875                 handle_incoming_vpn_packet(ls, &pkt[i], &addr[i]);
1876         }
1877
1878 #else
1879         vpn_packet_t pkt;
1880         sockaddr_t addr = {0};
1881         socklen_t addrlen = sizeof(addr);
1882
1883         pkt.offset = 0;
1884         ssize_t len = recvfrom(ls->udp.fd, (void *)DATA(&pkt), MAXSIZE, 0, &addr.sa, &addrlen);
1885
1886         if(len <= 0 || (size_t)len > MAXSIZE) {
1887                 if(!sockwouldblock(sockerrno)) {
1888                         logger(DEBUG_ALWAYS, LOG_ERR, "Receiving packet failed: %s", sockstrerror(sockerrno));
1889                 }
1890
1891                 return;
1892         }
1893
1894         pkt.len = len;
1895
1896         handle_incoming_vpn_packet(ls, &pkt, &addr);
1897 #endif
1898 }
1899
1900 void handle_device_data(void *data, int flags) {
1901         (void)data;
1902         (void)flags;
1903         vpn_packet_t packet;
1904         packet.offset = DEFAULT_PACKET_OFFSET;
1905         packet.priority = 0;
1906         static int errors = 0;
1907
1908         if(devops.read(&packet)) {
1909                 errors = 0;
1910                 myself->in_packets++;
1911                 myself->in_bytes += packet.len;
1912                 route(myself, &packet);
1913         } else {
1914                 sleep_millis(errors * 50);
1915                 errors++;
1916
1917                 if(errors > 10) {
1918                         logger(DEBUG_ALWAYS, LOG_ERR, "Too many errors from %s, exiting!", device);
1919                         event_exit();
1920                 }
1921         }
1922 }