# How many distinct Tor circuits are possible?

Given the current relay census, and assuming a standard Tor Browser Bundle installation, approximately how many distinct Tor circuits are possible? Once entry guards have been chosen, approximately how many distinct circuits are possible using those entry guards?

Also, what is the method for making these estimates?

• This should be easy enough to calculate at any given time; no estimates needed. You can grab the list of relays and then separate them out into exits, guards, and normal relays and do a bit of math (not sure if exits and guards can be normal relays as well, you'd have to double check that). Oct 30, 2013 at 4:26

As a start, this script (see below) will grab a list of nodes from this website (or update the list if it's >30 minutes old) and display them. You should be able to fetch them from any directory server as well, but I'm not entirely sure how. You'd have to look at the dir spec.

As of posting this we have:

• 868 exits
• 1579 guards
• 2320 relays
• 369 relays that are both guards and exits

If we ignore the fact that some relays are both entry guards and exits (and wouldn't be chosen for both) we can do some basic combinatorics to figure out how many distinct circuits are possible:

868 * 1579 * 2320 = 3,179,727,040 distinct circuits

Of course, this is a naive approach. One could do better. I'm also still unsure if entry guards and exits still also act as normal relays, in which case the numbers above need to be tweaked.

Once entry guards have been selected, this reduces to:

868 * 3 * 2320 = 6,041,280 distinct circuits

Which seems like it would make an attackers job that much easier if they could guess your guard nodes. However, let's calculate the number of possible guard node selections. Mathematically, we want a k-combination of a set (the set of all guard nodes, in this case) with n distinct elements (1579). Since we select three guard nodes (citation needed?) by default, k will be 3. The formula for a k-combination is: solved for the number of guard nodes (1579) selecting 3: So we have 654891829 possible guard node combinations. That's a lot for an attacker with no other advantage (eg. one who can't listen in on the wire) to guess or figure out.

## Improvements

This is a pretty good estimate, but we could figure out a way to calculate these numbers exactly at any given time. To do so, the following improvements are suggested:

• Figure out if guards/exits can be normal relays as well
• Take into account the guard/exit overlap (since this gets rid of any circuits which would contain a single node for both guard and exit)

## The script

``````#!/bin/sh

echo "List: \${LIST:=/tmp/tornodes}"

get_list() {
curl https://www.dan.me.uk/tornodes | \
sed '/<!-- __BEGIN_TOR_NODE_LIST__ \/\/-->/,/<!-- __END_TOR_NODE_LIST__ \/\/-->/!d' | \
tail -n +2 | head -n -1 > \${LIST}
}

if [ -e \$LIST ]; then
NOW=\$(date +%s)
FCTIME=\$(stat -c %Y \${LIST})
let "AGE=\$NOW-\$FCTIME"
if [[ \$AGE -gt 1800 ]]; then
get_list
fi
else
get_list
fi

TOTAL=\$(wc -l \${LIST} | cut -d' ' -f1)
EXITS=0
RELAYS=0
GUARDS=0

FLAGS=\$(echo \${node} | cut -d'|' -f5)
case "\$FLAGS" in
*E*G*|*G*E*) ((EXITS++)); ((GUARDS++));;
*E* ) ((EXITS++));;
*G* ) ((GUARDS++));;
* ) ((RELAYS++));;
esac
done < "\$LIST"

echo "Exits: \$EXITS"
echo "Guards: \$GUARDS"
echo "Relays: \$RELAYS"
echo "---"
echo "Total nodes: \$TOTAL"
echo "Guard/Exit overlap: \$(((\$GUARDS+\$EXITS+\$RELAYS-\$TOTAL)))"
``````
• How do Tor's relay-selection algorithms affect the estimate? Do they just change selection probabilities? But if some relays are rarely chosen, don't they count less toward the total? Oct 31, 2013 at 5:05
• @mirimir you asked for a method to "estimate" (calculate) them. The selection algorithm only affect the probability of a circuit from being the chosen one, not the total number of (possible) circuits. Oct 31, 2013 at 12:13
• Updated to reflect the guard node part of the question. Oct 31, 2013 at 13:06
• Remember that two relays that are in the same subnet will not be matched together. May 5, 2018 at 23:18

approximately how many distinct Tor circuits are possible?

This deppends greatly in the amount of nodes available at given time and the possible combinations, but there isn't a fixed number that won't be obsolete the next time you calculate this. Tor normally is run by well stablished nodes, but if the amount of nodes change rapidly calculate this could prove quite a feat. You of course can calculate in a specific timeframe (as Sam answer shows) but theoretically you can have as many circuits as available nodes can be combined.

Once entry guards have been chosen, approximately how many distinct circuits are possible using those entry guards?

Same as above. It depends greatly on the availability of exits/relays at given time.

• "Unlimited, unknown and ever changing" Not at all; it's finite, countable, and relatively stable. Of course it depends on the availability of nodes at X time, but it doesn't change drastically or rapidly enough to matter that much. Oct 31, 2013 at 2:55
• @SamWhited he's asking as "how many are possible" as "what is the maximum (if there are any)" in which case is unlimited as many combinations of nodes are available (the more nodes available, the growing the number until no new nodes are created). I took that approach while answering. If you see another possible interpretation, I did not take that into consideration. Oct 31, 2013 at 3:17
• I've clarified the question. Sorry to be unclear. Oct 31, 2013 at 5:34