[or-cvs] add a changelog for 0.1.0.3-rc

[Nick Mathewson]

On Fri, Apr 08, 2005 at 08:43:40AM -0400, Paul Syverson wrote:
> On Fri, Apr 08, 2005 at 02:16:40AM -0400, Roger Dingledine wrote:
> > +    - Start sending 'truncated' cells back rather than destroy cells,
> > +      if the circuit closes in front of you. This means we won't have
> > +      to abandon partially built circuits.
> 
> I thought we decided a few years ago that this would be a bad idea.
> E.g., if an entry or middle node (from some cabal of evil nodes)
> decides that something about a circuit looks interesting it can cause
> a truncated circuit and, when it is re-extended, increase the
> probability that the cabal owns or observes the exit too. All the
> worse if this can be done repeatedly for a single circuit or if
> tor clients can choose to simply exit from the point of truncation.
> 
> The client might allow use of this circuit if only circuit building
> has happened so far on the circuit. Two counters to
> that. 1. Presumably it removes most of the advantage that was desired
> since the amount of times that this would happen after a circuit was
> successfully extended but before anything was sent would be both rare
> and minimally advantageous over just building a new circuit.  2. Even
> in this limited form, it is a bit worse than the attack that we now
> live with of an evil node just selectively refusing to extend to an
> honest node sometimes. Now an evil first node can see if the circuit
> extends past a middle node to an evil third node (exit in our current
> default). If not, it can truncate before the handshake from the third
> node goes back to the client.
> 
> The attacks are significant but not devastating I think. If a compelling
> tradeoff argument exists we could allow this as an option, but it would
> need to be pretty compelling.

The idea is not only, as you suspect, to do this:
  - only during the circuit-building phase,
But also:
  - only in immediate response to a failed extend,
  - only a limited number of times per circuit.

Your point "1." above is not the issue in practice: it is common to
try to extend to an OR that is down or overloaded, and get a circuit
destroyed for that reason.  This is more common than getting circuits
truncated at any point after they are established.

Hm, let's try some analysis: suppose that a fraction C of our ORs is
compromised.  Suppose that we only allow one failed extend attempt per
hop, and on a second failed extend we abandon the circuit.
Previously, C^2 circuits will have compromised first and last hops.
With this retry approach, a circuit will be compromised if we pick a
compromised first hop that forces us to pick a compromised last hop.
But to do so, it would have to force a compromised second hop[*], and
the second hop would have to force a compromised third hop.  Since
we'd only retry each hop once, the chance of this working at a single
hop is P=1-(1-C)^2; the chance of it working for both hops is smaller
still.  Of course, this may still matter, we should analyze more.


[*] A compromised first hop couldn't just allow a free selection of
    second hop and truncate if he doesn't like the third hop, since we
    would only re-extend in response to a failed extend.  So if the
    first hop truncated after the second hop was established, we
    would abandon the circuit.

We should probably talk about this some more when we're all at CFP.

yrs,
-- 
Nick Mathewson
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 652 bytes
Desc: not available
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20050408/d1e9b902/attachment.pgp>