Filename: 353-secure-relay-identity.md
Title: Requiring secure relay identities in EXTEND2
Author: David Goulet, Steve Engler
Created: Oct 23rd, 2024
Status: Draft

Introduction

Tor relays, for a long time now, have both a RSA identity and an Ed25519 identity key. And since the creation of the EXTEND2 message, both RSA and Ed25519 keys are added to the link specifier list by our C-tor implementation.

As we move towards a RSA1024 free world, this proposal aims at declaring identity types to be considered either "secure" or "insecure" in order to define a more precise channel selection algorithm when a relay receives an EXTEND2 message.

Furthermore, our protocol does NOT enforce that all identities be present as link specifiers in an EXTEND2 message. By declaring that an identity type (ex: ed25519) is secure, we then also need to enforce at the protocol level that an EXTEND2 message MUST contain a secure identity link specifiers.

Proposal

We propose several changes to the protocol in order to achieve the use of secure identity type in circuit extension.

  1. Classification of the RSA1024 identity as "insecure" and the Ed25519 identity as "secure".
  2. Relays require at least one "secure" identity in an incoming EXTEND2 message.
  3. A new channel selection algorithm for relays using the new "secure" concept when handling EXTEND2 messages.

Secure Identity

We currently have two types of relay identity keys: RSA1024 and Ed25519. This is the EXTEND message LSTYPE 0x02 (legacy identity) and 0x03 respectively.

As RSA1024 is widely considered dangerous, we can reasonably assume that RSA signature are forgeable. Furthermore, with the advent of SHAttered paper, we can also assume that a SHA1 fingerprint is also forgeable.

Considering the above, we propose that the identities be classified as either secure or insecure, and that at least one secure identity is mandatory as a link specifier on an EXTEND2 message. Specifically, we classify RSA1024 as insecure and Ed25519 as secure. See next section for the details.

EXTEND2 Requirement Change

Considering that we now have the concept of a secure identity, we need to enforce the presence of such identity in an EXTEND2 message in order to have a precise relay identity matching algorithm defined in the next section.

This, in effect, makes it that a relay MUST deny and send back a DESTROY message with reason PROTOCOL if an EXTEND2 message is seen without any secure identity---for example, if only the RSA identity is sent by a client.

All relays already have the capability of handling one or both identities and so this change doesn't require a new sub-protocol version in order to implement.

The server descriptor format requires all relays to have an Ed25519 identity, and since tor-0.2.4.x (11 years ago), clients send both the RSA and Ed25519 identities in their EXTEND2 messages, so this requirement change will not affect existing clients.

Relay Identity Matching Algorithm

This section describes a relay identity matching algorithm which only considers the identity key link specifiers found in an EXTEND2 message.

Definitions and Notation

Before we start, some notation in this section:

RSA_x: RSA Identity [Insecure] Ed_x: Ed25519 Identity [Secure] Q_x: Quantum Identity (not real) [Secure] D_x: Decadongdong Identity (not real but oh my secure) [Secure] Secure(X): Subset of secure identities of the set X.

Each relay have a set of secure and possibly insecure identities.

By definition, we assume that no well-behaving relays exist that share a secure identity with another relay.

(Two relays could share a secure identity if the corresponding secret identity key were stolen, or if the administrator accidentally set them up with the same secret identity key. The former indicates an out-of-scope security breach; the latter is a misconfiguration.)

In other words, as an example:

  • (RSA_A, Ed_A) => Relay A
  • (RSA_B, Ed_B) => Relay B

However, we can't blindly tie (RSA_B, Ed_A) to Relay A because even if the insecure key (RSA_B) considered forgeable is different, we still want to avoid choosing a channel that was not requested for safety purposes.

In the future, Tor may need to simultaneously support additional identities, so the following algorithm is given to be abstract but heavy in examples.

Overview

Starting by setting up a scenario:

  • Let's suppose that, if a channel exists with a set of identities S1 (with at least one secure identity) and we are asked to extend a circuit to a set S2 (from an EXTEND2 message).

  • Let's also suppose also that there is some overlap between S1 and S2, so that there is a possibility that the channel might be used to handle the extend request.

  • Let's assume we have an established channel Chan1 that has authenticated with S1, the following set of identities:

    `S1 = (RSA_1, Ed_1, Q_1)`

It is important to remember that during channel authentication, the relay we are connecting to will send all its identities and so even if an EXTEND2 request only contains (RSA_1, Ed_1), the end result of the S1 set as an open authenticated channel Chan1 is that it contains all possible identities.

Notice here, S1 doesn't include D_1 but we are assuming that we support that identity type as a relay and that a client might request it. Here is the algorithm to follow when an EXTEND2 message is received:

The following algorithm only considers S2 against S1 but it should be noted that we consider every channel that has any identities in common with S2.

In other words, the following algorithm should be run for each pending and opened channel we have resulting in possibly:

  • A set of usable channels.
  • A possible new channel (S1, the request from the EXTEND2).

The set of usable channels is passed on the channel selection algorithm (out of scope for this proposal). The possible new channel is only open if the set of usable channel is empty.

Algorithm

  1. Make sure that S2 contains at least one secure identity. If not, tear down the circuit by sending a DESTROY message with reason PROTOCOL. Else, proceed to (2).

    Examples of what will evaluate to true and thus close the circuit: S2 = (RSA_1) => No secure keys

  2. If S2 ⊆ S1, then S1 is put in the usable channel set. Else proceed to (3).

    (Rationale: every identity that the client requested in S2 is an authenticated identity of the channel.)

    S2 = (Ed_1) S2 = (Ed_1, Q_1) S2 = (RSA_1, Ed_1) S2 = (RSA_1, Ed_1, Q_1) S2 = (RSA_1, Q_1)

    Examples evaluating to false and thus proceed to (3):

    S2 = (D_1) S2 = (Ed_1, D_1) S2 = (Ed_2) S2 = (RSA_1, D_1) S2 = (RSA_1, Ed_1, Q_2) S2 = (RSA_2, Ed_1) S2 = (RSA_2, Ed_1, Q_1) S2 = (RSA_2, Ed_2)

  3. Reaching this step implies:

    1. S2 has at least one secure identity
    2. S2 has an identity (secure or not) NOT in S1.

    Together, this properties mean that we can never use the channel with identities S1: The client has asked for an identity that this channel does not provide. Therefore, the only possibilities are to try to open a new channel, or to close the circuit.

    If Secure(S1) ∩ Secure(S2) != Ø then tear down the circuit by sending DESTROY message with reason PROTOCOL. Else, open a new channel to S2.

    Why does this work? Remember from the start of this section: "we assume that no well-behaving relays exist that share a secure identity with another relay". And so a secure intersection means that we are in this case and we need to close the circuit because the next relay is likely malicious if it can identify with a key of another relay:

    S2 = (Ed_1, D_1) S2 = (RSA_1, Ed_1, Q_2) S2 = (RSA_2, Ed_1)

    For an empty intersection, we open a new channel:

    S2 = (D_1) => S1 doesn't know about D_1 thus considered a new identity, new channel. S2 = (Ed_2) => Complete different secure identity, new channel. S2 = (RSA_1, D_1) => S1 doesn't know about D_1 and insecure keys are considered forgeable so this is a new channel. S2 = (RSA_2, Ed_2) => Everything is different, new channel.