11

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?

  • 2
    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). – Sam Whited Oct 30 '13 at 4:26
8

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:

k-combination of a set with n elements

solved for the number of guard nodes (1579) selecting 3:

Number of guard node selections

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)))"
  • 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? – mirimir Oct 31 '13 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. – Braiam Oct 31 '13 at 12:13
  • Updated to reflect the guard node part of the question. – Sam Whited Oct 31 '13 at 13:06
  • Remember that two relays that are in the same subnet will not be matched together. – forest May 5 '18 at 23:18
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.

  • "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. – Sam Whited Oct 31 '13 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. – Braiam Oct 31 '13 at 3:17
  • I've clarified the question. Sorry to be unclear. – mirimir Oct 31 '13 at 5:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.