Some questions about SPTPS

[Etienne Dechamps]

Since this is a complex issue that involves a lot of different 
approaches and tradeoffs, I took the liberty of writing a design doc to 
flesh it all out:

https://docs.google.com/document/d/1lOo05SsylNMMLLavdzJwdQ37Y25i6AkVMFhztcCDu6o/edit?usp=sharing

To my dismay, I realized that my original proposal for transporting node 
identifiers in UDP packets using a simple cleartext header is not viable 
because it would introduce a nasty security vulnerability allowing an 
external attacker to trick any node into sending packets to *any* IP 
address (including addresses outside the graph). Details can be found at 
the end of the "unauthenticated relay header" section in the doc.

Therefore I believe Guus' SPTPS-in-SPTPS idea is the only viable one 
when it comes to the UDP packet format for relaying.

Regarding the node identifiers, the document lists all ideas that were 
brought up.

After carefully weighing the tradeoffs, and realizing that I was 
probably a little too concerned about overhead (10 bytes is only 0.6% of 
a MTU-sized packet after all...), I would vote for the following:

Node identifiers: hash-based identifier, 48-bit hash, no conflict 
resolution.
Wire format: SPTPS in SPTPS with cleartext signed node identifiers; 
identifiers would also appear in direct (non-relayed) packets as well to 
make unknown-source-address key selection faster at the receiving end.

On 27/07/2014 17:07, Etienne Dechamps wrote:
> On 27/07/2014 14:58, Guus Sliepen wrote:
>>> 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.
>>
>> Hashes are indeed an option, but they can fail. And if they fail, the
>> only option would be to rename a node, which is very inconvenient.
>
> Yes, I'm aware, but that seems very unlikely to happen: according to the
> "Goals" page we want tinc to be able to scale to one thousand nodes. As
> I mentioned, with one thousand nodes the probability of collision is
> 0.01% (one in one thousand). Besides, if two nodes do collide, it's not
> the end of the world: it just means these two nodes can't be used as the
> source or destination of a relay path. They would still be reachable via
> direct UDP communication, they would still be reachable via TCP, and
> they would still be able to act as relays themselves.
>
> Here's another idea, though: we could add a conflict resolution
> mechanism to the protocol. By default the "relay ID" would be the hash
> of the name of the node (because that requires no coordination), but
> then, if a node realizes it has the same "relay ID" as another node, it
> would change its relay ID to an unused one and then broadcast a message
> "my relay ID changed, here's the new one", thus ending the conflict. Of
> course, there would be some way of making sure only one of the two nodes
> changes its ID (for example it could be the one with the top name in
> lexicographical order). All nodes would then make sure the entire graph
> is aware of these "non-canonical relay IDs" by broadcasting them on each
> new metaconnection.
>
> In fact, with this resolution mechanism we could probably get away with
> making these "relay IDs" only 2 bytes instead of 4. After all, even if
> every node has to broadcast an ID, it's still less metaconnection
> traffic than the list of edges for example. This would cap the maximum
> number of nodes on a graph to 65536, but is that really a problem?
>
>> Two other options:
>>
>> - Rely on the fact that all nodes have exactly the same list of edges
>>    and subnets, and that those are ordered. So one can number them and
>>    use those numbers instead of hashes. That way, there normally are no
>>    conflicts, only for brief moments when add/del messages are being
>>    sent.
>
> I don't think I like this idea. Sure, it's simple, but then I'm worried
> about what will happen if there are frequent changes to the graph. One
> example is a node with a flaky connection to the rest of the graph: in
> that case there could be changes every few seconds. This is of course
> exacerbated by large numbers of nodes. The problem is, these changes
> don't propagate immediately; if you are actively using a link, then you
> would end up losing a few packets every time that happens, which is not
> something users tend to like very well. I think there's too much
> potential for things to go very wrong when relying on such a brittle
> pointer mechanism.
>
>> - Use a form of MPLS: when node A wants to relay messages to C via B, it
>>    asks B to give it a tag that is unique for B that tells B the packets
>>    are from A and to be forwarded to C. Of course, then B itself should
>>    get a tag from C (or if B cannot reach C directly either, from another
>>    intermediate node). The drawback of this scheme is that it requires
>>    additional requests and more data structures to maintain.
>
> I had this idea as well. As you mentioned, the drawback is additional
> complexity (stateful vs stateless). The lifetime of these tags would
> have to be managed, I'm guessing using a timeout. It would also increase
> the overhead of setting up a relay path and increase traffic on
> metaconnections - especially if the path is long (multi-relay), though I
> guess that's not a big deal.
>
> The only advantage I can see (when compared with my conflict resolution
> idea) is that we could get away with a one-byte tag, but then a source
> can only use a relay to reach 256 different destinations.
>
>>> 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 other option is to do hop-by-hop and end-to-end encryption in this
>> case, with the hop-by-hop encrypted packet getting a different SPTPS
>> record type than the normal packets, to signal the intermediate nodes
>> that they have to forward it and that it has an 8 byte header to tell
>> the source and destination. Apart from reducing the path MTU, this is
>> only less efficient for the source and final destination, for the
>> intermediate nodes it's the same amount of work as with the legacy
>> protocol. A benefit would be that there is no way for MITMs or other
>> attackers to make a node relay fake or duplicate packets.
>
> I thought of that, but now in each relayed packet you have one more
> seqno, one more type byte, and most importantly one more HMAC, which
> brings the total overhead including the 8-byte routing information to 29
> bytes! That's a lot of overhead just to protect against a benign fake
> relay scenario...
>
>> One possibility would be to reserve one value of the seqno field in the
>> UDP SPTPS packets (say, 0xffffffff) for signalling that this is not a
>> regular packet. That means the header for to-be-forwarded packets
>> becomes 12 bytes, but that's a small price to pay.
>
> Yeah, but I don't think we have to pay that price, because failing to
> decrypt is cheap anyway (since the seqno will be completely off in most
> cases).
>
>> Everything you wrote makes sense. I had already thought about this issue
>> myself a bit, and had similar ideas. If you want to try to implement
>> this, go ahead!
>
> I might, but I wouldn't hold my breath; I'm busy with other things at
> the moment.
>


-- 
Etienne Dechamps