proposals/105-handshake-revision.txt

   1 Filename: 105-handshake-revision.txt
   2 Title: Version negotiation for the Tor protocol.
   3 Author: Nick Mathewson, Roger Dingledine
   4 Created: Jan 2007
   5 Status: Closed
   6 Implemented-In: 0.2.0.x
   7
   8 Overview:
   9
  10   This document was extracted from a modified version of tor-spec.txt that we
  11   had written before the proposal system went into place.  It adds two new
  12   cells types to the Tor link connection setup handshake: one used for
  13   version negotiation, and another to prevent MITM attacks.
  14
  15   This proposal is partially implemented, and partially proceded by
  16   proposal 130.
  17
  18 Motivation: Tor versions
  19
  20    Our *current* approach to versioning the Tor protocol(s) has been as
  21    follows:
  22      - All changes must be backward compatible.
  23      - It's okay to add new cell types, if they would be ignored by previous
  24        versions of Tor.
  25      - It's okay to add new data elements to cells, if they would be
  26        ignored by previous versions of Tor.
  27      - For forward compatibility, Tor must ignore cell types it doesn't
  28        recognize, and ignore data in those cells it doesn't expect.
  29      - Clients can inspect the version of Tor declared in the platform line
  30        of a router's descriptor, and use that to learn whether a server
  31        supports a given feature.  Servers, however, aren't assumed to all
  32        know about each other, and so don't know the version of who they're
  33        talking to.
  34
  35    This system has these problems:
  36      - It's very hard to change fundamental aspects of the protocol, like the
  37        cell format, the link protocol, any of the various encryption schemes,
  38        and so on.
  39      - The router-to-router link protocol has remained more-or-less frozen
  40        for a long time, since we can't easily have an OR use new features
  41        unless it knows the other OR will understand them.
  42
  43    We need to resolve these problems because:
  44      - Our cipher suite is showing its age: SHA1/AES128/RSA1024/DH1024 will
  45        not seem like the best idea for all time.
  46      - There are many ideas circulating for multiple cell sizes; while it's
  47        not obvious whether these are safe, we can't do them at all without a
  48        mechanism to permit them.
  49      - There are many ideas circulating for alternative circuit building and
  50        cell relay rules: they don't work unless they can coexist in the
  51        current network.
  52      - If our protocol changes a lot, it's hard to describe any coherent
  53        version of it: we need to say "the version that Tor versions W through
  54        X use when talking to versions Y through Z".  This makes analysis
  55        harder.
  56
  57 Motivation: Preventing MITM attacks
  58
  59    TLS prevents a man-in-the-middle attacker from reading or changing the
  60    contents of a communication.  It does not, however, prevent such an
  61    attacker from observing timing information.  Since timing attacks are some
  62    of the most effective against low-latency anonymity nets like Tor, we
  63    should take more care to make sure that we're not only talking to who
  64    we think we're talking to, but that we're using the network path we
  65    believe we're using.
  66
  67 Motivation: Signed clock information
  68
  69    It's very useful for Tor instances to know how skewed they are relative
  70    to one another.  The only way to find out currently has been to download
  71    directory information, and check the Date header--but this is not
  72    authenticated, and hence subject to modification on the wire.  Using
  73    BEGIN_DIR to create an authenticated directory stream through an existing
  74    circuit is better, but that's an extra step and it might be nicer to
  75    learn the information in the course of the regular protocol.
  76
  77 Proposal:
  78
  79 1.0. Version numbers
  80
  81    The node-to-node TLS-based "OR connection" protocol and the multi-hop
  82    "circuit" protocol are versioned quasi-independently.
  83
  84    Of course, some dependencies will continue to exist: Certain versions
  85    of the circuit protocol may require a minimum version of the connection
  86    protocol to be used.  The connection protocol affects:
  87      - Initial connection setup, link encryption, transport guarantees,
  88        etc.
  89      - The allowable set of cell commands
  90      - Allowable formats for cells.
  91
  92    The circuit protocol determines:
  93      - How circuits are established and maintained
  94      - How cells are decrypted and relayed
  95      - How streams are established and maintained.
  96
  97    Version numbers are incremented for backward-incompatible protocol changes
  98    only.  Backward-compatible changes are generally implemented by adding
  99    additional fields to existing structures; implementations MUST ignore
 100    fields they do not expect.  Unused portions of cells MUST be set to zero.
 101
 102    Though versioning the protocol will make it easier to maintain backward
 103    compatibility with older versions of Tor, we will nevertheless continue to
 104    periodically drop support for older protocols,
 105       - to keep the implementation from growing without bound,
 106       - to limit the maintenance burden of patching bugs in obsolete Tors,
 107       - to limit the testing burden of verifying that many old protocol
 108         versions continue to be implemented properly, and
 109       - to limit the exposure of the network to protocol versions that are
 110         expensive to support.
 111
 112    The Tor protocol as implemented through the 0.1.2.x Tor series will be
 113    called "version 1" in its link protocol and "version 1" in its relay
 114    protocol.  Versions of the Tor protocol so old as to be incompatible with
 115    Tor 0.1.2.x can be considered to be version 0 of each, and are not
 116    supported.
 117
 118 2.1. VERSIONS cells
 119
 120    When a Tor connection is established, both parties normally send a
 121    VERSIONS cell before sending any other cells.  (But see below.)
 122
 123          VersionsLen          [2 byte]
 124          Versions             [VersionsLen bytes]
 125
 126    "Versions" is a sequence of VersionsLen bytes.  Each value between 1 and
 127    127 inclusive represents a single version; current implementations MUST
 128    ignore other bytes.  Parties should list all of the versions which they
 129    are able and willing to support.  Parties can only communicate if they
 130    have some connection protocol version in common.
 131
 132    Version 0.2.0.x-alpha and earlier don't understand VERSIONS cells,
 133    and therefore don't support version negotiation.  Thus, waiting until
 134    the other side has sent a VERSIONS cell won't work for these servers:
 135    if the other side sends no cells back, it is impossible to tell
 136    whether they
 137    have sent a VERSIONS cell that has been stalled, or whether they have
 138    dropped our own VERSIONS cell as unrecognized.  Therefore, we'll
 139    change the TLS negotiation parameters so that old parties can still
 140    negotiate, but new parties can recognize each other.  Immediately
 141    after a TLS connection has been established, the parties check
 142    whether the other side negotiated the connection in an "old" way or a
 143    "new" way.  If either party negotiated in the "old" way, we assume a
 144    v1 connection.  Otherwise, both parties send VERSIONS cells listing
 145    all their supported versions.  Upon receiving the other party's
 146    VERSIONS cell, the implementation begins using the highest-valued
 147    version common to both cells.  If the first cell from the other party
 148    has a recognized command, and is _not_ a VERSIONS cell, we assume a
 149    v1 protocol.
 150
 151    (For more detail on the TLS protocol change, see forthcoming draft
 152    proposals from Steven Murdoch.)
 153
 154    Implementations MUST discard VERSIONS cells that are not the first
 155    recognized cells sent on a connection.
 156
 157    The VERSIONS cell must be sent as a v1 cell (2 bytes of circuitID, 1
 158    byte of command, 509 bytes of payload).
 159
 160    [NOTE: The VERSIONS cell is assigned the command number 7.]
 161
 162 2.2. MITM-prevention and time checking
 163
 164    If we negotiate a v2 connection or higher, the second cell we send SHOULD
 165    be a NETINFO cell.  Implementations SHOULD NOT send NETINFO cells at other
 166    times.
 167
 168    A NETINFO cell contains:
 169          Timestamp              [4 bytes]
 170          Other OR's address     [variable]
 171          Number of addresses    [1 byte]
 172          This OR's addresses    [variable]
 173
 174    Timestamp is the OR's current Unix time, in seconds since the epoch.  If
 175    an implementation receives time values from many ORs that
 176    indicate that its clock is skewed, it SHOULD try to warn the
 177    administrator. (We leave the definition of 'many' intentionally vague
 178    for now.)
 179
 180    Before believing the timestamp in a NETINFO cell, implementations
 181    SHOULD compare the time at which they received the cell to the time
 182    when they sent their VERSIONS cell.  If the difference is very large,
 183    it is likely that the cell was delayed long enough that its
 184    contents are out of date.
 185
 186    Each address contains Type/Length/Value as used in Section 6.4 of
 187    tor-spec.txt.  The first address is the one that the party sending
 188    the NETINFO cell believes the other has -- it can be used to learn
 189    what your IP address is if you have no other hints.
 190    The rest of the addresses are the advertised addresses of the party
 191    sending the NETINFO cell -- we include them
 192    to block a man-in-the-middle attack on TLS that lets an attacker bounce
 193    traffic through his own computers to enable timing and packet-counting
 194    attacks.
 195
 196    A Tor instance should use the other Tor's reported address
 197    information as part of logic to decide whether to treat a given
 198    connection as suitable for extending circuits to a given address/ID
 199    combination.  When we get an extend request, we use an
 200    existing OR connection if the ID matches, and ANY of the following
 201    conditions hold:
 202        - The IP matches the requested IP.
 203        - We know that the IP we're using is canonical because it was
 204          listed in the NETINFO cell.
 205        - We know that the IP we're using is canonical because it was
 206          listed in the server descriptor.
 207
 208    [NOTE: The NETINFO cell is assigned the command number 8.]
 209
 210 Discussion: Versions versus feature lists
 211
 212    Many protocols negotiate lists of available features instead of (or in
 213    addition to) protocol versions.  While it's possible that some amount of
 214    feature negotiation could be supported in a later Tor, we should prefer to
 215    use protocol versions whenever possible, for reasons discussed in
 216    the "Anonymity Loves Company" paper.
 217
 218 Discussion: Bytes per version, versions per cell
 219
 220    This document provides for a one-byte count of how many versions a Tor
 221    supports, and allows one byte per version.  Thus, it can only support only
 222    254 more versions of the protocol beyond the unallocated v0 and the
 223    current v1.  If we ever need to split the protocol into 255 incompatible
 224    versions, we've probably screwed up badly somewhere.
 225
 226    Nevertheless, here are two ways we could support more versions:
 227      - Change the version count to a two-byte field that counts the number of
 228        _bytes_ used, and use a UTF8-style encoding: versions 0 through 127
 229        take one byte to encode, versions 128 through 2047 take two bytes to
 230        encode, and so on.  We wouldn't need to parse any version higher than
 231        127 right now, since all bytes used to encode higher versions would
 232        have their high bit set.
 233
 234        We'd still have a limit of 380 simultaneously versions that could be
 235        declared in any version.  This is probably okay.
 236
 237      - Decide that if we need to support more versions, we can add a
 238        MOREVERSIONS cell that gets sent before the VERSIONS cell.  The spec
 239        above requires Tors to ignore unrecognized cell types that they get
 240        before the first VERSIONS cell, and still allows version negotiation
 241        to
 242        succeed.
 243
 244    [Resolution: Reserve the high bit and the v0 value for later use.  If
 245     we ever have more live versions than we can fit in a cell, we've made a
 246     bad design decision somewhere along the line.]
 247
 248 Discussion: Reducing round-trips
 249
 250    It might be appealing to see if we can cram more information in the
 251    initial VERSIONS cell.  For example, the contents of NETINFO will pretty
 252    soon be sent by everybody before any more information is exchanged, but
 253    decoupling them from the version exchange increases round-trips.
 254
 255    Instead, we could speculatively include handshaking information at
 256    the end of a VERSIONS cell, wrapped in a marker to indicate, "if we wind
 257    up speaking VERSION 2, here's the NETINFO I'll send.  Otherwise, ignore
 258    this."  This could be extended to opportunistically reduce round trips
 259    when possible for future versions when we guess the versions right.
 260
 261    Of course, we'd need to be careful about using a feature like this:
 262      - We don't want to include things that are expensive to compute,
 263        like PK signatures or proof-of-work.
 264      - We don't want to speculate as a mobile client: it may leak our
 265        experience with the server in question.
 266
 267 Discussion: Advertising versions in routerdescs and networkstatuses.
 268
 269    In network-statuses:
 270
 271      The networkstatus "v" line now has the format:
 272         "v" IMPLEMENTATION IMPL-VERSION "Link" LINK-VERSION-LIST
 273             "Circuit" CIRCUIT-VERSION-LIST NL
 274
 275      LINK-VERSION-LIST and CIRCUIT-VERSION-LIST are comma-separated lists of
 276      supported version numbers.  IMPLEMENTATION is the name of the
 277      implementation of the Tor protocol (e.g., "Tor"), and IMPL-VERSION is the
 278      version of the implementation.
 279
 280      Examples:
 281         v Tor 0.2.5.1-alpha Link 1,2,3 Circuit 2,5
 282
 283         v OtherOR 2000+ Link 3 Circuit 5
 284
 285      Implementations that release independently of the Tor codebase SHOULD NOT
 286      use "Tor" as the value of their IMPLEMENTATION.
 287
 288      Additional fields on the "v" line MUST be ignored.
 289
 290    In router descriptors:
 291
 292      The router descriptor should contain a line of the form,
 293        "protocols" "Link" LINK-VERSION-LIST "Circuit" CIRCUIT_VERSION_LIST
 294
 295      Additional fields on the "protocols" line MUST be ignored.
 296
 297      [Versions of Tor before 0.1.2.5-alpha rejected router descriptors with
 298      unrecognized items; the protocols line should be preceded with an "opt"
 299      until these Tors are obsolete.]
 300
 301 Security issues:
 302
 303    Client partitioning is the big danger when we introduce new versions; if a
 304    client supports some very unusual set of protocol versions, it will stand
 305    out from others no matter where it goes.  If a server supports an unusual
 306    version, it will get a disproportionate amount of traffic from clients who
 307    prefer that version.  We can mitigate this somewhat as follows:
 308
 309      - Do not have clients prefer any protocol version by default until that
 310        version is widespread.  (First introduce the new version to servers,
 311        and have clients admit to using it only when configured to do so for
 312        testing.  Then, once many servers are running the new protocol
 313        version, enable its use by default.)
 314
 315      - Do not multiply protocol versions needlessly.
 316
 317      - Encourage protocol implementors to implement the same protocol version
 318        sets as some popular version of Tor.
 319
 320      - Disrecommend very old/unpopular versions of Tor via the directory
 321        authorities' RecommmendedVersions mechanism, even if it is still
 322        technically possible to use them.
 323