# Post-Quantum Migration of the Tor Application
## 2 Literature Review
### Tor Design and Architecture
#### 2.1.1 Circuits and Handshake  
Circuit creation relies on the directory authorities in the very first step of the process when a given client (OP) chooses the first relay. As it needs a list of reliable relays, it will fetch the consensus document from the directory authorities, providing necessary data on the relays, such as their public keys, roles, supported protocols, and bandwidth [10]. Figure 1 below shows a high-level view of the circuit creation process. A circuit is typically composed of four channels: OP to R1, R1 to R2, R2 to exit node (RN), and RN to destination. After a circuit is established, the OP securely shares a unique symmetric key with each relay in the circuit. Additionally, each R exchanges a distinct circuit identifier with the nodes adjacent to it within the circuit, facilitating secure and efficient communication between nodes without revealing the entire path. A channel is defined as an encrypted link established directly between two relays or between a client and a relay, implemented as TLS sessions over TCP. Tor relies on several cell types: cells, shown in Figure 1, are responsible for circuit creation. During channel negotiation, CERTS cells are used to describe the keys that a Tor instance is claiming to have. It also provides certificates to authenticate that those keys belong to long-term key(s) that uniquely identify a relay. In standard TLS, the authentication is usually only necessary on the server side as the client identity is not important; this also applies to the first connection of a Tor circuit. Yet, the three other channel establishments need mutual authentication as the nodes must prove the genuineness of their affiliation in the circuit [11]. Figure 1: Tor circuit creation. The /2 represents the version, as their older specifications have become obsolete [10]. NTOR, the key exchange protocol currently used by Tor, introduced significant improvements over the TAP protocol [12]. It reduces the computational overhead by employing ECC, offering faster key exchange and smaller data transmissions. Also, NTOR strengthens FS, preventing decryption, even if long-term keys are compromised. The paper reflects on the challenge of One-Way Authenticated Key Exchange (1W-AKE) and how it applies to anonymity. In 1W-AKE, one party (the client) authenticates the other (relay) and remains unauthenticated. [PERSON] et al. 's design [12] offers to authenticate the relay to the client by using the relay's public key and performing a key exchange via Curve25519 Diffie-Hellman. [PERSON] and [PERSON] [13] address the limitations of NTOR in light of quantum algorithms while maintaining forward secrecy, calling their 1W-AKE implementation HybridOR. It combines lattice-based cryptography, Learning With Error (ring-LWE), with the current DH assumption, maintaining compatibility with the current infrastructure. [PERSON] et al. [11] proposed a hybrid design of the not circuit-extension handshake demonstrating a practical implementation using NTRU Encrypt. [PERSON] et al. [11] permits the incorporation of any number of KEMs, allowing the other quantum-resistant algorithms to be integrated more easily without rebuilding the entire protocol. They compare the performance of this hybrid handshake with the main Tor's handshakes (tap and ntor) and the one from [PERSON] and [PERSON]. Computation time (in microseconds, \(\mu\)s) and the communication overhead, the number of bytes transmitted between the client and server, are shown for an instantiation with ntruees443 ep1. NTOR remains the most efficient in terms of both overhead and time taken. They also display the proportion of the total handshake time that is spent on the client-side operations relative to the overall handshake time. ntor equally shares the handshake time, the hybrid reaches 74%, and Gosh-Kate 67%. Gosh-Kate protocol's implementation by [PERSON] et al. [11] showed, on average, a smaller computation time (900 \(\upmu\)s) but a larger number of bytes (1344).