[tor-dev] Ideas for metrics of the safety of the Tor network

George Kadianakis desnacked at riseup.net
Sat Jun 8 18:44:07 UTC 2013

A year ago or so, during FOCI '12, with the help of some smart people [0]
I compiled a list of interesting metrics/visualizations that could
help us understand the security of the Tor network.

Since even more people are interested in metrics lately, I thought of
posting this list here, in case it inspires someone (better than
letting it rot unseen). Note that some of the stuff in the list might
have been implemented already, and there are also some upcoming
academic papers that explore this area.

Also, check out https://trac.torproject.org/projects/tor/ticket/6460

In any case, I'm inlining the list:

1 Attacker strategy 
    1.1 Are there certain geographic or network locations where adding relays with a given capacity will most influence your safety metrics? This influence could be positive ("where should I put my relay to best help the Tor network?") or negative ("where should I put my relay to best attack users?"). 
    1.2 What happens to the network if X relays are compromised? 
        1.2.1 All Windows relays. 
        1.2.2 All relays running old Tor versions. 
        1.2.3 All "top 10% relays" are compromised... 
    1.3 How much bandwidth do I need to compromise, in order to compromise a random user's path in a given timeframe 
        1.3.1 Use 'guessing entropy'?
    1.4 Is there a difference between compromising a '5Mbit relay' and 'five 1Mbit relays'? Should there be a difference? 
    1.5 Change classic Tor formula to start considering bandwidth load balancing. 
        1.5.1 "If an adversary controls m out of n nodes, he can correlate at most (m/n)^2 of the traffic." should consider bandwidth 
    1.6 See how many exits are exiting on a different IP than the one they accept traffic? (they can sniff twice) 

2 Network diversity 
    2.1 How many relays are running old Tor versions? 
    2.2 Fraction of paths that have the entry and exit at the same country/AS. 
    2.3 Fraction of paths that pass twice through AMS-IX/LINX/DE-CIX. 
    2.4 What happens to the network if we discard relays of certain characteristics? 
        2.4.1 What happens if we discard the slowest relays? 
        2.4.2 What happens if we cap the fastest relays? 
        2.4.3 Discard paths with expected high latency (http://swiki.cc.gatech.edu:8080/ugResearch/uploads/7/ImprovingTor.pdf) 
    2.5 If only a given fraction of exit relays support IPv6, how much does it reduce your anonymity to be going to an IPv6-only destination?
        2.5.1 Should we add a fourth hop, like we do in exit enclaving? 
    2.6 Is there any relationship between the rate of new relay arrival (e.g. during political events or after popular conferences) and the level of diversity of these relays?
    2.7 Graph showing "the X% of the relays see Y% of the traffic" 
        2.7.1 example, "The 5% of the relays route 55% of the traffic"... 
        2.7.2 Lorenz Curve / Gini coefficient  (Used in "Improving Security and Performance in the Tor Network through Tunable Path Selection")
    2.8 Measure router families and how much bandwidth they control/how many circuits they can compromise. 
    2.9 What is the security difference if families did not exist? 
    2.10 How much does the /16 subnet restriction influence path selection? 

3 Optimization results 
    3.1 Robustness over time: is an adversary that can knock out X% of the capacity in the network (for various values of X) getting more or less influential as the network grows? How about an adversary who can knock out an absolute capacity of K bytes for various values of K? 
        3.1.1 Look at the vailability/uptime/whatever of relays and YOU decide which relay has the guard flag. 
        3.1.2 Is weighted uptime the correct way of assigning a guard flag? Relay with 4 days of uptime gets flag, relay with one day down and three weeks of uptime does not get the guard flag. 
    3.2 If we give out Guard flags according to some other algorithm, how much safety can we get back? 
        3.2.1 Safety measures 
        3.2.2 Alternative guard algorithms 
    3.3 In Tor 0.2.1.x we started load balancing based on active bandwidth measurements, so we use the bandwidth weights in the network consensus rather than the weights in each relay descriptor. We know that change improved performance, but at what cost to safety? 
    3.4 What happens to the network diversity if we put a low cap on the bandwidth weighting of any node that hasn't been assigned a measurement by the bandwidth authorities yet, to protect against relays that lie about their bandwidth? If there's no real effect, we should do it; but if there's a large effect, we should find a better plan. 
    3.5 What if some Tor users choose their paths to optimize a different network property (like latency or jitter), as suggested by Micah Sherr? The infrastructure you've built to measure diversity here should apply there too. 

4 Notes 
    4.1 Modularize the path selection code of pytorctl for researchers to use. 

5 Papers to read 
    5.1 Trust-based Anonymous Communication: Adversary Models and Routing Algorithms 
    5.2 Latest version of Tariq's "Changing of Guards" paper 
        5.2.1 Look at "Closed Analysis" section in appendix 
    5.3 Improving Security and Performance in the Tor Network through Tunable Path Selection 
    5.4 Metrics for Security and Performance in Low-Latency Anonymity Networks (PDF) (Cached: PDF) 

[0]: the list includes Aaron Johnson, Ian Goldberg, Tariq Elahi,
     Roger, Nikita Borisov, and more that I can't remember right now.

More information about the tor-dev mailing list