Practical Traffic Analysis:Extending and resisting statistical disclosureby Nick Mathewson and Roger DingledineThe Free Haven Project{nickm,arma}@freehaven.netMay 26, 2004PET2004SummaryWe extend earlier work on end-to-end traffic analysis attacks against high-latency anonymity networks.We simulate these attacks, and note some cases in which they may be impractical.We close with recommendations.Anonymity Networks(what are we attacking?)•Many senders (“Alice”), many recipients (“Bob”)•Alice wants to hide Alice/recipient connection•... from recipients•... from attackers (active and passive)•... from the infrastructure itselfAnonymity Networks(how do they work?)•Receive encrypted messages•Decrypt, learn next hop•Delay to hide timing correlations(High-latency systems only!)•Deliver towards recipientEx: Mix-nets (1981), Mixmaster (1995), Babel (1996), Mixminion (2003)A1A3A2B1B2B3Attack Category:Long-term IntersectionThe Goal:•Link targeted senders to their recipientsThe Attack:•Alice has a set of regular recipients•When Alice has sent a message, those recipients are likelier to receive•So, watch for a long time, and see who receives more when Alice has been sendingPrevious work: The Disclosure Attack(Kesdogan, Agrawal, and Penz, 2002)•Batch mix (get b messages, then relay)•NP-complete computation•Identifies Alice’s recipients with certaintyPrevious work:Statistical Disclosure(Danezis, 2003)•Easier to implement•Statistical: Identifies probable recipients•Method: Compute mean recipient distribution when Alice is sending; compare to (known) background distributionOur contribution•Strengthen attack to work against better networks:•Unknown background distribution•Complex sender behavior•Pool mixes and mix-nets•Padding (“dummy”) messages•Non-global attacker•(Also, ways to exploit additional info)Simulation Model•Scale-free network of recipients•Alice sends with geometric distribution•Background sends with normal distribution•Global attacker•No other linkable info in messages•Static, steady-state networkUnknown background101001000100001000001000000101102103104105RoundsNumber of recipients (N)b=125; PM=0.5Uniform,m∈{8,16}Weighted,m∈{8,16}Statistical disclosureMethod: estimate background by averagingrounds in which Alice is not sending.Pool mixes and mix-netsMethod: compute expected contribution of each message to subsequent rounds101001000100001000001000000.10 .20 .30 .40 .50 .60 .70 .80 .90RoundsMessage volume from Alice (PM)BG=125; m=32; N=65536len=1len=2len=4len=8Pdelay=.1Pdelay=.3Pdelay=.6Pdelay=.9Non-global attackersMethod: Sample! 1010010001000010000010000000.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0RoundsFraction observed entering and exiting (Pobserve)2N=65536; m=32; BG=125pdelay=.1pdelay=.6Independent PaddingNo changes needed -- it’s just more noise101001000100001000001000000.0 .10 .20 .30 .40 .50 .60 .70 .80 .90RoundsPadding volume from Alice (Pjunk)PM=0.6; N=65536; m=32; BG=125Pdelay=.1,len=1Pdelay=.6,len=1Pdelay=.1,len=4Pdelay=.6,len=4Perfect threshold padding Alice wins.But if Alice is unreliable...If Alice is sometimes offline, threshold padding can fail.101001000100001000001000000.10 .20 .30 .40 .50 .60 .70 .80 .90 .100RoundsFraction of time online (Ponline)PM=0.6; N=65536; m=32; BG=125; M=2Pdelay=.1,len=1Pdelay=.6,len=1Pdelay=.1,len=4Pdelay=.6,len=4An activeattacker canmake this happen!And if Alice must join/leave...Threshold padding still doesn’t help at all.101001000100001000001000000.10 .20 .30 .40 .50 .60 .70 .80 .90RoundsPdelayPM=0.6; N=65536; m=32; BG=125; len=1Padding, known U, M=2No padding, unknown UNo padding, known UOther scenarios(not simulated)•Slowly changing cover traffic•Attacks against recipients•Exploiting message linkability•Pseudonyms•Message propertiesLessons (1)•Intersection attacks may be feasible; being almost-global isn’t necessary.•Don’t ask: “Is it categorically secure?”Ask: “How long does it secure whom?”•Senders: Don’t participate longer than necessary.Lessons (2)•It’s hard to get padding perfect... ...and the imperfections matter. ...but padding can still help.•High message delay variance is essential(It makes padding more effective and partial observation less effective.)Model LimitationsIn Alice’s favor:•User behavior changes over time.•What if Alice runs a mix?In attacker’s favor:•User behavior is not geometric, not quite scale-free-network. (Diaz, Sassaman, and Dewitte, [TR, submitted])•Messages may be linkable.•Attacker might be active.Future work•Better models for users•Strengthen attacks (active attackers; linkable messages)•Do “lessons” change when other attacks are considered?•Closed-form solutions where possible.•Link to other models of anonymity?•Self-optimizing mix networks?Q&A ?•Simulation code available at
View Full Document
Unlocking...