Some questions about SPTPS

[Etienne Dechamps]

On 16/07/2014 10:52, Etienne Dechamps wrote:
> - The way SPTPS is currently implemented in tinc, sending packets over
> TCP is extremely inefficient because instead of using PACKET messages
> like the legacy protocol does, it encapsulates the packet in a REQ_KEY
> message (for backwards compatibility reasons, I guess).

Looking into this some more, I realized it's even worse than I thought: 
not only is TCP packet transport inefficient, it's also the only way to 
indirect a packet through a relay. This is because, as far as I can 
tell, there is no way to relay UDP SPTPS packets, since there's no way 
to know what their recipient is without decrypting them, but only the 
recipient has the key.

This is a significant regression when compared to the legacy protocol: 
tinc used to try (1) direct UDP communication, (2) indirect UDP 
communication, (3) indirect TCP communication, thus always choosing the 
most efficient path to the destination. With SPTPS, (2) is impossible 
and tinc falls back directly to (3).

What's worse, with the way SPTPS over TCP is currently implemented using 
REQ_KEY/ANS_KEY messages, the packet will be transported over TCP 
through the entire graph. In contrast, with the legacy protocol tinc 
uses TCP over as few edges as possible, i.e. as soon as the packet lands 
on a node with an UDP path to the destination the packet would get an 
"upgrade" to "business class" UDP. This is not the case with SPTPS. One 
possible fix is to make nodes intercept SPTPS over TCP packets and 
resend them over UDP instead of TCP if possible, but it's not as simple 
as it sounds: indeed, when the final recipient receives the packet, it 
will fail to decrypt it because it will use the relay's key instead of 
the original sender's.

One simple solution to fix these relaying issues would be to send 
packets in SPTPS records that are encrypted using the relay's key, but 
of course that would defeat the whole point of end-to-end encryption.

I have a rough proposal that will hopefully bring the best of both 
worlds. Basically, when a node wants to send an SPTPS record through a 
relay via UDP, it would add a header to the UDP packet containing the 
first 4 bytes of the SHA-256 hash of the recipient node name and the 
source node name (total 8 bytes). The rest of the packet would be the 
original SPTPS datagram, encrypted as usual with the end-to-end key. The 
relay node would then use the hash to figure out what the final 
recipient is, and then blindly relay the packet to that recipient (or to 
the next relay). If multiple nodes have the same hash (which, according 
to the birthday problem, has a 0.01% chance of happening with 1000 
nodes), then UDP relaying is considered impossible and communication 
would fall back to TCP.

Now this is where it gets tricky: there is no simple way on the relay 
side to differentiate a "normal" incoming packet (where the first 4 
bytes is the seqno) and a "relay" incoming packet (where the first 4 
bytes is the recipient hash). I have a solution in mind, which is kinda 
ugly but should work just fine: try to decrypt the packet as usual, if 
it fails, and the first 8 bytes are two known hashes, then relay. This 
is not as inefficient as it sounds: we can make the decryption fail-fast 
in the vast majority of cases by checking the seqno first.

One thing to note though: for this to work the relay node needs to know 
the actual UDP address of the source node, otherwise it would try to get 
it from trying node keys on the packet, but the packet is not encrypted 
using any of those keys, so that wouldn't work. The obvious solution is 
to make the source node and the relay probe MTU between each other 
before attempting to relay, which will provide reliable UDP address 
information (as well as UDP hole punching, etc.) and is required anyway 
to ensure the UDP packets will get through. In that sense the behavior 
is identical to the legacy protocol.

When the final relay sends the packet over UDP to the final recipient, 
it will preserve the relay header when sending the packet. This is 
because the recipient needs the source node hash in order to know which 
key to use (otherwise it would use the relay node's key, and fail).

One could suggest that it would be useful to have this relay header for 
every packet (including direct ones), since that would optimize the 
unknown UDP source address code path (try_harder()) by using the source 
information instead of trying all keys. IMHO I don't think it's worth 
the overhead, especially since it would affect the case that's supposed 
to be the most efficient (direct UDP communication).

Of course, MTU calculations would have to take the relay header overhead 
(8 bytes) into account when sending a data packet through a relay.

The relaying feature would be accompanied by a minor protocol version 
bump. Sending nodes will fall back to TCP if the recipient node doesn't 
understand relaying.

In terms of security, while this doesn't allow an attacker to break the 
secrecy of communications (since end-to-end encryption is still used), 
it does allow an attacker to trick nodes into relaying bogus packets, 
assuming it can impersonate a node's UDP address. Therefore the worst 
that can be done would be to perhaps increase the load on the network 
somewhat (no potential for amplification). Considering this requires a 
MITM, I don't think this is important enough for us to care. In 
addition, one can deduce what the source and destination nodes are just 
by looking at a relay packet, but that's no worse than direct 
communication where this information is given away by the source and 
destination IP addresses anyway.

Thoughts?

-- 
Etienne Dechamps