Re: no circuit loops?

[Paul Syverson <syverson@itd.nrl.navy.mil>]

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
   both receiver activity and receiver content. Also, link padding is
   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