How to calculate the number of IPs an overall passive attacker would obtain by examining a connection?


A global passive attacker might be able to attempt various correlation attacks. In this example, I would like to calculate the number of IPs they would need to collect in order to have the IP address of the target client in their list, connecting to the guard node (I am not assuming their attack will be successful, just that their IP will be in the large list of candidates).

Let’s consider this example:

  • There are 10,000 Tor relays, and 50,000 users connected to the Tor network.
  • The global passive attacker observes 100% of the traffic.
  • Relays 1, 2, and 3 are each connected to 500 different IPs (to communicate with the other relays, or the client’s IP for the guard relay (relay 1).

Typical connection pattern: Client > Relay 1 > Relay 2 > Relay 3 > Destination

Thus, a global passive attacker could start by looking at all the IP addresses Relay 3 is talking to (500) and make a list.
Next, they would attempt to list all IPs that Relay 2 is in contact with. This is where it becomes a bit more complex, as even though the IP of Relay 2 is on the list, we don’t know which one it is among the 500 IPs (excluding correlation attacks), in order to know all the IPs it is communicating with, since each Tor client has a different path.

Therefore, I thought the correct calculation would be (500 x 500) + 500, totaling 250 500? (In reality, this could be translated as “each Tor relay is linked to all the other relays.”)

The additional +500 lists the IPs of clients in contact with the guard node, as it doesn’t communicate with other relays, I haven’t multiplied this part.

That sounds like the theory of the small world, which would significantly complicate the task of a global attacker.