Merge branch 'chan-negotiation-revision' into 'main'

Finish revising the description of channel negotiation

See merge request tpo/core/torspec!226

7 files changed, 443 insertions, 262 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/channels.md b/spec/tor-spec/channels.md
index 046181b..a649409 100644
--- a/spec/tor-spec/channels.md
+++ b/spec/tor-spec/channels.md
@@ -24,11 +24,15 @@ of one or more [**relay identities**](./relay-keys.md),
 using a [handshake](./negotiating-channels.md)
 that combines TLS facilities
 and a series of Tor messages.
-The initiator MAY prove cryptographic ownership
-of their own relay identities,
-if they have any:
+
+<span id="does-initiator-authenticate">
+As part of this handshake,
+the initiator MAY also prove cryptographic ownership
+of its own relay identities,
+if it has any:
 public relays SHOULD prove their identities when they initiate a channel,
 whereas clients and bridges SHOULD NOT do so.
+</span>
 
 Parties should usually reuse an existing channel
 rather than opening new a channel to the same relay.
diff --git a/spec/tor-spec/negotiating-channels.md b/spec/tor-spec/negotiating-channels.md
index 1ab3721..a95d4db 100644
--- a/spec/tor-spec/negotiating-channels.md
+++ b/spec/tor-spec/negotiating-channels.md
@@ -22,9 +22,11 @@ In brief:
    to establish clock skew and IP addresses.
  - The initiator checks whether the CERTS cell is correct,
    and decides whether to authenticate.
- - If the initiator does not wants to authenticate,
+ - If the initiator
+   [is not authenticating itself](./channels.md#does-initiator-authenticate),
    it sends a [NETINFO cell](#NETINFO-cells).
- - If the initiator wants to authenticate,
+ - If the initiator
+   [is authenticating itself](./channels.md#does-initiator-authenticate),
    it sends a [CERTS cell](#CERTS-cells),
    an [AUTHENTICATE cell](#AUTHENTICATE-cells),
    a [NETINFO cell](#NETINFO-cells).
@@ -47,7 +49,7 @@ sequenceDiagram
    Initiator ->> Responder: VERSIONS
    Responder ->> Initiator: VERSIONS, CERTS, AUTH_CHALLENGE, NETINFO
 
-   opt if the initiator wants to authenticate
+   opt if the initiator is authenticating
       Initiator ->> Responder: CERTS, AUTHENTICATE
    end
 
@@ -137,125 +139,147 @@ 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:
+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).
 
-| Field         | Description             | Size
-| -----         | -----------             | ----
-| N             | Number of certs in cell | 1 octet
-| N times:      |                         |
-| - CertType    |                         | 1 octet
-| - CLEN        |                         | 2 octets
-| - Certificate |                         | CLEN octets
+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 has enough information to authenticate the responder.
+To do so, the initiator MUST check that all of 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}
+
+
+An initiator's CERTS cell
+differs from a responders CERTS cell
+in that it contains a `SIGNING_V_LINK_AUTH` certificate
+instead of a `SIGNING_V_TLS_CERT` certificate.
+
+
+> First, recall that
+> [not all initiators authenticate themselves](./channels.md#does-initiator-authenticate);
+> bridges and clients do not do so.
+>
+> Second, if the initiator *does* choose to authenticate:
+> unlike the responder,
+> the initiator is not required to present a TLS certificate
+> during the TLS handshake.
+> Therefore, the initiator has
+> no meaningful `SIGNING_V_TLS_CERT` certificate.
+>
+> Therefore, 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.
+
+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.
+(A party MUST NOT conclude that an RSA identity key
+is associated with a channel
+without checking these properties.)
+
+- 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>
 
@@ -270,157 +294,166 @@ fields:
 | N_Methods | 2 octets
 | Methods   | 2 * N_Methods octets
 
-It is sent from the responder to the initiator. Initiators MUST
-ignore unexpected bytes at the end of the cell.  Responders MUST
-generate every challenge independently using a strong RNG or PRNG.
+It is sent from the responder to the initiator.
+Initiators MUST ignore unexpected bytes at the end of the cell.
+Responders MUST generate every challenge independently.
+
+The Challenge field is
+a [randomly generated](./preliminaries.md#random-values)
+binary string that the initiator must sign (a hash of)
+as part of their [AUTHENTICATE cell](#AUTHENTICATE-cells).
+
+The Methods are a list of authentication methods
+that the responder will accept.
+These methods are defined:
+
+| Type      | Method |
+| --------- | ------ |
+| `[00 01]` | [RSA-SHA256-TLSSecret] (Obsolete) |
+| `[00 02]` | (Historical, never implemented)   |
+| `[00 03]` | [Ed25519-SHA256-RFC5705]          |
 
-The Challenge field is a randomly generated string that the
-initiator must sign (a hash of) as part of authenticating.  The
-methods are the authentication methods that the responder will
-accept.  Only two authentication methods are defined right now:
-see [RSA-SHA256-TLSSecret](#RSA-SHA256-TLSSecret) and
-[Ed25519-SHA256-RFC570](#Ed25519-SHA256-RFC5705) below.
+
+[RSA-SHA256-TLSSecret]: ./obsolete-channels.md#RSA-SHA256-TLSSecret
+[Ed25519-SHA256-RFC5705]: #Ed25519-SHA256-RFC5705
 
 <a id="tor-spec.txt-4.4"></a>
 
 ## AUTHENTICATE cells{#AUTHENTICATE-cells}
 
-If an initiator wants to authenticate, it responds to the
-AUTH_CHALLENGE cell with a CERTS cell and an AUTHENTICATE cell.
-The CERTS cell is as a server would send, except that instead of
-sending a CertType 1 (and possibly CertType 5) certs for arbitrary link
-certificates, the initiator sends a CertType 3 (and possibly
-CertType 6) cert for an RSA/Ed25519 AUTHENTICATE key.
+To authenticate, an initiator MUST
+it respond to the AUTH_CHALLENGE cell
+with a CERTS cell and an AUTHENTICATE cell.
 
-This difference is because we allow any link key type on a TLS
-link, but the protocol described here will only work for specific key
-types as described in
-[RSA-SHA256-TLSSecret](#RSA-SHA256-TLSSecret) and
-[Ed25519-SHA256-RFC570](#Ed25519-SHA256-RFC5705) below.
+> Recall that initiators are
+> [not always required to authenticate](./channels.md#does-initiator-authenticate).
+>
+> ([As discussed above](#validate-initiator-certs),
+> the initiator's CERTS cell differs slightly
+> from what a responder would send.)
 
 An AUTHENTICATE cell contains the following:
 
 | Field           | Size
 | -----           | ----
-| AuthType        | 2 octets
-| AuthLen         | 2 octets
-| Authentication  | AuthLen octets
+| AuthType        | 2
+| AuthLen         | 2
+| Authentication  | AuthLen
 
 Responders MUST ignore extra bytes at the end of an AUTHENTICATE
-cell.  Recognized AuthTypes are 1 and 3, described in the next
-two sections.
-
-Initiators MUST NOT send an AUTHENTICATE cell before they have
-verified the certificates presented in the responder's CERTS
-cell, and authenticated the responder.
-
-<a id="tor-spec.txt-4.4.1"></a>
-
-### Link authentication type 1: RSA-SHA256-TLSSecret {#RSA-SHA256-TLSSecret}
-
-If AuthType is 1 (meaning "RSA-SHA256-TLSSecret"), then the
-Authentication field of the AUTHENTICATE cell contains the following:
-
-* TYPE: The characters "AUTH0001" \[8 octets\]
-* CID: A SHA256 hash of the initiator's RSA1024 identity key \[32 octets\]
-* SID: A SHA256 hash of the responder's RSA1024 identity key \[32 octets\]
-* SLOG: A SHA256 hash of all bytes sent from the responder to the
-    initiator as part of the negotiation up to and including the
-    AUTH_CHALLENGE cell; that is, the VERSIONS cell, the CERTS cell,
-    the AUTH_CHALLENGE cell, and any padding cells.  \[32 octets\]
-* CLOG: A SHA256 hash of all bytes sent from the initiator to the
-    responder as part of the negotiation so far; that is, the
-    VERSIONS cell and the CERTS cell and any padding cells. \[32
-    octets\]
-* SCERT: A SHA256 hash of the responder's TLS link certificate. \[32
-    octets\]
-* TLSSECRETS: A SHA256 HMAC, using the TLS master secret as the
-    secret key, of the following:
-      - client_random, as sent in the TLS Client Hello
-      - server_random, as sent in the TLS Server Hello
-      - the NUL terminated ASCII string:
-        "Tor V3 handshake TLS cross-certification"
-     \[32 octets\]
-* RAND: A 24 byte value, randomly chosen by the initiator.  (In an
-    imitation of SSL3's gmt_unix_time field, older versions of Tor
-    sent an 8-byte timestamp as the first 8 bytes of this field;
-    new implementations should not do that.) \[24 octets\]
-* SIG: A signature of a SHA256 hash of all the previous fields
-    using the initiator's "Authenticate" key as presented.  (As
-    always in Tor, we use OAEP-MGF1 padding; see [Ciphers](./preliminaries.md#ciphers))
-     \[variable length\]
-
-To check the AUTHENTICATE cell, a responder checks that all fields
-from TYPE through TLSSECRETS contain their unique
-correct values as described above, and then verifies the signature.
-The server MUST ignore any extra bytes in the signed data after
-the RAND field.
+cell.
 
-Responders MUST NOT accept this AuthType if the initiator has
-claimed to have an Ed25519 identity.
+The `AuthType` value corresponds to one of the
+authentication methods.
+The initiator MUST NOT send an AUTHENTICATE cell
+whose AuthType was not contained
+in the responder's AUTH_CHALLENGE.
 
-(There is no AuthType 2: It was reserved but never implemented.)
+An initiator MUST NOT send an AUTHENTICATE
+cell before it has verified the certificates
+presented in the responder's CERTS cell,
+and authenticated the responder.
 
 <a id="tor-spec.txt-4.4.2"></a>
 
 ### Link authentication type 3: Ed25519-SHA256-RFC5705 {#Ed25519-SHA256-RFC5705}
 
-If AuthType is 3, meaning "Ed25519-SHA256-RFC5705", the
-Authentication field of the AuthType cell is as below:
+If AuthType is `[00 03]`,
+meaning "Ed25519-SHA256-RFC5705",
+the Authentication field of the AUTHENTICATE cell is as follows
 
 Modified values and new fields below are marked with asterisks.
 
-* TYPE: The characters "AUTH0003" \[8 octets\]
-* CID: A SHA256 hash of the initiator's RSA1024 identity key \[32 octets\]
-* SID: A SHA256 hash of the responder's RSA1024 identity key \[32 octets\]
-* CID_ED: The initiator's Ed25519 identity key \[32 octets\]
-* SID_ED: The responder's Ed25519 identity key, or all-zero. \[32 octets\]
-* SLOG: A SHA256 hash of all bytes sent from the responder to the
-    initiator as part of the negotiation up to and including the
-    AUTH_CHALLENGE cell; that is, the VERSIONS cell, the CERTS cell,
-    the AUTH_CHALLENGE cell, and any padding cells.  \[32 octets\]
-* CLOG: A SHA256 hash of all bytes sent from the initiator to the
-    responder as part of the negotiation so far; that is, the
-    VERSIONS cell and the CERTS cell and any padding cells. \[32
-    octets\]
-* SCERT: A SHA256 hash of the responder's TLS link certificate. \[32
-    octets\]
-* TLSSECRETS: The output of an RFC5705 Exporter function on the
-    TLS session, using as its inputs:
-     - The label string "EXPORTER FOR TOR TLS CLIENT BINDING AUTH0003"
-     - The context value equal to the initiator's Ed25519 identity key.
-     - The length 32.
-       \[32 octets\]
-* RAND: A 24 byte value, randomly chosen by the initiator. \[24 octets\]
-* SIG: A signature of all previous fields using the initiator's
-     Ed25519 authentication key (as in the cert with CertType 6).
-     \[variable length\]
-
-To check the AUTHENTICATE cell, a responder checks that all fields
-from TYPE through TLSSECRETS contain their unique
-correct values as described above, and then verifies the signature.
-The server MUST ignore any extra bytes in the signed data after
+| Field      | Size | Summary |
+| ---------  | ---- | ----------- |
+| `TYPE`     | 8    | The nonterminated string `AUTH0003` |
+| `CID`      | 32   | `SHA256(KP_relayid_rsa)` for initiator |
+| `SID`      | 32   | `SHA256(KP_relayid_rsa)` for responder |
+| `CID_ED`   | 32   | `KP_relayid_ed` for initiator |
+| `SID_ED`   | 32   | `KP_relayid_ed` for responder |
+| `SLOG`     | 32   | Responder log digest, SHA256 |
+| `CLOG`     | 32   | Initiator log digest, SHA256 |
+| `SCERT`    | 32   | SHA256 of responder's TLS certificate |
+| `TLSSECRETS`|32   | RFC5705 information |
+| `RAND`     | 24   | [Random bytes] |
+| `SIG`      | 64   | Ed25519 signature |
+
+
+- The `TYPE` string distinguishes this authentication document from others.
+  It must be the nonterminated 8-byte string `AUTH0003`.
+- For `CID` and `SID`, the SHA256 digest of an RSA key
+  is computed as the SHA256 digest of its asn.1 encoding.
+- The `SLOG`  field is computed
+  as the SHA256 digest
+  of all bytes sent within the TLS channel up to and including
+  the AUTH_CHALLENGE cell.
+  - This includes the VERSIONS cell,
+    the CERTS cell,
+    the AUTH_CHALLENGE cell,
+    and any padding cells.
+- The `CLOG` field is computed
+  as the SHA256 digest
+  of all bytes sent within the TLS channel up to but not including
+  the AUTHENTICATE cell.
+  - This includes the VERSIONS cell,
+    the CERTS cell, and any padding cells.
+- The `SCERT` field holds the SHA256 digest
+  of the X.509 certificate presented by the responder
+  as part of the TLS negotiation.
+- The `TLSSECRETS` field is computed
+  as the output of a Keying Material Exporter function
+  on the TLS section.
+  - The parameters for this exporter are:
+    - Label string: "EXPORTER FOR TOR TLS CLIENT BINDING AUTH0003"
+    - Context value: The initiator's `KP_relayid_ed`.
+    - Length: 32.
+  - For keying material exporters on TLS 1.3,
+    see [RFC 8446 Section 7.5].
+  - For keying material exporters on older TLS versions,
+    see [RFC5705].
+- The `RAND` field is a uniform squence of [Random bytes].
+- The `SIG` field is an Ed25519 signature
+  of all earlier members in the Authentication
+  (from `TYPE` through `RAND`)
+  using `KS_link_ed`.
+
+
+[Random bytes]: ./preliminaries.md#random-values
+[RFC 8446 Section 7.5]: https://datatracker.ietf.org/doc/html/rfc8446#section-7.5
+[RFC5705]: https://datatracker.ietf.org/doc/html/rfc5705.
+
+
+To check an AUTHENTICATE cell,
+a responder checks that all fields from TYPE through TLSSECRETS
+contain their unique correct values as described above,
+and then verifies the signature.
+The responder MUST ignore any extra bytes in the signed data after
 the RAND field.
 
+<!-- TODO: We should consider removing that last sentence. -->
+
 <a id="tor-spec.txt-4.5"></a>
 
 ## NETINFO cells {#NETINFO-cells}
 
-If version 2 or higher is negotiated, each party sends the other a
-NETINFO cell.  The cell's payload is:
+To finish the handshake,
+each party sends the other
+a NETINFO cell.
+
+The cell's payload is:
 
 | Field            | Description                   | Size
 | -----            | -----------                   | ----
 | TIME             | Timestamp                     | 4 bytes
-| OTHERADDR:       | Other OR's address            |
+| OTHERADDR:       | Other party's address         |
 | - ATYPE          | Address type                  | 1 byte
 | - ALEN           | Address length                | 1 byte
-| - AVAL           | Address value in NBO          | ALEN bytes
-| NMYADDR          | Number of this OR's addresses | 1 byte
+| - AVAL           | Address value                 | ALEN bytes
+| NMYADDR          | Number of this party's addresses | 1 byte
 | NMYADDR times:   |                               |
 | - ATYPE          | Address type                  | 1 byte
 | - ALEN           | Address length                | 1 byte
-| - AVAL           | Address value in NBO          | ALEN bytes
+| - AVAL           | Address value                 | ALEN bytes
 
 Recognized address types (ATYPE) are:
 
@@ -429,23 +462,54 @@ Recognized address types (ATYPE) are:
 | 0x04  | IPv4
 | 0x06  | IPv6
 
-ALEN MUST be 4 when ATYPE is 0x04 (IPv4) and 16 when ATYPE is 0x06
-(IPv6).  If the ALEN value is wrong for the given ATYPE value, then
+Implementations SHOULD ignore addresses with unrecognized types.
+
+ALEN MUST be 4 when ATYPE is 0x04 (IPv4)
+and 16 when ATYPE is 0x06 (IPv6).
+If the ALEN value is wrong for the given ATYPE value, then
 the provided address should be ignored.
 
-The timestamp is a big-endian unsigned integer number of seconds
-since the Unix epoch. Implementations MUST ignore unexpected bytes
-at the end of the cell.  Clients SHOULD send "0" as their timestamp, to
-avoid fingerprinting.
+The `OTHERADDR` field SHOULD be set to the actual IP address
+observed for the other party.
+
+> (This is typically the address passed to `connect()`
+> when acting as the channel initiator,
+> or the address received from `accept()`
+> when acting as the channel responder.)
+
+In the `ATYPE`/`ALEN`/`AVAL` fields,
+relays SHOULD send the addresses that they have advertised
+in their router descriptors.
+Bridges and clients SHOULD send none of their own addresses.
+
+For the `TIME` field,
+relays send a (big-endian) integer
+holding the number of seconds since the Unix epoch.
+Clients SHOULD send `[00 00 00 00]` as their timestamp,
+to avoid fingerprinting.
+
+> See [proposal 338](../proposals/338-netinfo-y2038.md)
+> for a proposal to extend the timestamp to 8 bytes.
+
+Implementations MUST ignore unexpected bytes at the end of the NETINFO cell.
+
+### Using information from NETINFO cells {#using-netinfo}
 
 Implementations MAY use the timestamp value to help decide if their
-clocks are skewed.  Initiators MAY use "other OR's address" to help
-learn which address their connections may be originating from, if they do
-not know it; and to learn whether the peer will treat the current
-connection as canonical.  Implementations SHOULD NOT trust these
-values unconditionally, especially when they come from non-authorities,
-since the other party can lie about the time or IP addresses it sees.
+clocks are skewed.
 
-Initiators SHOULD use "this OR's address" to make sure
-that they have connected to another OR at its canonical address.
+Initiators MAY use "other OR's address" field
+to help learn which address their connections may be originating from,
+if they do not know it;
+and to learn whether the peer will treat the current connection as
+canonical.
 (See [Canonical connections](./creating-circuits.md#canonical-connections))
+
+Implementations SHOULD NOT trust these values unconditionally,
+especially when they come from non-authorities,
+since the other party can lie about the time
+or the IP addresses it sees.
+
+Initiators SHOULD use "this OR's address" to make sure
+that they have connected to another OR at its
+[canonical address](./creating-circuits.md#canonical-connections).
diff --git a/spec/tor-spec/obsolete-channels.md b/spec/tor-spec/obsolete-channels.md
index 5f3c053..52e716f 100644
--- a/spec/tor-spec/obsolete-channels.md
+++ b/spec/tor-spec/obsolete-channels.md
@@ -166,3 +166,104 @@ 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.
+
+
+<a id="tor-spec.txt-4.4.1"></a>
+
+## Link authentication type 1: RSA-SHA256-TLSSecret {#RSA-SHA256-TLSSecret}
+
+This is an obsolete authentication method
+used before RFC5705 support was ubiquitous.
+It is nearly the same as
+[Ed25519-SHA256-RFC5705](./negotiating-channels.md#Ed25519-SHA256-RFC5705),
+but lacks support for Ed25519,
+and does not use keying material exporters
+(which were not widely supported at the time it as used.
+
+If AuthType is `[00 01]` (meaning "RSA-SHA256-TLSSecret"),
+then the authentication field of the AUTHENTICATE
+cell contains the following:
+
+| Field      | Size | Description |
+| ---------  | ---- | ----------- |
+| `TYPE`     | 8    | The nonterminated string `AUTH0001` |
+| `CID`      | 32   | `SHA256(KP_relayid_rsa)` for initiator |
+| `SID`      | 32   | `SHA256(KP_relayid_rsa)` for responder |
+| `SLOG`     | 32   | SHA256 of responder transcript |
+| `CLOG`     | 32   | SHA256 of initiator transcript |
+| `SCERT`    | 32   | SHA256 of responder's TLS certificate |
+| `TLSSECRETS`|32   | An ad-hoc HMAC output |
+| `RAND`     | 24   | [Random bytes] |
+| `SIG`      | Variable | RSA signature |
+
+
+Notes are as for [Ed25519-SHA256-RFC5705],
+except as follows:
+
+
+- The `TLSSECRETS` fields holds a SHA256 HMAC,
+  using the TLS master secret as the secret key,
+  of the following concatenated fields:
+    - `client_random`, as sent in the TLS Client Hello
+    - `server_random`, as sent in the TLS Server Hello
+    - the NUL terminated ASCII string:
+        `"Tor V3 handshake TLS cross-certification"`
+* The `SIG` fields holds an RSA signature of a SHA256 hash
+  of all the previous fields
+  (that is, `TYPE` through `RAND`),
+  using the initiator's `KS_legacy_linkauth_rsa`.
+  This field extends through the end of the Authenticate message.
+
+[Random bytes]: ./preliminaries.md#random-values
+[Ed25519-SHA256-RFC5705]: ./negotiating-channels.md#Ed25519-SHA256-RFC5705
+
+Responders MUST NOT accept this AuthType if the initiator has
+claimed to have an Ed25519 identity.
+
diff --git a/spec/tor-spec/preliminaries.md b/spec/tor-spec/preliminaries.md
index 78e6e80..e69d47e 100644
--- a/spec/tor-spec/preliminaries.md
+++ b/spec/tor-spec/preliminaries.md
@@ -107,9 +107,13 @@ When we refer to "the hash of a public key", unless otherwise
 specified, we mean the SHA-1 hash of the DER encoding of an ASN.1 RSA
 public key (as specified in PKCS.1).
 
+<span id="random-values">
 All "random" values MUST be generated with a cryptographically
 strong pseudorandom number generator seeded from a strong entropy
 source, unless otherwise noted.
+All "random" values MUST selected uniformly at random from the
+universe of possible values, unless otherwise noted.
+</span>
 
 <a id="tor-spec.txt-0.4"></a>
 
diff --git a/spec/tor-spec/relay-keys.md b/spec/tor-spec/relay-keys.md
index 6086819..25ac3ed 100644
--- a/spec/tor-spec/relay-keys.md
+++ b/spec/tor-spec/relay-keys.md
@@ -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,21 +146,30 @@ 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
   ["Negotiating and initializing channels"](./negotiating-channels.md#negotiating).
   This key is signed by the "signing" key, and should be regenerated frequently.
 
+### Legacy channel authentication {#auth-legacy}
 
+These key types were used in
+[older versions](./obsolete-channels.md)
+of the channel negotiation handshakes.
 
+- <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.
diff --git a/spec/tor-spec/subprotocol-versioning.md b/spec/tor-spec/subprotocol-versioning.md
index 3e4cae3..b8ce11d 100644
--- a/spec/tor-spec/subprotocol-versioning.md
+++ b/spec/tor-spec/subprotocol-versioning.md
@@ -83,7 +83,7 @@ the v3+ link protocols.
 
 Current versions are:
 
- * "1" is the RSA link authentication described in [Link authentication type 1: RSA-SHA256-TLSSecret](./negotiating-channels.md#RSA-SHA256-TLSSecret).
+ * "1" is the RSA link authentication described in [Link authentication type 1: RSA-SHA256-TLSSecret](./obsolete-channels.md#RSA-SHA256-TLSSecret).
 
  * "2" is unused, and reserved by [proposal 244].