doc/dir-spec.txt

   1 $Id$
   2
   3                   Tor directory protocol for 0.1.1.x series
   4
   5 0. Scope and preliminaries
   6
   7    This document should eventually be merged into tor-spec.txt and replace
   8    the existing notes on directories.
   9
  10    This is not a finalized version; what we actually wind up implementing
  11    may be very different from the system described here.
  12
  13 0.1. Goals
  14
  15    There are several problems with the way Tor handles directories right
  16    now:
  17       1. Directories are very large and use a lot of bandwidth.
  18       2. Every directory server is a single point of failure.
  19       3. Requiring every client to know every server won't scale.
  20       4. Requiring every directory cache to know every server won't scale.
  21       5. Our current "verified server" system is kind of nonsensical.
  22       6. Getting more directory servers adds more points of failure and
  23          worsens possible partitioning attacks.
  24
  25    This design tries to solve every problem except problems 3 and 4, and to
  26    be compatible with likely eventual solutions to problems 3 and 4.
  27
  28 1. Outline
  29
  30    There is no longer any such thing as a "signed directory".  Instead,
  31    directory servers sign a very compressed 'network status' object that
  32    lists the current descriptors and their status, and router descriptors
  33    continue to be self-signed by servers.  Clients download network status
  34    listings periodically, and download router descriptors as needed.  ORs
  35    upload descriptors relatively infrequently.
  36
  37    There are multiple directory servers.  Rather than doing anything
  38    complicated to coordinate themselves, clients simply rotate through them
  39    in order, and only use servers that most of the last several directory
  40    servers like.
  41
  42 2. Router descriptors
  43
  44    The router descriptor format is unchanged from tor-spec.txt.
  45
  46    ORs SHOULD generate a new router descriptor whenever any of the
  47    following events have occurred:
  48
  49       - A period of time (18 hrs by default) has passed since the last
  50         time a descriptor was generated.
  51
  52       - A descriptor field other than bandwidth or uptime has changed.
  53
  54       - Bandwidth has changed by more than +/- 50% from the last time a
  55         descriptor was generated, and at least a given interval of time
  56         (20 mins by default) has passed since then.
  57
  58       - Uptime has been reset.
  59
  60    After generating a descriptor, ORs upload it to every directory
  61    server they know.
  62
  63 3. Network status
  64
  65    Directory servers generate, sign, and compress a network-status document
  66    as needed.  As an optimization, they may rate-limit the number of such
  67    documents generated to once every few seconds.  Directory servers should
  68    rate-limit at least to the point where these documents are generated no
  69    faster than once per second.
  70
  71    The network status document contains a preamble, a set of router status
  72    entries, and a signature, in that order.
  73
  74    We use the same meta-format as used for directories and router descriptors
  75    in "tor-spec.txt".
  76
  77    The preamble contains:
  78
  79       "network-status-version" -- A document format version.  For this
  80          specification, the version is "2".
  81       "dir-source" -- The hostname, current IP address, and directory
  82          port of the directory server, separated by spaces.
  83       "fingerprint" -- A base16-encoded hash of the signing key's
  84          fingerprint, with no additional spaces added.
  85       "contact" -- An arbitrary string describing how to contact the
  86          directory server's administrator.  Administrators should include at
  87          least an email address and a PGP fingerprint.
  88       "dir-signing-key" -- The directory server's public signing key.
  89       "client-versions" -- A comma-separated list of recommended client versions.
  90       "server-versions" -- A comma-separated list of recommended server versions.
  91       "published" -- The publication time for this network-status object.
  92       "dir-options" -- A set of flags separated by spaces:
  93           "Names" if this directory server performs name bindings.
  94           "Versions" if this directory server recommends software versions.
  95
  96    The dir-options entry is optional.  The "-versions" entries are required if
  97    the "Versions" flag is present.  The other entries are required and must
  98    appear exactly once. The "network-status-version" entry must appear first;
  99    the others may appear in any order.
 100
 101    For each router, the router entry contains:  (This format is designed for
 102    conciseness.)
 103
 104       "r" -- followed by the following elements, separated by spaces:
 105           - The OR's nickname,
 106           - A hash of its identity key, encoded in base64, with trailing =
 107             signs removed.
 108           - A hash of its most recent descriptor, encoded in base64, with
 109             trailing = signs removed.  (The hash is calculated as for
 110             computing the signature of a descriptor.)
 111           - The publication time of its most recent descriptor.
 112           - An IP
 113           - An OR port
 114           - A directory port (or "0" for none")
 115       "s" -- A series of space-separated status flags:
 116           "Exit" if the router is useful for building general-purpose exit
 117              circuits.
 118           "Stable" if the router tends to stay up for a long time.
 119           "Fast" if the router has high bandwidth.
 120           "Running" if the router is currently usable.
 121           "Named" if the router's identity-nickname mapping is canonical.
 122           "Valid" if the router has been 'validated'.
 123           "Authority" if the router is a directory authority.
 124
 125       The "r" entry for each router must appear first and is required.  The
 126       's" entry is optional.  Unrecognized flags, or extra elements on the
 127       "r" line must be ignored.
 128
 129    The signature section contains:
 130
 131       "directory-signature". A signature of the rest of the document using
 132       the directory server's signing key.
 133
 134    We compress the network status list with zlib before transmitting it.
 135
 136 4. Directory server operation
 137
 138    By default, directory servers remember all non-expired, non-superseded OR
 139    descriptors that they have seen.
 140
 141    For each OR, a directory server remembers whether the OR was running and
 142    functional the last time they tried to connect to it, and possibly other
 143    liveness information.
 144
 145    Directory server administrators may label some servers or IPs as
 146    blacklisted, and elect not to include them in their network-status lists.
 147
 148    Thus, the network-status list includes all non-blacklisted,
 149    non-expired, non-superseded descriptors for ORs that the directory has
 150    observed at least once to be running.
 151
 152    Directory server administrators may decide to support name binding.  If
 153    they do, then they must maintain a file of nickname-to-identity-key
 154    mappings, and try to keep this file consistent with other directory
 155    servers.  If they don't, they act as clients, and report bindings made by
 156    other directory servers (name X is bound to identity Y if at least one
 157    binding directory lists it, and no directory binds X to some other Y'.)
 158
 159    The authoritative network-status published by a host should be available at:
 160       http://<hostname>/tor/status/authority.z
 161
 162    An authoritative network-status published by another host with fingerprint
 163    <F> should be available at:
 164       http://<hostname>/tor/status/fp/<F>.z
 165
 166    An authoritative network-status published by other hosts with fingerprints
 167    <F1>,<F2>,<F3> should be available at:
 168       http://<hostname>/tor/status/fp/<F1>+<F2>+<F3>.z
 169
 170    The most recent network-status documents from all known authoritative
 171    directories, concatenated, should be available at:
 172          http://<hostname>/tor/status/all.z
 173
 174    The most recent descriptor for a server whose identity key has a
 175    fingerprint of <F> should be available at:
 176       http://<hostname>/tor/server/fp/<F>.z
 177
 178    The most recent descriptors for servers with fingerprints <F1>,<F2>,<F3>
 179    should be available at:
 180       http://<hostname>/tor/server/fp/<F1>+<F2>+<F3>.z
 181
 182    The descriptor for a server whose digest (in hex) is <D> should be
 183    available at:
 184       http://<hostname>/tor/server/d/<D>.z
 185
 186    The most recent descriptors with digests <D1>,<D2>,<D3> should be
 187    available at:
 188       http://<hostname>/tor/server/d/<D1>+<D2>+<D3>.z
 189
 190    The most recent descriptor for this server should be at:
 191       http://<hostname>/tor/server/authority.z
 192
 193    A concatenated set of the most recent descriptors for all known servers
 194    should be available at:
 195       http://<hostname>/tor/server/all.z
 196
 197    For debugging, directories MAY expose non-compressed objects at URLs like
 198    the above, but without the final ".z".
 199
 200    Clients MUST handle compressed concatenated information in two forms:
 201      - A concatenated list of zlib-compressed objects.
 202      - A zlib-compressed concatenated list of objects.
 203    Directory servers MAY generate either format: the former requires less
 204    CPU, but the latter requires less bandwidth.
 205
 206 4.1. Caching
 207
 208    Directory caches (most ORs) regularly download network status documents,
 209    and republish them at a URL based on the directory server's identity key:
 210       http://<hostname>/tor/status/<identity fingerprint>.z
 211
 212    A concatenated list of all network-status documents should be available at:
 213       http://<hostname>/tor/status/all.z
 214
 215 4.2. Compression
 216
 217
 218 5. Client operation
 219
 220    Every OP or OR, including directory servers, acts as a client to the
 221    directory protocol.
 222
 223    Each client maintains a list of trusted directory servers.  Periodically
 224    (currently every 20 minutes), the client downloads a new network status. It
 225    chooses the directory server from which its current information is most
 226    out-of-date, and retries on failure until it finds a running server.
 227
 228    When choosing ORs to build circuits, clients proceed as follows:
 229      - A server is "listed" if it is listed by more than half of the "live"
 230        network status documents the clients have downloaded.  (A network
 231        status is "live" if it is the most recently downloaded network status
 232        document for a given directory server, and the server is a directory
 233        server trusted by the client, and the network-status document is no
 234        more than D (say, 10) days old.)
 235      - A server is "valid" is it is listed as valid by more than half of the
 236        "live" downloaded" network-status document.
 237      - A server is "running" if it is listed as running by more than
 238        half of the "recent" downloaded network-status documents.
 239        (A network status is "recent" if it was published in the last
 240        60 minutes.  If there are fewer than 3 such documents, the most
 241        recently published 3 are "recent."  If there are fewer than 3 in all,
 242        all are "recent.")
 243
 244
 245    Clients store network status documents so long as they are live.
 246
 247 5.1. Scheduling network status downloads
 248
 249    This download scheduling algorithm implements the approach described above
 250    in a relatively low-state fashion.  It reflects the current Tor
 251    implementation.
 252
 253    Clients maintain a list of authorities; each client tries to keep the same
 254    list, in the same order.
 255
 256    Periodically, on startup, and on HUP, clients check whether they need to
 257    download fresh network status documents.  The approach is as follows:
 258      - If we have under X network status documents newer than OLD, we choose a
 259        member of the list at random and try download XX documents starting
 260        with that member's.
 261      - Otherwise, if we have no network status documents newer than NEW, we
 262        check to see which authority's document we retrieved most recently,
 263        and try to retrieve the next authority's document.  If we can't, we
 264        try the next authority in sequence, and so on.
 265
 266 5.2. Managing naming
 267
 268    In order to provide human-memorable names for individual server
 269    identities, some directory servers bind names to IDs.  Clients handle
 270    names in two ways:
 271
 272    If a client is encountering a name it has not mapped before:
 273
 274       If all the "binding" networks-status documents the client has so far
 275       received same claim that the name binds to some identity X, and the
 276       client has received at least three network-status documents, the client
 277       maps the name to X.
 278
 279    If a client is encountering a name it has mapped before:
 280
 281       It uses the last-mapped identity value, unless all of the "binding"
 282       network status documents bind the name to some other identity.
 283
 284 5.3. Notes on what we do now.
 285
 286    THIS SECTION SHOULD BE FOLDED INTO THE EARLIER SECTIONS; THEY ARE WRONG;
 287    THIS IS RIGHT.
 288
 289    All downloaded networkstatuses are discarded once they are 10 days old (by
 290    published date).
 291
 292    Authdirs download each others' networkstatus every
 293    AUTHORITY_NS_CACHE_INTERVAL minutes (currently 10).
 294
 295    Directory caches download authorities' networkstatus every
 296    NONAUTHORITY_NS_CACHE_INTERVAL minutes (currently 10).
 297
 298    Clients always try to replace any networkstatus received over
 299    NETWORKSTATUS_MAX_VALIDITY ago (currently 2 days). Also, when the most
 300    recently received networkstatus is more than
 301    NETWORKSTATUS_CLIENT_DL_INTERVAL (30 minutes) old, and we do not have any
 302    open directory connections fetching a networkstatus, clients try to
 303    download the networkstatus on their list after the most recently received
 304    networkstatus, skipping failed networkstatuses.  A networkstatus is
 305    "failed" if NETWORKSTATUS_N_ALLOWABLE_FAILURES (3) attempts in a row have
 306    all failed.
 307
 308    We do not update router statuses if we have less than half of the
 309    networkstatuses.
 310
 311    A networkstatus is "live" if it is the most recent we have received signed
 312    by a given trusted authority.
 313
 314    A networkstatus is "recent" if it is "live" and:
 315        - it was received in the last DEFAULT_RUNNING_INTERVAL (currently 60
 316          minutes)
 317    OR  - it was one of the MIN_TO_INFLUENCE_RUNNING (3) most recently received
 318          networkstatuses.
 319
 320    Authorities always believe their own opinion as to a router's status.  For
 321    other tors:
 322      - a router is valid if more than half of the live networkstatuses think
 323        it's valid.
 324      - a router is named if more than half of the live networkstatuses from
 325        naming authorities think it's named, and they all think it has the
 326        same name.
 327      - a router is running if more than half of the recent networkstatuses
 328        think it's running.
 329
 330    Everyone downloads router descriptors as follows:
 331
 332      - If any networkstatus lists a more recently published routerdesc with a
 333        different descriptor digest, and no more than
 334        MAX_ROUTERDESC_DOWNLOAD_FAILURES attempts to retrieve that routerdesc
 335        have failed, then that routerdesc is "downloadable".
 336
 337      - Every DirFetchInterval, or whenever a request for routerdescs returns
 338        no routerdescs, we launch a set of requests for all downloadable
 339        routerdescs.  We divide the downloadable routerdescs into groups of no
 340        more than DL_PER_REQUEST, and send a request for each group to
 341        directory servers chosen independently.
 342
 343      - We also launch a request as above when a request for routerdescs
 344        fails and we have no directory connections fetching routerdescs.
 345
 346    TODO Specify here:
 347     - When to 0-out failure count for networkstatus?
 348
 349     - Drop fallback to download-all.  Also, always split download.
 350
 351     - For versions: if you're listed by more than half of live versioning
 352       networkstatuses, good.  if less than half of networkstatuses are live,
 353       don't do anything.  If half are live, and half of less of the
 354       versioning ones list you, warn.  Only warn once every 24 hours.
 355
 356     - For names: warn if an unnamed router is specified by nickname.
 357       Rate-limit these warnings.
 358       - Also, don't believe N->K if another naming authdir says N->K'.
 359       - Revise naming rule: N->K is true if any naming directory says N->K,
 360         and no other naming directory says N->K' or N'->K.
 361
 362     - Minimum info to build circuits.
 363
 364     - Revise: always split requests when we have too little info to build
 365       circuits.
 366
 367     - Describe when router is "out of date".  (Any dirserver says so.)
 368
 369     - Change rule from "do not launch new connections when one exists" to
 370       "do not request any fingerprint that we're currently requesting."
 371
 372     - Launch new connections every minute, plus whenever a download fails.
 373     - Reset routerdesc failure count after 60 minutes, or when
 374       when network comes back on after absence.
 375     - Make "I didn't get the one I thought was most recent" a failure.
 376       - Retry these every 5 minutes if you're a client.
 377       - Mirrors should retry these harder and more often.
 378     - If we have a routerdesc for Bob, and he says, "I'm 0.1.0.x", don't
 379       fetch a new one if it was published in the last 2 hours. (??)
 380
 381     - Describe what we do with old server versions.
 382
 383     - If we have less than 16 to download, do not download unless 10 minutes
 384       have passed since last download.
 385
 386     - Which descriptors do directory servers remember?
 387
 388 6. Remaining issues
 389
 390    Client-knowledge partitioning is worrisome.  Most versions of this don't
 391    seem to be worse than the Danezis-Murdoch tracing attack, since an
 392    attacker can't do more than deduce probable exits from entries (or vice
 393    versa).  But what about when the client connects to A and B but in a
 394    different order?  How bad can it be partitioned based on its knowledge?
 395