[tor-dev] Proposal 256: Key revocation for relays and authorities

[Nick Mathewson]

Filename: 256-key-revocation.txt
Title: Key revocation for relays and authorities
Authors: Nick Mathewson
Created: 27 October 2015
Status: Open

1. Introduction

   This document examines the different kinds of long-lived public keys
   in Tor, and discusses a way to revoke each.

   The kind of keys at issue are:

      * Authority identity keys
      * Authority signing keys

      * OR identity keys (ed25519)
      * OR signing keys (ed25519)
      * OR identity keys (RSA)

   Additionally, we need to make sure that all other key types, if they
   are compromised, can be replaced or rendered unusable.

2. When to revoke keys

   Revoking keys should happen when the operator of an authority or
   relay believes that the key has been compromised, or has a
   significant risk of having been compromised.  In this proposal we
   deliberately leave this decision up to the authority/relay operators.

   (If a third party believes that a key has been compromised, they
   should attempt to get the key-issuing party to revoke their key.  If
   that can't be done, the uncompromised authorities should block the
   relay or de-list the authority in question.)

   Our key-generation code (for authorities and relays) should generate
   preemptive revocation documents at the same time it generates the
   original keys, so that operators can retain those documents in the
   event that access to the original keys is lost.  The operators should
   keep these revocation documents private and available enough so that
   they can issue the revocation if necessary, but nobody else can.

   Additionally, the key generation code should be able to generate
   retrospective revocation documents for existing keys and
   certificates.  (This approach can be more useful when a subkey is
   revoked, but the operator still has ready access to the issuing key.)

3. Authority keys

   Authority identity keys are the most important keys in Tor.  They are
   kept offline and encrypted.  They are used to sign authority signing
   keys, and for no other purpose.

   Authority signing keys are kept online.  They are authenticated by
   authority identity keys, and used to sign votes and consensus
   documents.

   (For the rest of section 2, all keys mentioned will be authority keys.)

3.1. Revocation certificates for authorities

   We add the following extensions to authority key certificates (see
   dir-spec.txt section 3.1), for use in key revocation.

   "dir-key-revocation-type" SP "master" | "signing" NL

      Specifies which kind of revocation document this is.

      If dir-key-revocation is absent, this is not a revocation.

      [At most once]

   "dir-key-revocation-notes" SP (any non-NL text) NL

      An explanation of why the key was revoked.

      Must be absent unless dir-key-revocation-type is set.

      [Any number of times]

   "dir-key-revocation-signing-key-unusable" NL

      Present if the signing key in this document will not actually be
      used to sign votes and consensuses.

      [At most once]

   "dir-key-revoked-signing-key" SP DIGEST NL

      Fingerprints of signing keys being explicitly revoked by this
      certificate. (All keys published before this one are _implicitly_
      revoked.)

      [Any number of times]

   "dir-key-revocation-published" SP YYYY-MM-DD SP HH:MM:SS NL

      The actual time when the revocation was generated. (Used since the
      'published' field in the certificate will lie; see below.)

      [at most once.]


3.2. Generating revocations

   Revocations for signing keys should be generated with:
     * A 'published' time immediately following the published date on
       the key that they are revoking.
     * An 'expires' time at least 48 hours after the expires date on
       the key that they are revoking, and at least one week in the
       future.

   (Note that this ensures as-correct-as-possible behavior for existing
   Tor clients and servers.  For Tor versions before 0.2.6, having a
   more recent published date than the older key will cause the revoked
   key certificate to be removed by trusted_dirs_remove_old_certs() if
   it is published at least 7 days in the past.  For Tor versions 0.2.6
   or later, the interval is reduced to 2 days.)

   If generating a signing key revocation ahead of time, the revocation
   document should include a dummy signing key, to be thrown away
   immediately after it is generated and used to make the revocation
   document.  The "dir-key-revocation-signing-key-unusable" element
   should be present.

   If generating a signing key revocation in response to an event,
   the revocation document should include the new signing key to be
   used.   The "dir-key-revocation-signing-key-unusable" element
   must be be absent.

   All replacement certificates generated for the lifetime of the
   original revoked certificate should be generated as revocations.



   Revocations for master keys should be generated with:
     * A 'published' time immediately following the published date on
       the most recently generated certificate, if possible.
     * An 'expires' time equal to 18 Jan 2038. (The next-to-last day
       encodeable in time_t, to avoid Y2038 problems.)
     * A dummy signing key, as above.

3.3. Submitting revocations

  In the event of a key revocation, authority operators should
  upload the revocation document to every other authority.

  If there is a replacement signing key, it should be included in the
  authority's votes (as any new key certificate would be).

3.4. Handling revocations

  We add these additional rules for caching and storing revocations on
  Tor servers and clients.
     * Master key revocations should be stored indefinitely.
     * If we have a master key revocation, no other certificates for
       that key should be fetched, stored, or served.
     * If we have a master key revocation, we should replace any
       DirAuthority entry for that master key with a 'null' entry -- an
       authority with no address and no keys, from which nothing can be
       downloaded and nothing can be trusted, but which still counts against
       the total number of authorities.

     * Signing key revocations should be retained until their 'expires'
       date.
     * If we have a signing key revocation document, we should not trust
       any signature generated with any key in an older signing key
       certificates for the same master key.  We should not serve such
       key certificates.
     * We should not attempt to fetch any certificate document matching
       an <identity, signing> pair for which a revocation document exists.

  We add these additional rule for directory authorities:

     * When generating or serving a consensus document, an authority
       should include a dir-source entry based on the most recent
       revocation cert it has from an authority, unless that authority
       has a more recent valid key cert.

       (This will require a new consensus method.)

     * When generating or serving a consensus document, if no valid
       signature exists from a given authority, and that authority has
       a currently valid key revocation document with a signing key in
       it, it should include a bogus signature purporting to be made
       with that signing key.  (All-zeros is suggested.)

       (Doing this will make old Tor clients download the revocation
       certificates.)

4. Router identity key revocations

4.1. RSA identity keys

   If the RSA key is compromised but the ed25519 identity and signing
   keys are not, simply disable the router.  Key pinning should take
   care of the rest.

   (This isn't ideal when key pinning isn't deployed yet, but I'm
   betting that key pinning comes online before this proposal does.)

4.2. Ed25519 master identity keys

   (We use the data format from proposal 220, section 2.3 here.)

   To revoke a master identity key, create a revocation for the master
   key and upload it to every authority.

   Authorities should accept these documents as meaning that the signing
   key should never be allowed to appear on the Tor network.  This can
   be enforced with the key pinning mechanism.

4.3. Ed25519 signing keys

   (We use the data format from proposal 220, section 2.3 here.)

   To revoke a signing key, include the revocation for every
   not-yet-expired signing key in your routerinfo document, as in:

      "revoked-signing-key" SP Base64-Ed25519-Key NL

        Note that this doesn't need to be authenticated, since the newer
        signing key certificate creates a trust path from the master
        identity key to the the revocation.

        [Up to 32 times.]

   Upon receiving these entries, authorities store up to 32 such entries
   per router per year.  (If you have more than 32 keys compromised,
   give up and take your router down. Start it with a new master key.)

   When voting, authorities include a "rev" line in the
   microdescriptor for every revoked-signing-key in the routerinfo:

      "rev" SP "ed25519" SP Base64-Ed25519-Key NL

      (This will require a new microdescriptor version.)

   Upon receiving such a line in the microdescriptor, Tor instances MUST
   NOT trust any signing key certificate with a matching key.