Securing Anonymous Communication Channels under Selective DoS Attack

Securing Anonymous Communication Channels under the Selective DoS Attack Anupam Das , Nikita Borisov University of Illinois at Urbana-Champaign (UIUC) FC 2013 4/4/2025 1

Outline Anonymous Communication (Tor) Selective DoS attack Our Detection Mechanism Evaluation Conclusion 4/4/2025 2

Anonymous Communication Hides user identity and defends users against internet surveillance and traffic analysis. The most widely used anonymity network is Tor ~3000 Tor Relays ~500,000 Users daily 4/4/2025 3

How Tor Works Tor Relay Encrypted link M M M M Unencrypted link Tor circuit /tunnel is built incrementally one hop by one hop Layered encryption is used Each router knows only its predecessor and successor 4/4/2025 4

Threats in Tor Tor relays are run by volunteers. So they can be malicious. Anonymity broken Probability of circuits being compromised: Pr(comprom Assuming t fraction of the bandwidth is controlled by a malicious authority. 4/4/2025 = 2 ised) t 5

Selective DoS in Tor Not Dropped Entry Middle Exit C- Compromised H- Honest Relay Entry Middle Exit H H C C H C H C C C C C Dropped H C H H H H C H H C C H 4/4/2025 6

Impact of Selective DoS Under Normal Condition: = 2 Pr(Comprom ised) t Under Selective DoS: 2 t = Pr(Comprom ised) + 2 3 1 ( ) t t 4/4/2025 7

Our Goal Design a detection mechanism that can distinguish compromised circuits from non-compromised circuits. We propose a 2-phase probing algorithm. 1. Generate candidate circuits 2. Identify potentially compromised circuits Threat Model: 1. Small fraction (~20%) of relays are compromised 2. Compromised relays perform selective DoS attack. 4/4/2025 8

Our Detection Mechanism Phase 1. Generate N working Tor circuits and test the reliability of the circuits by retrieving a web page through the circuit. Entry Middle Exit Entry Middle Exit H H C H H C H C C H C C Test reliability H C H H C H C H H C H H C C H C C H Circuits that survive 1st phase and passed onto the 2nd phase C H C C H C C C C C C C H H H H H H 4/4/2025 9

Our Detection Mechanism Phase 2. For each circuit choose K other random exit and middle relays. Test reliability of the modified circuits. Test Reliability Modified Circuits Entry Middle Exit Entry Middle Exit Hi Hi Hj Hk Hi Hb Cp . . . Cm Cn Cp Cp Repeat the process K times for each circuit. . . . . . . Ca Hb Hb Cc For each circuit keep track of the no. of success M IF(M>=Threshold) classify as potentially honest circuit 4/4/2025 10

Probabilistic Analysis Assuming t fraction of the bandwidth is controlled by a malicious authority. (t 20%) = 2 Pr(comprom ised circuit) = t Entry Middle Exit 3) Pr(honest circuit) 1 ( t C H C C C C H H H For t=0.2, (1-t)3 >> t2 So majority of the circuits in the second phase are honest. Therefore compromised circuits should have low success rate after circuit modification. 4/4/2025 11

Complex Attacks What if compromised nodes don t always drop to avoid detection? We consider 2 types of dropping strategy- 1. Random drop 2. Strategic drop Random Drop: Drops with probability d Strategic Drop: Don t drop circuits of form XXC as they are helpful in the 2nd phase Entry Middle Exit H H C H C C H C H C H H C C H C H C C C C H H H 4/4/2025 12

Disguising Probes To make probes indistinguishable from user traffic we adopt the following strategies- 1. Use popular websites as probing destination Alexa lists the top popular websites 2. Replay non-sensitive browsing history as probes 3. Randomize the middle relay from the set of (N-1) available relays after phase 1 4/4/2025 13

Evaluation We evaluate our approach through both simulation and real world experiments. Simulation setup: Gathered Tor node info from torstatus.blutmagie.de/ Randomly assigned 20% bandwidth to be compromised. To approximate the failure rate present in the current Tor network we take the help of TorFlow project [Torflow project. https://gitweb.torproject.org/torflow.git] We generate 10,000 Tor circuits and record their failure rate. Average failure rate after 10 run was found to be approximately 23%. 4/4/2025 14

Simulation Results As drop rate d increases the probability of selecting a compromised circuits decreases 4/4/2025 15

Real World Experiments We use Emulab and PlanetLab machines for our experimental setup. 11 Emulab machines= 10 run Tor protocol (20Kbps)+1 acted as server (gathering timing info from the other 10 machines) [Bauer et al. WPES 07] Extracted 40 other regular Tor node and added our 10 compromised nodes (t=20%). Use PlanetLab machines as clients. Fraction of compromised guards Pr(not compromised) Pr(not compromised) (Conventional Tor) 0 1.0 1.0 1/3 1.0 0.867 2/3 0.843 0.612 1 0.0 0.0 4/4/2025 16

Overhead Approximation Each usable circuit requires 4 probes Each probe size is 300KB (avg. size of the most popular web pages) So the total traffic used by a single user every one hour is (6*3*300*4)KB 21MB Currently, Tor s Bandwidth capacity = 3.21GB/s Approximately 5% of the bandwidth can be used to satisfy the current peak demand 4/4/2025 17

Related Work Danner et al. [FC 2009] proposed a probing technique where they create O(n*l) circuits to identify compromised relays. [where n= no. of relays, l=no. of times each probe is repeated] However, 1. They don t consider strategic adaptation by malicious nodes like random dropping. 2. More suitable as a centralized approach. Otherwise it would not be scalable. Probes might be more easier to distinguish. Mike Perry (Tor Performance Developer) recently proposed: Client-side accounting mechanism that tracks the circuit failure rate for each of the client s entry nodes. 4/4/2025 18

Conclusion Our detection algorithm filters out potentially compromised Tor circuits with high probability. We also show that adaptive adversaries who choose to deny service probabilistically do not benefit from adopting such strategy. Future Work: Can we lower the cost of probing/overhead? Can we not use probing at all? Maybe use historical data 4/4/2025 19

Questions 4/4/2025 20

4/4/2025 21

What is Tor? Tor (short for The Onion Routing) is a system that provides online anonymity. Tor hides user identity and defends users against internet surveillance and traffic analysis. Tor was originally launched in 2002 by US Naval Research Lab From 2004 it became an open source software. 4/4/2025 22

Why use Tor? Journalists & Activists & Whistleblowers Report controversial topics Report abuses from danger zones Human Rights Watch Normal users Unwanted Advertisements Hide physical location Sensitive survey Access blocked sites Militaries and Law enforcement officers Online surveillance Anonymous tip Intelligence gathering Business executives Keeping strategies confidential Accountability 4/4/2025 23

Probabilistic Analysis We evaluate the False positive and False negative rates. We also consider random network failure in our model. False Negative (FN)= Fraction of compromised circuits that are wrongly classified as honest False Positive (FP)= Fraction of honest circuits that are wrongly classified as compromised Ideally we want both FN and FP as small as possible. [detailed derivations in our tech report ] 4/4/2025 24

Tuning Parameters For choosing appropriate K and we define two evaluation metric- Security, Overhead, K=3 =2 4/4/2025 25

Complex Attacks Prob. of selecting XXC circuit in the 2nd phase Cost of forwarding traffic through non-compromised circuits 4/4/2025 26

4/4/2025 27

Tor Tunnel Construction 4/4/2025 28

Our Detection Mechanism Phase 2. For each circuit choose K other random exit and middle relays. Test reliability of the modified circuits. Test Reliability Modified Circuits Entry Middle Exit Entry Middle Exit Hi Hi Hj Hk Hi Hb Cp . . . Cm Cn Cp Cp Repeat the process K times for each circuit. . . . . . . Ca Hb Hb Cc For each circuit keep track of the no. of success for each circuit M IF(M>=Threshold) classify as potentially honest circuit 4/4/2025 29