Automated directories / key rotation / threshold dirservers

[Roger Dingledine <arma@mit.edu>]

With tor's directory server design, users and onion routers only need to
know initially about the handful of directory servers, and from there
they can learn more detailed information about the onion routers that
are currently connected to the network.

Currently each directory server has a routers.or file, which contains
a 'router descriptor' for each router: what ports it's listening on,
what bandwidth it prefers, its identity and link and circuit keys, exit
policies, etc. The current model is that whenever a descriptor changes,
the router operator should tell the dirserver operator (out of band)
about the new descriptor. This clearly cannot scale once we have people
futzing with exit policies, doing nightly encryption-key rotation, etc.

Right now a router is uniquely identified by address:port. But there's
no reason a given address:port must be permanent for a router.

I suggest that we give each router a permanent identity key. This key
signs stuff it does, so you can be sure you're talking about the right
guy. For example, rather than just self-signed certs for link encryption,
the certs should also be signed by the identity key of that router. For
our sanity, each router will also have a unique 'nickname' (eg moria or
nrl) bound to that identity key. The nicknames will come in handy when
we move to a restricted route topology, because the descriptor will need
to list adjacent routers.

In order to handle automated descriptor updating, I've generalized
our little built-in webserver to handle 'post' requests, so routers can
upload signed descriptors.

Keeping the get/post functionality conceptually separate from the OR
functionality of the dirserver may be useful down the road. Another
alternative way to do it would be to have routers send their descriptors
over cell-based (OR) connections. This is a bit trickier, since the
dirserver won't know the link encryption key for the router; but in
theory the cert would be signed by its identity key and it could work
out. Thoughts?

In any case, now the dirserver routers.or file just needs to have
the nickname and identity key of "approved" routers. (Approved means
I've looked at them, to reduce Sybil attacks.)

Each router has the responsibility of getting his descriptor to every
dirserver. I can think of a number of different approaches:
* Dirserver caches unexpired descriptors on disk, so it will have them
  if it restarts. The router uploads its descriptor on startup and
  whenever it changes.
* The router uploads its descriptor whenever a connection to a dirserver
  is established (or when the descriptor changes); so the post
  automatically happens when the dirserver comes back up. Then the
  dirserver never needs to use its disk except at startup.
* The router periodically downloads a directory from the dirserver
  (as he does now, to learn about new routers), and if the dirserver
  has an old or missing descriptor for that router, he uploads a new
  one. Again, no need to use disk except at startup.
How bad is it to deal with partial writes and other descriptor corruption
issues if we keep things on disk? (eg where the dirserver has a broken
copy, but the router figures he already sent it so why send it again).

Which brings us to the question of directory synchronization. A single
directory is a clear security and robustness bottleneck, yet there
are security and robustness problems if clients get different network
views from different dirservers (attacks where the adversary can guess
the initiator based on what directories have been given out; and simple
robustness issues where a given router doesn't know that another router
is up). For simplicity, we assume that all the participants will agree
on who the dirservers are. I guess that means for now that we force an
upgrade when the set of dirservers changes; later we can investigate
allowing partially different dirserver sets.

It would seem that dirservers should periodically collect directories from
other dirservers, and merge (and log) discrepancies. Since everything is
signed, there could be a paper trail so humans can track down misbehaving
parties.

Down the road, it would be nice for dirservers to collect signatures from
other dirservers and add them to the directory. (The stopgap alternative
would be to get users to download all the directories periodically.) To
get the directories identical requires (the easy part) a consistent
ordering of entries within a directory, and (the hard part) some way
of getting the dirservers to converge reasonably quickly on a single
directory.

--Roger