First of all, consider this TOR network as an "ideal" one (http://en.wikipedia.org/wiki/Ideal_gas)
We know agencies (e.g. NSA) run a number of both rely and exit nodes of the TOR network and is not very difficult to understand the reason :)
Number of running total nodes nodes(R) and exit nodes(E) is freely available[1].
Default number of hops (h) randomically chosen inside TOR network is equal to 3: 2 (h-1) relay nodes and 1 exit node.
Unique paths (N) between a Tor client (Alice) and a chosen destination(Bob) is given by the number of combination[2] of h distinct elements of set R multiplying the number of exit nodes, minus those chains where is present the same exit nodes more than once:
N = \dbinom{R}{h-1}E - \dbinom{R-1}{h-2}E
in this case h \ll R so we could apply the approximation:
for\ n \ll k: \dbinom{n}{k} \approx \frac{n^k}{k!}
thus:
N = \dbinom{R}{h-1}E - \dbinom{R-1}{h-2}E \approx \frac{R^{h-1}}{(h-1)!}E - o(R^{h-1})
N \approx \frac{R^{h-1}}{(h-1)!}E
At the time of writing these values are:
R = 4202
E = 934
assume:
h = 3
We can easily find the N value
N = \dbinom{4202}{2}934 - \dbinom{4201}{1}934 \approx \frac{4202^2}{2!} \cdot 934 \approx 8 \cdot 10^{9}
We know an "ideal TOR network" is a strong tool for anonymization, and even if some of the nodes we’re using are compromised we could feel quite safe. Obviously, in case the entire path is compromised every recipient: sender, destination and payload of the session is no longer secret. Let’s calculate the probability a connection over TOR is fully eavesdropped by controlling due a full compromised chain:
By definition probability(p) of an event is given by:
p = \frac{Number\ of\ Favorable\ Outcomes}{Total\ Number\ of\ Possible\ Outcomes}
in this case p is given by the ratio between the number of possible unsafe chains(N_c) and the total number of possible chains(N).
We know agencies (e.g. NSA) run a number of both rely and exit nodes of the TOR network and is not very difficult to understand the reason :)
Number of running total nodes nodes(R) and exit nodes(E) is freely available[1].
Default number of hops (h) randomically chosen inside TOR network is equal to 3: 2 (h-1) relay nodes and 1 exit node.
Unique paths (N) between a Tor client (Alice) and a chosen destination(Bob) is given by the number of combination[2] of h distinct elements of set R multiplying the number of exit nodes, minus those chains where is present the same exit nodes more than once:
N = \dbinom{R}{h-1}E - \dbinom{R-1}{h-2}E
in this case h \ll R so we could apply the approximation:
for\ n \ll k: \dbinom{n}{k} \approx \frac{n^k}{k!}
thus:
N = \dbinom{R}{h-1}E - \dbinom{R-1}{h-2}E \approx \frac{R^{h-1}}{(h-1)!}E - o(R^{h-1})
N \approx \frac{R^{h-1}}{(h-1)!}E
At the time of writing these values are:
R = 4202
E = 934
assume:
h = 3
We can easily find the N value
N = \dbinom{4202}{2}934 - \dbinom{4201}{1}934 \approx \frac{4202^2}{2!} \cdot 934 \approx 8 \cdot 10^{9}
We know an "ideal TOR network" is a strong tool for anonymization, and even if some of the nodes we’re using are compromised we could feel quite safe. Obviously, in case the entire path is compromised every recipient: sender, destination and payload of the session is no longer secret. Let’s calculate the probability a connection over TOR is fully eavesdropped by controlling due a full compromised chain:
By definition probability(p) of an event is given by:
p = \frac{Number\ of\ Favorable\ Outcomes}{Total\ Number\ of\ Possible\ Outcomes}
in this case p is given by the ratio between the number of possible unsafe chains(N_c) and the total number of possible chains(N).
p
= \frac{N_c}{N} \approx \frac{R_c^{h-1}}{R^{h-1}}\cdot\frac{E_c}{E} = \left
(\frac{R_c}{R} \right )^{h-1}\cdot\left (\frac{E_c}{E} \right )
where N_c and E_c are respectly the numbers of compromised relay and exit nodes.
let's call ratios \frac{Rc}{R} and \frac{Ec}{E} respectly Q_R and Q_E and here it is our simple and beautiful equation:
\boldsymbol{p = Q_R^{h-1}\cdot Q_E}
It is worth calculating the "best strategy" in deploying malicios nodes in order to maximize p:
p \approx \frac{R_c^{h-1}}{R^{h-1}}\cdot\frac{E_c}{E}
the number of "evil" nodes to be deployed is R_c both relay and exit nodes: E_c is a subset of R_c.
E_c = R_c \cdot z
where z is the ratio between relaying nodes and exit nodes.
p \approx \frac{R_c^{h-1}}{R^{h-1}}\cdot\frac{R_c \cdot z}{E} ; 0 \le z \le 1
p(z) \approx \frac{R_c^{h} \cdot z}{R^{h-1} \cdot E}
it's trivial to find maximum value of p(z) is at z=1, in other words when all the to-be-deployed nodes are setted as exit nodes.
Once achieved this piece of information let's calculate how many new nodes must be deployed in a TOR network in order to gain a given probability of fully eavesdrop someone.
the previous formulas could be rewritten in function of "evil nodes"(R_c) and due to the previous result these nodes will be all exit nodes (z=1; R_c=E_c):
p(R_c) \approx \frac{R_c^h}{(R+R_c)^{h-1} \cdot (E+R_c)}
and rewrite this in term of normalized R_c :
X = \frac{R_c}{R} ; R_c = R \cdot X
p(X) \approx \frac{(R \cdot X)^h}{(R+R \cdot X)^{h-1} \cdot (E+R \cdot X)}
here is a plot of the formula above:
x-axis represents how many "evil" exit nodes has been deployed versus the "good" nodes;
for instance: if it has been deployed 2000 "evil" nodes and there are 1000 "good" nodes already deployed the corresponding value on x-axis is 2 (2000/1000).
The graph shows clearly must be deployed a large number of evil exit nodes in order to have a reasonable probability to eavesdrop someone.
In order to have a 50% of chance to eavesdrop someone must be deployed a number a of evil nodes greater about four times the number of "good" exit nodes or taking control of 4/5 of the total exit nodes...
Conclusions
TOR is a great tool for anonymity, and its power comes from its distributed nature.
This short paper is merely a mathematical analysis of an "ideal TOR Network", a simplified network model useful to show some important properties of it.
Probability of being eavesdropped on a TOR network is dependent of number of compromised nodes:
\boldsymbol{p = Q_R^{h-1}\cdot Q_E}
next, the "optimous" strategy in deploying "evil" nodes in order to maximize p is to configure them all as exit nodes
p \approx \frac{R_c^{h}}{R^{h-1} \cdot E}
this result is as trivial as interesting:
in order to maximize efforts to find "evil" nodes, looking for them among exit nodes would be a good strategy too.
The last consideration should convince us deploying new "evil" nodes in order to eavesdrop someone isn't a good strategy at all.
Let's consider the "at the time of writing" number of exit nodes in the real TOR network:
E = 934
a potential attacker, in order to gain 50% probability to eavesdrop someone, needs to deploy about 4000 own nodes, or compromise about 750 "good" nodes.
If I was the attacker I would keep a low profile and invest resources and time in a good strategy aimed to compromise "good" nodes and not, actually, in a baroque, expensive and noisy nodes mass deploying.
[1] e.g. http://torstatus.blutmagie.de/
where N_c and E_c are respectly the numbers of compromised relay and exit nodes.
let's call ratios \frac{Rc}{R} and \frac{Ec}{E} respectly Q_R and Q_E and here it is our simple and beautiful equation:
\boldsymbol{p = Q_R^{h-1}\cdot Q_E}
It is worth calculating the "best strategy" in deploying malicios nodes in order to maximize p:
p \approx \frac{R_c^{h-1}}{R^{h-1}}\cdot\frac{E_c}{E}
the number of "evil" nodes to be deployed is R_c both relay and exit nodes: E_c is a subset of R_c.
E_c = R_c \cdot z
where z is the ratio between relaying nodes and exit nodes.
p \approx \frac{R_c^{h-1}}{R^{h-1}}\cdot\frac{R_c \cdot z}{E} ; 0 \le z \le 1
p(z) \approx \frac{R_c^{h} \cdot z}{R^{h-1} \cdot E}
it's trivial to find maximum value of p(z) is at z=1, in other words when all the to-be-deployed nodes are setted as exit nodes.
Once achieved this piece of information let's calculate how many new nodes must be deployed in a TOR network in order to gain a given probability of fully eavesdrop someone.
the previous formulas could be rewritten in function of "evil nodes"(R_c) and due to the previous result these nodes will be all exit nodes (z=1; R_c=E_c):
p(R_c) \approx \frac{R_c^h}{(R+R_c)^{h-1} \cdot (E+R_c)}
and rewrite this in term of normalized R_c :
X = \frac{R_c}{R} ; R_c = R \cdot X
p(X) \approx \frac{(R \cdot X)^h}{(R+R \cdot X)^{h-1} \cdot (E+R \cdot X)}
here is a plot of the formula above:
x-axis represents how many "evil" exit nodes has been deployed versus the "good" nodes;
for instance: if it has been deployed 2000 "evil" nodes and there are 1000 "good" nodes already deployed the corresponding value on x-axis is 2 (2000/1000).
The graph shows clearly must be deployed a large number of evil exit nodes in order to have a reasonable probability to eavesdrop someone.
In order to have a 50% of chance to eavesdrop someone must be deployed a number a of evil nodes greater about four times the number of "good" exit nodes or taking control of 4/5 of the total exit nodes...
Conclusions
TOR is a great tool for anonymity, and its power comes from its distributed nature.
This short paper is merely a mathematical analysis of an "ideal TOR Network", a simplified network model useful to show some important properties of it.
Probability of being eavesdropped on a TOR network is dependent of number of compromised nodes:
\boldsymbol{p = Q_R^{h-1}\cdot Q_E}
next, the "optimous" strategy in deploying "evil" nodes in order to maximize p is to configure them all as exit nodes
p \approx \frac{R_c^{h}}{R^{h-1} \cdot E}
this result is as trivial as interesting:
in order to maximize efforts to find "evil" nodes, looking for them among exit nodes would be a good strategy too.
The last consideration should convince us deploying new "evil" nodes in order to eavesdrop someone isn't a good strategy at all.
Let's consider the "at the time of writing" number of exit nodes in the real TOR network:
E = 934
a potential attacker, in order to gain 50% probability to eavesdrop someone, needs to deploy about 4000 own nodes, or compromise about 750 "good" nodes.
If I was the attacker I would keep a low profile and invest resources and time in a good strategy aimed to compromise "good" nodes and not, actually, in a baroque, expensive and noisy nodes mass deploying.
[1] e.g. http://torstatus.blutmagie.de/
