George Kadianakis desnacked@riseup.net writes:
A main theme in the recent Tor development meeting was guard node security as discussed in Roger's blog post and in Tariq's et al. paper [0].
Over the course of the meeting we discussed various guard-related subjects. Here are some of them:
a) Reducing the number of guards to 1 or 2 (#9273).
b) Increasing the guard rotation period (to 9 months or so) (#8240).
<snip>
i) If we restrict the number of guards to 1, what happens to the unlucky users that pick a slow guard? What's the probability of being an unlucky user? Should we bump up the bandwidth threshold for being a guard node? How does that change the diversity of our guard selection process?
<snip>
To move forward, we decided that proposals should be written for (a) and (b). We also decided that we should first evaluate whether doing (a) and (b) are good ideas at all, especially with regards to (i).
I started working on evaluating whether reducing the number of guards to a single guard will result in horrible performance for users. Also, whether increasing the bandwidth threshold required for being a guard node will result in a less diverse guard selection process.
You can find the script here: https://git.gitorious.org/guards/guards.git https://gitorious.org/guards/guards
This is a thread to hear feature requests of what we need to find out before going ahead and implementing our ideas.
For now, I wrote an analysis.py script, which reads a user-supplied consensus, calculates the entropy of the guard selection process (like we did in #6232), then it removes the slow guards from the consensus (with a user-supplied threshold value), redoes the bandwidth weights, and recalculates the diversity of the guard selection process. Then it prints the two entropy values. This is supposed to give us an idea of how much diversity we lost by pruning the slow guard nodes. For more info, see the analysis() function.
Here is an execution of the script: """" $ python analysis.py consensus 400 # kB/s WARNING:root:Entropy: 9.41949523094 (max entropy of 1999 guards: 10.9650627567). WARNING:root:Before pruning: 1999 guards. After pruning: 1627 guards WARNING:root:Entropy: 9.36671628404 (max entropy of 1627 guards: 10.6679985357). WARNING:root:Original: 9.41949523094. Pruned: 9.36671628404 """ In this case, the entropy of the original guard selection process was 9.4 bits, and after we pruned slow guard nodes (below 400kB/s), we got an entropy of 9.3 bits. Is this good or bad? It's unclear, since comparing two Shannon entropy values does not make much sense (especially since they are in the logarithmic scale).
So here is a TODO list on how to make this analysis script more useful:
* Instead of printing the entropy, visualize the probability distribution of guard selection. A histogram of the probability distribution, for example, might make the loss of diversity more clear.
* Find a way to compare entropy values in a meaningful way. We can use the maximum entropy of each consensus to see how far from max entropy we are in each case. Or we can try to linearize the entropy value somehow.
* Find other ways to measure diversity of guard node selection.
* Given another speed threshold, print the probability that the guard selection will give us a guard below that threshold.
Even if we restrict guards to above 600kB/s, we still want to learn what's the chance you are going to encounter a guard below 1000kB/s.
* Fix errors on the current script.
For example, I'm not sure if I'm using the correct bandwidth values. I'm currently using the value in 'w' lines of the consensus ('w Bandwidth=479'). I used to think that this is a unitless number, but looking at dir-spec.txt it seems to be "kilobytes per second". Is this the value I should be using to figure out which guards I should cut-off?
* Implement ideas (d) and (e) and use historical data to evaluate whether they are worth doing:
d) The fact that authorities assign flags based on knowledge they acquired while they were up. They don't use historical data to assign flags, which means that an authority thas has been up for 1 month, only knows 1 month worth of information about each relay (#10968).
e) We discussed introducing a weight parameter that makes guards that have been guards for a long time, be more likely to be used as guards.
What else do we need to do?
PS: Here is another execution of the script with a higher cut-off value (100MB/s): """ $ python analysis.py consensus 100000 # kB/s WARNING:root:Entropy: 9.41949523094 (max entropy of 1999 guards: 10.9650627567). WARNING:root:Before pruning: 1999 guards. After pruning: 17 guards WARNING:root:Entropy: 3.76986046797 (max entropy of 17 guards: 4.08746284125). WARNING:root:Original: 9.41949523094. Pruned: 3.76986046797 """