Trying Trusted Tor Traceroutes

A similar project description was given in the original email on 10/23/13 to tor-relays@lists.torproject.org.

We are running an experiment to improve Tor security. As you may be aware, the anonymity of a connection over Tor is vulnerable to an adversary who can observe it in enough places along its route. For example, traffic that crosses the same country as it enters and leaves the Tor network can potentially be deanonymized by an authority in that country who can monitor all network communication. Researchers have been working to figure out how Tor traffic gets routed over the Internet, but determining routes with high confidence has been difficult.

To figure out where traffic travels from each Tor relay, we'd like Tor relay operators to run a bunch of "traceroutes" — network measurements that show the paths traffic takes. This is a one-time experiment for now, but, depending on what we find out, regularly making such measurements may become a part of Tor itself. We have already gotten some results thanks to Linus Nordberg of DFRI and Moritz Bartl of torservers.net, and now we are extending it to all relay operators.

We have written some shell scripts to automate most of the process. The easiest way to get them is with git, using the following commands:

We have made the files from that commit available as a single archive here (for Debian older scamper version 20070523n please run this script), and you can also download the individual files directly at the Bitbucket repository. Detailed instructions for setting up and running the experiment are in the README. sha512 hash of the source code is available here.

Basically the experiment does traceroutes to three groups: all "routable IP prefixes", all Tor relays, and then all /24 subnets. These kinds of measurements are not uncommon, and they will not be done at a high rate (see this question for details on resource consumption). By default the scripts will periodically move the results to our server via SSH, although you can keep the results around and/or not send them automatically if you wish (see the README). The traceroute data recorded is not sensitive or private at all. We plan to make the code and data public, following Tor's practice of open cooperation with the research community.

The measurements will work best if you have the "scamper" tool from the Cooperative Association for Internet Data Analysis (CAIDA) installed (see the README for installation instructions). This is a standard and open-source tool that handles the many modern complexities of Internet routing measurement. If you are not able to run scamper, the script will also work with the more-common but less-accurate and slower "traceroute" utility. We do not currently have support for Windows relays. The output will take up around 500KB disk space if you use scamper; on the other hand if you use "traceroute" utility each output will be around 4MB (see this question for details on resource consumption). Depending on whether you run scamper or traceroute the total time required varies but results for traceroutes to "routable IP prefixes" and all Tor relays should finish within one week (possibly earlier). We would like to request relay operators to upload those results once finished (see the README for instructions on doing so).

This experiment is in collaboration with several researchers, but the leads are Anupam Das, a Ph.D. student at the University of Illinois at Urbana-Champaign, and his advisor Nikita Borisov. Based on a review of the scripts of commit 4493e7c21199fcabd23e41a817599ac2bec6397b, we believe that they operate as described above. Please do read through them yourself, and let us know if you have any questions or concerns. And also feel free to contact us for help or with suggestions.

Live Scoreboard of Participants

We have implemented a live scoreboard for participants to check the current status of the script running on their machines. The live scoreboard is available here.

FAQ (Frequently Anticipated Questions)

The time to completion varies, but if you use the scamper tool we expect it to complete within 4 days, and if you use the traceroute tool we expect it to complete within 24 days. Also, the measurement proceeds in three phases, each of which is very useful on its own. If you choose to run the measurements without automatic upload, please send us the results of each phase when it is finished (for details on see the README). Here are detailed completion times for each phase and with different parameter settings you might select:

	Scamper completion time			Traceroute completion time
	PPS=1000 (default)	PPS=500	PPS=100	PARALLEL=128 (default)	PARALLEL=64	PARALLEL=32
Phase 1 (Routable IP prefixes)	3.3 hours	6.5 hours	1.4 days	21 hours	1.6 days	3.3 days
Phase 2 (Tor relays)	3.6 min	7.3 min	36.3 min	3 hours	43.5 min	1.5 hours
Phase 3 (All /24 subnets)	4 days	8 days	38 days	23 days	45 days	92 days
Total (All phases)	4 days	8 days	40 days	24 days	48 days	96 days

You can adjust the rate at which the measurement is done to change bandwidth requirements. For scamper, change the PPS parameter from its default of 1000. For traceroute, change PARALLEL from its default of 128. Here is what you can expect:

	Using Scamper	Using Traceroute
Bandwidth (Up/Down) PPS=1000, PARALLEL=128 (default)	58.6/58.6 KiBps	45/45 KiBps
Bandwidth (Up/Down) PPS=500, PARALLEL=64	29.3/29.3 KiBps	22.5/22.5 KiBps
Bandwidth (Up/Down) PPS=100, PARALLEL=32	5.86/5.86 KiBps	11.25/11.25 KiBps
Disk space DONTERASE=no (default)	300—700 KiB	1—4 MiB
Disk space DONTERASE=yes	110 MiB	500 MiB
RAM	16.4 MiB	1000 MiB
CPU	0.15 GHz	0.061 GHz

We want to know the actual routes on the Internet that traffic takes to and from Tor relays. This will help us figure out which network providers, governments, facility operators, etc. are in a position to watch Tor's traffic. Although the traffic is encrypted, the "traffic pattern" (how much is sent at any given time) is not altered much. This is to keep Tor speedy and efficient. However, the pattern can reveal clues about the content (e.g. website fingerprinting) or allow somebody next to the source and destination to figure out that they are talking together (e.g. traffic correlation). There are ways to infer these paths that don't use direct measurements from Tor relays, but we don't have high confidence in them, and we are running an experiment to see how much more we can learn from direct measurements. If it works well, such measurements could become part of the Tor relay program itself. The traceroute measurement is done by the Scamper tool from CAIDA (unless you opt for the standard traceroute tool packaged in most UNIX systems). Basically, during these traceroutes, a sequence of UDP packets is sent with a time-to-live (TTL) that starts at 1 and incremented by 1 with each subsequent packet. TTLs are decremented by 1 each time they pass through an IP router. When an IP router receives a packet with a TTL of 0, it drops it and returns an ICMP "Time exceeded" packet, thus revealing the router to be on the route to the destination. The measurement proceeds in three phases:

The first phase runs a traceroute to each "routable IP prefix", as revealed by Route Views. The list we are using (in prefix.txt) includes 491,762 prefixes, and this phase performs a traceroute to one random IP within each of them. Because of the potential for latency attacks, we filter all timing information in this phase and only record IPs.
The second phase runs a traceroute to each relay in the Tor network. This helps us figure out how traffic flows inside the Tor network. We include any IP that appeared in a consensus during the week of 9/19/13-9/25/13. There are 9058 such IPs (see relay-ips.txt). We do include the latency measurements in this phase because (i) published latency attacks only require measuring latency of the links outside the Tor network, (ii) they are already so easy to measure by anybody (just measure the time to extend a Tor circuit between two relays), and (iii) the latencies will help researchers model the Tor network.
The third phase runs traceroutes to each IPv4 /24 subnet on the Internet. Our script will perform a traceroute to a random IP within each of the 14,461,947 possible /24s (see allowed-ips.txt for a list of the ranges). Although in theory all IPs that share a prefix in our IP prefix list from Phase 1 should have the same path, we include this measurement phase because (i) BGP tables (and thus the IP prefixes) can change at any time, (ii) BGP operates at the AS level, while we are interested in other path features (e.g. IXPs) that may differ even if the AS-level path is the same, and (iii) routes advertised over BGP are merely promises without any verification. Then why do we start with the prefixes at all? We do because we are interested in any discrepancies between the two phases, and also because the first phase is much faster and will get us most of what we need even if the relay goes down or has to stop running the measurement over the longer term.

The sequence is which IPs are chosen have been randomized to prevent intermediate routers from rate-limiting ICMP responses and to reduce the chance of setting off any alarm by Intrusion Detection Systems. We have used the permutation algorithm proposed by Jeff Preshing.

Absolutely! If you have another machine on the same local network that you know uses the same routers applying the same routing rules, then this is just as good. We must be able to infer which Tor relays share the network with that machine, but presumably we can do so simply by assigning relays to a measurement server in the same /24.

A couple of things that scamper does better than traceroute are (i) it uses the Paris traceroute techniques to map load-balancing (i.e. multiple) paths, and (ii) it implements efficient traceroute parallelization which was up to 6x faster in our tests. Scamper has been refined over many years to do exactly the kind of Internet-wide traceroute measurement that we are doing, and it has been designed by the masters of this kind of measurement, the Cooperative Association for Internet Data Analysis (CAIDA).

No. This project is done in cooperation with the Tor Project, Karsten Loesing being the main participant from Tor. We take security very seriously, and all of the code is open source and was written to be easy to read and verify. Moreover, none of the data that we collect is considered private, as fairly accurate Internet maps and traceroute measurements are already publicly available, and anybody can run traceroutes to Tor relays.

In fact, this project is just the opposite: an attempt to improve Tor security. By figuring out how to accurately determine Internet routing on behalf of Tor clients, we can ultimately change the way that they connect to Tor to better protect their privacy. However, if you have a concern about security. please do contact us. We are definitely open to suggested improvements!

No, the traceroutes are sent directly from the relay to the destinations.

We would like all public Tor relays to participate, that is, all normal relays but not bridge relays. This data will be public, and so we cannot use data from bridges. You are running a bridge only if you have specifically chosen to be a bridge.

Guard and exit relays are particularly useful because the security issue we are investigating concerns traffic into and out of Tor. However, we believe that doing these measurements from middle relays will be useful for other kinds of security analyses, and therefore we ask every public relay to participate.

The short answer is: probably not. We have received measurements from over 90 separate IPs, and, of these, we are aware of 2 relay operators who have had a problem with their network provider. In both cases, the provider was Hetzner, which seems to automatically classify the traceroutes as a Netscan and threaten the server with disconnection if the activity doesn't stop (see the report). We're trying to figure out what specifically triggers the classification to give a recommendation for this case.

In general, the measurements have been designed to avoid setting off any triggers for high-volume or anomalous traffic: they use a measurement methodology that is compliant with Internet protocol standards, they are not done at a very high rate, their destination ports are not "interesting", they do not cover every IPv4 address (only every IPv4 /24 subnet), and their address order is randomized.

Will multiple runs of the script be useful?

Yes, we encourage multiple runs of the script if possible because such measurements will potentially help us identify any temporal change in the routes taken by the traffic. ISPs often change paths based on their policy causing the traffic to take different paths. So doing multiple runs will help us narrow down the probable paths.

Trying Trusted Tor Traceroutes

Project Description

Live Scoreboard of Participants

FAQ (Frequently Anticipated Questions)