RetroShare’s anonymous routing model

• Component: Turtle router
• Development: Dec. 2009 – Jun. 2010
• Status: released

Motivation

Transferring data/files in a Peer-to-Peer (P2P) network boils down to requesting and sending data packets between computers in the internet, referred to by their IP address. In typical Peer-to-Peer (P2P) protocols such as bittorrent, emule, a peer connects directly with many peers and gets a small part of the desired file from each. This is termed a file-sharing swarm, and often contains many computers which are unknown to each other, and only identified by their internet (IP) address (See [2] for a complete overview):

Classical bittorrent style file transfer: any participating peer that has the file can be a direct source to the requesting client C.

As a consequence, determining what a peer is downloading is pretty simple: one just needs to setup a computer to provide many files (acting as a bait) and record the IP addresses of the downloaders. Its obviously more complex than that, but the important thing to note, is that direct connections between a client and its sources is the weak point.

RetroShare solves this problem by using a Friend-to-Friend file search and exchange mechanism based on two principles:

• explicit data transfers only occur between trusted friends
• friend-to-friend transfers are encrypted using signed SSL certificates.

These friend-2-friend connections are chained together to provide a secure and anonymous file-transfer tunnels across the whole Retroshare network, using a turtle router. The first principle prevents classical bittorrent spying techniques such as the one described above. The second prevents more advanced spying mechanisms based on man-in-the-middle attacks.

RetroShare’s file transfer uses an anonymous routing model called turtle router over the friend-to-friend network. This routing algorithm allows non direct friends to exchange data anonymously using tunnels. The data is by nature encrypted between each pair of friends along the tunnel.

RetroShare model: C, as a client receives data through its trusted friends only. The ultimate sources G and J and not known to C, and C is not known to them either.

The original idea was taken from the PhD thesis of Petr Matejka: Security in Peer-to-Peer Networks [1].

Search mechanism

Searching through the RetroShare network is performed by broadcasting a search request packet to all connected friends. These friends will forward it to their own friends, until the packet is too old. If a result is found the list of matching files is sent back by the inverse route that the request took.

Implementation wise, this behaviour is achieved by keeping a cache of received search requests. The cache is examined each time new request is received. If already present, the request is discarded.

Tunnel establishment protocol

Turtle tunnels are established using the same protocol as search. A separate cache is used to store tunnel requests, and route tunnel accept packets back to the original client.

Each time a tunnel request is sent, it is given two numbers: its request id, and its half-id. The former is used to index the tunnel request in the cache of all peers that store it. Each time a new tunnel is formed, a new random id must be used.

The half-id of a tunnel request is a non reversible hash of the client SSL id, and the file hash for which the tunnel will be used. It is salted by a session-dependent random number. Once a peer responds to the tunnel request, it will merge this half-id with his own half-id, in a non symmetric way to obtain the final tunnel id (RetroShare users see tunnels as “anonymous tunnel 0x45eb7a34”. The ending number is the tunnel id). This means that:

• tunnels between a given source and destination for a given hash, always have the same tunnel id (although the tunnel request id changes every time) whatever the route they take;
• the tunnel id is non symmetrical. This means that a tunnel from A to B for a given hash will not have the same id than a tunnel from B to A for this hash;
• from the half-id alone (resp. tunnel id), it is not possible to brute-force the requesting peer id, because of the salting mechanism.

The second property is important because two peers might have two tunnels to each others for the same file going both ways. This happens when both peers are clients for a hash that is swarming between multiple peers. The two tunnels might cross in between and their ids should cause no ambiguity.

Finally, the tunnel protocols in RetroShare use no global addressing, as opposed to the original design by Matejka [1]. Once established, a tunnel is always represented at each peer along the tunnel by a pair of direct friends. When data comes from one friend, it is automatically forwarded to the other friend and vis versa.

Tunnel life handling

One major difference between the implementation of turtle in RetroShare and the original implementation described by P.Matejka in his thesis, is that tunnels in RetroShare do not need additional management packets such as for closing a tunnel, or managing bandwidth.

Tunnels are removed from the list of existing tunnels by each peer when the traffic along the tunnel is null for a definite period of time (60 seconds). This simple technique allows us to robustly handle any incidental change of the network topology. If a tunnel is e.g. broken because a peer disconnects, the tunnel will be removed by all other participating peers after 60 seconds, without the need to send a special tunnel closing packet.

Tunnels do not need bandwidth management either. In the RetroShare model, the client is responsible for asking data chunks, and adapts its requests to the speed at which the data comes. Since the speed of a tunnel is governed by the minimum speed along each hop, the data will eventually come at the maximum speed it can achieve, and the full tunnel bandwidth will be used. From the point of view of a local observer, it is however not easy to quantify how fast a tunnel could be, and except for that slowest hop, the tunnel always appears to be slower than it could locally go.

From the point of view of the file transfer, each tunnel appears as just another connected peer to which data chunks can be requested.

Performance

Transfer rates for a given file in the multi-hop friend-to-friend model  are governed by two factors:

• the minimum upload speed along the tunnels
• the number of tunnels that serve a file

Using asymmetric DSL connections, the former mostly depends on the upload speed of peers along the tunnel (Mostly 100 kB/s in France). When people have fibre optics internet connections, the speed is considerably larger (can easily be 600 kB/s per tunnel, up to 3 MB/s depending on the ISP).

Having multiple tunnels for a single downloads is quite the normal situation with RetroShare. The number of sources for well shared files is mostly in the range of 5-15 tunnels, although there is no explicit limitation. Not all tunnels have maximal speed however, since each peer potentially routes many tunnels at once, and the performances are shared between all tunnels passing through a given peer.

As a consequence, RetroShare users do not experience the same transfer rates than using bittorrent, but this is the price to pay for 100% privacy.

In an upcoming post, we’ll treat the more technical aspects of the turtle router: security, speed, and other nasty algorithmic details.

References:

[1] Safe and Private Data Sharing with Turtle: Friends Team-Up and Beat the System
Popescu, B.C. ; Crispo, B. ; Tanenbaum, A.S.
Proceedings of the 12th Cambridge International Workshop on Security Protocols, 2004

https://en.wikipedia.or/wiki/Turtle_F2F.

[2] Handbook of Peer-to-Peer Networking (1st ed.).
Shen, Xuemin; Yu, Heather; Buford, John; Akon, Mursalin  New York: Springer. (2009). ISBN 0-387-09750-3.