Some questions about SPTPS

[Etienne Dechamps]

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