Filename: 256-key-revocation.txt
Title: Key revocation for relays and authorities
Authors: Nick Mathewson
Created: 27 October 2015
Status: Reserve
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.