Improving Privacy And Performance In Anonymous Communications

Anonymous communications systems provide an important privacy service by keeping passive eavesdroppers from linking communicating parties. However, an attacker can use long-term statistical analysis of traffic sent to and from such a system to link senders with their receivers. While it is important to protect anonymous systems against such attacks, it is also important to ensure they provide good performance. In this thesis, we aim to make contributions to both these areas.In the statistical disclosure attack (SDA), an eavesdropper isolates his attack against a single user, whom we call Alice, with the aim of exposing her set of contacts. To study the SDA we introduce an analytical method to bound the time for the eavesdropper to identify a contact of Alice, with high probability. We analyze the attack in different scenarios beginning with a basic scenario in which Alice has a single contact. Defenses against this attack include sending cover traffic, which consists of sending dummy messages along with real messages. We extend our analysis to study the effect of two different types of cover traffic on the time for the attack to succeed. We further extend our analysis to investigate the effectiveness of the attack for a partial eavesdropper who can observe only a part of the network. We validate our analysis through simulations and show that the simulation results closely follow the results of analysis. Although our bounds are loose, they provide a way to compare between different amounts and types of cover traffic in various scenarios. In this part of the thesis, we investigate how cover traffic can be used as an effective counter strategy against this attack. We propose that the mix generate cover traffic that mimics the sending patterns of users in the system. This {\em receiver-bound cover (RBC)} helps to make up for users that aren't there, confusing the eavesdropper. We show through simulation how this makes it difficult for the eavesdropper to discern cover from real traffic and perform attacks based on statistical analysis. Our results show that receiver-bound cover substantially increases the time required for this attack to succeed. When our approach is used in combination with user-generated cover traffic, the attack takes a very long time to succeed. The original statistical disclosure attack has focused on finding the receivers to whom Alice sends. In this part, we investigate the effectiveness of statistical disclosure in finding all of Alice's contacts, including those from whom she receives messages. To this end, we propose a new attack called the {\em Reverse Statistical Disclosure Attack (RSDA)}. RSDA uses observations of all users sending patterns to estimate both the targeted user's sending pattern and her receiving pattern. The estimated patterns are combined to find a set of the targeted user's most likely contacts. We study the performance of RSDA in simulation using different mix network configurations and also study the effectiveness of cover traffic as a countermeasure. Our results show that that RSDA outperforms the traditional SDA in finding the user's contacts, particularly as the amounts of user traffic and cover traffic rise. In the final part of this thesis, we study how a sparse network topology affects the security of anonymous systems. We show that an expander topology such as a sparse, D-regular graph exhibits security properties comparable to a fully connected graph; within a reasonable number of hops and even for small values of degree D. Further, we show that if the expander graph is constructed with a bias towards lower round-trip time links, there is a considerable gain in performance without compromise in security.