Revise description of CERTS cells.

Instead of a bunch of unsorted properties,
I'm trying to make it more clear why each property is checked.

I'm also trying to remove duplication, and move obsolete piles of
checks into the "obsolete-channels.md" section.

4 files changed, 191 insertions, 131 deletions

diff --git a/spec/cert-spec.md b/spec/cert-spec.md
index ed827cd..873c258 100644
--- a/spec/cert-spec.md
+++ b/spec/cert-spec.md
@@ -168,7 +168,7 @@ during channel negotiation.
 |------| -------------    | ------ | ----------------------- | ------------        | --------- | ----- |
 |`[01]`| `TLS_LINK_X509`  | [X.509]| [`KP_legacy_conn_tls`]  | [`KS_relayid_rsa`]  | [Legacy channel negotiation] | Obsolete |
 |`[02]`| `RSA_ID_X509`    | [X.509]| [`KP_relayid_rsa`]      | [`KS_relayid_rsa`]  | [Legacy channel negotiation] | Obsolete |
-|`[03]`| `LINK_AUTH_X509` | [X.509]| ? | ?                                         | [Legacy channel negotiation] | Obsolete |
+|`[03]`| `LINK_AUTH_X509` | [X.509]| [`KP_legacy_linkauth_rsa`]|[`KS_relayid_rsa`]    | [Legacy channel negotiation] | Obsolete |
 |`[04]`| `IDENTITY_V_SIGNING` |[Ed]| [`KP_relaysign_ed`]     | [`KS_relayid_ed`]   | [Online signing keys] | |
 |`[05]`| `SIGNING_V_TLS_CERT` |[Ed]| A TLS certificate       | [`KS_relaysign_ed`] | [CERTS cells] | |
 |`[06]`| `SIGNING_V_LINK_AUTH`|[Ed]| [`KP_link_ed`]          | [`KS_relaysign_ed`] | [CERTS cells] | |
@@ -178,13 +178,11 @@ during channel negotiation.
 |`[0A]`| `NTOR_CC_IDENTITY`   |[Ed]| [`KP_relayid_ed`]       | [`EdCvt`]`(`[`KS_ntor`]`)` | [ntor cross-cert] | |
 |`[0B]`| `HS_IP_CC_SIGNING`   |[Ed]| [`KP_hss_ntor`]         | [`KS_hs_desc_sign`]  | [HsDesc (`enc-key-cert`)] | Backwards, see [note 1](#note-1) |
 
-
-<!-- TODO: Figure out what [03] was for! -->
-
 [X.509]: #x509
 [Rsa]: #rsa-cross-cert
 [Ed]: #ed-certs
 [`KP_legacy_conn_tls`]: ./tor-spec/relay-keys.md#legacy_conn_tls
+[`KP_legacy_linkauth_rsa`]: ./tor-spec/relay-keys.md#legacy_linkauth_rsa
 [`KP_relayid_rsa`]: ./tor-spec/relay-keys.md#relayid_rsa
 [`KP_relaysign_ed`]:  ./tor-spec/relay-keys.md#relaysign_ed
 [`KP_relayid_ed`]:  ./tor-spec/relay-keys.md#relayid_ed
@@ -221,6 +219,7 @@ are given in the table.
 They were originally meant to be the inverse of this order.
 </span>
 
+
 <a id="cert-spec.txt-A.2"></a>
 
 ## List of extension types { #list-ext-types }
diff --git a/spec/tor-spec/negotiating-channels.md b/spec/tor-spec/negotiating-channels.md
index 1ab3721..cf559a4 100644
--- a/spec/tor-spec/negotiating-channels.md
+++ b/spec/tor-spec/negotiating-channels.md
@@ -137,125 +137,134 @@ The currently specified [Link](./subprotocol-versioning.md#link) protocols are:
 
 ## CERTS cells {#CERTS-cells}
 
-The CERTS cell describes the keys that a Tor instance is claiming
-to have.  It is a variable-length cell.  Its payload format is:
-
-| Field         | Description             | Size
-| -----         | -----------             | ----
-| N             | Number of certs in cell | 1 octet
-| N times:      |                         |
-| - CertType    |                         | 1 octet
-| - CLEN        |                         | 2 octets
-| - Certificate |                         | CLEN octets
+The CERTS cell describes the keys
+that a Tor instance is claiming to have,
+and provides certificates to authenticate that those keys
+belong, ultimately, to one or more
+[identity keys](./relay-keys.md#identity).
+
+CERTS is a variable-length cell.  Its payload format is:
+
+| Field         | Size | Description                    |
+| -----         | ---- | ------------------------------ |
+| N             | 1    | Number of certificates in cell |
+| N times:      |      |                                |
+| - CertType    | 1    | Type of certificate            |
+| - CertLen     | 2    | Length of "Certificate" field  |
+| - Certificate | CertLen | Encoded certificate         |
 
 Any extra octets at the end of a CERTS cell MUST be ignored.
 
-Relevant certType values are:
-
-| certType | Description
-| -------- | -----------
-| 1        | Link key certificate certified by RSA1024 identity
-| 2        | RSA1024 Identity certificate, self-signed.
-| 3        | RSA1024 AUTHENTICATE cell link certificate, signed with RSA1024 key.
-| 4        | Ed25519 signing key, signed with identity key.
-| 5        | TLS link certificate, signed with ed25519 signing key.
-| 6        | Ed25519 AUTHENTICATE cell key, signed with ed25519 signing key.
-| 7        | Ed25519 identity, signed with RSA identity.
-
-The certificate format for certificate types 1-3 is DER encoded X509.
-For others, the format is as documented in [a later section](../cert-spec.md)
-
-Note that type 7 uses a different format from types 4-6.
-
-A CERTS cell may have no more than one certificate of each CertType.
-
-To authenticate the responder as having a given Ed25519,RSA identity key
-combination, the initiator MUST check the following.
-
-* The CERTS cell contains exactly one CertType 2 "ID" certificate.
-* The CERTS cell contains exactly one CertType 4 Ed25519
- "Id->Signing" cert.
-* The CERTS cell contains exactly one CertType 5 Ed25519
- "Signing->link" certificate.
-* The CERTS cell contains exactly one CertType 7 "RSA->Ed25519"
- cross-certificate.
-* All X.509 certificates above have validAfter and validUntil dates;
- no X.509 or Ed25519 certificates are expired.
-* All certificates are correctly signed.
-* The certified key in the Signing->Link certificate matches the
- SHA256 digest of the certificate that was used to
- authenticate the TLS connection.
-* The identity key listed in the ID->Signing cert was used to
- sign the ID->Signing Cert.
-* The Signing->Link cert was signed with the Signing key listed
- in the ID->Signing cert.
-* The RSA->Ed25519 cross-certificate certifies the Ed25519
- identity, and is signed with the RSA identity listed in the
- "ID" certificate.
-* The certified key in the ID certificate is a 1024-bit RSA key.
-* The RSA ID certificate is correctly self-signed.
-
-To authenticate the responder as having a given RSA identity only,
-the initiator MUST check the following:
-
-* The CERTS cell contains exactly one CertType 1 "Link" certificate.
-* The CERTS cell contains exactly one CertType 2 "ID" certificate.
-* Both certificates have validAfter and validUntil dates that
- are not expired.
-* The certified key in the Link certificate matches the
- link key that was used to negotiate the TLS connection.
-* The certified key in the ID certificate is a 1024-bit RSA key.
-* The certified key in the ID certificate was used to sign both
- certificates.
-* The link certificate is correctly signed with the key in the
- ID certificate
-* The ID certificate is correctly self-signed.
-
-In both cases above, checking these conditions is sufficient to
-authenticate that the initiator is talking to the Tor node with the
-expected identity, as certified in the ID certificate(s).
-
-To authenticate the initiator as having a given Ed25519,RSA
-identity key combination, the responder MUST check the following:
-
-* The CERTS cell contains exactly one CertType 2 "ID" certificate.
-* The CERTS cell contains exactly one CertType 4 Ed25519
- "Id->Signing" certificate.
-* The CERTS cell contains exactly one CertType 6 Ed25519
- "Signing->auth" certificate.
-* The CERTS cell contains exactly one CertType 7 "RSA->Ed25519"
- cross-certificate.
-* All X.509 certificates above have validAfter and validUntil dates;
- no X.509 or Ed25519 certificates are expired.
-* All certificates are correctly signed.
-* The identity key listed in the ID->Signing cert was used to
- sign the ID->Signing Cert.
-* The Signing->AUTH cert was signed with the Signing key listed
- in the ID->Signing cert.
-* The RSA->Ed25519 cross-certificate certifies the Ed25519
- identity, and is signed with the RSA identity listed in the
- "ID" certificate.
-* The certified key in the ID certificate is a 1024-bit RSA key.
-* The RSA ID certificate is correctly self-signed.
-
-To authenticate the initiator as having an RSA identity key only,
-the responder MUST check the following:
-
-* The CERTS cell contains exactly one CertType 3 "AUTH" certificate.
-* The CERTS cell contains exactly one CertType 2 "ID" certificate.
-* Both certificates have validAfter and validUntil dates that
- are not expired.
-* The certified key in the AUTH certificate is a 1024-bit RSA key.
-* The certified key in the ID certificate is a 1024-bit RSA key.
-* The certified key in the ID certificate was used to sign both
- certificates.
-* The auth certificate is correctly signed with the key in the
- ID certificate.
-* The ID certificate is correctly self-signed.
-
-Checking these conditions is NOT sufficient to authenticate that the
-initiator has the ID it claims; to do so, [AUTH_CHALLENGE](#AUTH-CHALLENGE-cells)
-and [AUTHENTICATE](#AUTHENTICATE-cells) cells (described next) must be exchanged.
+The CertType field determines
+the format of the certificate,
+and the roles of its keys within the Tor protcol.
+Recognized values are defined in
+["Certificate types (CERT_TYPE field)"](../cert-spec.md#list-cert-types).
+
+A CERTS cell MUST have no more than one certificate of any CertType.
+
+### Authenticating the responder from its CERTS {#auth-responder}
+
+The responder's CERTS cell is meant to prove
+that the responder posses one or more
+[relay identities](./relay-keys.md#identity).
+It does this by containing certificate chains
+from each relay identity key
+to the TLS certificate presented during the TLS handshake.
+
+> The responder's ownership of that TLS certificate
+> was already proven during the TLS hadnshake itself.
+
+From a CERTS cell,
+an initiator can authenticate the responder
+when all the following apply:
+
+- The CERTS cell contains exactly one CertType 4 Ed25519
+  `IDENTITY_V_SIGNING_CERT`.
+  - This cert must be self-signed;
+    the signing key must be included in a
+    ["signed-with-ed25519-key" extension](../cert-spec.md#signed-with-ed25519)
+    extension.
+    This signing key is `KP_relayid_ed`.
+    The subject key is `KP_relaysign_ed`.
+- The CERTS cell contains exactly one CertType 5 Ed25519
+  `SIGNING_V_TLS_CERT` certificate.
+  - This cert must be signed with `KP_relaysign_ed`.
+    Its subject must be the SHA-256 digest
+    of the TLS certificate
+    that was presented curing the TLS handshake.
+- All of the certs above must be correctly signed, and not expired.
+
+It the above tests all pass,
+the initiator knows that the responder
+has the identity `KP_relayid_ed`.
+
+
+### Validating an initiator's CERTS {#validate-initiator-certs}
+
+Unlike the responder,
+the initiator was not required to present a TLS certificate
+during the TLS handshake.
+Therefore, the initiator has
+no meaningful `SIGNING_V_TLS_CERT` certificate.
+
+Instead, the initiator's CERTS cell
+proves a chain from the initiator's relay identities
+to a "link authentication" key.
+This key is later used to sign an "authentication challenge",
+and bind it to the channel.
+
+Therefore, to process an initiator's CERTS cell,
+the responder must procede as for a responder's certificates,
+[as described above](#auth-responder),
+except that **instead** of checking for a `SIGNING_V_TLS_CERT`,
+it must verify that:
+
+- The CERTS cell contains exactly one CertType 6
+  `SIGNING_V_LINK_AUTH` certificate.
+  - This certificate must be signed with `KP_relayid_ed`.
+    (Its subject key is deemed to be `KP_link_ed`.)
+- All of the certs above must be correctly signed, and not expired.
+
+This is _not_ yet sufficent to authenticate the channel.
+It only proves that
+_if_ the initiator can send a valid
+[AUTHENTICATE cell](#AUTHENTICATE-cells),
+then the initiator has the presented `KP_relayid_ed`.
+
+
+### Authenticating an RSA identity (#auth-RSA)
+
+After processing a CERTS cell
+to find the other party's
+`KP_relayid_ed` Ed25519 identity key,
+a Tor instance MAY *additionally* check the CERTS cell
+to find the other party's
+`KP_relayid_rsa` legacy RSA identity key.
+
+A party with a given `KP_relayid_ed` identity key
+also has a given `KP_relayid_rsa` legacy identity key
+when all of the following are true.
+
+- The CERTS cell contains exactly one CertType 2
+  `RSA_ID_X509` certificate.
+  - This must be a self-signed certificate containing a 1024-bit RSA key;
+    that key's exponent must be 65537.
+    That key is `KP_relayid_rsa`.
+- The CERTS cell contains exactly one CertType 7
+  `RSA_ID_V_IDENTITY` certificate.
+  - This certificate must be signed with `KP_relayid_rsa`.
+  - This certificate's subject key must be the same
+    as an already-authenticated `KP_relayid_ed`.
+- All of the certs above must be correctly signed,
+  not expired,
+  and not before their `validAfter` dates.
+
+If the above tests all pass,
+then any relay which can prove it has the the identity `KP_relayid_ed`
+also has the legacy identity `KP_relayid_rsa`.
+
+
 
 <a id="tor-spec.txt-4.3"></a>
 
diff --git a/spec/tor-spec/obsolete-channels.md b/spec/tor-spec/obsolete-channels.md
index 5f3c053..33874d4 100644
--- a/spec/tor-spec/obsolete-channels.md
+++ b/spec/tor-spec/obsolete-channels.md
@@ -166,3 +166,51 @@ TLS_DHE_RSA_WITH_AES_256_CBC_SHA, TLS_DHE_RSA_WITH_AES_128_CBC_SHA,
 and SSL_DHE_RSA_WITH_3DES_EDE_CBC_SHA.
 
 Clients no longer report ciphers that they do not support.
+
+
+## Legacy CERTS authentication: Responder has RSA Identity only {#certs-responder-legacy}
+
+A Tor relay that has only an RSA identity key (`KP_relayid_rsa`)
+and not an Ed25519 identity key (`KP_relayid_ed`)
+will present a different set of certificates in its CERTS cell.
+
+(Relays like this are no longer supported;
+all relays must now have Ed25519 identities.)
+
+To authenticate a responder as having only an RSA identity,
+the initiator would verify the following:
+
+- The CERTS cell contains exactly one CertType 2 `RSA_ID_X509` certificate.
+  - This must be a self-signed certificate containing a 1024-bit RSA key;
+    that key's exponent must be 65537.
+    That key is `KP_relayid_rsa`.
+- The CERTS cell contains exactly one CertType 1 `TLS_LINK_X509` certificate.
+  - It must be signed with `KP_relayid_rsa`.
+  - Its subject key must be the same
+    as `KP_legacy_conn_tls`
+    (the key used to negotiate the TLS connection).
+- All of the certs above must be correctly signed,
+  not expired,
+  and not before their `validAfter` dates.
+
+### Legacy CERTS authentication: Initiator has RSA Identity only {#certs-initiator-legacy}
+
+
+As discussed in
+["Validating an initiator's CERTS"](./negotiating-channels.md#validate-initiator-certs),
+the initiator of the v3 handshake does not present a TLS certificate.
+
+Therefore, to process an initiator's CERTS cell,
+the responder would have to  procede as for a responder's certificates,
+[as described above](#certs-responder-legacy),
+except that **instead** of checking for a `TLS_LINK_X509` certificate,
+it would need to verify that:
+
+- The CERTS cell contains exactly one CertType 3
+  `LINK_AUTH_X509` certificate.
+  - This certificate must be signed with `KP_relayid_rsa`.
+    Its subject key is deemed to be `KP_legacy_linkauth_rsa`.
+- All of the certs above must be correctly signed,
+  not expired,
+  and not before their `validAfter` dates.
+
diff --git a/spec/tor-spec/relay-keys.md b/spec/tor-spec/relay-keys.md
index 6086819..aa8f4ec 100644
--- a/spec/tor-spec/relay-keys.md
+++ b/spec/tor-spec/relay-keys.md
@@ -18,7 +18,7 @@ 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.
+2> or shortened versions of that name.
 > The identifier for a key, however,
 > should always be unique and unambiguous.
 
@@ -31,7 +31,7 @@ a relay's identity key `KP_relayid_ed`
 MUST NOT also be used
 as its medium-term signing key `KP_relaysign_ed`.
 
-## Identity keys
+## Identity keys {#identity}
 
 An **identity key** is a long-lived key
 that uniquely identifies a relay.
@@ -146,15 +146,6 @@ 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. -->
-
-- <span id="legacy_conn_tls">`KP_legacy_conn_tls`, `KS_legacy_conn_tls`</span>:
-  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.
-
 - <span id="link_ed">`KP_link_ed`, `KS_link_ed`</span>.
   A short-term Ed25519 "link authentication" key, used to authenticate
   the link handshake: see
@@ -162,5 +153,18 @@ and SHOULD rotate them frequently—typically, at least once a day.
   This key is signed by the "signing" key, and should be regenerated frequently.
 
 
+- <span id="legacy_linkauth_rsa">`KP_legacy_linkauth_rsa`, `KS_legacy_linkauth_rsa`</span>:
+  A 1024-bit RSA key, used to authenticate the link handshake.
+  (No longer used in modern Tor.)
+  It played a role similar to `KP_link_ed`.
 
 
+As a convenience, to describe legacy versions of the link handshake,
+we give a name to the public key used for the TLS handshake itself:
+
+- <span id="legacy_conn_tls">`KP_legacy_conn_tls`, `KS_legacy_conn_tls`</span>:
+  A short term key used to for TLS connections.
+  (No longer used in modern Tor.)
+  This was another name for the server's TLS key,
+  which at the time was required to be an RSA key.
+  It was used in some legacy handshake versions.