Onions Got Puzzled: On the Challenges of Mitigating Denial-of-Service Problems in Tor Onion Services

Denial-of-service (DoS) attacks present significant challenges for Tor onion services, where strict anonymity requirements render conventional mitigation strategies inapplicable. In response, the Tor community has recently revived the client puzzle idea in an official update to address real-world DoS attacks, leading to its adoption by several major onion services. In this paper, we uncover a critical vulnerability in the current puzzle system in Tor through a novel family of attacks, dubbed ONIONFLATION. The proposed attacks artificially inflate the required puzzle difficulty for all clients without causing noticeable congestion at the targeted service, rendering any existing onion service largely unusable at an attack cost of a couple of dollars per hour. Our ethical evaluation on the live Tor network demonstrates the impact of these attacks, which we have reported to the Tor Project and received acknowledgment. Our analysis reveals an undesirable trade-off in the client puzzle mechanism, which is the root cause of the discovered vulnerability, that forces the Tor onion system to choose between inflation resistance and congestion resistance, but not both. We offer practical guidance for Tor onion services aimed at balancing the mitigation of these attacks.