Untagging Tor: A Formal Treatment of Onion Encryption

Jean Paul Degabriele, Martijn Stam

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

1 Citation (Scopus)


Tor is a primary tool for maintaining anonymity online. It provides a low-latency, circuit-based, bidirectional secure channel between two parties through a network of onion routers, with the aim of obscuring exactly who is talking to whom, even to adversaries controlling part of the network. Tor relies heavily on cryptographic techniques, yet its onion encryption scheme is susceptible to tagging attacks (Fu and Ling, 2009), which allow an active adversary controlling the first and last node of a circuit to deanonymize with near-certainty. This contrasts with less active traffic correlation attacks, where the same adversary can at best deanonymize with high probability. The Tor project has been actively looking to defend against tagging attacks and its most concrete alternative is proposal 261, which specifies a new onion encryption scheme based on a variable-input-length tweakable cipher.

We provide a formal treatment of low-latency, circuit-based onion encryption, relaxed to the unidirectional setting, by expanding existing secure channel notions to the new setting and introducing circuit hiding to capture the anonymity aspect of Tor. We demonstrate that circuit hiding prevents tagging attacks and show proposal 261's relay protocol is circuit hiding and thus resistant against tagging attacks.
Original languageEnglish
Title of host publicationAdvances in Cryptology - EUROCRYPT 2018
Subtitle of host publication37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part I
EditorsJesper Buus Nielsen , Vincent Rijmen
Number of pages35
ISBN (Electronic)9783319783819
ISBN (Print)9783319783802
Publication statusPublished - 2 Jun 2018

Publication series

NameLecture Notes in Computer Science
PublisherSpringer International Publishing AG Switzerland
ISSN (Print)0302-9743
ISSN (Electronic)1611-3394


  • Anonymity
  • Onion Routing
  • Secure Channels
  • Tor
  • Tagging Attacks


Dive into the research topics of 'Untagging Tor: A Formal Treatment of Onion Encryption'. Together they form a unique fingerprint.

Cite this