|
Hello, Thank you for your helpful review, teor. I updated the proposal from most of your comments (see attached .txt) and I respond inline to add some precisions relative to a few of your questions. Btw, I've mirrored my private repo to github
https://github.com/frochet/Waterfilling, such that you have the
proper commit history. On 2018-01-11 14:47, teor wrote:
That's a good point. Waterfilling uses the current bandwidth-weights logic as a basis and they doesn't account for onion service circuit, hence it also ignore this sort of traffic. Prop 265 tries to address that problem when producing the bandwidth-weights; Since our method achieves the same total consensus weight balance between position as the one produced by bandwidth-weights, Waterfilling would directly inherit Prop 265's properties if this proposal is merged.
Yes, we mean consensus weight :) I did s/bandwidth/consensus weight within the proposal
Well, I changed my wording here to avoid ambiguity. I was talking about relays flagged as Exits being used only in the exit position (Wee and Wed have the max value), which means that we cannot apply our method over those relays with the current state of the Tor network.
The problem your mention is more a measurement problem that would not exist if the bwauths were perfect, within a perfect network. I believe that research such as Peerflow[0] is the right path to track down such issue, and this is compatible to our proposal. [0] www.robgjansen.com/publications/peerflow-popets2017.pdf
Yep, this is basically what we tried to say. In fact, what I wrote was the description of the *consequence* of bandwidth-weights. I tried to re-word with your suggestion, thank you. <skip> Yes, this can be added. But I think that this condition is redundant, since BW_i are sorted in decreasing order.
This is a very good question. Currently in my implementation, I ignore the remainder. This is negligible for large network but can be weird for small one (of a few relays). A possible solution would be to use floating precision for consensus weights.
From my note, my current implementation would crash if the water level reaches the smallest relay. Since it was prototype code, I didn't mind to think about it, and I let it that way. I think that below a fixed size of the network, it does not make sense to use this proposal. In this example, the remainder accounts for a large part of the network capacity and would just be wasted. <skip> Yes, binary search. It does require division. However, waterfilling is designed to be executed in the authority side and called only when the consensus document is produced. Moreover, my tests indicates that the computation consumes a few ms. <skip> That's difficult to predict, I cannot be sure if it is better or worse for that type of traffic since internal circuits use at least 2 middle relays + the guard and sometimes, even not the guard. Hence we might also think that pushing a bit more to the middle position could be a good thing to do. Moreover, middle relays are unstable and often at the edge of the internet, while guard are stable and most of them within the core of the internet. Hence, a little more of them within the middle position *could* be a good thing, especially if it makes entry's selection probability more uniform. Anyway, I don't have any proof to assert this, as well that I don't have any proof to assert that this optimization could be bad. What I got, is that, for exit circuits, it does not slow down anything. This optimization is not mandatory, and could also be enabled/disabled at will by the directory auths.
If it happens that any bandwidth is pushed away from fast relays within the entry position and make the entry position slower, at average, then it will make the middle position faster (because it got that bandwidth pushed away). Since the latency of your traffic flow just care about the global latency of the circuit, this will not appear to be slower or faster, on average. This is exactly what we observe in Shadow, and yes, it captures latency accurately. At least, better than any other simulator.
~ 25 %
Sorry about this. I've updated the repo with a proper commit history based on my fork. The code gives an idea about the easiness to plug-in this method to the current path selection. <skip> These are redundant, and could significantly expand the size of the True, each time the consensus weights are modified, those waterfilling weights need to be recomputed. It adds one line per guard, which is about 2~3% of the size of the full consensus. Is such a thing a problem?
This is again a very good question: for such a critical feature (path selection), it is important that the directory auths have full power over the weight computation. If it happens that some change are needed, then the Tor network is updated in a straightforward way. This is not the case if those weights are computed in client code. In fact, I believe that one of the strength of this proposal is the oriented design towards the dirauths.
I am sorry, I don't really understand why a feedback loop is needed. Measuring bandwidth and producing bandwidth-weights seems orthogonal to me.
I've added a section within the proposal for all upcoming questions. Best, Florentin
|
Filename: waterfilling-balancing-with-max-diversity.txt
Title: Waterfilling
Authors: Florentin Rochet and Olivier Pereira
Reviewed by (thanks!): George Kadianakis, Edouard Cuvelier, teor
Created: Jan 2018
Status: Open
0 Motivation
An adversary who monitors the entry and exit of a Tor communication
path is usually able to de-anonymize that communication by traffic
correlation. In order to limit the number of users that a single
corrupted entry node could attack, the users keep using the same entry
node, also called a "guard" for long periods of time: since guard
rotation is limited, the users are less likely to use a corrupted
guard at some point in their communication. In the current design, the
amount of traffic that a given guard sees is directly proportional to
the bandwidth that is provided by this guard. As a result, the few
guards offering the highest amount of bandwidth become very attractive
targets for an attacker.
Waterfilling is a new path selection mechanism designed to make the
guard selection even more efficient: if an adversary wants to profile
more users, she has to increase her bandwidth _and_ increase the
number of relays injected/hacked into the network.
Waterfilling mitigates the risks of end-to-end traffic correlation
by balancing the load as evenly as possible on endpoints of user
circuits. More precisely, waterfilling modifies the probability
distribution according to which users select guard nodes my making
that distribution closer to the uniform distribution, without
impacting the performance of the Tor network.
1 Overview
The current Tor path selection algorithm is designed to satisfy two
important properties:
1) Each relay should handle a fraction of connections that is
proportional to its consensus weight.
2) The nodes in each circuit position (entry-middle-exit) should
be able to handle the same volume of connections.
Hence, in addition to select paths in a probabilistic manner, the
path selection algorithm is responsible for balancing the network,
that is, making sure that enough consensus weight is made available in
all the positions. The current balance of the network is decided by
the bandwidth-weights (see dir-spec.txt section 3.8.3. or/and the
Waterfilling PETS2017 paper
https://petsymposium.org/2017/papers/issue2/paper05-2017-2-source.pdf).
This balance does not achieve maximum diversity in end-positions of
user paths: the same network throughput could be achieved by
decreasing the use of high consensus weight relays and increasing the
use of lower consensus weight relays in the guard position, instead of
using these relays in a way that is just proportional to their
consensus weight. Such a change would make top relays less attractive
targets to adversaries, and would increase the number of relays that
need to be
compromised in order to obtain a given probability of mounting a
successful correlation attack.
Our proposal only modifies the balance between the relays in a given
position in the network. It does not modify, and actually takes as
its starting point, any allocation mechanism used to decide the
consensus weight that is allocated in guard, middle and exit
positions. As a consequence, the changes that we propose are quite
minimal in terms of code base and performance and, in particular, they
do not interfere with prop 265.
2 Design
Correlation attacks require to control guard and exit nodes, but the
scarcity of exit consensus weight is such that there is no real
freedom in the way to use it. As a result, the Waterfilling proposal
focuses on the guard position. However, it could be easily extended to
the exit position if, someday, nodes in that position happen not to be
exploited to their full capacity at the exit position. Indeed, relays
flagged as Exits are currently using all their resource at the exit
position due to bandwidth-weights Wee and Wed being maximum.
_Recall_: Tor currently computes bandwidth-weights in order to balance
the consensus weight made available by nodes between the different
path positions. In particular the Wgg weight indicates to *clients* how
often they should select guards in the guard position in *circuits*.
Consequently, Wgg can be seen as the proportion of guards consensus
weight which should be used for entry traffic (the rest being normally
devoted to the middle position). This proportion is the same for all
guards.
_Proposal_: We use Tor's bandwidth-weight Wgg as the basis of
Waterfilling. This Wgg, combined with the total consensus weight made
available by all guards, defines the total consensus weight made
available in the guard position. In order to allocate this bandwidth,
the Waterfilling proposal proceeds by "raising the water level": it
requires all guard relays to devote to their guard role all the
consensus weight that they have, until a so-called "water level" is
reached. This water level is positioned in such a way that the total
consensus weight provided in the guard position is exactly the same as
the one that is currently made available in the Tor network.
As a result, guards offering a small amount of consensus weight, below
the water level, will fully allocate their consensus weight to guard
traffic, while all the guards offering a consensus weight that is
higher than the water level will limit their guard consensus weight to
the water level, and allocate the rest to the middle traffic (assuming
that they are not exit flagged as Exits).
Concretely, we compute the weight Wgg_i for each guard-flagged relay_i
as follows:
1) Sort all the guard relays by consensus weight in decreasing order
(i.e. the i-th guard has more consensus weight than the i+1-th).
(i) BW_i >= BW_{i+1}
2) Let K be the total number of guards, BW_i be the consensus weight
of the i-th ranked guard and G be the total consensus weight that
guards make available. Compute a "pivot" N and the weight Wgg_i
assigned to relay_i in such a way that:
(a) Wgg_i * BW_i == Wgg_{i+1} * BW_{i+1} forall i in [1, N]
(b) Wgg_i == 1 forall i in [N+1, K]
(c) sum_{i=1}^{K} Wgg_i*BW_i = Wgg*G (Wgg is provided by Tor)
As a result of this process, each guard ranked before the pivot N
dedicates the same consensus weight to its guard role (equation (a))
-- we say that these guards achieve the water level, while each guard
ranked after the pivot N dedicates its full consensus weight to the
guard role (equation (b)) -- they are below the water level. Equation
(c) makes sure that the pivot and the water level are positioned in a
way that guarantees that the total amount of consensus weight
dedicated to the guard position is the same as before. In practice,
the value of N can be efficiently computed by binary search on
Equation (c), and the value of the Wgg_i then immediately follows from
Equations (a) and (b).
Once Wgg_i is computed, we can compute Wmg_i = 1 - Wgg_i, which
allocates to the middle position all the consensus weight that is left
above the water level in the first N relays. The bigger the node is,
the more it contributes to the middle position compared to the others.
A visual representation of this process is available in Figure 1 in
the Waterfilling paper.
2.1 Going further by tweaking original bandwidth-weights computation
As explained above, our Waterfilling equations are based on: 1) the
Wgg weight computed by Tor 2) the assumption that the consensus weight
available in exit is scarce, i.e., it is lower than the one available
for guard (and middle) positions.
The second point is satisfied most of the time in Tor, and we do take
it for granted here.
We, however, observe that Waterfilling could be made even more
effective by applying a minor change in the way Tor computes the
Wgg. For the moment, Tor computes Wgg in such a way that the same
total consensus weight is allocated to the guard and middle positions.
As a result, both positions are in excess compared to the exit
position.
The water level could be decreased and, as a result, the uniformity
of the guard selection process could be improved, by computing Wgg
in a way that allocates the same total consensus weight to the guard
and exit positions, putting the middle position as the only position
in excess.
We show in the performance section of the Waterfilling paper that
scarcity on two positions does not reduce performance compared to
vanilla bandwidth-weights.
3 Security implications
An analysis of the security impact of the Waterfilling proposal is
made in Section 6 of the Waterfilling paper. It studies the
expectation of the number of relays that an adversary needs to
control in order to mount a successful correlation attack at a given
time, as well as an analysis of the evolution of the time until
first path compromise, based on TorPS.
Given that the distribution produced by Waterfilling is closer to
the uniform distribution, the use of Waterfilling increases the
expectation of the number of relays that an adversary needs to
compromise in order mount a successful correlation
attack. Concretely, and based on real data from 2015, this
expectation increases by approximately 150 relays (about 25%).
Waterfilling also considerably decreases the benefits of
compromising a top Tor relay: based on the same data, we computed
that around 35 relays need to be compromised in order to obtain the
benefits that would be obtained today by compromising Tor's top
guard. On the flip side, the total consensus weight that those 35
relays would need to provide is 38% smaller than the one of the top
relay, if they are designed to offer a consensus weight that is just
at the water level. Moreover, these 35 relays used to equalize the
impact of the current top guard is the lower bound. In practice, the
adversary needs to predict the water level of all upcoming consensus
to stay below it and not to waste consensus weight. A safe manner to
achieve this is to split the resource into way more than 35 relays. At
some point, the adversary would struggle between the need to stay off
the radar with many machines and the waste of consensus weight if she
has not enough of them.
4 Performance implications
This proposal aims at improving the anonymity provided by the Tor
network without impacting its performance negatively.
From a theoretical viewpoint, since Waterfilling does not change the
amount of consensus weight dedicated to the guard, middle and exit
position, we should not observe any difference compared to vanilla
Tor. The intuition is that, even if the top consensus weight relays
that are currently affected to the guard position are less likely to
be selected as guards, they become more likely to be selected as
middle nodes, hence maintaining their contribution to fast Tor
circuits.
We confirmed this intuition by running Shadow experiments with a Tor
implementation of Waterfilling. Our results give the same CDF for
time-to-fist-byte (ttfb) and time-to-last-byte (ttlb) metrics under
different network loads. We have run two classes of experiments, one
in a low network load and one with an heavy loaded network
proportionnaly close to the throughput of the real Tor nework. Of
course, these results depend on the accuracy with which the behavior
of current relays is measured and reported.
However, an interesting feature of the Waterfilling proposal is that
it is fully compatible with vanilla Tor: some Tor clients may run
the current Tor path selection algorithm, and others may run
Waterfilling without impacting the performance. This makes an
experimental deployment fairly easy to operate at a small or medium
scale, while maintaining the possibility to fall back to vanilla Tor
if an unexpected behavior is detected.
5 Implementation
5.1 Overview
Most of the implementation of Waterfilling is on the directory
authority side: only a few changes are needed on the client side and
no change is needed on the relay side. A prototype implementation is
available at https://github.com/frochet/waterfilling. Here is how it
works:
Every hour, directory authorities vote on a new consensus. Once the
votes are collected, the dirauths produce a deterministic network
consensus document containing information about each relay,
including the waterfilling bandwidth-weights produced from the
equations described above. e.g.:
...(more relays)
r relayguard34 PPTH75+WkHl1GGw07DRE/S+JNdo 1970-01-01 00:02:37
51.254.112.52 9111 9112
m lp08MLTivsSZPhpZQy88i8NPeBNx10tPKBpHZsM3gYM
s Fast Guard HSDir Running Stable V2Dir Valid
v Tor 0.2.6.7
w Bandwidth=10200
wfbw wgg=8029 wmg=1971.
r 4uthority3 PYnzXGQ+67m0WtO64qtJkwsUzME 1970-01-01 00:02:33 11.0.5.71
9111 9112
m d8G2/8UQzAN3a9DixCtmaivhfUFTvlFKAxCAV1xHVKk
s Authority Fast Guard HSDir Running Stable V2Dir Valid
v Tor 0.2.6.7
w Bandwidth=1890
wfbw wgg=10000 wmg=0.
...(more relays)
In this example, we see two relays having the Guard flag and their new
waterfilling bandwidth-weights allocation given on the lines starting
with wfbw. The first relay has a high consensus weight (Bandwidth),
above the water level (was around 8k for this consensus), and shares
that consensus weight between the guard and the middle positions, as
indicated by the wgg and wmg variables. The second relay has a lower
consensus weight, below the water level, and fully uses it for guard
traffic.
If no wgg or wmg weights are specified for a given relay, the
vanilla bandwidth-weights are used, as provided at the bottom of the
consensus.
Eventually, a modification of the client code is needed in order to
parse and use the waterfilling weights. The changes are
straightforward with a few lines of codes in existing functions.
6 Deployment discussion
Deploying a new feature that has a central role in security and
performance of the network can be difficult due to the distributed
nature of the network. Hopefully, this proposal does not suffer from
such issue. We give here some arguments supporting this claim.
- About performance: The balancing equations designed by the current
path selection are kept untouched. Hence mixing a set of clients
using Waterfilling in the network and another set of clients using
the vanilla path selection is not a problem: they will both
enforce the same allocation of total consensus weight between the
different path positions. We confirmed this with experiments in
Shadow.
- About user security: A co-existence of path selection algorithms
may be a threat to anonymity if the transition is not handled
carefully. A set of compromised middle relays may distinguish
users with Waterfilling configuration from others. This is a
problem if the anonymity set is not large enough. Hopefully,
"large enough" can be ensured with a consensus parameter that only
enables this feature when enough users have updated their client.
7 Note
Some important questions raised on the mailing list:
- How can we determine whether it is better for security in practice?
Whether this proposal is indeed better for security can be
summarized with the following fact: if the adversary wants to profile
more users against a Tor network using this Proposal, she has to
increase her consensus weight _and_ increase the number of IPs she
uses in the network. And, this is not true for the current path
selection (she has to increase bandwidth).
Moreover, the paper linked to this proposal offers a detailed security
analysis.
- How can we determine if it is faster or slower in practice?
Well, if Shadow missed capturing some important performance impact
within our simulations, then looking at the output of
metrics.torproject.org after such proposal is deployed, as well as
asking relay operators if they notice some burden is probably the best
we can do.
- How can we work out if someone is trying to game the system?
The optimal strategy for an adversary is explained in the paper. It
might be possible to detect an adversary applying the optimal
strategy, since we know it but it was out of the scope of the paper.
E.g., a bunch of new relays appearing with a consensus weight at the
water level could be considered suspicious.
7.1 Unanswered questions
- What about the feedback loop between this new allocation system
and the bandwidth authorities?
- Should bandwidth authority clients use the new system?
- How do we report on the new system?
_______________________________________________ tor-dev mailing list tor-dev@xxxxxxxxxxxxxxxxxxxx https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev