proposals/110-avoid-infinite-circuits.txt

   1 Filename: 110-avoid-infinite-circuits.txt
   2 Title: Avoiding infinite length circuits
   3 Version: $Revision$
   4 Last-Modified: $Date$
   5 Author: Roger Dingledine
   6 Created: 13-Mar-2007
   7 Status: Accepted
   8 Target: 0.2.1.x
   9 Implemented-In: 0.2.1.3-alpha
  10
  11 History:
  12
  13   Revised 28 July 2008 by nickm: set K.
  14   Revised 3 July 2008 by nickm: rename from relay_extend to
  15      relay_early.  Revise to current migration plan.  Allow K cells
  16      over circuit lifetime, not just at start.
  17
  18 Overview:
  19
  20   Right now, an attacker can add load to the Tor network by extending a
  21   circuit an arbitrary number of times. Every cell that goes down the
  22   circuit then adds N times that amount of load in overall bandwidth
  23   use. This vulnerability arises because servers don't know their position
  24   on the path, so they can't tell how many nodes there are before them
  25   on the path.
  26
  27   We propose a new set of relay cells that are distinguishable by
  28   intermediate hops as permitting extend cells. This approach will allow
  29   us to put an upper bound on circuit length relative to the number of
  30   colluding adversary nodes; but there are some downsides too.
  31
  32 Motivation:
  33
  34   The above attack can be used to generally increase load all across the
  35   network, or it can be used to target specific servers: by building a
  36   circuit back and forth between two victim servers, even a low-bandwidth
  37   attacker can soak up all the bandwidth offered by the fastest Tor
  38   servers.
  39
  40   The general attacks could be used as a demonstration that Tor isn't
  41   perfect (leading to yet more media articles about "breaking" Tor), and
  42   the targetted attacks will come into play once we have a reputation
  43   system -- it will be trivial to DoS a server so it can't pass its
  44   reputation checks, in turn impacting security.
  45
  46 Design:
  47
  48   We should split RELAY cells into two types: RELAY and RELAY_EARLY.
  49
  50   Only K (say, 10) Relay_early cells can be sent across a circuit, and
  51   only relay_early cells are allowed to contain extend requests. We
  52   still support obscuring the length of the circuit (if more research
  53   shows us what to do), because Alice can choose how many of the K to
  54   mark as relay_early. Note that relay_early cells *can* contain any
  55   sort of data cell; so in effect it's actually the relay type cells
  56   that are restricted. By default, she would just send the first K
  57   data cells over the stream as relay_early cells, regardless of their
  58   actual type.
  59
  60   Each intermediate server would pass on the same type of cell that it
  61   received (either relay or relay_early), and the cell's destination
  62   will be able to learn whether it's allowed to contain an Extend request.
  63
  64   If an intermediate server receives more than K relay_early cells, or
  65   if it sees a relay cell that contains an extend request, then it
  66   tears down the circuit (protocol violation).
  67
  68 Security implications:
  69
  70   The upside is that this limits the bandwidth amplification factor to
  71   K: for an individual circuit to become arbitrary-length, the attacker
  72   would need an adversary-controlled node every K hops, and at that
  73   point the attack is no worse than if the attacker creates N/K separate
  74   K-hop circuits.
  75
  76   On the other hand, we want to pick a large enough value of K that we
  77   don't mind the cap.
  78
  79   If we ever want to take steps to hide the number of hops in the circuit
  80   or a node's position in the circuit, this design probably makes that
  81   more complex.
  82
  83 Migration:
  84
  85   In 0.2.0, servers speaking v2 or later of the link protocol accept
  86   RELAY_EARLY cells, and pass them on.  If the next OR in the circuit
  87   is not speaking the v2 link protocol, the server relays the cell as
  88   a RELAY cell.
  89
  90   In 0.2.1.3-alpha, clients begin using RELAY_EARLY cells on v2
  91   connections.  This functionality can be safely backported to
  92   0.2.0.x.  Clients should pick a random number betweeen (say) K and
  93   K-2 to send.
  94
  95   In 0.2.1.3-alpha, servers close any circuit in which more than K
  96   relay_early cells are sent.
  97
  98   Once all versions the do not send RELAY_EARLY cells are obsolete,
  99   servers can begin to reject any EXTEND requests not sent in a
 100   RELAY_EARLY cell.
 101
 102 Parameters:
 103
 104   Let K = 8, for no terribly good reason.
 105
 106 Spec:
 107
 108   [We can formalize this part once we think the design is a good one.]
 109
 110 Acknowledgements:
 111
 112   This design has been kicking around since Christian Grothoff and I came
 113   up with it at PET 2004. (Nathan Evans, Christian Grothoff's student,
 114   is working on implementing a fix based on this design in the summer
 115   2007 timeframe.)
 116