Diversity and traffic confirmation in the Tor network

The Internet is an invaluable invention, yet it does not offer privacy to its users by default. Research in privacy-preserving communication has offered different designs to overcome this issue, with various security and performance properties. The Tor network is the most popular distributed, and volunteer-based deployed system, offering anonymous paths through the Internet to millions of people seeking online privacy while browsing the web, or using other Internet services. The Tor network provides some level of diversity to the users, which aims at minimizing the probability for an attacker to observe the paths taken through the network. Free and open-source, the Tor Project encourages audit and improvements coming from academic research. This thesis contributes to the Tor Project, and the privacy enhancing technologies community, with innovative proposals to improve the network diversity against some adversary, which aims at increasing the anonymity. Our proposals face the primary constraint to maintain the performance the Tor network currently provides. This thesis starts with a study of low-latency anonymous networks weaknesses and ends up to discover a new one. Our work features low-cost and efficient attacks to deanonymize Tor users and onion services based on a flexibility property of the routing protocol, called forward compatibility. Like any distributed system, the Tor network can be composed of relays with different versions. Forward compatibility prevents clients or relays from generating unrecoverable errors with other peers running forward versions of the protocol. We argue that preventing attacks exploiting forward compatibility would require changes within the routing protocol that would be difficult to set up, and would require further research if forward compatibility has to be maintained. To increase the diversity of the network, we explore the innermost feature to provide anonymity, namely the path selection algorithm, and show with light and local modifications of the current path selection how to achieve more diversity within the distribution of paths while maintaining a similar level of performance for Tor users. Furthermore, this part of the thesis offers a worst-case evaluation entropy metrics to assess the level of security of the network against some adversary, at a static point in time. This metric measures some notion of the network diversity, with the expectation on the number of relays that the adversary needs to compromise to deanonymize any Tor user. The final part of this thesis takes a more ambitious research direction to increase the Tor network diversity. We design and implement a new set of payment protocols to incentive relay participation through monetary retributions. Our design offers a secure, anonymous and efficient payment system including a tax system allowing the Tor Project to collect a fraction of each payment and to redistribute it to favor any diversity notion. Our approach leverages the latest advances in cryptocurrency research toward a design that is directly integrated into the existing Tor architecture and covers economic policies, novel payment algorithms, and networking implementations.