# no circuit loops?

Paul Syverson syverson at itd.nrl.navy.mil
Thu Oct 23 22:12:21 UTC 2003

On Thu, Oct 23, 2003 at 05:45:03PM -0400, Roger Dingledine wrote:
> On Thu, Oct 23, 2003 at 05:27:26PM -0400, Paul Syverson wrote:
> > But that's just a default yes? And, it's also just temporary. We
>
> Actually, the default is 2+n, where n is chosen from a geometric
> distribution around the config option CoinWeight (which really needs a
> new name). CoinWeight is generally .01 these days. Is there any known
> value to choosing path length this way against the adversary we expect,
> or should we simplify?
>

Hmmm. I'd have to look back at what we did before. I know we had
at least three different path length and path choice algorithms.
Some of these were not assuming that we had a clique, e.g.,
random walk for a <pick the distribution> length from each end
and shortest path to close. Another was to pick one or more
random points between the endpoints and then shortest path
between those.

A quick look also revealed the following stuff from a draft of the
PETs00 paper that didn't make it into camera ready. There's probably
more bits lying around.

Encrypted traffic looks the same as it passes along a path through
a Crowd. And, the decryption key is available to all path
participants.  Thus, any compromised node on the path compromises
not a system option.  As a result, a local eavesdropper and any one
compromised member of a path completely compromise all properties
mentioned in section~\ref{securitygoals}.  A local eavesdropper in
the remote-COR configuration of Onion Routing compromises sender
activity; however, unless the last COR in the connection is also
compromised, nothing else is revealed.  On the other hand, in this
configuration, the first untrusted component of the system is able
to compromise sender activity. For Crowds, the first untrusted
component of the system (i.e., the next node on the path) cannot
identify the initiator with certainty. In order to protect sender
activity from the first untrusted component, an OR network should
be accessed via the local-COR configuration. If there is no known
bound on the maximum path length of a route, then Onion Routing
protects all properties as well or better than Crowds. If one makes
the pessimistic assumption that there is a known maximum route
length, the protection of sender activity against collaborating
nodes on a maximum-length route is mostly worse than in Crowds.

Like Onion, Routing Crowds connection paths are of indeterminate
length.  However, unlike Onion Routing, paths are not of some
random length (within some bounds). Rather, after the first node
forwards to someone (possibly himself), then each node flips a
weighted coin and either forwards to another Crowds member or
becomes the terminal node in the path.  To make comparison
reasonable, we consider routes with the same expected length in
both Crowds and Onion Routing.  Assume an onion route of random
length between $2$ and $11$.  If all are equally likely, then
expected path length is $6.5$. If the probability of forwarding in
a Crowd is $p_f$, then expected path length $l$ is determined by

$$E(l) = (1-p_f) \sum_{l=1}^{\infty} l \cdot p_f^{(l-1)} = \frac{1}{1-p_f}$$

Thus, for $E(l) = 6.5$, it should be the case that $p_f = .85$.
Now, suppose some compromised nodes are on the same path.  What can
these nodes predict about the possibility that the node prior to
the earliest one is the initiator?  Let us assume that the
compromised nodes are able to discern a minimum route length $l_0$
based on what they know. The probability that the node prior to the
earliest one is in fact the initiator is the probability that $l = l_0$. In the given Crowd, $P(l = l_0 \mid l \geq l_0) = .15$,
regardless of $l_0$. In the given Onion Routing network, $P(l = l_0 \mid l \geq l_0)$ increases from $.1$ for $l_0 = 2$ to $1$ for $l_0 = 11$, crossing over $.15$ between $l_0 = 5$ and $l_0 = 6$.  Thus,
in Crowds, without an eavesdropper, the initiator cannot be exposed
for sender activity or even be seen as likely to be the
initiator. (More generally, for any $p_f > \frac{1}{2}$, $P(l = l_0 \mid l \geq l_0) < \frac{1}{2}$.)  Although the level of correct
suspicion is slightly higher than in Onion Routing for shorter
paths, for the specific case of sender activity, it is clearly
preferable that no percentage of nodes on the path can compromise
sender activity. On the other hand, a local eavesdropper
compromises sender activity for Crowds but not for local-COR based
Onion Routing connections.

> > still need to consider whether we get more vulnerability from
> > allowing loops or disallowing loops (or e.g. disallowing ABA loops
> > but allowing larger ones). And we should probably work that out before we
> > have route selection code that is new and shiny.
>
> Actually, I should make route selection code that can do it any of those
> ways and still be shiny. We will see. :)
>
> But you're right, we should solve this. At the least it should go as an
> open research problem in the design paper. If you have more of an answer
> than "gosh, hard problem" then let's hear it. :)
>

Not enough more yet ;>)
-Paul