Rewrite the relay key descriptions.

The old key descriptions were categorized by algorithm,
and were extremely janky. These should be more accurate, unless I've
messed something up.  (Please review carefully.)

I've left the link authentication keys nearly unmodified,
since I'm planning to revise the channels description soon,
and I expect I'll come back to these.

1 files changed, 153 insertions, 51 deletions

diff --git a/spec/tor-spec/relay-keys.md b/spec/tor-spec/relay-keys.md
index 975c460..6434b78 100644
--- a/spec/tor-spec/relay-keys.md
+++ b/spec/tor-spec/relay-keys.md
@@ -2,58 +2,160 @@
 
 # Relay keys and identities
 
-Every Tor relay has multiple public/private keypairs.
-
-These are 1024-bit RSA keys:
-
-- A long-term signing-only "Identity key" used to sign documents and
-  certificates, and used to establish relay identity.
-  `KP_relayid_rsa`, `KS_relayid_rsa`.
-- A medium-term TAP "Onion key" used to decrypt onion skins when accepting
-  circuit extend attempts.  (See 5.1.)  Old keys MUST be accepted for a
-  while after they are no longer advertised.  Because of this,
-  relays MUST retain old keys for a while after they're rotated.  (See
-  "onion key lifetime parameters" in dir-spec.txt.)
-  `KP_onion_tap`, `KS_onion_tap`.
-- A short-term "Connection key" used to negotiate TLS connections.
+Every Tor relay has multiple public/private keypairs,
+with different lifetimes and purposes.
+We explain them here.
+
+Each key here has an English name
+(like "Ed25519 identity key")
+and an unambiguous identifier
+(like `KP_relayid_ed`).
+
+In an identifier,
+a `KP_` prefix denotes a public key,
+and a `KS_` prefix denotes the corresponding secret key.
+
+> For historical reasons or reasons of space,
+> you will sometimes encounter
+> multiple English names for the same key,
+> or shortened versions of that name.
+> The identifier for a key, however,
+> should always be unique and unambiguous.
+
+For security reasons, **all keys MUST be distinct**:
+the same key or keypair should never be used
+for separate roles within the Tor protocol suite,
+unless specifically stated.
+For example,
+a relay's identity key `KP_relayid_ed`
+MUST NOT also be used
+as its medium-term signing key `KP_relaysign_ed`.
+
+## Identity keys
+
+An **identity key** is a long-lived key
+that uniquely identifies a relay.
+Two relays with the same set of identity keys
+are considered to be the same;
+any relay that changes its identity key
+is considered to have become a different relay.
+
+An identity keypair's lifetime
+is the same as the lifetime of the relay.
+
+Two identity keys are currently defined:
+
+- `KP_relayid_ed`, `KS_relayid_ed`:
+   An "ed25519 identity key",
+   also sometimes called a "master identity key".
+
+   This is an Ed25519 key.
+   This key never expires.
+   It is used for only one purpose:
+   signing the `KP_relaysign_ed` key,
+   which is used to sign
+   other important keys and objects.
+
+- `KP_relayid_rsa`, `KS_relayid_rsa`.
+   A _legacy_ "RSA identity key".
+
+   This is an RSA key.
+   It never expires.
+   It is always 1024 bits long,
+   and (as discussed [above](./preliminaries.md#ciphers))
+   its exponent must be 65537.
+   It is used to sign directory documents and certificates.
+
+Note that because the legacy RSA identity key is so short,
+it should not be assumed secure against an attacker.
+It exists for legacy purposes only.
+When authenticating a relay,
+a failure to prove an expected RSA identity
+is sufficient evidence of a _failure_ to authenticate,
+but a successful proof of an RSA identity is not sufficient
+to establish a relay's identity.
+Parties SHOULD NOT use the RSA identity on its own.
+
+We write `KP_relayid` to refer to a key which is either
+`KP_relayid_rsa` or `KP_relayid_ed`.
+
+## Online signing keys
+
+Since Tor's design tries to support
+keeping the high-value Ed25519 relay identity key offline,
+we need a corresponding key that can be used for online signing:
+
+- `KP_relaysign_ed`, `KS_relaysign_ed`:
+  A medium-term Ed25519 "signing" key.
+  This key is signed by the identity key `KP_relayid_ed`,
+  and must be kept online.
+  A new one should be generated periodically.
+  It signs nearly everything else,
+  including directory objects,
+  and certificates for other keys.
+
+
+## Circuit extension keys
+
+Each relay has one or more **circuit extension keys**
+(also called "onion keys").
+When [creating](./create-created-cells.md)
+or [extending](./create-created-cells.md#EXTEND)
+a circuit,
+a client uses this key to perform
+a [one-way authenticated key exchange][cacr2021-goldberg]
+with the target relay.
+If the recipient does not have the correct private key,
+the handshake will fail.
+
+[cacr2011-goldberg]: https://cacr.uwaterloo.ca/techreports/2011/cacr2011-11.pdf
+
+Circuit extension keys have moderate lifetimes,
+on the order of weeks.
+They are published as part of the directory protocol,
+and relays SHOULD accept handshakes for a while
+after publishing any new key.
+(The exact durations for these are set via
+[a set of network parameters](../param-spec.md#onion-key-rotation-days).)
+
+There are two current kinds of circuit extension keys:
+
+- `KP_ntor`, `KS_ntor`:
+  A curve25519 key
+  used for the [`ntor`](./create-created-cells.md#ntor)
+  and [`ntorv3`](./create-created-cells.md#ntor-v3)
+  circuit extension handshakes.
+
+- `KP_onion_tap`, KS_onion_tap`:
+  A 1024 bit RSA key
+  used for the obsolete [`TAP`](./create-created-cells.md#ntor)
+  circuit extension handshake.
+
+
+## Channel authentication
+
+There are other keys that relays use to authenticate
+as part of their [./channels.md](channel negotiation handshakes).
+
+These keys are authenticated with other, longer lived keys.
+Relays MAY rotate them as often as they like,
+and SHOULD rotate them frequently—typically, at least once a day.
+
+<!-- TODO: The following should get revised after I revise the channel
+     handshake distinction. As it stands I'm not at all sure I can
+     describe them correctly. -->
+
+- `KP_conn_tls`, `KS_conn_tls`:
+  A short-term RSA "Connection key" used to negotiate TLS connections.
   Tor implementations MAY rotate this key as often as they like, and
   SHOULD rotate this key at least once a day.
   `KP_conn_tls`, `KS_conn_tls`.
 
-This is Curve25519 key:
-
-- A medium-term ntor "Onion key" used to handle onion key handshakes when
-  accepting incoming circuit extend requests.  As with TAP onion keys,
-  old ntor keys MUST be accepted for at least one week after they are no
-  longer advertised.  Because of this, relays MUST retain old keys for a
-  while after they're rotated. (See "onion key lifetime parameters" in
-  dir-spec.txt.)
-  `KP_ntor`, `KS_ntor`.
-
-These are Ed25519 keys:
-
-- A long-term "master identity" key.  This key never
-  changes; it is used only to sign the "signing" key below.  It may be
-  kept offline.
-  `KP_relayid_ed`, `KS_relayid_ed`.
-- A medium-term "signing" key.  This key is signed by the master identity
-  key, and must be kept online.  A new one should be generated
-  periodically.  It signs nearly everything else.
-  `KP_relaysign_ed`, `KS_relaysign_ed`.
-- A short-term "link authentication" key, used to authenticate
-   the link handshake: see section 4 below.  This key is signed
-   by the "signing" key, and should be regenerated frequently.
-   `KP_link_ed`, `KS_link_ed`.
-
-KP_relayid\_\* together identify a router uniquely.  Once a router
-has used a KP_relayid_ed (an Ed25519 master identity key)
-together with a given KP_relayid_rsa (RSA identity key), neither of
-those keys may ever be used with a different key.
-
-We write KP_relayid to refer to a key which is either
-KP_relayid_rsa or KP_relayid_ed.
-
-The same key or keypair should never be used for separate roles within
-the Tor protocol suite, unless specifically stated.  For example,
-a relay's identity keys K_relayid should not also be used as the
-identity keypair for a hidden service K_hs_id (see rend-spec-v3.txt).
+- `KP_link_ed`, `KS_link_ed`.
+  A short-term Ed25519 "link authentication" key, used to authenticate
+  the link handshake: see section 4 below.  This key is signed
+  by the "signing" key, and should be regenerated frequently.
+
+
+
+