tor-parallel-relay-conn/doc/spec/proposals/105-handshake-revision.txt

Filename: 105-handshake-revision.txt
Title: Version negotiation for the Tor protocol.
Version: $Revision$
Last-Modified: $Date$
Author: Nick Mathewson, Roger Dingledine
Created:
Status: Open

Overview:

  This document was extracted from a modified version of tor-spec.txt that we
  had written before the proposal system went into place.  It adds two new
  cells types to the Tor link connection setup handshake: one used for
  version negotiation, and another to prevent MITM attacks.

  This is an open proposal.

Motivation: Tor versions

   Our *current* approach to versioning the Tor protocol(s) has been as
   follows:
     - All changes must be backward compatible.
     - It's okay to add new cell types, if they would be ignored by previous
       versions of Tor.
     - It's okay to add new data elements to cells, if they would be
       ignored by previous versions of Tor.
     - For forward compatibility, Tor must ignore cell types it doesn't
       recognize, and ignore data in those cells it doesn't expect.
     - Clients can inspect the version of Tor declared in the platform line
       of a router's descriptor, and use that to learn whether a server
       supports a given feature.  Servers, however, aren't assumed to all
       know about each other, and so don't know the version of who they're
       talking to.

   This system has these problems:
     - It's very hard to change fundamental aspects of the protocol, like the
       cell format, the link protocol, any of the various encryption schemes,
       and so on.
     - The router-to-router link protocol has remained more-or-less frozen
       for a long time, since we can't easily have an OR use new features
       unless it knows the other OR will understand them.

   We need to resolve these problems because:
     - Our cipher suite is showing its age: SHA1/AES128/RSA1024/DH1024 will
       not seem like the best idea for all time.
     - There are many ideas circulating for multiple cell sizes; while it's
       not obvious whether these are safe, we can't do them at all without a
       mechanism to permit them.
     - There are many ideas circulating for alternative circuit building and
       cell relay rules: they don't work unless they can coexist in the
       current network.
     - If our protocol changes a lot, it's hard to describe any coherent
       version of it: we need to say "the version that Tor versions W through
       X use when talking to versions Y through Z".  This makes analysis
       harder.

Motivation: Preventing MITM attacks

   TLS prevents a man-in-the-middle attacker from reading or changing the
   contents of a communication.  It does not, however, prevent such an
   attacker from observing timing information.  Since timing attacks are some
   of the most effective against low-latency anonymity nets like Tor, we
   should take more care to make sure that we're not only talking to who
   we think we're talking to, but that we're using the network path we
   believe we're using.

Motivation: Signed clock information

   It's very useful for Tor instances to know how skewed they are relative
   to one another.  The only way to find out currently has been to download
   directory information, and check the Date header--but this is not
   authenticated, and hence subject to modification on the wire.  Using
   BEGIN_DIR to create an authenticated directory stream through an existing
   circuit is better, but that's an extra step and it might be nicer to
   learn the information in the course of the regular protocol.

Proposal:

1.0. Version numbers

   The node-to-node TLS-based "OR connection" protocol and the multi-hop
   "circuit" protocol are versioned quasi-independently.

   Of course, some dependencies will continue to exist: Certain versions
   of the circuit protocol may require a minimum version of the connection
   protocol to be used.  The connection protocol affects:
     - Initial connection setup, link encryption, transport guarantees,
       etc.
     - The allowable set of cell commands
     - Allowable formats for cells.

   The circuit protocol determines:
     - How circuits are established and maintained
     - How cells are decrypted and relayed
     - How streams are established and maintained.

   Version numbers are incremented for backward-incompatible protocol changes
   only.  Backward-compatible changes are generally implemented by adding
   additional fields to existing structures; implementations MUST ignore
   fields they do not expect.  Unused portions of cells MUST be set to zero.

   Though versioning the protocol will make it easier to maintain backward
   compatibility with older versions of Tor, we will nevertheless continue to
   periodically drop support for older protocols,
      - to keep the implementation from growing without bound,
      - to limit the maintenance burden of patching bugs in obsolete Tors,
      - to limit the testing burden of verifying that many old protocol
        versions continue to be implemented properly, and
      - to limit the exposure of the network to protocol versions that are
        expensive to support.

   The Tor protocol as implemented through the 0.1.2.x Tor series will be
   called "version 1" in its link protocol and "version 1" in its relay
   protocol.  Versions of the Tor protocol so old as to be incompatible with
   Tor 0.1.2.x can be considered to be version 0 of each, and are not
   supported.

2.1. VERSIONS cells

   When a Tor connection is established, both parties normally send a
   VERSIONS cell before sending any other cells.  (But see below.)

         NumVersions          [1 byte]
         Versions             [NumVersions bytes]

   "Versions" is a sequence of NumVersions link connection protocol versions,
   each one byte long.  Parties should list all of the versions which they
   are able and willing to support.  Parties can only communicate if they
   have some connection protocol version in common.

   Version 0.2.0.x-alpha and earlier don't understand VERSIONS cells,
   and therefore don't support version negotiation.  Thus, waiting until
   the other side has sent a VERSIONS cell won't work for these servers:
   if the other side sends no cells back, it is impossible to tell
   whether they
   have sent a VERSIONS cell that has been stalled, or whether they have
   dropped our own VERSIONS cell as unrecognized.  Thus, immediately after
   a TLS connection has been established, the parties check whether the
   other side has an obsolete certificate (organizationName equal to "Tor"
   or "TOR").  If the other party presented an obsolete certificate,
   we assume a v1 connection.  Otherwise, both parties send VERSIONS
   cells listing all their supported versions.  Upon receiving the
   other party's VERSIONS cell, the implementation begins using the
   highest-valued version common to both cells.  If the first cell from
   the other party has a recognized command, and is _not_ a VERSIONS cell, we
   assume a v1 protocol.

   Implementations MUST discard VERSIONS cells that are not the first
   recognized cells sent on a connection.

   The VERSIONS cell must be sent as a v1 cell (2 bytes of circuitID, 1
   byte of command, 509 bytes of payload).

2.2. MITM-prevention and time checking

   If we negotiate a v2 connection or higher, the second cell we send SHOULD
   be a NETINFO cell.  Implementations SHOULD NOT send NETINFO cells at other
   times.

   A NETINFO cell contains:
         Timestamp              [4 bytes]
         This OR's address      [variable]
         Other OR's address     [variable]

   Timestamp is the OR's current Unix time, in seconds since the epoch.  If
   an implementation receives time values from many ORs that
   indicate that its clock is skewed, it SHOULD try to warn the
   administrator. (We leave the definition of 'many' intentionally vague
   for now.)

   Each address contains Type/Length/Value as used in Section 6.4 of
   tor-spec.txt.  The first address is the address of the interface the
   party sending the NETINFO cell
   used to connect to or accept connections from the other -- we include it
   to block a man-in-the-middle attack on TLS that lets an attacker bounce
   traffic through his own computers to enable timing and packet-counting
   attacks.

   The second address is the one that the party sending the NETINFO cell
   believes the other has -- it can be used to learn what your IP address
   is if you have no other hints.

Discussion: Versions versus feature lists

   Many protocols negotiate lists of available features instead of (or in
   addition to) protocol versions.  While it's possible that some amount of
   version negotiation could be supported in a later Tor, we should prefer to
   use protocol versions whenever possible, for reasons discussed in
   the "Anonymity Loves Company" paper.

Discussion: Bytes per version, versions per cell

   This document provides for a one-byte count of how many versions a Tor
   supports, and allows one byte per version.  Thus, it can only support only
   254 more versions of the protocol beyond the unallocated v0 and the
   current v1.  If we ever need to split the protocol into 255 incompatible
   versions, we've probably screwed up badly somewhere.

   Nevertheless, here are two ways we could support more versions:
     - Change the version count to a two-byte field that counts the number of
       _bytes_ used, and use a UTF8-style encoding: versions 0 through 127
       take one byte to encode, versions 128 through 2047 take two bytes to
       encode, and so on.  We wouldn't need to parse any version higher than
       127 right now, since all bytes used to encode higher versions would
       have their high bit set.

       We'd still have a limit of 380 simultaneously versions that could be
       declared in any version.  This is probably okay.

     - Decide that if we need to support more versions, we can add a
       MOREVERSIONS cell that gets sent before the VERSIONS cell.  The spec
       above requires Tors to ignore unrecognized cell types that they get
       before the first VERSIONS cell, and still allows version negotiation to
       succeed.

Discussion: Reducing round-trips

   It might be appealing to see if we can cram more information in the
   initial VERSIONS cell.  For example, the contents of NETINFO will pretty
   soon be sent by everybody before any more information is exchanged, but
   decoupling them from the version exchange increases round-trips.

   Instead, we could speculatively include handshaking information at
   the end of a VERSIONS cell, wrapped in a marker to indicate, "if we wind
   up speaking VERSION 2, here's the NETINFO I'll send.  Otherwise, ignore
   this."  This could be extended to opportunistically reduce round trips
   when possible for future versions when we guess the versions right.

   Of course, we'd need to be careful about using a feature like this:
     - We don't want to include things that are expensive to compute,
       like PK signatures or proof-of-work.
     - We don't want to speculate as a mobile client: it may leak our
       experience with the server in question.

Discussion: Advertising versions in routerdescs and networkstatuses.

   In network-statuses:

     The networkstatus "v" line now has the format:
        "v" IMPLEMENTATION IMPL-VERSION "Link" LINK-VERSION-LIST
            "Circuit" CIRCUIT-VERSION-LIST NL

     LINK-VERSION-LIST and CIRCUIT-VERSION-LIST are comma-separated lists of
     supported version numbers.  IMPLEMENTATION is the name of the
     implementation of the Tor protocol (e.g., "Tor"), and IMPL-VERSION is the
     version of the implementation.

     Examples:
        v Tor 0.2.5.1-alpha Link 1,2,3 Circuit 2,5

        v OtherOR 2000+ Link 3 Circuit 5

     Implementations that release independently of the Tor codebase SHOULD NOT
     use "Tor" as the value of their IMPLEMENTATION.

     Additional fields on the "v" line MUST be ignored.

   In router descriptors:

     The router descriptor should contain a line of the form,
       "protocols" "Link" LINK-VERSION-LIST "Circuit" CIRCUIT_VERSION_LIST

     Additional fields on the "protocols" line MUST be ignored.

     [Versions of Tor before 0.1.2.5-alpha rejected router descriptors with
     unrecognized items; the protocols line should be preceded with an "opt"
     until these Tors are obsolete.]


Security issues:

   Client partitioning is the big danger when we introduce new versions; if a
   client supports some very unusual set of protocol versions, it will stand
   out from others no matter where it goes.  If a server supports an unusual
   version, it will get a disproportionate amount of traffic from clients who
   prefer that version.  We can mitigate this somewhat as follows:

     - Do not have clients prefer any protocol version by default until that
       version is widespread.  (First introduce the new version to servers,
       and have clients admit to using it only when configured to do so for
       testing.  Then, once many servers are running the new protocol
       version, enable its use by default.)

     - Do not multiply protocol versions needlessly.

     - Encourage protocol implementors to implement the same protocol version
       sets as some popular version of Tor.

     - Disrecommend very old/unpopular versions of Tor via the directory
       authorities' RecommmendedVersions mechanism, even if it is still
       technically possible to use them.