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.
