136-legacy-keys.txt

Filename: 136-legacy-keys.txt
Title: Mass authority migration with legacy keys
Author: Nick Mathewson
Created: 13-May-2008
Status: Closed
Implemented-In: 0.2.0.x

Overview:

  This document describes a mechanism to change the keys of more than
  half of the directory servers at once without breaking old clients
  and caches immediately.

Motivation:

  If a single authority's identity key is believed to be compromised,
  the solution is obvious: remove that authority from the list,
  generate a new certificate, and treat the new cert as belonging to a
  new authority.  This approach works fine so long as less than 1/2 of
  the authority identity keys are bad.

  Unfortunately, the mass-compromise case is possible if there is a
  sufficiently bad bug in Tor or in any OS used by a majority of v3
  authorities.  Let's be prepared for it!

  We could simply stop using the old keys and start using new ones,
  and tell all clients running insecure versions to upgrade.
  Unfortunately, this breaks our cacheing system pretty badly, since
  caches won't cache a consensus that they don't believe in.  It would
  be nice to have everybody become secure the moment they upgrade to a
  version listing the new authority keys, _without_ breaking upgraded
  clients until the caches upgrade.

  So, let's come up with a way to provide a time window where the
  consensuses are signed with the new keys and with the old.

Design:

  We allow directory authorities to list a single "legacy key"
  fingerprint in their votes.  Each authority may add a single legacy
  key.  The format for this line is:

     legacy-dir-key FINGERPRINT

  We describe a new consensus method for generating directory
  consensuses.  This method is consensus method "3".

  When the authorities decide to use method "3" (as described in 3.4.1
  of dir-spec.txt), for every included vote with a legacy-dir-key line,
  the consensus includes an extra dir-source line.  The fingerprint in
  this extra line is as in the legacy-dir-key line.  The ports and
  addresses are in the dir-source line.  The nickname is as in the
  dir-source line, with the string "-legacy" appended.

      [We need to include this new dir-source line because the code
      won't accept or preserve signatures from authorities not listed
      as contributing to the consensus.]

  Authorities using legacy dir keys include two signatures on their
  consensuses: one generated with a signing key signed with their real
  signing key, and another generated with a signing key signed with
  another signing key attested to by their identity key.  These
  signing keys MUST be different.  Authorities MUST serve both
  certificates if asked.

Process:

  In the event of a mass key failure, we'll follow the following
  (ugly) procedure:
     - All affected authorities generate new certificates and identity
       keys, and circulate their new dirserver lines.  They copy their old
       certificates and old broken keys, but put them in new "legacy
       key files".
     - At the earliest time that can be arranged, the authorities
       replace their signing keys, identity keys, and certificates
       with the new uncompromised versions, and update to the new list
       of dirserer lines.
     - They add an "V3DirAdvertiseLegacyKey 1" option to their torrc.
     - Now, new consensuses will be generated using the new keys, but
       the results will also be signed with the old keys.
     - Clients and caches are told they need to upgrade, and given a
       time window to do so.
     - At the end of the time window, authorities remove the
       V3DirAdvertiseLegacyKey option.

Notes:

  It might be good to get caches to cache consensuses that they do not
  believe in.  I'm not sure the best way of how to do this.

  It's a superficially neat idea to have new signing keys and have
  them signed by the new and by the old authority identity keys.  This
  breaks some code, though, and doesn't actually gain us anything,
  since we'd still need to include each signature twice.

  It's also a superficially neat idea, if identity keys and signing
  keys are compromised, to at least replace all the signing keys.
  I don't think this achieves us anything either, though.