# Post-Quantum Migration of the Tor Application
## 2 Literature Review
### Schemes
#### 2.2.2 Signature
TLS signatures can be divided into two categories: \"online\" signatures of messages in the handshake protocol and static ones of certificates in the certificate chain; the \"statics\" allow a greater signing time as the computation takes place in advance. Typically, the root certificate signs the intermediate CA certificate, which itself signs the leaf certificate. The latter is used to sign the transcript during the handshake; the other signatures are static. The certificate chain size gives practical insight into assessing the overhead. [PERSON] and [PERSON] [44] estimate the authentication data sizes of ML-DSA-44 and ML-DSA-6 to be 14 KB and 19 KB, respectively (including the intermediate CA certificate). Their work on the increased latency caused by the certificates is based on the estimated sizes of the chain; the observed chains are built with RSA, not actual ML-DSA certificates. The paper states a 32% handshake time increase compared to the 2.5 KB chain. In Tor TLS, the certified key type varies from Ed25519 to a hash (SHA256) of an X.509 certificate. Since \begin{table}
\begin{tabular}{l c c c c c} \hline \hline  & **Keygen/s** & **Keypair** & **Sign/s** & **Verify/s** & **Security** \\  & & **(Cycles)** & **Sign/s** & **Category** \\ \hline Falcon-512 & 53.26 & 46,938,518 & 176.55 & 17,246.00 & 1 \\ Falcon-1024 & 17.91 & 139,565,458 & 80.56 & 8341.00 & 5 \\ Dilithium2 & 9486.00 & 263,444 & 2099.33 & 8752.33 & 2 \\ Dilithium3 & 5184.33 & 482,134 & 1320.00 & 5519.00 & 3 \\ SPHINCS+SHA2-128f-s & 558.81 & 4,473,508 & 23.86 & 404.73 & 1 \\ SPHINCS+SHA2-192f-s & 382.08 & 6,542,247 & 14.52 & 270.91 & 3 \\ \hline \hline \end{tabular}
\end{table} 
Table 6: PQC performance comparison. Operations per second per algorithm, reference code type (unoptimised), 2 April 2024, OQS [35]. the hash itself is not directly reversible, this part of TLS authentication is, therefore, less exposed to quantum attacks. Yet, the underlying X.509 certificate remains dependent on the public key primitive used. While standards drafts are proposing to include the recently standardised SLH-DSA [45], its performance stays far behind Dilithium and Falcon [46]. [PERSON] and [PERSON] [47] proposed a backwards-compatible mechanism to omit the intermediate CA certificate, allowing lighter and faster PQC TLS handshakes. Currently, an IETF draft is in progress to extend ACME challenges to validate \".onion\" domains through a Tor-compatible mechanism; the draft by [PERSON] [48] presents a new challenge type, \"onion-csr-01\", while still incorporating the \"http-01\", \"dns-01\", and \"tls-alpn-01\" challenges. Relying on the broader web PKI, aside from the potential privacy concerns for the onion service, remains sensitive to quantum attacks. If proposal #340 is implemented as specified, the digest field, responsible for checking the cell integrity, should reach a size of 14 bytes, allowing the integration of larger hashes (currently SHA-1). Although hash functions are less directly threatened by quantum algorithms than PKE schemes, it has been shown that [PERSON]'s algorithm can be used to reduce the time required for preimage attacks on hash functions like SHA-1, SHA-2, and SHA-3, as well as minimise the time needed for hash inversion in \(O(\sqrt{n})\), halving the security of the function [49]. Ultimately, NIST [50] is still looking for a signature scheme and has declared that some second-round candidates have undergone minimal or no formal cryptanalysis in published research. Thus, potential signature schemes may still reveal themselves in future research and deployment as a match for Tor's requirements. For instance, FAEST, which achieves faster key generation than ML-DSA, displays smaller key sizes and relies on the mature security of SHA3 and AES, yet its signatures are more than twice the size of those of the latter lattice-based scheme at their respective minimum security levels [51].