Attacking and Improving the Tor Directory Protocol

Attacking and Improving the Tor Directory Protocol

Speakers: Zhongtang Luo, Adithya Bhat, Kartik Nayak, Aniket Kate

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=VycqeaOXkOs

Overview

Tor, short for The Onion Router, stands as the largest anonymous communication service globally, serving approximately 4 million users daily. Its fundamental operation relies on clients obtaining a list of available volunteer relay nodes from a set of directory servers, subsequently routing traffic through a randomly selected three-hop path to its destination. While extensive research has historically focused on the security of this three-hop relay path, this talk, presented by Zhongtang Luo and his collaborators, shifts focus to a critical, yet often overlooked, component: the security of the initial step where clients acquire network information from directory servers.

The presentation, titled "Attacking and Improving the Tor Directory Protocol," delves into a newly identified, sophisticated vulnerability within Tor's directory protocol (DP). This vulnerability, termed an equivocation attack, allows a malicious Directory Authority to subtly manipulate the network's consensus view, circumventing existing public detection mechanisms. The research not only exposes the theoretical underpinnings of this attack but also demonstrates its practical implications through specific scenarios like bandwidth and Sybil relay attacks.

Beyond merely identifying the problem, the researchers propose and implement two distinct solutions. First, TorEQ, a reactive, online equivocation detector already integrated into the Tor codebase, aims to identify irregular activities. Second, DieCast, a novel, proactive protocol, is introduced as a long-term architectural improvement designed to prevent equivocation entirely, thereby enhancing the theoretical soundness and resilience of the Tor network's foundational information distribution system. This work is crucial for maintaining the integrity and trustworthiness of Tor, a vital tool for privacy and freedom of expression worldwide.

Background

▶ Watch: Introduction to Tor and directory protocol's critical role (0:00)

Tor's architecture is built on the principle of distributed trust and anonymous routing. A Tor client initiates its journey by first acquiring a comprehensive list of volunteer relay nodes from a Directory Authority (DA). This initial information is paramount, as it dictates the client's subsequent ability to construct secure, anonymous paths through the network. The evolution of Tor's directory protocol reflects a continuous effort to address scalability, resilience, and security challenges inherent in maintaining such a dynamic, decentralized network.

The earliest iteration, Tor Directory Protocol Version 1, was simplistic. It involved a collection of volunteer servers that gathered and published relay information. Clients would then arbitrarily pick one of these servers to fetch the network's state. The fundamental flaw in this design was a critical trust bottleneck: "if a single Authority were to lie, it could make clients believe an arbitrary view of the Tor Network." Counterintuitively, increasing the number of directory servers in this model didn't enhance security; it merely expanded the attack surface by introducing more potential points of compromise.

Recognizing this drawback, Tor Directory Protocol Version 2 emerged. In this version, clients were designed to download network information from multiple servers and aggregate this data locally. While an improvement, this approach quickly became a scalability nightmare. The directory, which grew to approximately 5 megabytes in size, when multiplied by nine authorities and 4 million daily users, resulted in an astounding 180 terabytes of data being transferred daily – a volume far exceeding Tor's operational capacity and preferences. Furthermore, this version was susceptible to partition attacks, where censorship in specific locations could lead clients to receive divergent network views, potentially isolating or compromising them.

Since 2007, Tor has largely migrated to Directory Protocol Version 3, which forms the basis of the current system and the focus of this research. This version employs a small, fixed set of nine trusted Directory Authorities (DAs). Every hour, each DA signs a summary of its view of the network, known as a status vote. These signed votes are then exchanged among all DAs. Upon receiving all votes, each DA computes an aggregation, known as the consensus document, which represents the agreed-upon state of the network. The DAs then sign this consensus document and broadcast their signatures. Clients can then obtain a consensus document from any DA, verifying its validity by ensuring it carries at least five valid signatures from the set of trusted DAs. The speakers provocatively likened this decentralized agreement mechanism to a blockchain, noting its operational longevity predates Bitcoin.

The operational flow of the Tor v3 directory protocol involves several intricate steps:

1. Relay Information Collection: Directory Authorities continuously gather information (router descriptors) from active Tor relays.
2. Vote Broadcasting: Each DA broadcasts its individual status vote, encapsulating its current view of the network, to all other DAs.
3. Fetch Votes: To account for network latency and potential packet loss, DAs actively query their peers for any missing status votes.
4. Computing Consensus: Once a sufficient number of votes are collected, each DA independently computes the consensus document by aggregating the received votes according to a specific algorithm. This involves complex logic for agreeing on relay properties, bandwidths, and other network parameters.
5. Signature Broadcasting: DAs sign the computed consensus document and broadcast these signatures to their peers.
6. Fetch Signatures: Similar to votes, DAs query peers for any missing consensus signatures.
7. Client Service: With a signed consensus document, DAs are ready to serve this information to Tor clients, who validate it using the collected signatures.

Despite these advancements, the v3 protocol has empirically demonstrated vulnerabilities. In 2010, the consensus protocol experienced a singular failure to form a consensus due to network instability or denial-of-service (DoS) attacks. More recently, approximately three years prior to the talk, a Directory Authority suffered a DoS attack, consuming an unsustainable amount of bandwidth. These incidents, while problematic, were attributed to external attackers. The critical question posed by this research is the protocol's security in the presence of Byzantine or internal "bad actors" among the Directory Authorities themselves.

Key Findings

▶ Watch: How Tor Directory Authorities create consensus documents (4:10)

The central discovery presented in this talk is the equivocation attack, a sophisticated protocol design vulnerability within the Tor v3 consensus mechanism. This attack fundamentally undermines the integrity of the network's shared view by allowing a malicious Directory Authority to present different, contradictory information to different honest DAs.

The mechanism of equivocation works as follows: a malicious DA, let's call it 'E', can craft two distinct status votes for the same voting period. 'E' then strategically sends Vote_A to a subset of honest DAs (e.g., H1, H3, H5) and Vote_B to another subset of honest DAs (e.g., H2, H4, H6). Crucially, Vote_A and Vote_B differ on a specific property, such as the advertised bandwidth of a new relay or the existence of a set of Sybil relays. This deliberate split causes the honest DAs to form divergent perspectives. From H1's viewpoint, receiving 'E's Vote_A and other honest votes, it might see a majority supporting a certain network state, leading it to sign Consensus_A. Simultaneously, H2, receiving 'E's Vote_B, might see a majority for a different network state, leading it to sign Consensus_B.

This process creates a scenario where two or more valid consensus documents can exist concurrently, each potentially signed by a sufficient number of DAs (e.g., 5 out of 9, including the equivocating DA and the honest DAs it influenced). A naive application of this attack can result in a liveness attack, preventing a unified consensus from forming, or causing multiple conflicting consensuses to be produced.

However, the more insidious aspect is the silent equivocation attack. In this variant, the attacker 'E' can publish one of the valid consensus documents (e.g., Consensus_A) to the public, ensuring it has the required five signatures and appears legitimate to clients. Simultaneously, 'E' can privately obtain five signatures for the alternative Consensus_B, which contains the attacker's desired malicious state (e.g., a high-bandwidth honey relay). Because clients only observe the publicly available Consensus_A, the existence of Consensus_B and the attacker's manipulation remains hidden. This directly circumvents Tor's heavy reliance on public detection measures and auditability, making the attack virtually undetectable by external observers.

The researchers demonstrated this vulnerability with two specific attack scenarios:

1. Bandwidth Attack: The attacker publishes a "honey relay" with an artificially inflated bandwidth. Tor clients are naturally inclined to choose high-bandwidth relays for better performance, making them more likely to select this malicious relay. While normally detectable through public monitoring of advertised bandwidths, the equivocation attack allows the attacker to silently inject this high-bandwidth relay into a consensus document that is only seen by a subset of DAs and then privately signed, while a "clean" consensus is published publicly. The talk specifically highlighted a vulnerability in the bandwidth voting code, noting that "any three directory Authority can that can dictate the bandwidth of a new board ready."
2. Sybil Relay Attack: Instead of a single high-bandwidth relay, the attacker introduces a multitude of new "honey relays" (Sybil relays) into the network. Ordinarily, such a sudden influx of new relays would draw significant attention and be easily detectable. However, using the equivocation technique, these Sybil relays can be integrated into a privately signed consensus, again bypassing public scrutiny.

The core takeaway from these findings is that Tor's security model, which heavily depends on the transparency and public auditability of its consensus process, is fundamentally vulnerable to insider threats that can exploit the equivocation vulnerability. This reveals a critical gap between the protocol's theoretical design and its practical resilience against Byzantine actors.

To address these profound findings, the researchers proposed and developed two distinct solutions:

1. TorEQ (Reactive Mitigation): This is an online equivocation detector designed to identify irregularities in the consensus process. It's a built-in detection mechanism that has been merged into the Tor codebase and is currently live. TorEQ can generate a report in approximately five minutes, flagging potential equivocation attempts. However, a key limitation acknowledged by the authors is that TorEQ introduces a new trust bottleneck, as clients must now trust the detector itself.
2. DieCast (Proactive Improvement): This is a completely new, theoretically sound protocol designed to prevent equivocation entirely, rather than just detecting it. DieCast aims to solve the interactive consistency problem, ensuring all honest servers output the same set of input values, even in the presence of Byzantine faults. It leverages parallel Byzantine broadcast and targets f+1 security (tolerating f faulty DAs). DieCast is designed with Tor's specific constraints in mind (low number of nodes, large document size) and incorporates optimizations like message compression to ensure comparable performance.

Technical Deep Dive

▶ Watch: Introducing the Equivocation Attack on Tor (6:35)

The Tor Directory Protocol v3, as currently deployed, operates on an hourly cycle involving nine trusted Directory Authorities (DAs). The process begins with each DA collecting router descriptors from active relays, detailing their operational status, capabilities, and network addresses. Subsequently, each DA synthesizes this information into a status vote, which is essentially a signed summary of its individual view of the network's current state. These status votes are then broadcast among all nine DAs. To maintain robustness against network latency and packet loss, a crucial fetch votes step is incorporated, allowing DAs to query their peers for any missing votes.

Once a DA has collected a sufficient number of status votes (typically a supermajority), it proceeds to the Computing consensus phase. Here, a complex aggregation algorithm is executed to synthesize all received votes into a single, unified consensus document. This document details the agreed-upon list of active relays, their properties (such as advertised bandwidths, flags indicating exit or guard capabilities), and other network parameters. Following the computation, each DA signs this consensus document, signifying its agreement, and broadcasts its signature to the other DAs. A fashion signatures step further ensures that all DAs have obtained a quorum of signatures for the consensus. Finally, any DA can serve this signed consensus document to a Tor client, which validates its authenticity by verifying that it carries at least five valid signatures from the trusted DAs. This multi-signature requirement is the cornerstone of trust in the current system.

The equivocation attack exploits a subtle vulnerability in this multi-stage, distributed agreement process. A malicious DA, acting as a Byzantine fault, can craft two distinct status votes for the same hourly period. Let's say Vote_X and Vote_Y are these two votes, where Vote_X asserts a property P1 (e.g., relay R has 100 Mbps bandwidth) and Vote_Y asserts P2 (relay R has 1 Gbps bandwidth). The malicious DA then selectively sends Vote_X to a subset of honest DAs (e.g., H_A) and Vote_Y to another, disjoint subset of honest DAs (e.g., H_B).

When DAs in H_A compute the consensus, they will see Vote_X from the malicious DA. If their collective votes (including the malicious DA's Vote_X) lead to a majority for P1, they will sign a consensus document Consensus_A that includes P1. Conversely, DAs in H_B, having received Vote_Y from the malicious DA, might form a majority for P2 and thus sign Consensus_B containing P2. The key is that the malicious DA's equivocation causes a split in the collective perception and subsequent signing behavior of the honest DAs. The attacker can then choose to publish Consensus_A (which might be "clean" and appear legitimate) while privately holding Consensus_B (which contains the malicious state, such as an artificially high-bandwidth honey relay or a collection of Sybil relays), along with its required five signatures. This bypasses all public detection measures that rely on observing a single, unified consensus. The talk specifically highlighted a vulnerability in the bandwidth voting logic, stating that "any three directory Authority can that can dictate the bandwidth of a new board ready," indicating that a small coalition including the equivocating DA could manipulate relay bandwidths.

To proactively address this fundamental vulnerability, the researchers designed DieCast, a new protocol aimed at achieving interactive consistency. The interactive consistency problem requires that all non-faulty processes (DAs) agree on the same value, even if some processes are Byzantine (malicious). DieCast operates under a bounding synchrony model, similar to the current Tor protocol, with an assumed round time of 150 seconds. It targets f+1 security, meaning it can tolerate f Byzantine DAs out of N total DAs, where N = 9 for Tor.

DieCast specifically accounts for Tor's unique characteristics: a very low number of nodes (9 DAs), a very large document size (5MB per consensus), and an "outdated code in PKI structure." The protocol is structured into two main phases:

1. Bootstrap Phase:

• Propose: All DAs broadcast their initial messages, which would typically be their router descriptors and proposed network state.
• Sync Up: DAs exchange these proposed messages and actively check for any signs of equivocation. If a DA is observed sending conflicting messages to different peers, it is identified as equivocating. The goal of this phase is to "weed out equivocation" and ensure that each honest DA holds a "good behaving certificate" for all non-equivocating DAs. This phase is critical for establishing a shared understanding of which DAs are behaving honestly.

1. Agreement Phase:

• Once DAs have established the set of non-equivocating authorities and their certified inputs, this phase focuses on synchronizing these certificates among all DAs. The objective is to ensure that even in the presence of crashes, all honest DAs reach a final agreement on the same set of certified inputs. In an optimistic scenario where no crashes occur, this phase can complete in just two rounds. However, if crashes do occur, it may take up to f+1 rounds, aligning with established upper bounds in Byzantine fault tolerance protocols like Dolev-Strong.

A significant optimization implemented in DieCast is message compression. Recognizing that the differences between consecutive consensus documents tend to be small, DieCast proposes broadcasting only these differences rather than the entire 5MB document. This drastically reduces message size and communication complexity, making the protocol's performance comparable to the current Tor protocol despite its enhanced security guarantees. The initial implementation of DieCast was in C code, mirroring the Tor codebase, with plans to migrate to Rust as Tor's directory authority components transition to that language.

Demo / Proof of Concept

▶ Watch: Practical Equivocation: The Bandwidth Attack (8:30)

The talk included a demonstration and verification of the equivocation attack on a testnet environment. While not a full, interactive live demo captured in extensive detail within the transcript, the speakers explicitly stated that they "tested and verify the result on testnet."

Specifically, the demonstration focused on the bandwidth attack scenario. The researchers showcased how their attack manipulated the "pick a bandwidth code" within the Tor protocol, highlighting a specific vulnerability where "any three directory Authority can that can dictate the bandwidth of a new board ready." This implies that a malicious DA, in collusion with just two other DAs (or by equivocating to create the perception of such a coalition), could influence the bandwidth assigned to a new relay.

The presentation included visual aids, likely screenshots or diagrams, illustrating the attack results. They showed "a very large bandwidth" being assigned to an attacker-controlled "honey relay" within a consensus document. Crucially, they also demonstrated "how this consensus document were not able to be published because of insufficient and signatures." This indicates that the equivocation successfully caused a split in the consensus generation, leading to a situation where the attacker's preferred malicious consensus either failed to garner enough signatures for public release or was intentionally suppressed by the attacker in favor of a "clean" public consensus, while the malicious one was privately signed. This directly substantiates the claim that equivocation can lead to divergent consensus views and silently bypass public audit.

Defensive Implications

▶ Watch: Main takeaway: circumventing Tor's public audit mechanism (10:10)

The findings from "Attacking and Improving the Tor Directory Protocol" carry significant defensive implications for the Tor network and, by extension, other decentralized systems relying on distributed consensus and public audit.

The most immediate and actionable defensive measure is the deployment and active monitoring of TorEQ, the online equivocation detector developed by the researchers. As TorEQ has already been merged into the Tor codebase and is currently live, Directory Authorities should ensure its proper configuration and actively review its reports. TorEQ provides a reactive mechanism to detect irregular activities and identify DAs that might be equivocating. This allows the Tor project to potentially identify and remove malicious authorities, thereby mitigating ongoing attacks. However, defenders must also be cognizant of TorEQ's stated limitation: it introduces a new trust bottleneck, as the detector itself becomes a critical component that, if compromised, could mislead clients.

For long-term architectural resilience, the Tor project should seriously evaluate migrating to a proactively secure protocol like DieCast. While a significant undertaking, DieCast offers a fundamental solution by preventing equivocation by design, rather than merely detecting it. This shift would move Tor's consensus mechanism from a public audit-dependent model to a theoretically sound interactive consistency protocol, offering stronger guarantees against Byzantine faults. The coordinated disclosure process, which involved reporting the vulnerability in 2022 and shipping the detector a year later, demonstrates a responsible approach to security and provides a roadmap for future protocol upgrades. The ongoing migration of Tor's codebase to Rust also presents a timely opportunity to integrate DieCast's principles into a modern, memory-safe language.

More broadly, the research underscores a critical vulnerability in systems that heavily rely on public audit mechanisms for security. Defenders must recognize that sophisticated insider threats, capable of equivocation, can bypass transparency by presenting different views to different observers. This necessitates a re-evaluation of how trust is established and maintained in decentralized networks. Security measures should not solely focus on external threats but also on the integrity of internal processes and the behavior of trusted participants.

The specific attack examples – bandwidth attacks and Sybil relay attacks – demonstrate that classic network manipulation tactics can be rendered "silent" through equivocation. This means traditional monitoring for unusually high-bandwidth relays or sudden surges in new relays might no longer be sufficient. Defenders need to shift their focus to verifying the consistency and integrity of the consensus process itself, rather than just the final published network state.

Finally, the mention of "outdated code in pki structure" suggests an ongoing need for code modernization and robust security audits within the Tor codebase. Addressing technical debt and ensuring that critical components are built with modern security best practices can reduce the attack surface and make such complex exploits more difficult to execute.

Key Takeaways

• Tor's Directory Protocol v3 is vulnerable to equivocation attacks, where a malicious Directory Authority can present different views of the network to different honest authorities.
• Equivocation enables silent attacks like high-bandwidth "honey relays" or Sybil relay attacks, which circumvent Tor's public audit mechanisms and traditional detection methods.
• TorEQ, an online equivocation detector, has been developed and integrated into the Tor codebase as a reactive mitigation to identify and report suspicious activities in the consensus process.
• DieCast is a novel, proactive protocol proposed to fundamentally prevent equivocation by ensuring interactive consistency among Directory Authorities, thereby enhancing the theoretical soundness of Tor's consensus.
• The research highlights that heavy reliance on public audit mechanisms alone is insufficient for robust security against sophisticated insider threats in decentralized, distributed systems.
• The work emphasizes the critical importance of designing and implementing theoretically sound Byzantine fault-tolerant protocols for foundational infrastructure like the Tor network.

About the Speaker(s)

The research presented in this talk was a collaborative effort by Zhongtang Luo, Adithya Bhat, Kartik Nayak, and Aniket Kate. Zhongtang Luo, who presented the talk, is a researcher deeply involved in understanding and improving the security of anonymous communication systems. His collaborators, Adithya Bhat, Kartik Nayak, and Aniket Kate, are also researchers contributing to the field, collectively bringing their expertise to analyze and address complex protocol vulnerabilities within the Tor ecosystem. Their work demonstrates a commitment to advancing the security and resilience of critical privacy-enhancing technologies.