There is a good argument for making the number of hops in a path unpredictable, Is there a research paper that tells us what to do?

The following is a quote from Tor FAQ:

There is a good argument for making the number of hops in a path unpredictable [Thus Random]. For example, somebody who happens to control the last two hops in your path still doesn't know who you are, but they know for sure which entry node you used. Choosing path length from, say, a geometric distribution will turn this into a statistical attack, which seems to be an improvement. On the other hand, a longer path length is bad for usability, and without further protections it seems likely that an adversary can estimate your path length anyway. We're not sure of the right trade-offs here. Please write a research paper that tells us what to do.

Is anybody aware of or involved in a research paper on this issue?

Hеllo, Roya!

If we try to represent circuits as table, where:

• A letter C is a client
• A letter D is a destination
• A letter N is a node
• A number after letter N is number of node
• A compromised node placed into square brackets
• A not compromised node placed into round brackets
• Attacker have a control of a half of all nodes

Then we can see something like that:

For one-hop circuits:

``````C -> (N1) -> D => [Safe]
C -> [N1] -> D => [Unsafe]

Safe circuits: 1
Unsafe circuits: 1
``````

For two-hop circuits:

``````C -> (N1) -> (N2) -> D => [Safe]
C -> [N1] -> (N2) -> D => [Safe]
C -> (N1) -> [N2] -> D => [Unsafe]
C -> [N1] -> [N2] -> D => [Unsafe]

Safe circuits: 2
Unsafe circuits: 2
``````

For three-hop circuits:

``````C -> (N1) -> (N2) -> (N3) -> D => [Safe]
C -> [N1] -> (N2) -> (N3) -> D => [Safe]
C -> (N1) -> [N2] -> (N3) -> D => [Safe]
C -> (N1) -> (N2) -> [N3] -> D => [Unsafe]
C -> [N1] -> [N2] -> (N3) -> D => [Safe]
C -> (N1) -> [N2] -> [N3] -> D => [Unsafe]
C -> [N1] -> (N2) -> [N3] -> D => [Unsafe]
C -> [N1] -> [N2] -> [N3] -> D => [Unsafe]

Safe circuits: 4
Unsafe circuits: 4
``````

And so on. As you can see, when route length is bigger, then more variants of possible safe and unsafe circuits we can use. But attitude of safety to circuits that we can build is not changed. So, when we can build a 50 percents maximum of compromised circuits with two-hop route length, we also can build a 50 percents maximum of compromised circuits with three-hop length. But, if attacker have a control to a bigger number of nodes, so then we have a bigger chance to build a compromised circuit. I think we can set a variable length of route and must change circuits more often, but this length must not be smaller than three, because only in this way we have an entry, middle and exit nodes that is different from each other. Maybe I'm wrong in this, then please correct me.

• Hello dear, I agree with you that minimum number of hops should be 3. If we do similar type of analysis that you have done with assumption that 50% of relays are either owned, controlled, or spied on by an adversary (all three situations will result in a compromized relay), random number of hops will help enormously, because an adversary never knows when she is done (Thus adversary can not deterministically figure out how many hops she need to go until she gets done. That make analysis by adversary enormously more difficult. [Continue in the next comment]
– Roya
Jul 15, 2014 at 13:54
• As a matter of fact the adversary need to give up on deterministic analysis and resort to statistical analysis. This provides much less certainty than deterministic analysis for the advarsary and provide a breathing room for the clients.
– Roya
Jul 15, 2014 at 14:00
• Dear, by the way you have my upvote and thanks for being the first angel to answer this question.
– Roya
Jul 15, 2014 at 14:04
• Dear, when I say 50% of relays in the above comment I mean 50% realy by weight, meaning that the higher capacity relays count more than lower capacity relays. For example a relay with 30 MB/s capacity is equivalent to 30 relays each with 1.0 MB/s capacity. So the actual number of relays compromized need not to be 50% of all relays. The capacity of compromised relays need to be 50% of total capacity of all relays.
– Roya
Jul 15, 2014 at 14:21
• Thanks, Roya! I'm not know an answer to this question, and we can wait someone else who can do it. Think that if there is can be present an timing attack, randomising a route length can help to partially prevent it executing. Jul 15, 2014 at 15:43