proposals/112-bring-back-pathlencoinweight.txt

   1 Filename: 112-bring-back-pathlencoinweight.txt
   2 Title: Bring Back Pathlen Coin Weight
   3 Version: $Revision$
   4 Last-Modified: $Date$
   5 Author: Mike Perry
   6 Created:
   7 Status: Superseded
   8 Superseded-By: 115
   9
  10
  11 Overview:
  12
  13   The idea is that users should be able to choose a weight which
  14   probabilistically chooses their path lengths to be 2 or 3 hops. This
  15   weight will essentially be a biased coin that indicates an
  16   additional hop (beyond 2) with probability P. The user should be
  17   allowed to choose 0 for this weight to always get 2 hops and 1 to
  18   always get 3.
  19
  20   This value should be modifiable from the controller, and should be
  21   available from Vidalia.
  22
  23
  24 Motivation:
  25
  26   The Tor network is slow and overloaded. Increasingly often I hear
  27   stories about friends and friends of friends who are behind firewalls,
  28   annoying censorware, or under surveillance that interferes with their
  29   productivity and Internet usage, or chills their speech. These people
  30   know about Tor, but they choose to put up with the censorship because
  31   Tor is too slow to be usable for them. In fact, to download a fresh,
  32   complete copy of levine-timing.pdf for the Anonymity Implications
  33   section of this proposal over Tor took me 3 tries.
  34
  35   There are many ways to improve the speed problem, and of course we
  36   should and will implement as many as we can. Johannes's GSoC project
  37   and my reputation system are longer term, higher-effort things that
  38   will still provide benefit independent of this proposal.
  39
  40   However, reducing the path length to 2 for those who do not need the
  41   (questionable) extra anonymity 3 hops provide not only improves
  42   their Tor experience but also reduces their load on the Tor network by
  43   33%, and can be done in less than 10 lines of code. That's not just
  44   Win-Win, it's Win-Win-Win.
  45
  46   Furthermore, when blocking resistance measures insert an extra relay
  47   hop into the equation, 4 hops will certainly be completely unusable
  48   for these users, especially since it will be considerably more
  49   difficult to balance the load across a dark relay net than balancing
  50   the load on Tor itself (which today is still not without its flaws).
  51
  52
  53 Anonymity Implications:
  54
  55   It has long been established that timing attacks against mixed
  56   networks are extremely effective, and that regardless of path
  57   length, if the adversary has compromised your first and last
  58   hop of your path, you can assume they have compromised your
  59   identity for that connection.
  60
  61   In [1], it is demonstrated that for all but the slowest, lossiest
  62   networks, error rates for false positives and false negatives were
  63   very near zero. Only for constant streams of traffic over slow and
  64   (more importantly) extremely lossy network links did the error rate
  65   hit 20%. For loss rates typical to the Internet, even the error rate
  66   for slow nodes with constant traffic streams was 13%.
  67
  68   When you take into account that most Tor streams are not constant,
  69   but probably much more like their "HomeIP" dataset, which consists
  70   mostly of web traffic that exists over finite intervals at specific
  71   times, error rates drop to fractions of 1%, even for the "worst"
  72   network nodes.
  73
  74   Therefore, the user has little benefit from the extra hop, assuming
  75   the adversary does timing correlation on their nodes. The real
  76   protection is the probability of getting both the first and last hop,
  77   and this is constant whether the client chooses 2 hops, 3 hops, or 42.
  78
  79   Partitioning attacks form another concern. Since Tor uses telescoping
  80   to build circuits, it is possible to tell a user is constructing only
  81   two hop paths at the entry node. It is questionable if this data is
  82   actually worth anything though, especially if the majority of users
  83   have easy access to this option, and do actually choose their path
  84   lengths semi-randomly.
  85
  86   Nick has postulated that exits may also be able to tell that you are
  87   using only 2 hops by the amount of time between sending their
  88   RELAY_CONNECTED cell and the first bit of RELAY_DATA traffic they
  89   see from the OP. I doubt that they will be able to make much use
  90   of this timing pattern, since it will likely vary widely depending
  91   upon the type of node selected for that first hop, and the user's
  92   connection rate to that first hop. It is also questionable if this
  93   data is worth anything, especially if many users are using this
  94   option (and I imagine many will).
  95
  96   Perhaps most seriously, two hop paths do allow malicious guards
  97   to easily fail circuits if they do not extend to their colluding peers
  98   for the exit hop. Since guards can detect the number of hops in a
  99   path, they could always fail the 3 hop circuits and focus on
 100   selectively failing the two hop ones until a peer was chosen.
 101
 102   I believe currently guards are rotated if circuits fail, which does
 103   provide some protection, but this could be changed so that an entry
 104   guard is completely abandoned after a certain ratio of extend or
 105   general circuit failures with respect to non-failed circuits. This
 106   could possibly be gamed to increase guard turnover, but such a game
 107   would be much more noticeable than an individual guard failing circuits,
 108   though, since it would affect all clients, not just those who chose
 109   a particular guard.
 110
 111
 112 Why not fix Pathlen=2?:
 113
 114   The main reason I am not advocating that we always use 2 hops is that
 115   in some situations, timing correlation evidence by itself may not be
 116   considered as solid and convincing as an actual, uninterrupted, fully
 117   traced path. Are these timing attacks as effective on a real network
 118   as they are in simulation? Would an extralegal adversary or authoritarian
 119   government even care? In the face of these situation-dependent unknowns,
 120   it should be up to the user to decide if this is a concern for them or not.
 121
 122   It should probably also be noted that even a false positive
 123   rate of 1% for a 200k concurrent-user network could mean that for a
 124   given node, a given stream could be confused with something like 10
 125   users, assuming ~200 nodes carry most of the traffic (ie 1000 users
 126   each). Though of course to really know for sure, someone needs to do
 127   an attack on a real network, unfortunately.
 128
 129
 130 Implementation:
 131
 132   new_route_len() can be modified directly with a check of the
 133   PathlenCoinWeight option (converted to percent) and a call to
 134   crypto_rand_int(0,100) for the weighted coin.
 135
 136   The entry_guard_t structure could have num_circ_failed and
 137   num_circ_succeeded members such that if it exceeds N% circuit
 138   extend failure rate to a second hop, it is removed from the entry list.
 139   N should be sufficiently high to avoid churn from normal Tor circuit
 140   failure as determined by TorFlow scans.
 141
 142   The Vidalia option should be presented as a boolean, to minimize confusion
 143   for the user. Something like a radiobutton with:
 144
 145    * "I use Tor for Censorship Resistance, not Anonymity. Speed is more
 146       important to me than Anonymity."
 147    * "I use Tor for Anonymity. I need extra protection at the cost of speed."
 148
 149   and then some explanation in the help for exactly what this means, and
 150   the risks involved with eliminating the adversary's need for timing attacks
 151   wrt to false positives, etc.
 152
 153 Migration:
 154
 155   Phase one: Experiment with the proper ratio of circuit failures
 156   used to expire garbage or malicious guards via TorFlow.
 157
 158   Phase two: Re-enable config and modify new_route_len() to add an
 159   extra hop if coin comes up "heads".
 160
 161   Phase three: Make radiobutton in Vidalia, along with help entry
 162   that explains in layman's terms the risks involved.
 163
 164
 165 [1] http://www.cs.umass.edu/~mwright/papers/levine-timing.pdf