Why not just use Tor?

Tor (onion routing) is a peer-to-peer system for achieving anonymous communication. At a high level, the idea is that, by forwarding encrypted data through a sequence of hops, a passive observer would not be able to determine who the two end-points of the communication are. Tor has become very popular and successful at avoiding some kinds of attacks. So successful, in fact, that some regions seek to block all Tor traffic altogether.

There is some precedence for avoidance in Tor; it currently has a feature by which users can explicitly exclude certain countries from Tor's circuit construction algorithm, but unfortunately this does not preclude those countries from being on the path between two hops on the circuit.

We believe Alibi Routing can complement Tor by choosing hops so that the entire end-to-end path avoids regions that users suspect are dropping Tor traffic.

How do you prove exactly where the packet went?

Simple: we don't!

Instead, we prove two things:

  1. That the packet went through an overlay node (a peer). This is proved by the peer signing (or more simply adding a MAC to) the packet.
  2. That the round-trip time of the data (the time it takes to go from the source, through the relay, to the destination, and back) is less than the time it would have taken a packet to go through the relay and the forbidden region.
So, in other words, we use the signature (or MAC) to know precisely one place in the world the packet did go, and we use end-to-end timing to figure out where else in the world it could not have gone.

How do you measure the minimal time it takes for a packet to travel?

One of the goals of Alibi Routing is to be able to work without having to actively measure the topology of the Internet, or even typical latencies on the Internet, as both of these could be manipulated by an active adversary.

Instead, we make use of something that no adversary can manipulate: the fact that information cannot travel faster than the speed of light. If we know that the shortest possible distance to get to any point in a forbidden region is D, then the shortest possible round-trip time through that point is 2*D/c. If we ever see a round-trip time less than this, then we know it could not have gone through the forbidden region.

Is the speed of light enough to really factor into latencies?

Light (and information) can travel really fast: in one second, it could circle the world about 7.5 times. Over very short distances (e.g., two laptops in the same room), latencies are dominated by the time it takes the computers to process the data.

But when considering longer paths -- paths that traverse countries, not just rooms -- the speed at which information can propagate does indeed play a large role. For example, the minimum time it would take to cross the United States and return is about 32 milliseconds (assuming a distance of 3000 miles). In Internet latencies, this is significant and easy for a program to measure.

Where can I download Alibi Routing?

You can download the research prototype at the Alibi Routing homepage. We are actively working on an easier-to-use tool, and we hope to make it publicly available by the end of the year. Stay tuned!