A Peel of Onion Paul Syverson U S Naval Research Laboratory ●  ●  paul syverson@nrl navy mil http www syverson org “Our motivation here is not to provide anonymous communication but to separate identification from routing ” ●  “Proxies for anonymous routing” Reed Syverson and Goldschlag ACSAC 1996 A Motivational Use Case Example Navy Petty Officer Alice is temporarily in Repressia Don't be a Target identify you as a potential target Items that display your DOD af liation may also help 9 Don't be 4 S Level I Trainin stem wy 9 gigm g 311 Not all threats are predictable or can be recogi As a result you should concentrate on not bell for attack Reduce your exposure by being anonymous ar your surroundings 0 Do not wear clothing or carry items that mi criminal attention 0 Remain low key and do not draw attention 1 0 Avoid places of high criminal activity In addition to blending in try to reduce your exposure 0 Select places with security measures approi local threat 0 Be unpredictable and vary your routes and 0 Travel with a friend or in a small group 0 Use automobiles and residences with adeQL features You can greatly increase your personal protect remaining anonymous and reducing your expo Next continue A Motivational Use Case Example ●  Safe back in her room at the Repressia Grand Hotel PO Alice wants to read and or post to sealiftcommand com Civilian Maritime obs MSC Military Seaiift Command Without Computer Security Y- Civilian Maritime Jobs MSC Si 2 33 sealiftcommand com Like 4k ABOUT M80 MARITIME EMPLOYMENT RESOURCES 8T MILITARY A plugin 5 mm red to play addi Please dowr loac Acooe ash MSC COMMAND NEWS AND ANNOUNCEMENTS Sealift Command Accepts Navy's Newest Shlp USNS McLean SAN DIEGO NNS Military Sealift Command accepted delivery of dry cargo ammunition ship USNS William McLean T-AKE 12 during a ceremony at the General Dynamics NASSCO shipyard in San Diego Sept 28 The 689-foot long McLean designated T-AKE 12 is the 12th of 14 new Read More TALK JOBS NOW HIRING GETTING I Career RSS View all career fairs 9 I Now lelng RSS Vlew all open positions Resources MSC Career Falr Able Seaman San Franciaoo CA - Amouncement open 1 November througm MSC MILITARY 30 mm 20 areer a 11 03 11 ONLY Milingmn TN 11AM- 3PM - Medlcal Servlces Of cer 11 03 MSC Career Falr - Nviounoetnenlopen 3 Ochober201 l with Cumm Mariners lee a Vet Career Falr Departan 11 11 Second Cook Raleigh NC 10AM -3PM 11 1o 11 Recruit Wle Veterans Expo was Maritime School Miami FL 11AM - 3m A Motivational Use Case Ex Navy PO Alice in her hotel Don't be a Target identify you as a potential target Items that display your DOD af liation may also help 9 Don't be 4 S Level I Trainin stem wy 9 gigm g 311 Not all threats are predictable or can be recogi As a result you should concentrate on not bell for attack Reduce your exposure by being anonymous ar your surroundings 0 Do not wear clothing or carry items that mi criminal attention 0 Remain low key and do not draw attention 1 0 Avoid places of high criminal activity In addition to blending in try to reduce your exposure 0 Select places with security measures approi local threat 0 Be unpredictable and vary your routes and 0 Travel with a friend or in a small group 0 Use automobiles and residences with adeQL features You can greatly increase your personal protect remaining anonymous and reducing your expo Next continue Connecting when overseas Navy PO Alice in her hotel Contacted sealiftcommand com 05 06 2014 9PM 20 min encrypted Connecting when overseas Navy PO Alice in her hotel Contacted sealiftcommand com 05 06 2014 9PM 20 min encrypted Rm 416 Ckout on 05 08 2014 Security of operations concern as well as personnel security concern Navy PO Alice in her hotel Contacted nrl navy mil 05 06 2014 9PM 20 min encrypted Rm 416 Ckout on 05 08 2014 Some more government uses ●  ●  ●  ●  ●  Open source intelligence gathering Sensitive communications with untrusted untrusting parties Encouraging open communications with citizens Location protected servers for defense in depth Protecting the public infrastructure –  Interacting with network sensors Ordinary citizen Alice ●  ●  ●  ●  ●  ●  ●  Protecting her behavior from Cyberstalking abusive ex-spouse Behavior tracking and DNS shenanigans from her ISP Misunderstanding from her employer when she investigates disease info for an ailing friend Harassment for blogging her views Malicious parties watching her log into Club Penguin and watching her mom logged into twitter from work Spear phishers watching her log into her bank EBA TOW Facebook protest forces Israeli cheese price cuts protest has scored a victory for consumers in Israel Their threats of a boycott have forced dairy manufacturers to lower the price of cottage cheese by some 25% The two-week campaign drew more than 105 000 people to join a Facebook group vowing to boycott the Israeli staple until prices dropped The campaign has touched a nerve among Israelis concerned about rising prices and eroding salaries JERUSALEM AP A high-profile Facebook spread to other fields the price which is now over $8 a gallon 2 00d products have recently skyi well It also has highlighted the powe media outlets in sparking Chang comparing it to the revolutions elsewhere in the Middle East True this is not Tahrir Square 3 cottage cheese rebellion did ml to take any real action just to pi skip the cottage cheese shelf in supermarket columnist Ben C the Maariv daily referring to the was the epicenter of the Egyptie This was inaction not action a demanded no real sacri ce The Facebook page of the cotta bo cott identi es or anizers as delawamnnline Opinion 13 Entertainment 3 It's not only about dissidents in Print Story Discuss Story Top StoryChat 0 Jury finds in favor of officers in wrongful death case - rn-i villi faraway lands News Choices Get Published 3 Webcasts Lg Wireless Text Alerts RSS Feeds News Archive Delaware I HOME BUSINESS Freedom of speech better ask your boss The First Amendment takes on a different role when applied to the workplace By GARY HABER The News Journal Convinced you have freedom of speech at work Think again Maybe you should ask the AstraZeneca pharmaceutical sales manager fired earlier this month for comments he reportedly made in a company newsletter comparing physicians' of ces to a big bucket of money The News Journal HOWARD JOHNSON Or the Utah Web designer red for observations about her job she posted on her personal blog Or former Philadelphia Eagles wide receiver Terrell Owens whose pointed criticism of the team and its quarterback got him suspended in 2005 Thai Fircf am nnirlt in mint nut r lmcn'f Ordinary citizen Alice ●  ●  ●  ●  ●  ●  ●  Protecting her behavior from Cyberstalking abusive ex-spouse Behavior tracking and DNS shenanigans from her ISP Misunderstanding from her employer when she investigates disease info for an ailing friend Harassment for blogging her views Malicious parties watching her log into Club Penguin and watching her mom logged into twitter from work Spear phishers watching her log into her bank Ordinary citizen Alice ●  ●  ●  ●  ●  ●  ●  Protecting her behavior from Cyberstalking abusive ex-spouse Behavior tracking and DNS shenanigans from her ISP Misunderstanding from her employer when she investigates disease info for an ailing friend Harassment for blogging her views Malicious parties watching her log into Club Penguin and watching her mom logged into twitter from work Spear phishers watching her log into her bank Officer Alice ●  Setting up a sting operation –  –  ●  ●  as a collaborator as a service provider Monitoring criminal activity online Encouraging anonymous tips Researcher Reporter Rights Worker Alice ●  ●  ●  Gathering information while protecting sources Accessing information that is locally censored or monitored Reporting information that is locally censored or monitored Corporation Alice ●  ●  ●  Investigating competitors’ public sites Avoiding leaking strategy or nonpublic information Protecting customers –  –  –  spearphishing attacks or selective service disruption privacy sensitivity Aside some other benefits of an anonymity system ●  Besides protecting affiliation etc can provide “poor man’s VPN” Access to the internet despite •  •  Network port policy disconnects DNS failure You can't be anonymous by yourself private solutions are ineffective Citizen Alice Alice's small anonymity net Officer Alice Municipal anonymity net AliceCorp AliceCorp anonymity net Investigated suspect “One of the 25 users on AliceNet ” “Looks like a cop ” Competitor “It's somebody at malware host AliceCorp ” so anonymity loves company Citizen Alice Officer Alice Shared anonymity net “ ” Investigated suspect “ ” Competitor “ ” AliceCorp The simplest designs use a single relay to hide connections Bob1 Alice1 Alice2 Alice3 Bob1 “Y” Relay “Z” Bob2 Bob3 But an attacker who sees Alice can see who she's talking to Bob1 Alice1 Alice2 Alice3 Bob1 “Y” Relay “Z” Bob2 Bob3 Add encryption to stop attackers who eavesdrop on Alice Bob1 Alice1 Alice2 Alice3 E Bob1 “Y” Relay “Z” Bob2 Bob3 e g some commercial proxy providers Anonymizer But a single relay is a single point of failure Bob1 Alice1 Evil or Alice2 Alice3 E Bob1 “Y” Compromised Relay “Z” Bob2 Bob3 But a single relay is a single point of bypass Bob1 Alice1 Alice2 Alice3 E Bob1 “Y” Irrelevant Relay “Z” Bob2 Bob3 Timing analysis bridges all connections through relay ⇒ An attractive fat target Low-latency systems are vulnerable to end-to-end correlation attacks Low-latency Alice1 sends Bob2 gets   Alice2 sends   Bob1 gets   High-latency Alice1 sends  Alice2 sends   Bob1 gets Bob2 gets           Time match  match           These attacks work in practice The obvious defenses are expensive like high-latency useless or both But a single relay is a single point of bypass Bob1 Alice1 Alice2 Alice3 E Bob1 “Y” Irrelevant Relay “Z” Bob2 Bob3 Timing analysis bridges all connections through relay ⇒ An attractive fat target 80 add multiple relays so that no single one can betray Alice A corrupt first hop can tell that talking but not to whom In A corrupt last hop can tell some talking to Bob but not who Onion Routing Circuit construe Onion Routing Circuit construe Onion Routing Circuit construe Onion Routing Connection ore Onion Routing Data Exchan Onion Routing Data Exchan Onion Routers Relays Nodes Clique topology 239 Onion Routers Relays Nodes Overlay network That's onion routing in a nutshell Mix networks vs Onion routing networks Low-latency Alice1 sends Bob2 gets The image cannot be displayed Your computer may not have enough memory to open the image or the image may have been corrupted Restart your computer and then open the file again If the red x still appears you may have to delete the image and then insert it again   Alice2 sends   Bob1 gets   High-latency Alice1 sends  Alice2 sends   Bob1 gets Bob2 gets           Time match  match           These attacks work in practice The obvious defenses are expensive like high-latency useless or both VA message 1 b w message 2 gC message 3 Mix ne work 24 '4 message 4 Randomly permutes and inputs What onion routing is NOT Mixes ●  Entirely different threat model •  •  •  •  ●  Entirely different communications paradigm Circuit based encryption vs per message •  •  ●  mixes are based on an adversary not being able to correlate inputs and outputs he sees onion routing is based on an adversary not being able to see both inputs and outputs to correlate mix networks more secure against global passive adversary mix networks can be less secure vs local active adversary onion routing supports bidirectional communication onion routing supports low-latency communication Can be combined to make mixing onion routers but not typically done or desired What onion routing is ●  ●  Uses expensive crypto public-key to lay a cryptographic circuit over which data is passed Typically uses free-route circuit building to make location of circuit endpoints unpredictable Why call it “onion routing” Answer Because of the original key distribution data structure Bob Alice R1 R3 R5 R4 R2 Why is it called onion routing KA R5 KA R2 R5 KA R1 R2 Alice R1 R4 ●  Bob R5 R2 R3 Onion Just layers of public-key crypto •  Nothing in the center just another layer Mixi networks have a message in the middle of a public-key onion Ciphertext 49 Why is it called onion routing KA R5 KA R2 R5 KA R1 R2 Alice R1 R4 ●  Bob R5 R2 R3 Onion Just layers of public-key crypto •  Nothing in the center just another layer Circuit setup KA R5 KA R2 R5 KA R1 R2 ●  NRL v0 and v1 onion routing and also ZKS Freedom network used onions to build circuits •  •  ●  Lacked Forward Secrecy Required storing record of onions against replay Tor NRL v2 uses one layer “onion skins” •  •  •  ephemeral Diffie-Hellman yields forward secrecy No need to record processed onions against replay From suggestion out of Zack Brown’s Cebolla Aside Why is it called ‘Tor’ and what does ‘Tor’ mean ●  ●  ●  ●  ●  Frequent question to Roger c 2001-2 Oh you’re working on onion routing which one Roger THE onion routing The original onion routing project from NRL Rachel That’s a good acronym Roger And it’s a good recursive acronym Plus as a word it has a good meaning in German door gate portal and Turkish finemeshed net Aside Why is it called ‘Tor’ and what does ‘Tor’ mean ●  ●  We foolishly called the first Tor paper “Tor the second generation onion router” But this was very confusing •  •  •  ‘Tor’ stands for “The onion routing” or “Tor’s onion routing” It does not stand for “the onion router” The paper is about the whole system not just the onion routers Tor is not the second generation Aside Why is it called Tor and what does Tor mean Aside Why is it called ‘Tor’ and what does ‘Tor’ mean ●  ●  ●  ●  ●  Tor A class of onion routing design created at NRL starting c 2001-2 Tor A U S 501 c 3 nonprofit organization formed in 2006 Tor A client software program that connects your computer to the Tor network Tor A volunteer network comprised of c 5000 nodes serving c 4 GiB s data for c 1M users see metrics torproject org Any amorphous combination of the above or other users Onion routing origins Generation 0 ●  ●  ●  ●    ●  Fixed-length five-node circuits Integrated configuration Static topology Loose-source routing Partial active adversary Rendezvous servers and reply onions Onion routing the next generation   ●  ●    ●  ●  ●  ●  Running a client separated from running an OR Variable length circuits up to 11 hops per onion---or tunnel for more Application independent proxies SOCKS plus redirector Entry policies and exit policies Dynamic network state flat distribution of state info Multiplexing of multiple application connections in single onion routing circuit Mixing of cells from different circuits Padding and bandwidth limiting Third-generation onion routing Tor   ●  ●  ●  ●  ●  ●  ●  Onion skins not onions Diffie-Hellman based circuit building Fixed-length three-hop circuits Rendezvous circuits and hidden servers Directory servers caching evolved w in Tor Most application specific proxies no longer needed still need e g for DNS Congestion control End-to-end integrity checking No mixing and no padding Circuit setup KA R5 KA R2 R5 KA R1 R2 ●  NRL v0 and v1 onion routing and also ZKS Freedom network used onions to build circuits •  •  ●  Lacked Forward Secrecy Required storing record of onions against replay Tor NRL v2 uses one layer “onion skins” •  •  •  ephemeral Diffie-Hellman yields forward secrecy No need to record processed onions against replay From suggestion out of Zack Brown’s Cebolla Tor Circuit Setup Create Client chooses first node establishes session key over TLS connection Hash Client Initiator Onion Router TLS connection Tor Circuit Setup Create Client chooses first node establishes session key over TLS connection Hash Client Initiator Onion Router Tor Circuit Setup Extend Client chooses first node establishes session key over TLS connection OR2 Client Initiator Hash Hash OR1 OR2 Tor Circuit Setup Begin and Data Flow Slight simplification of actual protocol Connect Reply Client Initiator OR2 OR1 Reply Web server How do we know where to build a circuit Network discovery ●  ●  ●  Flat flooding of network state complex tricky scales in principal but Tor has a directory system Originally a single directory signing information about network nodes Then a multiple redundant directory with mirrors Then a majority vote system Then a consensus document system Then separate things that need to be signed and updated frequently Then Onion routing was invented to separate identification from routing ●  ●  ●  ●  ●  What if onion-routing-network-user is the identification you want to avoid Bridges are proxies into the Tor network that are not publicly listed Tricky to get bridge info out to potential users without giving it to the network blockers Flash Proxy plugin on volunteer’s browser connects to both censored client and Tor relay Can also use obfuscated transport to hide Tor protocols from DPI What if adversary owns a botnet or has nation level resources ●  ●  Consumer Alice abuse disease victim Alice local law enforcement Alice etc probably OK Intelligence analyst Alice DoD road warrior Alice etc Network diversity environment •  Government comms sometimes must use public internet •  •  •  •  •  •  Open source intelligence gathering Traveling employees communicating back home Interacting with untrusted semitrusted parties Need a network with diversely run infrastructure Economic and usage feasibility implies a freeto-use network with infrastructure open to any contributors Cannot preclude adversaries running a significant portion of your network First-Last Correlation Problem What Adversary observes first and last routers Traffic patterns link first and last routers ●  ●  Why ●  ●  Attack completely breaks anon regardless of number of users Attack possible with moderate resources –  ●  17MB s compromises random 1% of current Tor users 100 or so home Internet accounts needed for attack Padding etc too expensive and will never work anyway Key Idea Trust ●  Users may know how likely a router is to be under observation Tor Routers with Possible Trust Factors Name Hostname Bandwidth Uptime moria nexico ediscom de 4 KB s Republic xvm-107 mit edu 121 KB s Unnamed static58 KB s ip-166-154-142-114 rev dyxnet com Location Tor version OS 67 days Germany 0 2 1 26 Linux 49 days USA 0 2 1 29 Linux 58 days Hong Kong 0 2 1 29 Windows Server 2003 SP2 Source http torstatus blutmagie de 10 12 2011 Basic Adversary Model Routers 0 Users A Adversary A Basic Trust Model Routers Users A 0 Probability of Compromise 1 Adversary A Trust Model 1 Limited Adversary Routers R Destinations Users 0 1 Probability of Compromise c Adversary A A⊆R A ≤k Trust Model 1 Limited Adversary Routers R Destinations Users 0 1 Probability of Compromise c Adversary A A⊆R A ≤k Trust Model 2 Per-User Adversary Routers R User u Destinations Naïve users N 0 1 Probability of Compromise c Adversary AN The Man Trust Model 2 Per-User Adversary Routers R User u Destinations Naïve users N 0 1 Probability of Compromise c Adversary AN Trust Model 2 Per-User Adversary Routers R User u Destinations Naïve users N 0 1 Probability of Compromise c Adversary Au Adversary AN Downhill Algorithm Key idea Blend in with the naïve users 1   Set path length l and trust levels λ1 … λl to optimize anonymity metric Downhill Algorithm Key idea Blend in with the naïve users 1   Set path length l and trust levels λ1 … λl to optimize anonymity metric 2   For 1 ≤ i ≤ l Randomly select among routers with trust ≥ λi Downhill Algorithm Key idea Blend in with the naïve users 1   Set path length l and trust levels λ1 … λl to optimize anonymity metric 2   For 1 ≤ i ≤ l Randomly select among routers with trust ≥ λi Downhill Algorithm Key idea Blend in with the naïve users 1 1   Set path length l and trust levels λ1 … λl to optimize anonymity metric 2   For 1 ≤ i ≤ l Randomly select among routers with trust ≥ λi Downhill Algorithm Key idea Blend in with the naïve users 1 1   Set path length l and trust levels λ1 … λl to optimize anonymity metric 2   For 1 ≤ i ≤ l Randomly select among routers with trust ≥ λi Downhill Algorithm Key idea Blend in with the naïve users 2 1 1   Set path length l and trust levels λ1 … λl to optimize anonymity metric 2   For 1 ≤ i ≤ l Randomly select among routers with trust ≥ λi Downhill Algorithm Key idea Blend in with the naïve users 2 1 1   Set path length l and trust levels λ1 … λl to optimize anonymity metric 2   For 1 ≤ i ≤ l Randomly select among routers with trust ≥ λi Downhill Algorithm Key idea Blend in with the naïve users 3 2 1 1   Set path length l and trust levels λ1 … λl to optimize anonymity metric 2   For 1 ≤ i ≤ l Randomly select among routers with trust ≥ λi Downhill Algorithm Key idea Blend in with the naïve users 3 2 1 1   Set path length l and trust levels λ1 … λl to optimize anonymity metric 2   For 1 ≤ i ≤ l Randomly select among routers with trust ≥ λi 3   For each connection Create circuit through selected routers to the destination Anonymity Analysis of Downhill Algorithm Metric Posterior probability of actual source of a given connection Expected anonymity Downhill Most trusted Random Lower bound Many @ medium trust 0 0274 0 2519 0 1088 0 01 Many @ low trust 0 0550 0 1751 0 4763 0 001 Anonymity Analysis Metric Posterior probability of actual source of a given connection Expected anonymity Downhill Most trusted Random Lower bound Many @ medium trust 0 0274 0 2519 0 1088 0 01 Many @ low trust 0 0550 0 1751 0 4763 0 001 Scenario 1 User has some limited information c 01 c 1 c 9 10 routers 5 routers 1000 routers Anonymity Analysis Metric Posterior probability of actual source of a given connection Expected anonymity Downhill Most trusted Random Lower bound Many @ medium trust 0 0274 0 2519 0 1088 0 01 Many @ low trust 0 0550 0 1751 0 4763 0 001 Scenario 2 User and friends run routers Adversary is strong c 001 c 05 c 5 5 routers 50 routers 1000 routers Tor Actual path selection Tor Actual path selection Tor Actual path selection Tor Actual path selection Relay choice is weighted by bandwidth depends on uptime R1 Alice R5 Bobs R3 R4 R2 Users get routed ACM CCS’13 NRL Georgetown collaboration ●  80% of all types of users may be deanonymized by moderate Tor-relay adversary within 6 months First-Last Correlation Problem What ●  ●  Adversary observes first and last routers Traffic patterns link first and last routers Onion Routers Relays Nodes Overlay network Users get routed ACM CCS’13 NRL Georgetown collaboration ●  ●  ●  ●  80% of all types of users may be deanonymized by moderate Tor-relay adversary within 6 months Against a single-AS adversary roughly 100% of users in some common locations are deanonymized within three months or 95% in 3 months for a single IXP 2-AS adversary reduces median time to the first client deanonymization by an order of magnitude –  –  from over 3 months to only 1 day for typical web user from over 3 months to c 1 month for a BitTorrent user Using Trust is first approach to protect traffic even if adversary owns a large chunk of the network Not yet or much mentioned future work ●  Datagram transport ●  Links ●  Performance congestion throttling incentives ●  Hidden services ●  Trust propagation ●  Better security models