Anomalous keys in Tor relays

Overview  •  Writing  •  Code  •  Data  •  Contact


Counting almost 7,000 relays, the Tor network is one of the largest volunteer-run anonymity networks operating today. Most of the volunteers who operate these relays choose to remain anonymous, and little is known about how they set up or operate their relays. As a result, it is not clear if all relays correctly generated the cryptographic key material that is needed to participate in the Tor network. Key generation issues can have devastating consequences, and led to severe vulnerabilities in the past, emphasizing the importance of knowing if the Tor network is affected by the same weaknesses.

In this research project, we took a closer look at the cryptographic keys of Tor relays. Drawing on a dataset containing more than 3.7 million Tor relay public keys over the past 10 years, (i) we checked if any relays share prime factors or moduli, (ii) we identified relays that used non-standard RSA exponents, and (iii) we characterized malicious relays that we discovered in the first two steps. Our experiments revealed that ten relays shared moduli, and 3,557 relays—most part of a research project—shared prime factors, allowing adversaries to reconstruct their private keys. Fortunately, all the relays we found with weak keys have been absent from the Tor network for years. We further discovered 122 relays that used non-standard RSA exponents, presumably in an attempt to attack onion services. By simulating how onion services are positioned in Tor’s distributed hash table, we could identify four onion services that were likely targeted by these malicious relays.

What does our work mean for Tor users? There is no need for concern. While we discovered that some relays were vulnerable in the past, these relays are no longer online, and there is no reason to believe that the vulnerabilities were exploited. In addition to demonstrating these issues, we suggest countermeasures that The Tor Project can adopt to find vulnerable relays early, and remove them from the network. As a result, our work further strengthens the security of the Tor network.


The main outcome of this project is a research paper that we will present at Financial Cryptography 2018 on Curaçao.


Our GitHub repository contains the LaTeX code of our paper as well as our Python and Go code snippets:

git clone

The repository also contains our tool itos that we used to identify onion services that were likely targeted by malicious onion service directories. Run itos -h for a list of supported options. You can run the tool as follows:

cd anomalous-tor-keys/code/itos/
go build itos.go
./itos -hss onion-services.csv -hsdirs hsdirs.csv


We publish the following datasets. Each tarball contains a README.txt file that explains the respective dataset.


We are a team of four researchers from two institutions. Please copy all of us if you have any questions or remarks.

Last update: 2017-12-15