How many distinct Tor circuits are possible?

Question

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?

Answer 1

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

while read -r node; do
    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)))"

Answer 2

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.