Cryptology ePrint Archive: Report 2013/664

TUC: Time-sensitive and Modular Analysis of Anonymous Communication

Michael Backes and Praveen Manoharan and Esfandiar Mohammadi

Abstract: The anonymous communication protocol Tor constitutes the most widely deployed technology for providing anonymity for user communication over the Internet. Several frameworks have been proposed that show strong anonymity guarantees; none of these, however, are capable of modeling the class of traffic-related timing attacks against Tor, such as traffic correlation and website fingerprinting.

In this work, we present TUC: the first framework that allows for establishing strong anonymity guarantees in the presence of time-sensitive adversaries that mount traffic-related timing attacks. TUC incorporates a comprehensive notion of time in an asynchronous communication model with sequential activation, while offering strong compositionality properties for security proofs. We apply TUC to evaluate a novel countermeasure for Tor against website fingerprinting attacks. Our analysis relies on a formalization of the onion routing protocol that underlies Tor and proves rigorous anonymity guarantees in the presence of traffic-related timing attacks.

Category / Keywords: foundations / cryptographic protocols, security analysis of protocols, concurrent composition, anonymous communication

Date: received 17 Oct 2013, last revised 11 Feb 2014

Contact author: manoharan at cs uni-saarland de

Available format(s): PDF | BibTeX Citation

Note: We added an internal simulation lemma and proved that in our model all activation orders are equivalent. Moreover, we more thoroughly discussed timing attacks.

Version: 20140212:020428 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]